回溯法_ppt課件

1、第五章. 回溯法回溯法 (Back traiking)1 1、窮舉法應(yīng)用：、窮舉法應(yīng)用：有限離散問(wèn)題總可以用窮舉法求得問(wèn)題的全部有限離散問(wèn)題總可以用窮舉法求得問(wèn)題的全部 0-1 0-1背包問(wèn)題背包問(wèn)題( (0-10-1Knapsack Problem Knapsack Problem ) )設(shè)有設(shè)有n n個(gè)物體和一個(gè)背包個(gè)物體和一個(gè)背包, ,物體物體i i的重量為的重量為w wi i價(jià)值為價(jià)值為p pi i背包的載荷為背包的載荷為M,M,若將物體若將物體i i(1(1 i i n,)n,)裝入背包裝入背包, ,則有價(jià)值為則有價(jià)值為p pi i . .目標(biāo)是找到一個(gè)方案目標(biāo)是找到一個(gè)方案, ,使

2、得能放入背包的物體總價(jià)值最高使得能放入背包的物體總價(jià)值最高例例 題題若取若取W= (16,15, 15), P= (40,25, 25), C=30W= (16,15, 15), P= (40,25, 25), C=30窮舉法求解相當(dāng)于分別計(jì)算每個(gè)可能解，再求優(yōu)解窮舉法求解相當(dāng)于分別計(jì)算每個(gè)可能解，再求優(yōu)解例如例如 取取N=3 , N=3 , 問(wèn)題所有可能的解為問(wèn)題所有可能的解為(解空間解空間): (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) 時(shí)間復(fù)雜性時(shí)間復(fù)雜性:

3、O(2n)2 2、窮舉法改進(jìn)、窮舉法改進(jìn)對(duì)于某些組合難題的較大實(shí)例，我們可以用窮舉法求解，對(duì)于某些組合難題的較大實(shí)例，我們可以用窮舉法求解，但窮舉法的規(guī)模較大，所以我們對(duì)它進(jìn)行改進(jìn)，提出了回溯法和但窮舉法的規(guī)模較大，所以我們對(duì)它進(jìn)行改進(jìn)，提出了回溯法和分支界限法兩種算法設(shè)計(jì)技術(shù)。分支界限法兩種算法設(shè)計(jì)技術(shù)。它們每次只構(gòu)造候選解的一個(gè)分量，然后評(píng)估這個(gè)部分它們每次只構(gòu)造候選解的一個(gè)分量，然后評(píng)估這個(gè)部分構(gòu)造解：如果加上剩下的分量也不可能求得一個(gè)解，就絕不會(huì)生構(gòu)造解：如果加上剩下的分量也不可能求得一個(gè)解，就絕不會(huì)生成剩下的分量。成剩下的分量。他們是一構(gòu)造一棵解空間樹(shù)為基礎(chǔ)的，樹(shù)的節(jié)點(diǎn)反映了他們是一

4、構(gòu)造一棵解空間樹(shù)為基礎(chǔ)的，樹(shù)的節(jié)點(diǎn)反映了對(duì)一個(gè)部分解做出的特定選擇，如果可以保證，節(jié)點(diǎn)子孫所對(duì)應(yīng)對(duì)一個(gè)部分解做出的特定選擇，如果可以保證，節(jié)點(diǎn)子孫所對(duì)應(yīng)的選擇不可能得出問(wèn)題的一個(gè)結(jié)，兩種技術(shù)都回立即停止處理這的選擇不可能得出問(wèn)題的一個(gè)結(jié)，兩種技術(shù)都回立即停止處理這個(gè)節(jié)點(diǎn)。個(gè)節(jié)點(diǎn)。兩種技術(shù)的區(qū)別在于他們能處理的問(wèn)題類(lèi)型不同，分支兩種技術(shù)的區(qū)別在于他們能處理的問(wèn)題類(lèi)型不同，分支界限法只能應(yīng)用于最優(yōu)問(wèn)題，而回溯法可以搜索任何問(wèn)題的所有界限法只能應(yīng)用于最優(yōu)問(wèn)題，而回溯法可以搜索任何問(wèn)題的所有解和任一解。解和任一解。5.1 回溯法基本思想窮舉法技術(shù)建議我們先生成所有的候選解，然后找出那個(gè)窮舉法技術(shù)建議我

5、們先生成所有的候選解，然后找出那個(gè)具有需要特性的元素具有需要特性的元素1 1、回溯法主要思想是每次只構(gòu)造解的一個(gè)分量，然后按照、回溯法主要思想是每次只構(gòu)造解的一個(gè)分量，然后按照鮮明的方法來(lái)評(píng)估這個(gè)部分構(gòu)造解。如果一個(gè)部分構(gòu)造解可以進(jìn)一鮮明的方法來(lái)評(píng)估這個(gè)部分構(gòu)造解。如果一個(gè)部分構(gòu)造解可以進(jìn)一步構(gòu)造而不會(huì)違反問(wèn)題的約束，我們就接受對(duì)下一個(gè)分量所作的第步構(gòu)造而不會(huì)違反問(wèn)題的約束，我們就接受對(duì)下一個(gè)分量所作的第一個(gè)合法選擇。如果無(wú)法對(duì)下一個(gè)分量進(jìn)行合法的選擇，就不對(duì)剩一個(gè)合法選擇。如果無(wú)法對(duì)下一個(gè)分量進(jìn)行合法的選擇，就不對(duì)剩下的任何分量再做任何選擇了。在這種情況下，該算法進(jìn)行回溯，下的任何分量再做任

6、何選擇了。在這種情況下，該算法進(jìn)行回溯，把部分構(gòu)造解的最后一個(gè)分量替換為它的下一個(gè)選擇。把部分構(gòu)造解的最后一個(gè)分量替換為它的下一個(gè)選擇。2 2、解空間樹(shù)：通過(guò)對(duì)所做的選擇結(jié)構(gòu)構(gòu)造一棵解空間樹(shù)，、解空間樹(shù)：通過(guò)對(duì)所做的選擇結(jié)構(gòu)構(gòu)造一棵解空間樹(shù)，樹(shù)根代表了在查找解之前的初始狀態(tài)。樹(shù)的第一層節(jié)點(diǎn)代表對(duì)解的樹(shù)根代表了在查找解之前的初始狀態(tài)。樹(shù)的第一層節(jié)點(diǎn)代表對(duì)解的第一個(gè)分量所做的選擇，第二層節(jié)點(diǎn)代表了對(duì)解的第二個(gè)分量所做第一個(gè)分量所做的選擇，第二層節(jié)點(diǎn)代表了對(duì)解的第二個(gè)分量所做的選擇，以此類(lèi)推。的選擇，以此類(lèi)推。如果一個(gè)部分構(gòu)造解（子樹(shù)）仍然有可能導(dǎo)致一個(gè)完整解，如果一個(gè)部分構(gòu)造解（子樹(shù)）仍然有可能導(dǎo)

