第12章-回溯法.ppt

1、1、了解學(xué)習(xí)要點回溯方法的深度優(yōu)先搜索策略。利用回溯方法求解問題的算法框架遞歸掌握回溯子集樹算法框架陣列樹算法框架，應(yīng)用樣本，學(xué)習(xí)回溯方法的設(shè)計策略。回溯算法，2，很多問題?；厮莘ń?jīng)常在需要找出其解法或回答某個解法是滿足特定約束條件的最佳解法時使用。(莎士比亞，回溯，回溯，回溯，回溯，回溯，回溯)回溯法的基本方法是一種徹底的搜索方法，可以通過搜索或組織方式來避免不必要的搜索。此方法適用于解決組合數(shù)相當(dāng)多的問題?；厮莘椒ǜ鶕?jù)問題的解決空間樹中的深度優(yōu)先策略，在根節(jié)點中搜索解決空間樹。算法搜索解決方案空間樹的任意位置時，首先確定該節(jié)點是否包含問題的解決方案。如果確實不包含，請?zhí)^對節(jié)點為根的子樹的

2、搜索，并返回到父節(jié)點。否則，進(jìn)入子樹并根據(jù)深度優(yōu)先級策略繼續(xù)搜索。回溯方法，3，問題的解決空間，問題的解決向量：回溯方法希望一個問題的解決用N元表達(dá)式(X1，X2，XN)表示。展示約束：限制元件Xi的值。隱式約束：為了解決問題，在徐璐其他零部件之間應(yīng)用的約束。分析空間：在問題的一個實例中，分析向量滿足顯式約束的所有多組構(gòu)成了該實例的分析空間。注意：同一問題可能有多種表現(xiàn)形式，有些表現(xiàn)形式更簡單，所需表現(xiàn)形式的狀態(tài)空間更小(存儲容量更小，檢索方法更簡單)。n=3點0-1背包問題是用完整二叉樹表示的解空間，4，生成問題狀態(tài)的基本方法，生成擴(kuò)展節(jié)點：兒子的節(jié)點稱為擴(kuò)展節(jié)點活動節(jié)點：創(chuàng)建了自己但兒子尚

3、未全部創(chuàng)建的節(jié)點稱為活動節(jié)點：創(chuàng)建問題狀態(tài)的方法，將所有兒子已經(jīng)創(chuàng)建的節(jié)點稱為死節(jié)點深度優(yōu)先級：對擴(kuò)展完成對子樹C (C根子樹)的徹底搜索后，將R更改回擴(kuò)展節(jié)點，繼續(xù)創(chuàng)建R的下一個兒子(如果有)寬度優(yōu)先級問題狀態(tài)的生成方法。擴(kuò)展節(jié)點回溯方法，直到擴(kuò)展節(jié)點成為死節(jié)點：必須繼續(xù)利用邊界函數(shù)，以避免生成無法生成最佳解決方案的問題狀態(tài)。具有邊界函數(shù)的深度優(yōu)秀教師成法定義了回溯，5，回溯方法的基本思想，(1)給定問題的解決空間。(2)確定易于搜索的解決方案空間結(jié)構(gòu)。(3)以深度優(yōu)先級搜索解釋空間，在搜索過程中使用修剪函數(shù)防止錯誤搜索。典型修剪函數(shù)：使用約束函數(shù)在擴(kuò)展節(jié)點上剪切不符合約束條件的子樹。使用邊

