回溯演算法(Backtracking)课件.ppt

回溯演算法(Backtracking) 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 (樹的追蹤) 簡介 回溯法通常被用來解下面這類型問題。 問題敘述：你必須從一個物件集合中選出一序列的物件，並且這序列要滿足一些指定條件。 例如，n-Queen問題。必須要將 n 個皇后放在一個 n?n 的西洋棋盤上而不互相攻擊。序列：安全地擺皇后的n個位置。物件集合：所有可能的n2個棋盤上的位置。 回溯技巧：深度優先搜尋(Depth-first search) 演算法之變形 生成樹 回溯法的定義 當我們知道此節點一定會通往死路時，我們就立即返回父節點，繼續走訪父節點的其它子節點。 沒前景(nonpromising)：某節點一定無法帶我們找到答案。 有前景(promising)：某節點可能帶我們找到答案。 回溯法的定義(續) 修剪(pruning)狀態空間樹：走到nonpromising節點時，立刻返回父節點的動作。 修剪過的狀態空間樹(pruned state space tree)：修剪後剩下的那些走訪過的節點。 回溯法解0-1背包問題的策略(續) 狀態空間樹的節點數 總共節點數 = 1+2+22+...+2n = 2n+1 - 1 (參考 A.3) 必須用 Monte Carlo 來分析才有辦法評估效率。 圖形著色 V1 V2 V3 V4 本圖無 2-著色問題的解， 但有 3-著色問題的解(6個)。 m-圖形著色問題的定義： 每個相鄰節點不可用相同 的顏色來著色。 最多用 m 種顏色。 不同 m 值的問題視為彼此 單獨不同的問題。 平面圖形(Planar) 一個圖形可在平面上著色且任何節線不相交，即稱為Planar。 地圖 Planar 加上(V1，V5)和(V2，V4)後就不再是 Planar。 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0 相鄰矩陣 V1 V2 V3 V4 使用回溯來解決3-著色問題 第一個 解答 解 m-著色問題(回溯演算法) 問題：找出所有可能方式，只用 m 種顏色來對一個無向圖 著色，並使得任兩相鄰頂點均為相異色。 輸入：正整數 n 和 m，一個有 n 個頂點的無向圖形 (以相鄰 矩陣表示之)。 輸出：所有可能的方法，最多用 m 種顏色。 著色結果存在索引為 1 到 n 的 vector 陣列中，vector[i] 代表的就是第 i 個頂點的顏色 (正整數 1 到 m)。 void m_coloring ( index i ) { int color ; if ( promising ( i ) ) if ( i == n ) cout vector[1] 到 vcolor[n] ; else for ( color = 1 ; color = m ; color ++ ) { vcolor[i+1] = color ; //對下個頂點嘗試 m_coloring( i+1 ) ; //著每種顏色 } } bool promising ( index i ) { index j ; bool switch ; switch = true ; j = 1 ; while ( j i switch ) { if ( W[i][j] vcolor[i] == vcolor[j] ) switch = false ; //檢查相連頂點是否有 j ++ ; //相同顏色 } return switch ; } 漢米爾頓迴路問題 V1 V2 V3 V4 V5 V6 V7 V8 V1?V2?V8?V7?V6?V5?V4?V3?V1 V1 V2 V3 V4 V5 找不到任何一條漢米爾頓迴路 漢米爾頓迴路的回溯策略 1. 路徑上第 i 個點在圖形上必須與路徑上第 i-1 個點相連。 2. 路徑上第 n-1 個點在圖形上必須與路徑上第 0 個點相連。 3. 路徑上第 i 個點不可以與路徑上的前 i-1 個點重複。