7、致一個(gè)完整解，我們說(shuō)這個(gè)部分解在樹(shù)中的相應(yīng)節(jié)點(diǎn)是有希望的。否則說(shuō)是沒(méi)希望我們說(shuō)這個(gè)部分解在樹(shù)中的相應(yīng)節(jié)點(diǎn)是有希望的。否則說(shuō)是沒(méi)希望的。的。葉子要么代表沒(méi)希望的，要么代表算法找到完整解葉子要么代表沒(méi)希望的，要么代表算法找到完整解若取若取W= (16,15, 15), W= (16,15, 15), P= (40,25, 25), P= (40,25, 25), C=30 C=30例如例如 取取N=3 , N=3 , 問(wèn)題所有可能的解為問(wèn)題所有可能的解為(解空間解空間): (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1

8、), (1, 1, 0), (1, 1, 1)0-10-1背包問(wèn)題解空間樹(shù)背包問(wèn)題解空間樹(shù)可表示為一棵可表示為一棵3層的完全正則二叉樹(shù)層的完全正則二叉樹(shù)時(shí)間復(fù)雜性時(shí)間復(fù)雜性: O(2n)求解過(guò)程相當(dāng)于在樹(shù)中搜索求解過(guò)程相當(dāng)于在樹(shù)中搜索滿(mǎn)足條件的葉結(jié)點(diǎn)滿(mǎn)足條件的葉結(jié)點(diǎn). .3、搜索策略、搜索策略回溯法在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根節(jié)回溯法在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根節(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任一節(jié)點(diǎn)時(shí)，先點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任一節(jié)點(diǎn)時(shí)，先判斷該節(jié)點(diǎn)是否包含問(wèn)題的解。判斷該節(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)以該節(jié)點(diǎn)為根的子樹(shù)的搜

9、索，如果肯定不包含，則跳過(guò)對(duì)以該節(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先節(jié)點(diǎn)回溯逐層向其祖先節(jié)點(diǎn)回溯否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索。否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索?；厮莘ㄇ髥?wèn)題的所有解時(shí)，要回溯到根，且根節(jié)點(diǎn)的所回溯法求問(wèn)題的所有解時(shí)，要回溯到根，且根節(jié)點(diǎn)的所有子樹(shù)都已被搜索遍才結(jié)束。有子樹(shù)都已被搜索遍才結(jié)束?；厮莘ㄇ蠼鈫?wèn)題的一個(gè)解時(shí)，只要搜索到問(wèn)題的一個(gè)解回溯法求解問(wèn)題的一個(gè)解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可以結(jié)束。就可以結(jié)束。這種以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱(chēng)為回溯法。這種以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱(chēng)為回溯法。回溯法舉例：回溯法舉例：若取若取W= (16,15,

10、15), P= (40,25, 25), C=30W= (16,15, 15), P= (40,25, 25), C=30回溯法舉例：回溯法舉例： 旅行商問(wèn)題旅行商問(wèn)題 在這個(gè)問(wèn)題中，給出一個(gè)在這個(gè)問(wèn)題中，給出一個(gè)n n 頂點(diǎn)網(wǎng)絡(luò)（有向頂點(diǎn)網(wǎng)絡(luò)（有向或無(wú)向），要求找出一個(gè)包含所有或無(wú)向），要求找出一個(gè)包含所有n n 個(gè)頂點(diǎn)的具有最小耗個(gè)頂點(diǎn)的具有最小耗費(fèi)的環(huán)路。任何一個(gè)包含網(wǎng)絡(luò)中所有費(fèi)的環(huán)路。任何一個(gè)包含網(wǎng)絡(luò)中所有n n 個(gè)頂點(diǎn)的環(huán)路被稱(chēng)個(gè)頂點(diǎn)的環(huán)路被稱(chēng)作一個(gè)旅行（作一個(gè)旅行（t o u rt o u r）。在旅行商問(wèn)題中，要設(shè)法找到一）。在旅行商問(wèn)題中，要設(shè)法找到一條最小耗費(fèi)的旅行。條最小耗

11、費(fèi)的旅行。 分析分析 圖給出了一個(gè)四頂點(diǎn)網(wǎng)絡(luò)。在這個(gè)網(wǎng)絡(luò)中，一些旅圖給出了一個(gè)四頂點(diǎn)網(wǎng)絡(luò)。在這個(gè)網(wǎng)絡(luò)中，一些旅行如下：行如下： 1 , 2 , 4 , 3 , 11 , 2 , 4 , 3 , 1；1 , 3 , 2 , 4 , 11 , 3 , 2 , 4 , 1和和1 , 4 , 3 , 2 , 11 , 4 , 3 , 2 , 1。旅行旅行1 , 2 , 4 , 3 , 11 , 2 , 4 , 3 , 1的耗費(fèi)為的耗費(fèi)為6 66 6；而；而1 , 3 , 2 , 4 , 11 , 3 , 2 , 4 , 1的耗費(fèi)的耗費(fèi)為為2 52 5；1 , 4 , 3 , 2 , 11 , 4 ,

12、3 , 2 , 1為為5 95 9。故。故1 , 3 , 2 , 4 , 11 , 3 , 2 , 4 , 1是該網(wǎng)絡(luò)中是該網(wǎng)絡(luò)中最小耗費(fèi)的旅行。最小耗費(fèi)的旅行。旅行是包含所有頂點(diǎn)的一個(gè)循環(huán)，故可以把任意一個(gè)點(diǎn)作旅行是包含所有頂點(diǎn)的一個(gè)循環(huán)，故可以把任意一個(gè)點(diǎn)作為起點(diǎn)（因此也是終點(diǎn)）。針對(duì)該問(wèn)題，任意選取點(diǎn)為起點(diǎn)（因此也是終點(diǎn)）。針對(duì)該問(wèn)題，任意選取點(diǎn)1 1作為起點(diǎn)和作為起點(diǎn)和終點(diǎn)，則每一個(gè)旅行可用頂點(diǎn)序列終點(diǎn)，則每一個(gè)旅行可用頂點(diǎn)序列1, 1, v v2 ,2 , , , vnvn , 1, 1來(lái)描述，來(lái)描述，v v2, 2, , , vnvn 是是(2, 3, (2, 3, , , n n

13、) ) 的一個(gè)排列?？赡艿穆眯锌捎靡粋€(gè)樹(shù)來(lái)的一個(gè)排列。可能的旅行可用一個(gè)樹(shù)來(lái)描述，其中每一個(gè)從根到葉的路徑定義了一個(gè)旅行。下圖給出了描述，其中每一個(gè)從根到葉的路徑定義了一個(gè)旅行。下圖給出了一棵表示四頂點(diǎn)網(wǎng)絡(luò)的樹(shù)。從根到葉的路徑中各邊的標(biāo)號(hào)定義了一棵表示四頂點(diǎn)網(wǎng)絡(luò)的樹(shù)。從根到葉的路徑中各邊的標(biāo)號(hào)定義了一個(gè)旅行（還要附加一個(gè)旅行（還要附加1 1作為終點(diǎn)）。例如，到節(jié)點(diǎn)作為終點(diǎn)）。例如，到節(jié)點(diǎn)L L的路徑表示了的路徑表示了旅行旅行1 , 2 , 3 , 4 , 11 , 2 , 3 , 4 , 1，而到節(jié)點(diǎn)，而到節(jié)點(diǎn)O O的路徑表示了旅行的路徑表示了旅行1 , 3 , 1 , 3 , 4 , 2 ,

14、 14 , 2 , 1。網(wǎng)絡(luò)中的每一個(gè)旅行都由樹(shù)中的一條從根到葉的確定。網(wǎng)絡(luò)中的每一個(gè)旅行都由樹(shù)中的一條從根到葉的確定路徑來(lái)表示。因此，樹(shù)中葉的數(shù)目為路徑來(lái)表示。因此，樹(shù)中葉的數(shù)目為( (n n- 1 )- 1 )！。！。回溯算法將用深度優(yōu)先方式從根節(jié)點(diǎn)開(kāi)始，通過(guò)搜索解空間回溯算法將用深度優(yōu)先方式從根節(jié)點(diǎn)開(kāi)始，通過(guò)搜索解空間樹(shù)發(fā)現(xiàn)一個(gè)最小耗費(fèi)的旅行。對(duì)題中網(wǎng)絡(luò)，利用前頁(yè)的解空間樹(shù)，樹(shù)發(fā)現(xiàn)一個(gè)最小耗費(fèi)的旅行。對(duì)題中網(wǎng)絡(luò)，利用前頁(yè)的解空間樹(shù)，一個(gè)可能的搜索為一個(gè)可能的搜索為A B C F LA B C F L。在。在L L點(diǎn)，旅行點(diǎn)，旅行1 , 2 , 3 , 4 , 11 , 2 , 3 , 4

