回溯演算法(Backtracking)

1、回溯演算法(Backtracking)2n The Divide-and-Conquer Strategy (個各擊破)l binary Searching、Quick Sort. n The Greedy Method(貪婪演算法) l Prim MST、Kruskal MST、Djikstras algorithmn Dynamic Programming(動態演算法)l 二項是係數、矩陣連乘、最佳二元搜尋樹n Trace Back(回溯)l 圖形著色、漢米爾迴路問題.n Branch-and-Bound (樹的追蹤)3回溯法通常被用來解下面這類型問題。問題敘述：你必須從一個物件集合中選出

2、一的物件，並且這序列要滿足一些。例如，n-Queen問題。必須要將 n 個皇后放在一個 nn 的西洋棋盤上而不互相攻擊。序列：安全地擺皇后的n個位置。物件集合：所有可能的n2個棋盤上的位置。4 回溯技巧：深度優先搜尋(Depth-first search) 演算法之變形5128113 4 75 69 10 1213161415Depth-First Search6depth_first_tree_search Algorithmvoid depth_first_tree_search ( node v )node u ;visit v ; / 走訪 vfor ( v 的每個子節點 u ) /

3、由左到右依序走訪depth_first_tree_search ( u ) ;7生成樹V1V2V4V3V58n=4 的 n-Queen 問題后后后后若將第一個皇后放在第一行，則第二個皇后不可以放在第一行或是第二行。9Start1,11,21,31,42,12,12,22,32,43,13,23,33,44,14,24,34,44,14,24,34,44-Queen問題的部份狀態空間樹 表示第 i 列的皇后放在第 j 行。任何一條從樹根到葉節點的路徑就代表著一個可能的答案。10回溯法的定義1. 當我們知道此節點一定會通往死路時，我們就立即返回父節點，繼續走訪父節點的其它子節點。2. 沒前景(no

4、npromising)：某節點一定無法帶我們找到答案。3. 有前景(promising)：某節點可能帶我們找到答案。11回溯法的定義(續)1. 修剪(pruning)狀態空間樹：走到nonpromising節點時，立刻返回父節點的動作。2. 修剪過的狀態空間樹(pruned state space tree)：修剪後剩下的那些走訪過的節點。12回溯的一般演算法 checknodevoid checknode ( node v )node u ;if ( promising ( v ) )if ( v 是答案 )印出答案 ;elsefor ( v 的每個子節點 u )checknode ( u

5、) ;針對不同問題設計1314154-Queen 的回溯演算法Start1,12,1 2,2 2,32,43,1 3,2 3,3 3,4 3,1 3,2 3,3 3,44,1 4,2 4,3 4,41,22,12,2 2,32,43,14,1 4,2 4,3后后后后后后后后后后后后后后后遇到nonpromosing節點就立即返回父節點，並走訪父節點的其他子節點。16用expand來改進checknode的效率void expand ( node v )node u ;for ( v 的每個子節點 u )if ( promising ( u ) )if ( 在 u 有解答 )印出解答 ;else

6、expand ( u ) ;先檢查再走訪為何這樣較有效率？17The n-Queens ProblemCol(i) : 第 i 列皇后所在的行位置。Col(3) = 1, Col(6) = 4Col(6) - Col(3)= 4 - 1 = 3 ( = 6 - 3 )Col(2) = 8, Col(6) = 4Col(6) - Col(2) = 4 - 8 = -4 ( = 2 - 6 )可改寫成 :| Col(6) - Col(2) |= 4 ( = 6 - 2 )18void queens ( index i ) index j ; if ( promising (i) ) if ( i

7、= n ) cout col 1 至 col n ; else for ( j = 1; j = n ; j+ ) col i + 1 = j ; / 檢查位於第 (i+1) 列的 queens (i + 1); / 皇后可否放在第 j 行上 The Backtracking Algorithm for the n-Queens Problem 19bool promising ( index i ) index k ; bool switch ; k = 1 ; switch = true ; / 檢查有沒有其他皇后會攻擊while ( k W 設 total 代表剩下物件的總重量。 non

8、promising 檢驗策略：weight + total W28展示使用回溯法來處理 n=4、W=13所有不含解答的葉節點都是nonpromising一定要走到葉節點才會有解嗎？29用回溯解決 Sum-of-Subsets 問題問題：給定 n 個正整數(重量)和另一個正整數W，找出所有重量 和是W的正整數集合。輸入：正整數 n ，已經排序過的遞增正整數 w，正整數W。輸出：所有重量總和為W的正整數集合。void sum_of_subsets ( index i , int weight , int total ) if ( promising ( i ) ) /檢查第 i 個物品是否 pro

9、misingif ( weight = W ) cout = W ) &( weight = W | weight + wi+1 = W)且(目前已選取物品總重量 = W) 或(目前已選取物品總重量 + 剩下物品中最輕的重量 = W )31狀態空間樹的節點數總共節點數 = 1+2+22+.+2n = 2n+1 - 1(參考 A.3)必須用 Monte Carlo 來分析才有辦法評估效率。32圖形著色V1V2V3V4本圖無 2-著色問題的解，但有 3-著色問題的解(6個)。m-圖形著色問題的定義：每個相鄰節點不可用相同的顏色來著色。最多用 m 種顏色。不同 m 值的問題視為彼此單獨不同的問題。3

