算法分析與設(shè)計章

第五章圖的搜索算法

每節(jié)一經(jīng)典走不通就“掉頭”----回退第1講回溯法回溯(Backtravking)算法：實際是一個類似枚舉的搜索嘗試方法，它的思想是在搜索嘗試中找問題的解，當不滿足求解條件就“回溯”(返回)，嘗試別的路徑。回溯算法是嘗試搜索算法中最為基本的一種算法,其采用了一種“走不通就掉頭”的思想，作為其控制結(jié)構(gòu)。第1講回溯法解空間（solutionspace）的定義定義S={(X1,…,Xn)|(X1,X2,…,Xn)為滿足問題的所有解}這個空間必須至少包含該問題的一個解，而這個解也可能就是一個最佳解

范例

在具有n個商品的0/1背包問題中，解空間的一個合理選擇是2n個長度為n的{0,1}向量之集合，這個集合表示所有將0和1指配給Xi的可能方法,設(shè)n=3的時候,其解空間為：S={(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}，共有2n=23=8個向量第1講回溯法解空間(solutionspace)的定義解空間樹(三個商品的0/1背包問題)G1G2G3商品：G1G2G3notG3notG2notG3notG2G2notG1G3G3notG3G3notG3包的初始狀態(tài)一個解:(1,1,1)第1講回溯法解空間(solutionspace)的定義問題的解向量：回溯法希望一個問題的解能表示成一個n元式(x1,x2,…,xn)的形式。顯約束：對分量xi的取值限定。隱約束：為滿足問題的解而對不同分量之間施加的約束。例如：在0-1背包中：目標:max∑xi*vi顯約束：xi

{0,1}隱約束：∑wi.xi≤Ci=1,2,…n第1講回溯法認識回溯法例1

：八皇后問題模型建立要在8*8的國際象棋棋盤中放八個皇后，使任意兩個皇后都不能互相吃掉。規(guī)則：皇后能吃掉同一行、同一列、同一對角線的任意棋子。如圖為一種方案，求所有的解。8765432187654321問題理解：

其中一個解：

8765432187654321第1講回溯法設(shè)八個皇后為xi,她們分別在第i行(i=1,2,3,4……,8),這樣問題的解空間,xi就是一個皇后所在列的序號，為n元一維向量(x1,x2,x3,x4,x5,x6,x7,x8),搜索空間是1≤xi≤8（i=1，2，3，4……，8），共88(每個xi均有8種位置)個狀態(tài)。約束條件是八個皇后：（x1,x2,x3,x4,x5,x6,x7,x8)兩兩不在同一行、同一列和同一對角線上（與邊框45度角的直線）。模型建立8765432187654321例如：圖中就是解空間的一組解：（4，6，8，2，7，1，3，5）第1講回溯法雖然問題共有88個狀態(tài)，但算法不會真正地搜索這么多的狀態(tài)，因為前面已經(jīng)說明，回溯法采用的是“走不通就掉頭”的策略，而形如(1,1,x3,x4,x5,x6,x7,x8)的狀態(tài)共有86個，由于1，2號皇后在同一列，不滿足約束條件，回溯后這86個狀態(tài)是不會搜索的。

模型建立8765432187654321第1講回溯法

加約束條件的枚舉算法最簡單的算法就是通過八重循環(huán)模擬搜索空間中的88個狀態(tài)，按深度優(yōu)先思想，把第1個皇后放在第1列，然后開始搜索第2到第8個皇后的合理位置，每個皇后只能在同一行的8個位置存放，每前進一步檢查是否滿足約束條件,不滿足時，檢查下一個位置，若滿足約束條件，開始下一個皇后的合理位置檢查，直到找出8個皇后的所有合理位置（即問題的全部解）。算法設(shè)計1第1講回溯法約束條件“不在同一列”的表達式為xi≠xj；i和j的值代表第i個皇后和第j個皇后，也就是行號；而“在同一對角線上”時它們的斜率為±1,即：解向量：(x1,x2,…,xn)

顯約束：xi=1,2,…,n

隱約束：

1)不同列：xi

xj

2)不處于同一正、反對角線：|i-j|