15、 , 1作為當(dāng)前作為當(dāng)前最好的旅行被記錄下來(lái)。它的耗費(fèi)是最好的旅行被記錄下來(lái)。它的耗費(fèi)是5 95 9。從。從L L點(diǎn)回溯到活節(jié)點(diǎn)點(diǎn)回溯到活節(jié)點(diǎn)F F。由。由于于F F沒(méi)有未被檢查的孩子，所以它成為死節(jié)點(diǎn)，回溯到?jīng)]有未被檢查的孩子，所以它成為死節(jié)點(diǎn)，回溯到C C點(diǎn)。點(diǎn)。C C變?yōu)樽優(yōu)镋-E-節(jié)點(diǎn)，向前移動(dòng)到節(jié)點(diǎn)，向前移動(dòng)到G G，然后是，然后是MM。這樣構(gòu)造出了旅行。這樣構(gòu)造出了旅行1 , 2 , 4 , 3 , 1 , 2 , 4 , 3 , 1 1，它的耗費(fèi)是，它的耗費(fèi)是6 66 6。既然它不比當(dāng)前的最佳旅行好，拋棄它并回溯。既然它不比當(dāng)前的最佳旅行好，拋棄它并回溯到到G G，然后是，然后是

16、C , BC , B。從。從B B點(diǎn)，搜索向前移動(dòng)到點(diǎn)，搜索向前移動(dòng)到D D，然后是，然后是H , NH , N。這。這個(gè)旅行個(gè)旅行1 , 3 , 2 , 4 , 11 , 3 , 2 , 4 , 1的耗費(fèi)是的耗費(fèi)是2 52 5，比當(dāng)前的最佳旅行好，把它作為，比當(dāng)前的最佳旅行好，把它作為當(dāng)前的最好旅行。當(dāng)前的最好旅行。從從NN點(diǎn)，搜索回溯到點(diǎn)，搜索回溯到HH，然后是，然后是D D。在。在D D點(diǎn)，再次向前移動(dòng)，到點(diǎn)，再次向前移動(dòng)，到達(dá)達(dá)O O點(diǎn)。如此繼續(xù)下去，可搜點(diǎn)。如此繼續(xù)下去，可搜索完整個(gè)樹(shù)，得出索完整個(gè)樹(shù)，得出1 , 3 , 2 , 4 , 1 , 3 , 2 , 4 , 1 1是最少耗

17、費(fèi)的旅行。是最少耗費(fèi)的旅行。設(shè)問(wèn)題的解可表示為設(shè)問(wèn)題的解可表示為n n元組元組( (x x1 1, , x x2 2, , x xn n), ), x xi i s si i , , s si i為有限為有限集集, ,n n元組的子組元組的子組( (x x1 1, , x x2 2, , x xi i) ) i in 回溯法回溯法1.1.子集樹(shù)子集樹(shù): :當(dāng)解向量為不定長(zhǎng)當(dāng)解向量為不定長(zhǎng)n n元組時(shí)元組時(shí), , 樹(shù)中從根至每一結(jié)點(diǎn)的路徑樹(shù)中從根至每一結(jié)點(diǎn)的路徑集合構(gòu)成解空間集合構(gòu)成解空間. .樹(shù)的每個(gè)結(jié)點(diǎn)稱(chēng)為一個(gè)樹(shù)的每個(gè)結(jié)點(diǎn)稱(chēng)為一個(gè)解狀態(tài)解狀態(tài), ,有兒子的結(jié)點(diǎn)稱(chēng)為有兒子的結(jié)點(diǎn)稱(chēng)為可擴(kuò)展結(jié)點(diǎn)可

18、擴(kuò)展結(jié)點(diǎn), ,葉結(jié)點(diǎn)稱(chēng)為葉結(jié)點(diǎn)稱(chēng)為終止結(jié)點(diǎn)終止結(jié)點(diǎn), ,若結(jié)點(diǎn)若結(jié)點(diǎn)v v對(duì)應(yīng)解狀態(tài)對(duì)應(yīng)解狀態(tài)( (x x1 1, , x x2 2, , x xi i) ), ,則其兒子對(duì)應(yīng)則其兒子對(duì)應(yīng)擴(kuò)展的解擴(kuò)展的解狀態(tài)狀態(tài)( (x x1 1, , x x2 2, , x xi, i, x xi+1i+1 ). ).滿(mǎn)足所有滿(mǎn)足所有約束條件約束條件的解狀態(tài)結(jié)點(diǎn)稱(chēng)為的解狀態(tài)結(jié)點(diǎn)稱(chēng)為回答結(jié)點(diǎn)回答結(jié)點(diǎn).0-1.0-1背包問(wèn)題的解空間就是子集樹(shù)背包問(wèn)題的解空間就是子集樹(shù)2.2.排序樹(shù)排序樹(shù): :當(dāng)解向量為定長(zhǎng)當(dāng)解向量為定長(zhǎng)n n元組時(shí)元組時(shí), , 樹(shù)中從根至葉結(jié)點(diǎn)的路徑的集合樹(shù)中從根至葉結(jié)點(diǎn)的路徑的集合構(gòu)成解空間

19、構(gòu)成解空間. .樹(shù)的每個(gè)葉結(jié)點(diǎn)稱(chēng)為一個(gè)解狀態(tài)樹(shù)的每個(gè)葉結(jié)點(diǎn)稱(chēng)為一個(gè)解狀態(tài). .旅行商問(wèn)題的解空間就旅行商問(wèn)題的解空間就是排序樹(shù)是排序樹(shù)解空間樹(shù)構(gòu)造解空間樹(shù)構(gòu)造: :搜索按深度優(yōu)先策略從根開(kāi)始搜索按深度優(yōu)先策略從根開(kāi)始, , 當(dāng)搜索到任一結(jié)點(diǎn)時(shí)當(dāng)搜索到任一結(jié)點(diǎn)時(shí), ,判斷該點(diǎn)是否判斷該點(diǎn)是否滿(mǎn)足約束條件滿(mǎn)足約束條件D(D(剪枝函數(shù)剪枝函數(shù)),),滿(mǎn)足則繼續(xù)向下深度優(yōu)先搜索滿(mǎn)足則繼續(xù)向下深度優(yōu)先搜索, ,否則跳過(guò)否則跳過(guò)該結(jié)點(diǎn)以下的子樹(shù)該結(jié)點(diǎn)以下的子樹(shù)( (剪枝剪枝),),向上逐級(jí)回溯向上逐級(jí)回溯. .搜索過(guò)程搜索過(guò)程: :求解過(guò)程可表示為在一棵求解過(guò)程可表示為在一棵解空間樹(shù)解空間樹(shù) 作作 深度優(yōu)

20、先搜索深度優(yōu)先搜索. .Procedure BACKTRACK(n)；k:=l； repeat if TK (x1,x2,.xK-1 )中的值未取遍中的值未取遍 then xK:TK (x1，x2，., x K-1 )中未取過(guò)的一個(gè)值；中未取過(guò)的一個(gè)值； if BK (x1, x2, ., x K) then /狀態(tài)結(jié)點(diǎn)狀態(tài)結(jié)點(diǎn)(x1,.xk(x1,.xk) )被激活被激活 if kn then output(x1, x2, ., xk) /輸出一個(gè)回答結(jié)點(diǎn)輸出一個(gè)回答結(jié)點(diǎn) e1se k:k + l； /深度優(yōu)先深度優(yōu)先 e1se k:k-l； /回溯回溯 until k0；end；BACKT

