第二講回溯法

第二講回溯法第1頁，課件共27頁，創(chuàng)作于2023年2月關(guān)于搜索人類的思維過程既是一個搜索過程。先來看一個智力游戲第2頁，課件共27頁，創(chuàng)作于2023年2月傳教士與野人有三個傳教士和三個野人渡河，河邊有一條船，每次只能乘坐2人，為了傳教士的安全，應(yīng)如何規(guī)劃渡船方案，使得任何時刻，在河的兩岸及船上，傳教士的人數(shù)不能少于野人數(shù)。 第3頁，課件共27頁，創(chuàng)作于2023年2月第4頁，課件共27頁，創(chuàng)作于2023年2月搜索分類第5頁，課件共27頁，創(chuàng)作于2023年2月基本思想回溯法是一種通用性解法，可以將回溯法看作是帶優(yōu)化的窮舉法。回溯法的基本思想是在一棵含有問題全部可能解的狀態(tài)空間樹上進(jìn)行深度優(yōu)先搜索，解為葉子結(jié)點。搜索過程中，每到達(dá)一個結(jié)點時，則判斷該結(jié)點為根的子樹是否含有問題的解，如果可以確定該子樹中不含有問題的解，則放棄對該子樹的搜索，退回到上層父結(jié)點，繼續(xù)下一步深度優(yōu)先搜索過程。在回溯法中，并不是先構(gòu)造出整棵狀態(tài)空間樹，再進(jìn)行搜索，而是在搜索過程，逐步構(gòu)造出狀態(tài)空間樹，即邊搜索，邊構(gòu)造。第6頁，課件共27頁，創(chuàng)作于2023年2月第7頁，課件共27頁，創(chuàng)作于2023年2月應(yīng)用步驟1、確定問題狀態(tài)結(jié)構(gòu)；2、分析問題狀態(tài)空間樹；3、確定深度搜索與回溯規(guī)則；4、確定解狀態(tài)判別規(guī)則；第8頁，課件共27頁，創(chuàng)作于2023年2月二個問題八皇后問題全排列問題第9頁，課件共27頁，創(chuàng)作于2023年2月N皇后問題問題：在一個n×n的棋盤上布置n個王后，使其相互不能攻擊，即每行、每列，每斜線都只有一個皇后；問題的狀態(tài)即棋盤的布局狀態(tài)，狀態(tài)空間樹的根為空棋盤，每個布局的下一步可能布局為該布局結(jié)點的子結(jié)點；由于可以預(yù)知，在每行中有且只有一個王后，因此為了簡化狀態(tài)空間樹，采用逐行布局的方式，即每個布局有n個子結(jié)點；第10頁，課件共27頁，創(chuàng)作于2023年2月N后問題回溯過程分析1、從空棋盤起，逐行放置棋子。2、每在一個布局中放下一個棋子，即推演到一個新的布局。3、如果當(dāng)前行上沒有可合法放置棋子的位置，則回溯到上一行，重新布放上一行的棋子。第11頁，課件共27頁，創(chuàng)作于2023年2月N后問題算法描述初始化空棋盤（起始狀態(tài)）；從第一行開始準(zhǔn)備放子，直至第一行出現(xiàn)回溯在當(dāng)前行r中查找下一個可以放置王后的位置

如果找到了可以擺放的位置放下一個子

如果已經(jīng)是最后一行得到一個解撤掉該子，繼續(xù)尋找下一個解

否則（未到最后一行）準(zhǔn)備處理下一行

否則（沒有找到可以擺放的位置）回溯到上一行，并撤掉該行的棋子第12頁，課件共27頁，創(chuàng)作于2023年2月第13頁，課件共27頁，創(chuàng)作于2023年2月算法偽碼得到求解皇后問題的算法如下：

{

輸入棋盤大小值n；

m=0;

good=1;

do{

if(good)

if(m==n)

{

輸出解；

改變之，形成下一個候選解;

}

else

擴展當(dāng)前候選接至下一列；

else

改變之，形成下一個候選解；

good=檢查當(dāng)前候選解的合理性；

}while(m!=0);

}第14頁，課件共27頁，創(chuàng)作于2023年2月引入輔助變量一維數(shù)組（col[]），值col表示在棋盤第i列、col行有一個皇后。例如：col[3]=4，就表示在棋盤的第3列、第4行上有一個皇后。另外，為了使程序在找完了全部解后回溯到最初位置，設(shè)定col[0]的初值為0當(dāng)回溯到第0列時，說明程序已求得全部解，結(jié)束程序運行。數(shù)組a[]，a[k]表示第k行上還沒有皇后；數(shù)組b[]，b[k]表示第k列右高左低斜線上沒有皇后；數(shù)組c[]，c[k]表示第k列左高右低斜線上沒有皇后；第15頁，課件共27頁，創(chuàng)作于2023年2月【程序】

#include

<stdio.h>

#include

<stdlib.h>

#define

MAXN

20

intn,m,good;

intcol[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];

voidmain()

