《回溯演算法(Backtracking)》由会员分享，可在线阅读，更多相关《回溯演算法(Backtracking)（55页珍藏版）》请在金锄头文库上搜索。
1、回溯演算法(Backtracking),2,The Divide-and-Conquer Strategy (個各擊破) binary Searching、Quick Sort. The Greedy Method(貪婪演算法) Prim MST、Kruskal MST、Djikstras algorithmDynamic 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 ; / 走訪 vfor ( v 的每個子節點 u ) / 由左到右依序走訪depth_first_tree
3、_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 是答案 )印出答案 ;elsefor ( v 的每個子節點 u )checknode (
5、u ) ;,針對不同問題設計,13,14,15,4-Queen 的回溯演算法,后,后,后,后,后,后,后,后,后,后,后,后,后,后,后,遇到nonpromosing節點就立即返回父節點，並走訪父節點的其他子節點。,16,用expand來改進checknode的效率,void expand ( node v )node u ;for ( v 的每個子節點 u )if ( promising ( u ) )if ( 在 u 有解答 )印出解答 ;elseexpand ( u ) ;,先檢查再走訪,為何這樣較有效率？,17,The n-Queens Problem,Col(i) : 第 i 列皇后
6、所在的行位置。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 ),18,void queens ( index i ) index j ; if ( promising (i) ) if ( i = n ) cout col 1 至 col n ; else for ( j = 1; j = n ; j+ ) col i +
7、 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 W設 total 代表剩下物件的總重量。 nonpromising 檢驗策略：weight + total W,28,展示使用回溯法來處理 n=4、W=13,所有不含解答的葉節
8、點都是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 個物品是否 promisingif ( weight = W ) cout = W ) ,(續),promising 策略：(目前已
9、選取物品總重量 + 剩下物品總重量 = 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),一個圖形可在平面上著色且任何節線不相交，即
10、稱為Planar。,地圖,Planar,加上(V1，V5)和(V2，V4)後就不再是 Planar。,34,相鄰矩陣,使用回溯來解決3-著色問題,第一個解答,35,解 m-著色問題(回溯演算法),問題：找出所有可能方式，只用 m 種顏色來對一個無向圖 著色，並使得任兩相鄰頂點均為相異色。輸入：正整數 n 和 m，一個有 n 個頂點的無向圖形 (以相鄰 矩陣表示之)。輸出：所有可能的方法，最多用 m 種顏色。 著色結果存在索引為 1 到 n 的 vector 陣列中，vectori代表的就是第 i 個頂點的顏色 (正整數 1 到 m)。,36,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 ,