21、RACK算法模式算法模式5 5、回溯、回溯法解題步驟法解題步驟: :1).1).針對(duì)所給問(wèn)題針對(duì)所給問(wèn)題, ,定義問(wèn)題的解空間定義問(wèn)題的解空間2).2).確定解空間結(jié)構(gòu)確定解空間結(jié)構(gòu). .3).3).以深度優(yōu)先方式搜索以深度優(yōu)先方式搜索解空間解空間. .算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 回溯法回溯法6 6、遞歸回溯、遞歸回溯算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 回溯法回溯法調(diào)用一次調(diào)用一次Backtrack(1)即可完成整個(gè)回溯搜索過(guò)程即可完成整個(gè)回溯搜索過(guò)程void Backtrack(int t) if (t n) /t表示深度，表示深度，tn表示算法以搜索到葉節(jié)點(diǎn)。表示算法以搜索到葉節(jié)點(diǎn)。 Outp

22、ut(x);/記錄或輸出得到的可行解記錄或輸出得到的可行解x。 else for (int i = f(n,t);i 0) if (f(n,t) = g(n,t) for (int i = f(n,t);i 回溯法回溯法 n后問(wèn)題5.2 裝載問(wèn)題問(wèn)題描述問(wèn)題描述:n個(gè)集裝箱裝到2艘載重量分別為c1,c2的貨輪,其中集裝箱i的重量為wi且 問(wèn)題要求找到一個(gè)合理的裝載方案可將這n個(gè)貨箱裝上這2艘輪船。211ccwnii例如 當(dāng)n=3, c1=c2=50, w=10, 40, 40, 可將貨箱1和2裝到第一艘船上;貨箱3裝到第二艘船上; 若w=20, 40, 40, 則無(wú)法將全部貨箱裝船.當(dāng)當(dāng) 時(shí)問(wèn)

23、題等價(jià)于子集和問(wèn)題時(shí)問(wèn)題等價(jià)于子集和問(wèn)題; ; 當(dāng)當(dāng)c1=c2c1=c2且且 時(shí)時(shí)問(wèn)題等價(jià)于劃分問(wèn)題問(wèn)題等價(jià)于劃分問(wèn)題. .211ccwnii112cwnii若裝載問(wèn)題有解, 采用如下策略可得一個(gè)最優(yōu)裝載方案:(1)將第一艘輪船盡可能裝滿(mǎn); (2)將剩余的貨箱裝到第二艘輪船上。將第一艘船盡可能裝滿(mǎn)等價(jià)于如下0-l背包問(wèn)題:niiixw1m ma ax x12cxwniiixi0,1, 1in可采用動(dòng)態(tài)規(guī)劃求解, 其時(shí)間復(fù)雜性為:O(C1,2n)算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 回溯法回溯法 裝載問(wèn)題裝載問(wèn)題算法思路算法思路:用排序樹(shù)表示解空間,則解為n元向量x1, . ,xn , xi0, 1 j

24、iiixw1 + wj+1 c1約束條件:由于是最優(yōu)化問(wèn)題, 可利用最優(yōu)解性質(zhì)進(jìn)一步剪去不含最優(yōu)解的子樹(shù):設(shè) bestw: 當(dāng)前最優(yōu)載重量, cw = : 當(dāng)前擴(kuò)展結(jié)點(diǎn)的載重量 ; r = : 剩余集裝箱的重量;當(dāng) cw+r (限界函數(shù))bestw 時(shí), 將cw對(duì)應(yīng)右子樹(shù)剪去。jiiixw1njijw1cw+r bestwjiiixw1 + wj+1 c1例如例如 n=4, c1=12, w=8, 6, 2, 3.cw=0cw=8cw=14cw=8cw=10cw=13bestw=10cw=8bestw=11cw=0cw=6cw=8bestw=11 搜索從根搜索從根A開(kāi)始且開(kāi)始且cw= 0。若移

25、動(dòng)到左孩子。若移動(dòng)到左孩子B則則cw= 8，cwc1 = 12。以。以B為根的子樹(shù)包含一個(gè)可行的節(jié)點(diǎn)，故移動(dòng)到節(jié)點(diǎn)為根的子樹(shù)包含一個(gè)可行的節(jié)點(diǎn)，故移動(dòng)到節(jié)點(diǎn)B。從節(jié)點(diǎn)。從節(jié)點(diǎn)B不能移動(dòng)到節(jié)不能移動(dòng)到節(jié)點(diǎn)點(diǎn)D，因?yàn)椋驗(yàn)閏 w+w2 c1。移動(dòng)到節(jié)點(diǎn)。移動(dòng)到節(jié)點(diǎn)E，這個(gè)移動(dòng)未改變，這個(gè)移動(dòng)未改變c w。下一步為節(jié)。下一步為節(jié)點(diǎn)點(diǎn)J，c w= 1 0。J的左孩子的的左孩子的c w值為值為1 3，超出了，超出了c1，故搜索不能移動(dòng)到，故搜索不能移動(dòng)到J的的左孩子。左孩子。 可移動(dòng)到可移動(dòng)到J的右孩子，它是一個(gè)葉節(jié)點(diǎn)。至此，已找到了一個(gè)子集，它的右孩子，它是一個(gè)葉節(jié)點(diǎn)。至此，已找到了一個(gè)子集，它的的c

26、 w= 1 0。xi 的值由從的值由從A到到J的右孩子的路徑獲得，其值為的右孩子的路徑獲得，其值為 1 , 0 , 1 , 0 ?；厮菟惴ń又厮莸交厮菟惴ń又厮莸絁，然后是，然后是E。從。從E，再次沿著樹(shù)向下移，再次沿著樹(shù)向下移動(dòng)到節(jié)點(diǎn)動(dòng)到節(jié)點(diǎn)K，此時(shí)，此時(shí)c w= 8。移動(dòng)到它的左子樹(shù)，有。移動(dòng)到它的左子樹(shù)，有c w= 11。既然已到。既然已到達(dá)了一個(gè)葉節(jié)點(diǎn)，就看是否達(dá)了一個(gè)葉節(jié)點(diǎn)，就看是否c w的值大于當(dāng)前的最優(yōu)的值大于當(dāng)前的最優(yōu)c w 值。結(jié)果確值。結(jié)果確實(shí)大于最優(yōu)值，所以這個(gè)葉節(jié)點(diǎn)表示了一個(gè)比實(shí)大于最優(yōu)值，所以這個(gè)葉節(jié)點(diǎn)表示了一個(gè)比 1 , 0 , 1 , 0 更好的解更好的解決方

27、案。到該節(jié)點(diǎn)的路徑?jīng)Q定了決方案。到該節(jié)點(diǎn)的路徑?jīng)Q定了x 的值的值 1 , 0 , 0 , 1 。template Type Maxloading(type w, type c, int n,) loading X； /初始化X X. w=w; /集裝箱重量數(shù)組 X. c=c; /第一艘船載重量 X. n=n；/集裝箱數(shù) X. bestw=0; /當(dāng)前最優(yōu)載重 X. cw=0;/當(dāng)前載重量 X. r=0; /剩余集裝箱重量 for (int i=1; i b e s t wc w b e s t w，則表示當(dāng)前解優(yōu)于最優(yōu)解。目前最優(yōu)解答，則表示當(dāng)前解優(yōu)于最優(yōu)解。目前最優(yōu)解答的值被更新。的值被更新

28、。 當(dāng)當(dāng)inin 時(shí)，當(dāng)前擴(kuò)展節(jié)點(diǎn)時(shí)，當(dāng)前擴(kuò)展節(jié)點(diǎn)Z Z是子集樹(shù)中的內(nèi)部節(jié)點(diǎn)。它有兩個(gè)孩是子集樹(shù)中的內(nèi)部節(jié)點(diǎn)。它有兩個(gè)孩子節(jié)點(diǎn)。左孩子表示子節(jié)點(diǎn)。左孩子表示xixi= = 的情況，只有的情況，只有cw + wiccw + wic 時(shí)，才能移時(shí)，才能移到這里。到這里。 當(dāng)移動(dòng)到左孩子時(shí)，當(dāng)移動(dòng)到左孩子時(shí)，cwcw 被置為被置為cw+wicw+wi ，且到達(dá)一個(gè)，且到達(dá)一個(gè)i+1i+1層的節(jié)層的節(jié)點(diǎn)。以該節(jié)點(diǎn)為根的子樹(shù)被遞歸搜索。調(diào)用點(diǎn)。以該節(jié)點(diǎn)為根的子樹(shù)被遞歸搜索。調(diào)用Backtrack (i+1)Backtrack (i+1)； 當(dāng)搜索完成時(shí)，回到節(jié)點(diǎn)當(dāng)搜索完成時(shí)，回到節(jié)點(diǎn)Z Z（第（第i i

29、層）。為了得到層）。為了得到Z Z的的cwcw值，需用值，需用當(dāng)前的當(dāng)前的cwcw 值減去值減去wiwi 。Z Z的右子樹(shù)還未搜索。既然這個(gè)子樹(shù)表示的右子樹(shù)還未搜索。既然這個(gè)子樹(shù)表示xixi=0=0的情況，所以無(wú)需進(jìn)行可行性檢查就可移動(dòng)到該子樹(shù)，因?yàn)橐坏那闆r，所以無(wú)需進(jìn)行可行性檢查就可移動(dòng)到該子樹(shù)，因?yàn)橐粋€(gè)可行節(jié)點(diǎn)的右孩子總是可行的。即執(zhí)行個(gè)可行節(jié)點(diǎn)的右孩子總是可行的。即執(zhí)行Backtrack (i+1)Backtrack (i+1)；Backtrack(int i)算法實(shí)現(xiàn)：templatevoid Loading:Backtrack(int i) / /搜索第i層結(jié)點(diǎn) if (in) /到

