第 5 章 艱苦卓絕

《第 5 章 艱苦卓絕》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第5章艱苦卓絕回溯算法5.1組合問題與回溯算法?很多現(xiàn)實問題中，合法的解可能要通過在一個大量但有限多種可能性中做窮盡搜索才能獲得，這樣的問題通常稱之為組合問題。?一種通用的稱為回溯的搜索技巧用來在窮盡搜索過程中，能避免搜索所有的可能情形。它普遍地適用于解決需要檢測有限但卻是大量的可能解的組合問題。3-著色問題?1．問題的理解與描述?假定圖G的頂點集合為V={1,2,…,n}，則3-著色問題形式化為：?輸入：圖G=。?輸出：若G存在各頂點的合法著色方案，輸出所有解向量c=，其中1≤c≤312ni為

2、G的第i個頂點的著色，且對?(i,j)∈E，c≠ic。否則輸出無解信息。j樹根abca=1de(a)b=2b=3b=1c=1c=2c=3c=1c=2c=3d=1d=3d=1d=2d=2d=3e=1e=2e=3e=1e=2e=3e=1e=2e=3e=1e=2e=3(b)?(a)表示圖G，我們要對其頂點用顏色{1,2,3}來著色。(b)部分展示了合法著色方案形成過程中搜索樹的路徑。首先，在產(chǎn)生出第三個結(jié)點后，發(fā)現(xiàn)著色方案<1,1>不是合法部分解，所以該節(jié)點在圖中用×標(biāo)識為死結(jié)點。接著b涂成顏色2，這樣著色方案<1,2>看起來是

3、一個部分解。于是產(chǎn)生一個對應(yīng)于頂點b的新的孩子結(jié)點，其初始著色為1。重復(fù)上述過程，最終將得到一個合法的著色方案<1,2,2,1,3>。2．算法的偽代碼描述?THREE-COLOR(G)?1flag←false?2為解向量x分配存儲空間?3GRAPHCOLOR(1)?從根起對以下第1層節(jié)點進(jìn)行搜索?4ifflag=false?5thenprint"nosolution."?GRAPH-COLOR(k)?1ifk>n?判斷是否為完整解?2thenflag←true?3printx?4return?5forcolor←1to3?

4、對當(dāng)前第k個頂點逐一檢測3種可能的著色?6dox[k]←color?7fori←1tok-1?8doifi,k在G中相鄰且x[i]=x[k]?9then檢測x[k]的下一種著色?10GRAPH-COLOR(k+1)?進(jìn)入下一層搜索3．算法的運行時間?注意在最壞情形下將產(chǎn)生Θ(3n)個節(jié)點，對每一個產(chǎn)生的節(jié)點（x[k]的一個取值）第7～9行判斷其是否能與x[1...k-1]一起，使得x[1...k]構(gòu)成一個部分解需要用Θ(n)時間。所以，最壞情形下總的運行時間為Θ(n3n)。5.1.2n-皇后問題?如何在一個8×8的棋盤上放

5、置8個皇后使得任意兩個皇后之間不能相互攻擊？(a)(b)1．問題的理解與描述?我們將n-皇后問題形式化為：?輸入：棋盤規(guī)模n。?輸出：如果此n×n棋盤存在合法格局，則輸出所有由向量x=，其中，x,12n1x,…,x是1,2,…,n的一個排列，且?（1?i≠2nj?n）有x–x≠i–j且x–x≠j–i決定的格局：ijij棋盤上的第i行第x格放置一個皇后，i=1,i2,…,n。否則，輸出無解信息。x1=2x2=4Xx3=1x4=3對于n=4的情形，x置為1且x置為1。這將導(dǎo)致一個死節(jié)點，因為這12兩個皇后置于

6、同一列中。若x置為2也將發(fā)生同樣的結(jié)果，因為這兩2個皇后置于同一斜線上。將x置為3將導(dǎo)致一個部分解向量<1,3>且探2索對x尋求一個值。如圖中所示，無論x假設(shè)為何值，都不會得到33x=1,x=3及x>0的部分解。所以搜索回溯到第二層并對x賦予一個新1232的值，即4。如圖所示，這導(dǎo)致了部分解向量<1,4,2>。此向量還是不能被擴(kuò)展，在產(chǎn)生出一些新的節(jié)點后，搜索回到第一層?，F(xiàn)在，x增1加為2，以同樣的方式，找到部分解向量<2,4,1>。如此，此向量被擴(kuò)展為合法向量<2,4,1,3>，這就對應(yīng)一個合法解。2．算法的偽代碼描述?

7、N-QUEENS(n)?1flag←false?2為解向量x分配存儲空間?3PLACE(1)?從根起對以下第1層節(jié)點進(jìn)行搜索?4ifflag=false?5thenerror"nosolution"??PLACE(k)?1ifk>n?判斷是否為完整解?2thenflag←ture?3fori←1ton?4do輸出棋盤中第i行格局?5return?6forcolum←1ton?對當(dāng)前第k行逐一檢測各種可能的位置?7dox[k]←colum?8fori←1tok-1?9doifx[i]=x[k]or

8、x[i]–x[k]

9、=

10、i

11、–k

12、?10then檢測第k行的下一個置放位置?11PLACE(k+1)?進(jìn)入下一層搜索3．算法的運行時間?在最壞情形下將產(chǎn)生完全n叉樹中Θ(nn)個節(jié)點，對每一個產(chǎn)生的節(jié)點（x[k]的一個取值）第8～10行判斷其是否能與x[1...k-1]一起，使得x[1...k]構(gòu)成一個部分解需要用Θ(n)時間。所