回溯演算法(Backtracking).ppt

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

2、物件，並且這序列要滿足一些指定條件。 例如，n-Queen問題。必須要將 n 個皇后放在一個 nn 的西洋棋盤上而不互相攻擊。序列：安全地擺皇后的n個位置。物件集合：所有可能的n2個棋盤上的位置。,4,回溯技巧：深度優先搜尋(Depth-first search) 演算法之變形,5,1,Depth-First Search,6,depth_first_tree_search Algorithm,void depth_first_tree_search ( node v ) node u ; visit v ; / 走訪 v for ( v 的每個子節點 u ) / 由左到右依序走訪 depth

3、_first_tree_search ( u ) ; ,7,生成樹,V1,V2,V4,V3,V5,8,n=4 的 n-Queen 問題,若將第一個皇后放在第一行，則第二個皇后不可以 放在第一行或是第二行。,9,Start,1,1,1,2,1,3,1,4,2,1,2,1,2,2,2,3,2,4,3,1,3,2,3,3,3,4,4,1,4,2,4,3,4,4,4,1,4,2,4,3,4,4,4-Queen問題的部份狀態空間樹, 表示第 i 列的皇后 放在第 j 行。,任何一條從樹根到葉節點的路徑就代表著一個可能的答案。,10,回溯法的定義,當我們知道此節點一定會通往死路時，我們就立即返回父節點，繼

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

5、 的每個子節點 u ) checknode ( u ) ; ,針對不同問題設計,13,14,15,4-Queen 的回溯演算法,后,后,后,后,后,后,后,后,后,后,后,后,后,后,后,遇到nonpromosing節點 就立即返回父節點，並 走訪父節點的其他子節 點。,16,用expand來改進checknode的效率,void expand ( node v ) node u ; for ( v 的每個子節點 u ) if ( promising ( u ) ) if ( 在 u 有解答 ) 印出解答 ; else expand ( u ) ; ,先檢查再走訪,為何這樣較有效率？,17,T

6、he n-Queens Problem,Col(i) : 第 i 列皇后所 在的行位置。 Col(3) = 1, Col(6) = 4 Col(6) - Col(3) = 4 - 1 = 3 ( = 6 - 3 ) Col(2) = 8, Col(6) = 4 Col(6) - Col(2) = 4 - 8 = -4 ( = 2 - 6 ) 可改寫成 : | Col(6) - Col(2) | = 4 ( = 6 - 2 ),18,void queens ( index i ) index j ; if ( promising (i) ) if ( i = n ) cout col 1 至 c