4、界函數(shù)截斷無法獲得最佳解決方案的子樹。用回溯方法解決問題的一個突出特征是在搜索過程中動態(tài)引起問題的解決空間。在任何時候，算法僅存儲從根節(jié)點到當(dāng)前擴(kuò)展節(jié)點的路徑。如果解析空間樹中從根節(jié)點到分葉節(jié)點的最長路徑長度為h(n)，則回溯方式所需的計算空間通常為O(h(n)。要顯式保存整個解決方案空間，請選擇O(2h(n)或O(h(n)！)內(nèi)存空間。6，遞歸回溯，回溯方法對解析空間進(jìn)行深度優(yōu)先搜索，因此通常使用遞歸方法實現(xiàn)回溯方法。void back track(int)if(TN)output(x)；Else for (int i=f(n，t)；I=g(n，t)；I)XT=h(I)；可以使用If(約束(

5、t)，7，迭代回溯，樹的非迭代深度優(yōu)先遍歷算法，將回溯方法表示為非迭代過程。，void iterativeBacktrack()int t=1；While (t0) if (f (n，t)=g (n，t) for (int I=f (n，t)；I=g(n，t)；I)XT=h(I)；If (constraint(t)，8，子集樹和排序樹，計算時間O(2n)通過子集樹，計算時間O(n)通過數(shù)組樹！)時間計算，void back track(int t)if(TN)output(x)；else for(int I=0)；I=1；I)XT=I；If(普通(t)后方軌道(t1)；void back tr

6、ack(int)if(TN)output(x)；else for(int I=t；I=n；I) swap(xt，Xi) : If(常規(guī)(t)后方軌道(t1)；Swap(xt，Xi):9，裝載問題，共N個集裝箱，必須分別裝載C1和C2的船舶，其中集裝箱I的重量為wi，裝載問題需要確定這兩艘船是否有合理的裝載方案。如果存在，請查找裝載方案。解決了指定的裝載問題后，使用以下策略可以輕松地證明可以獲得最佳裝載方案：(1)先把第一艘輪船盡量裝滿。(2)將剩余容器安裝在第二艘船上。盡可能多地填充第一艘船，使其與選擇整個容器的子集相同，從而使該子集的容器重量總和最接近。由此可見，裝載問題與以下特殊的0-1背

7、包問題相同。設(shè)計了用回溯方法求解掛載問題的O(2n)計算時間算法。在某些情況下，該算法優(yōu)于動態(tài)編程算法。10，裝載問題，空間解決方法：子集樹可行性約束函數(shù)(選擇當(dāng)前要素):父函數(shù)(渡邊杏選擇當(dāng)前要素):當(dāng)前裝載重量CW剩馀容器的重量R當(dāng)前最佳裝載重量bestw，void backtrack (int i) /搜索層次結(jié)構(gòu)Ir-=wi；if(CW wi bestw)Xi=0；/搜索右側(cè)子樹back track(i1)；R=wi，11，批處理作業(yè)調(diào)度，給定N個作業(yè)的集合J1，J2，Jn。每個作業(yè)必須先在機器1上處理，然后在機器2上處理。作業(yè)Ji必須是機器J的處理時間tji。對于已確認(rèn)的作業(yè)調(diào)度，F(xiàn)

8、ji設(shè)置是作業(yè)I在系統(tǒng)J中完成處理的時間。要解決所有作業(yè)在系統(tǒng)2上完成處理的時間和稱為作業(yè)調(diào)度的完成時間和批處理作業(yè)調(diào)度問題，必須為指定的N個作業(yè)開發(fā)最佳作業(yè)調(diào)度方案，以將完成時間和最小化。這三個任務(wù)的6個可能的時間表方案是1，2，3。1，3，2；2，1，3；2，3，1；3，1，2；3，2，1；相應(yīng)的完成時間和分別為19，18，20，21，19，19。顯然，最佳調(diào)度方案是1，3，2，其完成時間和18。12，調(diào)度批處理作業(yè)，解決空間：陣列樹，void flowshop 3360: back track(int I)if(I n)for(int j=1；J f1)？f2i-13360 f1)mxj

9、 2；F=f2iIf (f bestf) Swap(xi，XJ)；back track(I 1)；Swap(xi，XJ):F1-=MX J1；f-=f2i；class flowshop friend flow (int * *，int，int)；private 3360 void back track(Int I):Int * * M，/每個作業(yè)所需的處理時間*x，/當(dāng)前作業(yè)調(diào)度*bestx，/當(dāng)前最佳作業(yè)調(diào)度*f2，13，符號三角形問題，-，下圖是由14個“”和14個“-”組成的符號三角形。兩個東湖下方都是“”，兩個兩湖下方都是“-”。通常，符號三角形的第一行有n個符號。符號三角形問題需要計

10、算多個不同的符號三角形，以使給定N的“”和“-”數(shù)相等。14，符號三角形問題，解決向量：符號三角形的第一行表示為N元組x1:n。可行性約束函數(shù)：當(dāng)前符號三角形中包含的“”數(shù)和“-”數(shù)不超過n*(n 1)/4未解決的判斷。n*(n 1)/2是奇數(shù)，void triangle :3360 back track If(TN)sum；else for(int I=0)；I2；I)p1t=I；count=I；for(int j=2；j=t；j)pjt-j 1=pj-1t-j 1pj-1t-j 2；count=pjt-j 1；back track(t 1)；for(int j=2；j=t；j)count-

11、=pjt-j 1；count-=I；-復(fù)雜性分析可計算性約束O(n)時間，最壞情況下為O(2n)節(jié)點可計算性約束，解釋符號三角形問題的回溯算法所需的計算時間為O(n2n)，15，N以后的問題，在nn格的棋盤上放置N個不受徐璐攻擊的皇后。根據(jù)國際象棋的規(guī)則，皇后可以攻擊同一排或同一排或同一斜線上的圍棋。N后的問題等于在N坎的棋盤上放置N個皇后。兩位皇后都不在同一排或同一排或同一排的斜線上。(阿爾伯特愛因斯坦，Northern Exposure(美國電視劇)，16，解決方案向量：(x1，x2，xn)顯示限制：xi=1，2，n隱含限制else for(int I=1；I=n；I)XT=I；if(Pl

12、ace(t)back track(t 1)；17，0-1背包問題，空間解釋：子集樹可行性約束函數(shù)：上限函數(shù)：template Typep knap 3360: bound(int I)/上限typewcleft=c-計算/按物料單位重量值降序裝入物料While(I=n，18，最大組問題，給定無向圖G=(V，e)。如果UV在任何U，vU上有(U，v)E，則U稱為G的完整子圖形。G的整個子圖U是G的組，僅當(dāng)U不包含在G的較大的整個子圖中時。g的最大組表示g包含的頂點數(shù)最多的組。如果UV在任意U，vU上有(U，v)E，則U稱為G的空圖形。G的空子圖形U是G的獨立集，僅當(dāng)U不包含在G的較大空圖形中時。

13、g的最大獨立集是g包含的頂點數(shù)最多的獨立集。無向圖G=(V，E)的補充圖G=(V1，E1)由V1=V定義，(u，v)E1僅由(u，v)E定義。u是g的最大組，僅在u是g的最大獨立集時可用。19，最大組問題，解決空間：子集樹可行性約束函數(shù)：從頂點I到選定頂點集中的每個頂點都有邊連接。上限函數(shù)：有足夠的可選頂點，算法可以在右側(cè)子樹中找到較大的組。void clique 3360: back track(int I)/最大組計算if (i n) /到達(dá)葉節(jié)點for(int j=1；J bestn) /進(jìn)入右側(cè)子樹Xi=0；back track(I 1)；復(fù)雜性分析最大組問題的回溯算法backtrac

14、k所需的計算時間為O(n2n)。20，進(jìn)一步改進(jìn)，選擇適當(dāng)?shù)乃阉黜樞?，更有效地使用上限函?shù)。例如，在搜索之前，可以按從小到大的順序排列頂點。這在某種意義上等同于啟發(fā)回溯方法。Si=vi、vi 1、定義vn，然后定義Sn、Sn-1、然后查找S1的解決方案。因此，可以得到更精確的上限函數(shù)，如果cn Si=max，則截斷樹枝。此外，如果找到從Si 1到Si的較大組，則VI必須屬于找到的組。此時Si=Si 1。否則，存在SI=SI 1。因此，如果更新了max中的值，則可以看到找到了最大值，不再需要向下搜索。21，圖中的M著色問題，給定無方向連接圖G和M種不同顏色。使用此顏色將圖形G中的每個頂點著色為一

15、種顏色。g的每條邊上的兩個頂點是否有不同顏色的著色方法。這是圖的M顏色確定問題。如果圖需要最小M種顏色，以便連接到圖每條邊的兩個頂點徐璐具有不同的顏色，則此數(shù)M稱為該圖的顏色數(shù)。尋找圖的顏色數(shù)M的問題稱為圖的M顏色優(yōu)化問題。22，矢量解釋：(x1，x2，xn)表示頂點I的顏色Xi可行性約束函數(shù)。頂點I與相鄰著色頂點顏色不重復(fù)。，圖m著色問題，void color :背面跟蹤(int)if(TN)sum；for(int I=1)；I=n；I)cout Xi；Cout endlelse for(int I=1；I=m；I)XT=I；If (ok (t)回溯(t1)；bool color 33603360 ok(int k)/檢查顏色可用性for(int j=1；j=n；J) if (akj=1)，復(fù)雜性分析圖M可著色問題的分析空間樹的內(nèi)部節(jié)點數(shù)針對每個內(nèi)部節(jié)點。在最壞的情況下，使用ok檢查當(dāng)前擴(kuò)展節(jié)點中每個兒子的顏色可用性需要O(mn)。因此，追溯方法的總時間成本為23，旅行推銷員問題，問題說明，一名推銷員想去多個城市銷售商品，知道各個城市之間的距離(或旅費)。他將從駐地出發(fā)，為每個城市選擇一次，最后選擇返回駐地的路線，將總旅費(或