{

intj;

charawn;

printf(“Entern:

“);

scanf(“%d”,&n);

for(j=0;j<=n;j++)

a[j]=1;

for(j=0;j<=2*n;j++)

cb[j]=c[j]=1;

m=1;

col[1]=1;

good=1;

col[0]=0;

do{

if(good)

if(m==n)

{

printf(“列\(zhòng)t行”);

for(j=1;j<=n;j++)

printf(“%3d\t%d\n”,j,col[j]);

printf(“Enteracharacter(Q/qforexit)!\n”);

scanf(“%c”,&awn);

if(awn==’Q’||awn==’q’)

exit(0);

while(col[m]==n)

{

m--;

a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;

}

col[m]++;

}

else

{

a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;

col[++m]=1;

}

else

{

while(col[m]==n)

{

m--;

a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;

}

col[m]++;

}

good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];

}while(m!=0);

}

第16頁，課件共27頁，創(chuàng)作于2023年2月全排列問題問題生成1..n的全排列。問題狀態(tài)可以將一個局部排列看作一個問題狀態(tài)。問題狀態(tài)空間樹由空排列出發(fā)，在一個局部排列上每增排一位數(shù)字，即可得到新的一個排列。所有局部排列之間的推導(dǎo)關(guān)系即可構(gòu)成一棵問題狀態(tài)空間樹。輔助向量設(shè)計可設(shè)置輔助向量D1..n，其中Di表示i是否已經(jīng)被排列。第17頁，課件共27頁，創(chuàng)作于2023年2月全排列問題算法描述初始化空排列，開始逐位進(jìn)行排列；循環(huán)，直到第一位出現(xiàn)回溯尋找當(dāng)前位的下一個可排列數(shù)字；若存在可排列數(shù)字排列若已排列滿，則輸出一個排列，并刪除該位（準(zhǔn)備下一個排列）否則準(zhǔn)備排列下一位否則（無可排列數(shù)字）退回上一位，并刪除所排列數(shù)字第18頁，課件共27頁，創(chuàng)作于2023年2月回溯法的分析一個可以用回溯法求解的問題，通?？梢员硎鰹橐韵滦问剑?/p>

對由n元組(x1,x2,…,xn)組成的狀態(tài)空間E={(x1,…,xn)}，給定n元組上的一個約束集D，求：E中滿足D的全部約束條件的所有n元組。將E中滿足D的全部約束條件的一個n元組稱為問題的一個解。通常約束集D具有完備性，即若i元組(x1…xi)滿足D中僅涉及x1…xi的所有約束，則(x1…xj)j<i也滿足D中僅涉及x1…xj的所有約束；也就是說，若(x1…xj)不能滿足D中所有涉及x1…xj的約束，則任何以(x1…xj)為前綴的i元組(x1…xi)i>j也不能滿足D中涉及x1…xi的約束，不必再繼續(xù)搜索問題的解。第19頁，課件共27頁，創(chuàng)作于2023年2月回溯法的分析回溯求解的效率在很大程度上依賴于：

產(chǎn)生局部解的時間；

計算約束所需的時間；

滿足局部約束的解的個數(shù)；通常可以應(yīng)用重排原理，先搜索分支較少的局部解，在約束不滿足時，可以裁剪去較多的搜索分支，從而提高搜索效率。第20頁，課件共27頁，創(chuàng)作于2023年2月一般圖搜索回溯搜索：只保留從初始態(tài)到當(dāng)前態(tài)的一條路徑圖搜索：保留所有搜索過的路徑實際上，圖搜索測量是實現(xiàn)從一個隱含圖中，生成一部分確實含有一個目標(biāo)節(jié)點的顯示表示的子圖搜索過程。第21頁，課件共27頁，創(chuàng)作于2023年2月啟發(fā)式搜索算法利用知識來引導(dǎo)搜索，達(dá)到減少搜索范圍，減低問題復(fù)雜度的目的，希望引入啟發(fā)知識，在保證找到最優(yōu)解的情況下，盡可能減少搜索范圍，提高搜索效率。強：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解第22頁，課件共27頁，創(chuàng)作于2023年2月小結(jié)

回溯方法的步驟如下：

1)定義一個解空間，它包含問題的解。

2)用適于搜索的方式組織該空間。

3)用深度優(yōu)先法搜索該空間，利用限界函數(shù)避免移動到不可能產(chǎn)生解的子空間。

回溯算法的一個有趣的特性是在搜索執(zhí)行的同時產(chǎn)生解空間。在搜索期間的任何時刻，僅保留從開始節(jié)點到當(dāng)前E-節(jié)點的路徑。因此，回溯算法的空間需求為O（從開始節(jié)點起最長路徑的長度）。這個特性非常重要，因為解空間的大小通常是最長路徑長度的指數(shù)或階乘。所以如果要存儲全部解空間的話，再多的空間也不夠用第23頁，課件共27頁，創(chuàng)作于2023年2月經(jīng)典問題[迷宮老鼠][0/1背包問題][旅行商問題]第24頁，課件共27頁，創(chuàng)作于2023年2月練習(xí)1.找出所有從m個元素中選取n(n<=m)元素的組合。2.設(shè)有A,B,C,D,E5人從事j1,j2,j3,j4,j55項工作每人只能從事一項,它們的效益表如下。求最佳安排,使效益最高.第25頁，課件共27頁，創(chuàng)作于2023年2月3.N個數(shù)中