|xi-xj|a88a87a86a85a84a83a82a81a78a77a76a75a74a73a72a71a68a67a66a65a64a63A62a61a58a57a56a55a54a53a52a51a48a47a46a45a44a43a42a41a38a37a36a35a34a33a32a31a28a27a26a25a24a23a22a21a18a17a16a15a14a13a12a11第1講回溯法步1.第1個皇后從第1行第1列開始直到第8列，搜索合理位置，每找到一個位置，開始下一步；否則結(jié)束（找不到合理解）步2.第2個皇后從第2行第1列開始直到第8列，搜索合理位置，每找到一個位置，開始下一步；否則回退到上一步，使前一個皇后向右找到一個合理的位置。步3.第3個皇后從第3行第1列開始直到第8列，搜索合理位置，每找到一個位置，開始下一步；否則回退到上一步，使前一個皇后向右找到一個合理的位置。步4.第4個皇后從第4行第1列開始直到第8列，搜索合理位置，每找到一個位置，開始下一步；否則回退到上一步，使前一個皇后向右找到一個合理的位置。步5.第5個皇后從第5行第1列開始直到第8列，搜索合理位置，每找到一個位置，開始下一步；否則回退到上一步，使前一個皇后向右找到一個合理的位置。步6.第6個皇后從第6行第1列開始直到第8列，搜索合理位置，每找到一個位置，開始下一步；否則回退到上一步，使前一個皇后向右找到一個合理的位置。步7.第7個皇后從第7行第1列開始直到第8列，搜索合理位置，每找到一個位置，開始下一步；否則回退到上一步，使前一個皇后向右找到一個合理的位置。步8.第8個皇后從第8行第1列開始直到第8列，搜索合理位置，每找到一個位置，開始下一步；否則回退到上一步，使前一個皇后向右找到一個合理的位置。步9.找到一組解，并輸出解，然后返回上一步.注：上述算法其實是一個8重循環(huán)。算法1(自然語言描述)第1講回溯法算法圖形化理解87654321876543X21XXXXX第1講回溯法queen1（）{inta[9];//初始化定義數(shù)組

for

(x1=1;x1<=8;x1++)

//從第一列開始搜索

for

(x2=1;

x2<=8;x2++)

{if（check(x2,2)=0）continue;//如果約束條件滿足，則執(zhí)行下一個for語句，否則當前皇后位置向右移動一位繼續(xù)檢查約束條件

for

(x3=1;x3<=8;x3++)

{if（check(x3,3)=0）continue;//同上

for

(x4=1;x4<=8;x4++){if（check(x4,4)=0）continue;//同上

for

(x5=1;x5<=8;x5++){if（check(x5,5)=0）continue;//同上

for

(x6=1;x6<=8;x6++)

{if（check(x6,6)=0）continue;//同上算法1(偽代碼描述)第1講回溯法

for(x7=1;x7<=8;x7++)

{if（check(x7,7)=0）continue;//同上

for(x8=1;x8<=8;x8++)//同上{if（check(x8,8)=0）continue;

//同上else//找到了一組解

for(i=1;i<=8;i++)//輸出一組滿足約束的解print(xi);}}}}}}}}第1講回溯法check(intxi,intn)

//該函數(shù)是用來判斷是否滿足約束

{inti;

for(i=1;i<=n-1;i++)//這里只需要判斷前n-1個

if(abs(xi-xn)=abs(i-n))or(xi=xn)//判斷是否同一列或者同一對角線

return(0);return(1);}第1講回溯法…………

八皇后共有92組滿足約束的解但只有12種是獨立的，其余的都可以由這12種利用對稱性或旋轉(zhuǎn)而得到。請同學們研究新算法（可作為課程論文研究）找不到時，回退第1講回溯法以四皇后為例，說明回溯算法的執(zhí)行過程找不到時，回退第1講回溯法四皇后為例找不到時，回退第一個皇后第1講回溯法四皇后為例找不到時，回退第一個皇后第1講回溯法回退到第一行皇后向右移找到一組解（2，4，1，3）四皇后為例第1講回溯法皇后向右移找到一組解（3，1，4，2）四皇后為例第1講回溯法皇后向右移未找到回退四皇后為例第1講回溯法皇后向右移未找到結(jié)束程序四皇后為例第1講回溯法四皇后問題的解空間樹4!=24leaves2157346101289111517131416212319202226282425273133293032373935363842444041434749454648535551525458605657596365616264183450x1=1x1=2x1=3x1=4222133311444422x2：x3：x4：失敗回溯13解第1講回溯法四皇后問題的部分搜索-回溯過程123424233213413回溯點解中間點x1x2x3x4第1講回溯法算法分析：表面看算法時間復雜性為88，而實際上算法在執(zhí)行中不斷運行continue語句回溯，所以時間復雜性遠遠低于88。若將算法中循環(huán)嵌套間的檢查是否滿足約束條件的語句:

“if(check(xi,i)=0)continue;i=2,3,4,5,6,7“都去掉，只保留最后一個檢查語句：

“if(check(xi,8)=0)continue;”那么，相應地check（）函數(shù)修改成：算法分析1：第1講回溯法check*(xi,n){inti,j;for(i=1;i<=n;i++)

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

if(abs(xi-xj)=abs(i-j))or(xi=xj)

return(0);return(1);

}

則算法退化成完全的盲目搜索，復雜性就是88了算法分析1：第1講回溯法以上的枚舉算法可讀性很好，但它只能解決八皇后問題，而不能解決任意的n皇后問題。因此不是通用的回溯算法。下面的非遞歸算法可以說是通用的n皇后問題算法模型。算法擴展：n皇后非遞歸回溯算法？？第1講回溯法算法2非遞歸回溯法：第1講回溯法算法2非遞歸回溯法：inta[20],n;main（）

{input(n);bckdate（n）;}//初始化，輸入皇后數(shù)目bckdate(intn)//該函數(shù)是用來尋找滿足約束的全部解{intk;a[1]=0;k=1;//k用來表示第k個皇后，a[k]表示第k個皇后所在列

while(k>0)

{a[k]=a[k]+1;

while((a[k]<=n)and(check(k)=0))/