30、達(dá)葉結(jié)點(diǎn) bestw=cw； return； /搜索子樹(shù) if (cw+wi=c) /xi=1左孩子 cw += wi； Backtrack (i+1)； cw - = wi; Backtrack(i+1)； /xi=0右孩子 3、加入上界函數(shù)、加入上界函數(shù) 引入上界函數(shù)，用于引入上界函數(shù)，用于剪去不含最優(yōu)解的子樹(shù)，剪去不含最優(yōu)解的子樹(shù)，從而改進(jìn)算法在平均情況從而改進(jìn)算法在平均情況下的運(yùn)行效率。下的運(yùn)行效率。 設(shè)設(shè)r是剩余集裝箱的是剩余集裝箱的重量。定義上界函數(shù)為重量。定義上界函數(shù)為cw+r。在以。在以Z為根的子樹(shù)為根的子樹(shù)中任意葉結(jié)點(diǎn)所相應(yīng)的載中任意葉結(jié)點(diǎn)所相應(yīng)的載重量不操作重量不操作cw+

31、r。因此，。因此，當(dāng)當(dāng)cw+rbestw時(shí)，可將時(shí)，可將Z的右子樹(shù)剪去。的右子樹(shù)剪去。4、構(gòu)造最優(yōu)解、構(gòu)造最優(yōu)解templatevoid Loading:Backtrack(int i) / /搜索第搜索第i層結(jié)點(diǎn)層結(jié)點(diǎn) if (in) /到達(dá)葉結(jié)點(diǎn)到達(dá)葉結(jié)點(diǎn) bestw=cw； return； /搜索子樹(shù)搜索子樹(shù) r - = wi; if (cw+wi bestw) /控制剪去右子樹(shù)控制剪去右子樹(shù) Backtrack(i+1)； r+=wi if (i n) / 在葉節(jié)點(diǎn)上在葉節(jié)點(diǎn)上for (int j = 1; j 回溯法回溯法 n后問(wèn)題53 批處理作業(yè)調(diào)度批處理作業(yè)調(diào)度問(wèn)題描述問(wèn)題描述:

32、給定n個(gè)作業(yè)的集合J=(J1, J2, . , Jn)。每一作業(yè)Ji都有兩項(xiàng)任務(wù)要分別在2臺(tái)機(jī)器上完成. 每一作業(yè)須先由機(jī)器l處理, 再由機(jī)器2處理. 設(shè)tji是作業(yè)Ji在機(jī)器j上的處理時(shí)間, i=1,.,n, j=1, 2.Fji是作業(yè)Ji在器j上完成處理的時(shí)間. 所有作業(yè)在機(jī)器2上完成時(shí)間和: f=F2i 稱(chēng)為作業(yè)調(diào)度的完成時(shí)間和完成時(shí)間和.對(duì)于給定的J, 要求制定一個(gè)最佳作業(yè)調(diào)度方案, 使完成時(shí)間和最小.算法思路算法思路:設(shè)解為n元向量x1,. ,xn , xi1,.n, 用排序樹(shù)表示解空間 約束條件: 當(dāng)i j , xi xj (元素不能重復(fù)選取)限界函數(shù): bestx:為當(dāng)前最小時(shí)間

33、和 x : 當(dāng)前擴(kuò)展結(jié)點(diǎn)的時(shí)間和; r : 剩余作業(yè)的時(shí)間和;當(dāng) x+r 回溯法回溯法 作業(yè)調(diào)度int Flow(int * M, int n, int bestx ) int ub = 32767; Flowshop X; X.x = new int n+ 1; /當(dāng)前調(diào)度 X.f2 = new intn+ l; X.M = M; /各作業(yè)所需處理時(shí)間 X.n= n; /作業(yè)數(shù) X.bestx = bestx; /當(dāng)前最優(yōu)調(diào)度 X. bestf = ub; /當(dāng)前最優(yōu)調(diào)度時(shí)間 X.fl = 0; /機(jī)器2完成處理時(shí)間 X.f = 0; /機(jī)器1完成處理時(shí)間 for(int i = 0;i=

34、n; i+) X.f2i = 0,X.xi=i; X. Backtrack( 1 ); delete X. x; delete X. f2; return X. bestf ;算法復(fù)雜性算法復(fù)雜性: O(n!)作業(yè)調(diào)度回溯回溯算法Backtrack中，中， 當(dāng)當(dāng)in時(shí)，算法搜索至?xí)r，算法搜索至葉結(jié)點(diǎn)，得到一個(gè)新的作葉結(jié)點(diǎn)，得到一個(gè)新的作業(yè)調(diào)度方案，此時(shí)算法適業(yè)調(diào)度方案，此時(shí)算法適合更新當(dāng)前最優(yōu)值和相應(yīng)合更新當(dāng)前最優(yōu)值和相應(yīng)的當(dāng)前最佳作業(yè)調(diào)度。的當(dāng)前最佳作業(yè)調(diào)度。 當(dāng)當(dāng)in) for(int j = 1;j = n; j+) bestxj = xj; bestf = f; else for (i

35、nt j = i; j fl)?f2i-1:fl) +Mxj2; f+= f2i; if (f 回溯法回溯法 作業(yè)調(diào)度 機(jī)器1 機(jī)器2 作業(yè)1 2 1 作業(yè)2 3 1 作業(yè)3 2 3 tji 這三個(gè)作業(yè)的6種可能調(diào)度方案是: 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, l, 2; 3, 2, l;（窮舉法）相應(yīng)的完成時(shí)間和分別是: 10, 8, 10，9，7，8。最佳調(diào)度: 3, 1, 2; 完成時(shí)間為7，時(shí)間從0開(kāi)始計(jì)時(shí)。機(jī)器1機(jī)器2J1J1J3J3J2J2調(diào)度1,3,2例例 題題機(jī)器1機(jī)器2J3J3J2J2調(diào)度3,1,2J1J1算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析

36、 回溯法回溯法 作業(yè)調(diào)度 機(jī)器1 機(jī)器2 作業(yè)1 2 1 作業(yè)2 3 1 作業(yè)3 2 3 tji 這三個(gè)作業(yè)的6種可能調(diào)度方案是: 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, l, 2; 3, 2, l;相應(yīng)的完成時(shí)間和分別是: 10, 8, 10，9，7，8。最佳調(diào)度: 3, 1, 2; 完成時(shí)間為7。x1=J1J2J3x2=J2J3J1x3=J3ABCDEFJ2bestx=7J3EFJ3J1J2EFJ2J2J1例例 題題算法思路算法思路:將棋盤(pán)從左至右將棋盤(pán)從左至右,從上到下編號(hào)為從上到下編號(hào)為1,.,n,皇后編號(hào)為皇后編號(hào)為1,.,n. 設(shè)解為設(shè)解為(x

37、1, ., xn) , xi為皇后為皇后i放在棋盤(pán)的第放在棋盤(pán)的第i行的第行的第xi列。列。解空間解空間:E= (x1,., xn) | xi Si, i=1,.,4, Si=1, ., 4,1 i n；解空間；解空間為排列樹(shù)為排列樹(shù).其其約束集合約束集合D為為 1) xi xj 2) xi-i xj-j 3) xi+i xj+j皇后皇后i,ji,j不在同一斜線上（隱約束）不在同一斜線上（隱約束）算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 回溯法回溯法 n n后問(wèn)題后問(wèn)題5.4 n5.4 n后問(wèn)題后問(wèn)題皇后皇后i,ji,j不在同一列上（顯約束）不在同一列上（顯約束）問(wèn)題描述問(wèn)題描述:nXn:nXn棋盤(pán)上放置