7、ol 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,19,bool promising ( index i ) index k ; bool switch ; k = 1 ; switch = true ; / 檢查有沒有其他皇后會攻擊 while ( k i ,The Backtracking Algorithm for the n-Qu

8、eens Problem,20,分析,整個狀態空間樹的節點總數為：,這就是我們所需走訪的節點數上限。 n = 8 時，,21,分析,嘗試分析 promising 節點數的上限值，以 n=8 狀況來說， 第一個皇后可以放在任何一行上面，而第二個皇后只剩下 七個行位置可以選，以此類推，第八個皇后只剩下一個行 位置可以選。,公式的一般式為：,個 promising 節點,夠精準嗎？ 對角線檢查呢？ 直接看看執行時所走訪的節點數。,22,列出使用回溯演算法來解決 n-皇后問題所能避免檢查的節點數,演算法二只考慮行和列是否 遭受攻擊的情況，故需走訪 n ! 個節點。,由 promising 知， exp

9、and 函式可節省 相當多時間。,DFS,23,演算法分析的目的,是要在程式執行之前就判斷演算法的效率。 給定兩個大小相同 ( n 值相等 ) 的不同問題，其中一 個可能只需走訪很少節點，另一個可能需要走訪所 有節點。如何知道回溯法對該問題是否有效？,24,Sum-of-Subsets 問題,範例 5.2 找出所有重量和為W的子集合 假設 n = 5，W = 21 且 w1=5 w2=6 w3=10 w4=11 w5=16 因為 w1+w2+w3 = 5+6+10 = 21 w1+w5 = 5+16 = 21 w3+w4 = 10+11 = 21 所以解答為 w1，w2，w3 、 w1，w5

10、、 w3，w4 在 0-1 背包問題中，只要找到一組解，就滿足小偷的要求。,25,圖5.7 Sum-of-Subsets 問題在 n = 3 時的狀態空間樹,n 很大時，可建立狀態空間樹,26,n=3，W=6 的狀態空間樹,唯一解,27,Sum-of-Subsets 的回溯策略,事先將所有重量以遞增方式排序。 設 wi+1 是第 i 層節點中剩下的最輕物品。 設 weight = 到第 i 層節點時的物件重量總和。 nonpromising 檢驗策略： weight + wi+1 W 設 total 代表剩下物件的總重量。 nonpromising 檢驗策略： weight + total W

11、,28,展示使用回溯法來處理 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 個物品是否 promising if ( weight =

12、W ) cout include1 到 include i ; /回溯 else includei + 1 = yes ; /選取 wi + 1 物品，展開左子樹 sum_of_subsets ( i+1 , weight + wi+1, total - wi+1 ); includei + 1 = no ; /不選取 wi + 1 物品，展開右子樹 sum_of_subsets ( i+1 , weight , total - wi+1 ) ; ,30,bool promising ( index i ) return ( weight + total = W ) ,(續),promisin

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

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

15、void 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 ) ; /著每種顏色 ,37,bool promising ( index i ) index j ; bool switch ; switch = true ; j = 1 ; while ( j i ,38,漢米爾

16、頓迴路問題,V1,V2,V3,V4,V5,V6,V7,V8,V1V2V8V7V6V5V4V3V1,V1,V2,V3,V4,V5,找不到任何一條漢米爾頓迴路,39,漢米爾頓迴路的回溯策略,1. 路徑上第 i 個點在圖形上必須與路徑上第 i-1 個點相連。 2. 路徑上第 n-1 個點在圖形上必須與路徑上第 0 個點相連。 3. 路徑上第 i 個點不可以與路徑上的前 i-1 個點重複。 若不符合上述三個條件要求，則立即回溯。 在演算法中，強制規定用 V1 當作路徑的起始點。,40,用回溯法來解漢米爾頓迴路問題,問題：在一個無向圖中找出所有的漢米爾頓迴路。 輸入：正整數 n。 一個有 n 頂點數的無

17、向圖，用一個二維陣列 W 表示。 行列編號皆由 1 至 n 表示。若 Wij = true，表示頂 點 i 和頂點 j 之間有邊相連接著。 輸出：找出所有從某起始點開始，經過其它頂點僅一次，然 後回到原起始點的路徑。將結果存放在 vindex 陣列中 ，索引為 1 到 n-1，vindexi 代表路徑上的第 i 個點。 路徑的起始點為 vindex0。,41,void hamiltonian ( index i ) index j ; if ( promising ( i ) ) /檢查路徑上的第 i 點是否有前景 if ( i = n-1 ) 列印出 vindex0 至 vindexn-1

18、之值 ; else for ( j=2 ; j = n ; j + ) /拿所有頂點當路徑的下一點 vindex i+1 = j ; hamiltonian ( i+1 ) ; ,初始呼叫方式： vindex0 = 1; /讓V1成為開始的頂點 hamiltonian ( 0 ) ;,42,bool promising ( index i ) index j ; bool switch ; if ( i = n-1 ,43,本演算法的狀態空間樹的總共節點數為,44,用回溯法解 0-1背包問題,Sum-of-Subsets 問題只要找到一組重量等於 W 的解答即可。 但 0-1背包問題則是除了重

19、量等於 W 之外，還要找到獲得利 益最大的那組解答，所以一定要搜尋完整個狀態空間樹的所 有節點才行。 void checknode ( node v ) node u ; if ( value ( v ) 比 best 更好 ) best = value ( v ) ; if ( promising ( v ) ) for ( 每個 v 的子節點 u ) checknode ( u ) ; ,初始時，給定一個最差 值給 best。,只要可以擴展子節點，就是 promising。,45,回溯法解0-1背包問題的策略,(1) 由樹的根節點往下走到第 i 層節點時，若已經沒空間 再放入更多物品的話，

20、則該節點就是 nonpromising。 設 weight = 在第 i 層節點所累積的物品總重量 若 weight W 則此節點一定是 nonpromising 。,背包的最大承受重量,46,回溯法解0-1背包問題的策略(續),(2) 從貪婪法則的觀點來找出一個較不明顯的判斷 promising 與否的方法。,前 k-1 個物品的 總獲益,可以分配給 第 k 個物品 的容量,第 k 個物品 單位重量的 獲益,總重量,到第 i 層節點為止的總重量,第 i+1 層到 k-1 層節點為止的總重量。 因為到第 k 層就爆了。,第 i 層節點 的最大獲益 上限值。,第 1 到 i 層節點的總獲益值,4

21、7,第 i 層節點若滿足下面條件，則為 nonpromising ： bound maxprofit,到目前為止所找到的 最好的獲益值。,第 i 層節點的最大獲益 能力。,48,範例 n=4，W=16,將物品依照單位重量獲益比 (Pi / Wi )值由大到小排序。 狀態空間樹的每個節點內部有三個數字，由上而下為： 全部獲益 ( 即 profit ) 全部重量 ( 即 weight ) 獲益上限值 ( 即 bound ),下一頁,49,回溯法解範例的修剪過的狀態空間樹,全部獲益 profit,全部重量 weight,最大獲益能力 bound,物品價值,物品重量,maxprofit =0,maxp

22、rofit =40,maxprofit =70,maxprofit =70,maxprofit =70,maxprofit =80,maxprofit =80,maxprofit =80,maxprofit =90,maxprofit =90,maxprofit =90,maxprofit =90,maxprofit =90,下一頁,上一頁,50,(0,0)節點計算過程,1. 將 maxprofit 設為 0 。( 指定一個最差值給目前最佳獲益值) 2. 走訪 (0, 0) 節點，即根節點。 (a) 計算它的 profit 和 weight。 profit = $0 weight = 0 (b

23、) 計算它的 bound 值。 2+5+10 = 17 且 17 16 (背包最大載重量 W) 所以加入第 3 個物品後就會使總重量超過 W。 = k = 3 (前面投影片中公式裡的 k 值),圖5.4,51,(0,0)節點計算過程(續),判斷出本節點 (0, 0) 是 promising。 因為 (1) weight = 0 小於 16 (W 的值) (2) bound = $115 大於 $0 (目前 maxprofit 的值),P1,P2,第3個物品的部份獲益值,圖5.4,52,回溯法解0-1背包問題,問題：給定 n 個物件及其個別 weight 與 profit 值 (皆為正整數)。 給定 W 值。在總重量不超過 W 的條件下，找出一組物件 使其總獲益是最大的。 輸入：正整數 n 和 W。 陣列 w 與 p (索引均由 1 到 n，且根據pi/wi由大到小 排序過)。 輸出：bestset 陣列 (索引由 1 到 n)，其中 bestseti 值是 yes 代表 要拿第 i 個物品，no 代表不拿第 i 個物品。 正整數 maxprofit (即最大獲益)。,53,void knapsack ( index i , int profit , int weight ) if ( weight maxprofit ) /若總重可接受，且獲益更好