10、3平面圖形(Planar)一個圖形可在平面上著色且任何節線不相交，即稱為Planar。地圖Planar加上(V1，V5)和(V2，V4)後就不再是 Planar。340111101011011010相鄰矩陣V1V2V3V4使用回溯來解決3-著色問題第一個解答35解 m-著色問題(回溯演算法)問題：找出所有可能方式，只用 m 種顏色來對一個無向圖 著色，並使得任兩相鄰頂點均為相異色。輸入：正整數 n 和 m，一個有 n 個頂點的無向圖形 (以相鄰 矩陣表示之)。輸出：所有可能的方法，最多用 m 種顏色。 著色結果存在索引為 1 到 n 的 vector 陣列中，vectori代表的就是第 i 個

11、頂點的顏色 (正整數 1 到 m)。36void m_coloring ( index i )int color ;if ( promising ( i ) )if ( i = n ) cout vector1 到 vcolorn ;else for ( color = 1 ; color = m ; color + ) vcolori+1 = color ; /對下個頂點嘗試m_coloring( i+1 ) ; /著每種顏色 37bool promising ( index i )index j ;bool switch ;switch = true ;j = 1 ;while ( j i

12、 & switch ) if ( Wij & vcolori = vcolorj )switch = false ; /檢查相連頂點是否有j + ; /相同顏色return switch ;38漢米爾頓迴路問題V1V2V3V4V5V6V7V8V1V2V8V7V6V5V4V3V1V1V2V3V4V5找不到任何一條漢米爾頓迴路39漢米爾頓迴路的回溯策略1. 路徑上第 i 個點在圖形上必須與路徑上第 i-1 個點相連。2. 路徑上第 n-1 個點在圖形上必須與路徑上第 0 個點相連。3. 路徑上第 i 個點不可以與路徑上的前 i-1 個點重複。若不符合上述三個條件要求，則立即回溯。在演算法中，強制規

13、定用 V1 當作路徑的起始點。40用回溯法來解漢米爾頓迴路問題問題：在一個無向圖中找出所有的漢米爾頓迴路。輸入：正整數 n。 一個有 n 頂點數的無向圖，用一個二維陣列 W 表示。 行列編號皆由 1 至 n 表示。若 Wij = true，表示頂 點 i 和頂點 j 之間有邊相連接著。輸出：找出所有從某起始點開始，經過其它頂點僅一次，然 後回到原起始點的路徑。將結果存放在 vindex 陣列中 ，索引為 1 到 n-1，vindexi 代表路徑上的第 i 個點。 路徑的起始點為 vindex0。41 void hamiltonian ( index i ) index j ; if ( pro

14、mising ( i ) ) /檢查路徑上的第 i 點是否有前景 if ( i = n-1 ) 列印出 vindex0 至 vindexn-1 之值 ; else for ( j=2 ; j 0 & ! Wvindexi-1vindexi )switch = false ; /第 i 點必須和第(i-1)點相連 else switch = true ;j = 1 ;while ( j 16 (背包最大載重量 W)所以加入第 3 個物品後就會使總重量超過 W。= k = 3 (前面投影片中公式裡的 k 值)13107520jjwweighttotweight圖5.451(0,0)節點計算過程(續

15、)115$1050$)716(30$40$0$)(131033jjwptotweightWpprofitbound判斷出本節點 (0, 0) 是 promising。因為 (1) weight = 0 小於 16 (W 的值) (2) bound = $115 大於 $0 (目前 maxprofit 的值)P1P2第3個物品的部份獲益值圖5.452回溯法解0-1背包問題問題：給定 n 個物件及其個別 weight 與 profit 值 (皆為正整數)。 給定 W 值。在總重量不超過 W 的條件下，找出一組物件 使其總獲益是最大的。輸入：正整數 n 和 W。 陣列 w 與 p (索引均由 1 到

16、 n，且根據pi/wi由大到小 排序過)。輸出：bestset 陣列 (索引由 1 到 n)，其中 bestseti 值是 yes 代表 要拿第 i 個物品，no 代表不拿第 i 個物品。 正整數 maxprofit (即最大獲益)。53 void knapsack ( index i , int profit , int weight ) if ( weight maxprofit ) /若總重可接受，且獲益更好maxprofit = profit ; /將最佳獲益值 maxprofit 設成現在這個numbest = i ; /將 numbest 設成目前考慮的物品數bestset = i

17、nclude ; /將 bestset 設成這個解 if ( promising ( i ) ) /判斷第 i 層節點可否往下擴展include i+1 = yes ; /拿 wi+1knapsack ( i+1 , profit + pi+1 , weight + wi+1 ) ;include i+1 = no ; /不拿 wi+1knapsack ( i+1 , profit , weight ) ; 54 bool promising ( index i ) index j , k ; int totweight ; float bound ; /第 i 層節點最大獲益能力 if ( weight = W ) return false ; /背包已經爆了 else j = i + 1 ; /從 i 的下一層物品一直拿到背包爆掉或無東西可拿為止bound = profit ;totweight = weight ;while ( j = n & totweight + wj = W ) totweight = totweight + wj ; /盡可能拿越多物品越好bound = bound + pj ; /每拿一個物品就增加最大獲益能力j + ;k = j ; /在拿第 k 層物品時背