38、棋盤(pán)上放置n n個(gè)皇后使得每個(gè)皇后互不受攻擊個(gè)皇后使得每個(gè)皇后互不受攻擊. . 即任二即任二皇后不能位于同行同列和同一斜線上皇后不能位于同行同列和同一斜線上. . 四后問(wèn)題的解四后問(wèn)題的解等價(jià)于：等價(jià)于： |i-j| |xi-xj|回溯回溯法解題步驟法解題步驟: :針對(duì)所給問(wèn)針對(duì)所給問(wèn)題題, ,定義問(wèn)題的解空間；確定定義問(wèn)題的解空間；確定解空間結(jié)構(gòu)；解空間結(jié)構(gòu)；以深度優(yōu)先方以深度優(yōu)先方式搜索式搜索解空間并按約束條件解空間并按約束條件進(jìn)行剪枝進(jìn)行剪枝. .算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 回溯法回溯法 n后問(wèn)題（未剪枝之前）（未剪枝之前）回溯求解四后問(wèn)題過(guò)程中被激活過(guò)的結(jié)點(diǎn)算法設(shè)計(jì)與分析算法設(shè)計(jì)與分

39、析 回溯法回溯法 n后問(wèn)題（a）（b）（c）（d）（e）（f）（g）（h）1 int nQueen(int n) QueenX； /初始化初始化X X X. n=n；/皇后個(gè)數(shù)皇后個(gè)數(shù) X. sum=0； int*p=new int n+1； for(int i=0；i 回溯法回溯法 n后問(wèn)題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 回溯法回溯法 n后問(wèn)題bool Queen: Place(int k) for (int j = 1; j n) sum+; else for (int i=1;i n時(shí)，算法搜索至葉時(shí)，算法搜索至葉結(jié)點(diǎn)，得到一個(gè)新的結(jié)點(diǎn)，得到一個(gè)新的n皇后皇后互不攻擊防止方案，當(dāng)前已互不攻

40、擊防止方案，當(dāng)前已找到方案數(shù)找到方案數(shù)sum增增1； in時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)Z的每一個(gè)兒子節(jié)點(diǎn)，由的每一個(gè)兒子節(jié)點(diǎn)，由Place檢查其可行性，并以檢查其可行性，并以深度優(yōu)先的方式遞歸地對(duì)可深度優(yōu)先的方式遞歸地對(duì)可行子樹(shù)搜索，或減去不可行行子樹(shù)搜索，或減去不可行子樹(shù)。子樹(shù)。12453完全子圖完全子圖：設(shè)無(wú)向圖設(shè)無(wú)向圖G=(V, E), U V, 若對(duì)任意若對(duì)任意u, v U, 有有(u,v) E, 則稱(chēng)則稱(chēng)U是是G的一個(gè)的一個(gè)完全子圖完全子圖。團(tuán)團(tuán)：G的完全子圖的完全子圖U是是G的一個(gè)的一個(gè)團(tuán)團(tuán)(完備子圖完備子圖)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)U不包含在不包含在G的更大的更大的完全子圖中。的完全

41、子圖中。最大團(tuán)最大團(tuán)：G的的最大團(tuán)最大團(tuán)是是G中所含頂點(diǎn)數(shù)最多的團(tuán)。中所含頂點(diǎn)數(shù)最多的團(tuán)?？兆訄D空子圖：如果：如果U V,且對(duì)任意且對(duì)任意u,v U,(u,v ) E, 則稱(chēng)則稱(chēng)U是是G的一個(gè)的一個(gè)空子圖空子圖。獨(dú)立集獨(dú)立集：G的空子圖的空子圖U是是G的一個(gè)的一個(gè)獨(dú)立集獨(dú)立集當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)U不包含在不包含在G的更大的空的更大的空子圖中。子圖中。G的的最大獨(dú)立集最大獨(dú)立集是是G中所含頂點(diǎn)數(shù)最多的獨(dú)立集。中所含頂點(diǎn)數(shù)最多的獨(dú)立集。*若若U是是G的一個(gè)的一個(gè)完全子圖完全子圖,則則U是是G的補(bǔ)圖的補(bǔ)圖 的一個(gè)獨(dú)立集的一個(gè)獨(dú)立集.5.7 最大團(tuán)問(wèn)題最大團(tuán)問(wèn)題 G問(wèn)題描述問(wèn)題描述:在在G G 中找一個(gè)最

42、大團(tuán)中找一個(gè)最大團(tuán). .例如例如最大團(tuán)最大團(tuán):1, 2, 5, 1, 4, 5, :2, 3, 5G的補(bǔ)圖的補(bǔ)圖子集子集1，2是不是團(tuán)？是不是團(tuán)？子集子集1，2，5是不是團(tuán)？是不是團(tuán)？子集子集1，2，4，5是不是團(tuán)？是不是團(tuán)？12453子集子集2，4是不是最大獨(dú)立集？是不是最大獨(dú)立集？最大獨(dú)立集最大獨(dú)立集:2，4子集子集1,2是不是圖是不是圖 最大獨(dú)立集？最大獨(dú)立集？子集子集1,2,5是不是圖是不是圖 最大獨(dú)立集？最大獨(dú)立集？GG設(shè)無(wú)向圖設(shè)無(wú)向圖G=(V, E), |V|=n,用鄰接矩陣用鄰接矩陣a表示圖表示圖G, 問(wèn)題的解可表示為問(wèn)題的解可表示為n n元向量元向量x1, . xn , x x

43、i i 0,10,1. . 問(wèn)題的解空間用子集樹(shù)表示問(wèn)題的解空間用子集樹(shù)表示.算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 回溯法回溯法 最大團(tuán)問(wèn)題 算法思路算法思路.1011011，2，51，4，52，3，5101101剪枝原則：剪枝原則：約束條件約束條件:x1,x2,.xi xi+1是團(tuán)是團(tuán).目標(biāo)函數(shù)限界目標(biāo)函數(shù)限界:設(shè)設(shè) bestn: 已求出的最大團(tuán)的尺寸已求出的最大團(tuán)的尺寸; cn : 當(dāng)前團(tuán)的尺寸當(dāng)前團(tuán)的尺寸 ; r :剩余結(jié)點(diǎn)數(shù)目剩余結(jié)點(diǎn)數(shù)目;r=n-i當(dāng)當(dāng) cn+r bestn 時(shí)時(shí), 將將cn對(duì)應(yīng)右子樹(shù)剪去。對(duì)應(yīng)右子樹(shù)剪去。.1，2，51，4，52，3，50算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 回溯法

44、回溯法 最大團(tuán)問(wèn)題 最大團(tuán)問(wèn)題的回溯算法最大團(tuán)問(wèn)題的回溯算法int MaxClique(int * a, int vi,int n) Clique Y;Y.x = new int n+l;Y.a= a; /圖圖G G的鄰接矩陣的鄰接矩陣Y.n= n; /圖圖G G頂點(diǎn)數(shù)頂點(diǎn)數(shù)Y.cn = 0; /當(dāng)前團(tuán)頂點(diǎn)數(shù)當(dāng)前團(tuán)頂點(diǎn)數(shù)Y.bestn=0; /當(dāng)前最大團(tuán)頂點(diǎn)數(shù)當(dāng)前最大團(tuán)頂點(diǎn)數(shù)Y.bestx = v; /當(dāng)前最優(yōu)解當(dāng)前最優(yōu)解Y. Backtrack( 1 );delete Y. x;return Y. bestn； void clique:Backtrack(int i) if (in) /找到

45、更大團(tuán)找到更大團(tuán), ,更新更新 for (int j=1; j=n；j+) bestxj = xj; bestn = cn; return; / /檢查頂點(diǎn)檢查頂點(diǎn)i i是否與當(dāng)前團(tuán)相連是否與當(dāng)前團(tuán)相連 int OK = 1; /滿(mǎn)足加入團(tuán)的條件滿(mǎn)足加入團(tuán)的條件 for(int j =1; j bestn) /剪右枝條件，否則向右枝遞歸剪右枝條件，否則向右枝遞歸 Xi=0；Backtrack(i + 1); 設(shè)當(dāng)前擴(kuò)設(shè)當(dāng)前擴(kuò)展節(jié)點(diǎn)展節(jié)點(diǎn)Z Z位于位于解空間樹(shù)的第解空間樹(shù)的第i i層，層， 在進(jìn)入左在進(jìn)入左子樹(shù)之前，必子樹(shù)之前，必須確認(rèn)從頂點(diǎn)須確認(rèn)從頂點(diǎn)i i到已入選的到已入選的頂點(diǎn)集中每一頂點(diǎn)

46、集中每一個(gè)頂點(diǎn)都有邊個(gè)頂點(diǎn)都有邊相連。相連。 在進(jìn)入右在進(jìn)入右子樹(shù)之前，必子樹(shù)之前，必須確認(rèn)還有足須確認(rèn)還有足夠多的可選擇夠多的可選擇的頂點(diǎn)使算法的頂點(diǎn)使算法有可能在右子有可能在右子樹(shù)中找到更大樹(shù)中找到更大的團(tuán)。的團(tuán)。復(fù)雜度分析：復(fù)雜度分析：回溯算法回溯算法backtrackbacktrack所需所需的計(jì)算時(shí)間顯的計(jì)算時(shí)間顯然為然為O(n2O(n2n n) )。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 回溯法回溯法 著色問(wèn)題圖的圖的m m色判定問(wèn)題色判定問(wèn)題: 給定無(wú)向連通圖給定無(wú)向連通圖G和和m種顏色。用這些顏色為圖種顏色。用這些顏色為圖G的各頂點(diǎn)的各頂點(diǎn)著色著色. 問(wèn)是否存在著色方法問(wèn)是否存在著色方法

47、, 使得使得G中任中任2鄰接點(diǎn)有不同顏色。鄰接點(diǎn)有不同顏色。圖的圖的m m色優(yōu)化問(wèn)題色優(yōu)化問(wèn)題: :給定無(wú)向連通圖給定無(wú)向連通圖G,為圖為圖G的各頂點(diǎn)著色的各頂點(diǎn)著色, 使圖中任使圖中任2鄰接點(diǎn)著鄰接點(diǎn)著不同顏色不同顏色,問(wèn)最少需要幾種顏色問(wèn)最少需要幾種顏色。所需的最少顏色的數(shù)目所需的最少顏色的數(shù)目m m稱(chēng)為該圖的稱(chēng)為該圖的色數(shù)色數(shù)。5.8 圖的圖的m m著色問(wèn)題著色問(wèn)題 問(wèn)題描述可平面圖：可平面圖：如果一個(gè)圖得所有頂點(diǎn)和邊都能用某種方式畫(huà)在平面上，且沒(méi)有如果一個(gè)圖得所有頂點(diǎn)和邊都能用某種方式畫(huà)在平面上，且沒(méi)有任何兩面相交，則稱(chēng)這個(gè)圖為可平面圖。任何兩面相交，則稱(chēng)這個(gè)圖為可平面圖。4 4色定理

48、：色定理：若圖若圖G是可平面圖是可平面圖,則它的色數(shù)不超過(guò)則它的色數(shù)不超過(guò)4色色4 4色定理的應(yīng)用色定理的應(yīng)用: :在一個(gè)平面或球面上的任何地圖能夠只用在一個(gè)平面或球面上的任何地圖能夠只用4種顏色來(lái)著色使種顏色來(lái)著色使得相鄰的國(guó)家在地圖上著有不同顏色得相鄰的國(guó)家在地圖上著有不同顏色4321512345a).a).將將G G的結(jié)點(diǎn)按照度數(shù)遞減的次序排列的結(jié)點(diǎn)按照度數(shù)遞減的次序排列. . b).b).用第一種顏色對(duì)第一個(gè)結(jié)點(diǎn)用第一種顏色對(duì)第一個(gè)結(jié)點(diǎn)著色著色, ,并并按照結(jié)點(diǎn)排列的次序按照結(jié)點(diǎn)排列的次序 對(duì)與前面對(duì)與前面著色著色點(diǎn)不鄰接的每一點(diǎn)著以相同顏色點(diǎn)不鄰接的每一點(diǎn)著以相同顏色. .c).c)

49、.用第二種顏色對(duì)尚未用第二種顏色對(duì)尚未著色的著色的點(diǎn)重復(fù)步驟點(diǎn)重復(fù)步驟b).b).用第三種顏色用第三種顏色 繼續(xù)這種作法繼續(xù)這種作法, , 直到所有點(diǎn)直到所有點(diǎn)著色完為止著色完為止. . 任意圖的著色任意圖的著色Welch PowellWelch Powell法法a1a5a4a6a2a3a7a8 排序排序: :a5, a3, a7, a1, a2, a4, a6, a8 著第一色著第一色: a5, a1,著第二色著第二色:a3,a4, a8著第三色著第三色:a7, a2, a6圖論圖論 對(duì)偶圖與著色對(duì)偶圖與著色算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 回溯法回溯法 圖的m著色設(shè)圖設(shè)圖G=(V, E), |

50、V|=n, 顏色數(shù)顏色數(shù)= m, 用鄰接矩陣用鄰接矩陣a表示表示G, 用整數(shù)用整數(shù)1, 2m來(lái)表示來(lái)表示m種不同的顏色。頂點(diǎn)種不同的顏色。頂點(diǎn)i所著的顏色用所著的顏色用xi表示。表示。問(wèn)題的問(wèn)題的解向量解向量可以表示為可以表示為n元組元組x= x1,.,xn . xi 1,2,.,m,解空間樹(shù)解空間樹(shù)為排序樹(shù)為排序樹(shù),是一棵是一棵n+1層的完全層的完全m叉樹(shù)叉樹(shù).在解空間樹(shù)中做深度優(yōu)先搜索在解空間樹(shù)中做深度優(yōu)先搜索, 約束條件約束條件: xi xj, 如果如果aji=1. 算法思路n=3, m=3n=3, m=3時(shí)的解空間樹(shù)時(shí)的解空間樹(shù)132011101110a=算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析

51、回溯法回溯法 著色問(wèn)題 int mColoring(int n, int m, int *a ) Color X； /初始化X Xn=n； /圖的頂點(diǎn)數(shù) Xm=m /可用顏色數(shù) Xa=a； /圖的鄰接矩陣 XSum=0; /已找到的著色方案數(shù) int*p=new int n+1； for (int i=0；in) sum+； for(int i=1; i=n; i+) cout xi ； cout endl ； else for ( int i=1; i=m; i+) xt=i; if (Ok(t) Backtrack( t+1); bool Color:Ok(int k)/檢查顏色可用性，即

52、約束條件檢查顏色可用性，即約束條件 for(int j=1；jn時(shí)，算法搜索至葉結(jié)點(diǎn)，得到時(shí)，算法搜索至葉結(jié)點(diǎn)，得到新的新的m著色方案，當(dāng)前找到的可著色方案，當(dāng)前找到的可m著色的著色的方案數(shù)方案數(shù)sum增一增一 當(dāng)當(dāng)in時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)Z是解空間中是解空間中的內(nèi)部結(jié)點(diǎn)。該結(jié)點(diǎn)有的內(nèi)部結(jié)點(diǎn)。該結(jié)點(diǎn)有xi=1,2,m共共m個(gè)兒子結(jié)點(diǎn)。對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)個(gè)兒子結(jié)點(diǎn)。對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)Z的每一的每一個(gè)兒子結(jié)點(diǎn)，由函數(shù)個(gè)兒子結(jié)點(diǎn)，由函數(shù)OK檢查其可行性，檢查其可行性，并以深度優(yōu)先遞歸地對(duì)可行的子樹(shù)進(jìn)行并以深度優(yōu)先遞歸地對(duì)可行的子樹(shù)進(jìn)行搜索，或減去不可行的子樹(shù)搜索，或減去不可行的子樹(shù)5.9 旅行售

53、貨員問(wèn)題旅行售貨員問(wèn)題 旅行商問(wèn)題的解空間是一個(gè)排列樹(shù)。如果以旅行商問(wèn)題的解空間是一個(gè)排列樹(shù)。如果以x=1, 2, , n 開(kāi)始，那么通過(guò)產(chǎn)生從開(kāi)始，那么通過(guò)產(chǎn)生從x2 到到xn 的所有排列，可生的所有排列，可生成成n 頂點(diǎn)旅行商問(wèn)題的解空間。頂點(diǎn)旅行商問(wèn)題的解空間。templateT AdjacencyWDigraph:TSP(int v) /* 用回溯算法解決旅行商問(wèn)題返回最優(yōu)旅游路徑的耗用回溯算法解決旅行商問(wèn)題返回最優(yōu)旅游路徑的耗費(fèi)，最優(yōu)路徑存入費(fèi)，最優(yōu)路徑存入v 1 : n */ /初始化初始化 x = new int n+1;/ x 是排列是排列 for (int i = 1; i

54、= n; i+) xi = i;bestc = NoEdge;bestx = v; / 使用數(shù)組使用數(shù)組v來(lái)存儲(chǔ)最優(yōu)路徑來(lái)存儲(chǔ)最優(yōu)路徑cc = 0; t S P ( 2 ) ; / 搜索搜索x 2 : n 的各種排列的各種排列 delete x;return bestc;void AdjacencyWDigraph:tSP(int i) / 旅行商問(wèn)題的回溯算法旅行商問(wèn)題的回溯算法if (i = n) / 位于一個(gè)葉子的父節(jié)點(diǎn)位于一個(gè)葉子的父節(jié)點(diǎn) 通過(guò)增加兩條邊來(lái)完成旅行通過(guò)增加兩條邊來(lái)完成旅行if (axn-1xn != NoEdge &axn1 != NoEdge & (c

55、c + axn-1xn + axn1 bestc |bestc = NoEdge) / 找到更優(yōu)的旅行路徑找到更優(yōu)的旅行路徑for (int j = 1; j = n; j+)bestxj = xj;bestc = cc + axn-1xn + axn1;else/ 嘗試子樹(shù)嘗試子樹(shù) for (int j = i; j = n; j+) / /能移動(dòng)到子樹(shù)能移動(dòng)到子樹(shù)x j 嗎嗎? if (axi-1xj != NoEdge &(cc + axi-1xi 0且且n o w j t o t a l j 時(shí)，時(shí)，Nj 在插槽在插槽i 和和i + 1之間有連線。之間有連線。插槽插槽i 和和i

56、 + 1間的線密度可利用該測(cè)試方法計(jì)算出來(lái)。在插槽間的線密度可利用該測(cè)試方法計(jì)算出來(lái)。在插槽k和和k + 1 ( 1ki ) 間的線密度的最大值給出了局部排列的密度。間的線密度的最大值給出了局部排列的密度。 為了實(shí)現(xiàn)電路板排列問(wèn)題的回溯算法，使用了類(lèi)為了實(shí)現(xiàn)電路板排列問(wèn)題的回溯算法，使用了類(lèi)B o a r d。函數(shù)函數(shù)A r r a n g e B o a r d s 返回最優(yōu)的電路板排列密度，最優(yōu)返回最優(yōu)的電路板排列密度，最優(yōu)的排列由數(shù)組的排列由數(shù)組bestx 返回。返回。 ArrangeBoards 創(chuàng)建類(lèi)創(chuàng)建類(lèi)Board 的一個(gè)成員的一個(gè)成員x 并初始化與之并初始化與之相關(guān)的變量。尤其是相關(guān)的變量。尤其是total 被初始化以使被初始化以使totalj 等于等于Nj 中電路中電路板的數(shù)量。板的數(shù)量。now1:n 被置為被置為0，與一個(gè)空的局部排列相對(duì)應(yīng)。，與一個(gè)空的局部排列相對(duì)應(yīng)。調(diào)用調(diào)用x .BestOrder(1,0) 搜索搜索x1:n 的排列樹(shù)，以從密度為的排列樹(shù)，以從密度為0的空的空排列中找到一個(gè)最優(yōu)的排列。排列中找到一個(gè)最優(yōu)的排列。通常，通常，x.BestOrder(i,cd) 尋找最優(yōu)的局部排列尋找最優(yōu)的