【正文】 計算機算法設計與分析 Design and Analysis of Computer Algorithms 第五章 回溯算法 Backtrack Algorithm 王紅霞 理學院 2021年 11月 12日 2 ? 理解回溯法的深度優(yōu)先搜索策略。 ? 掌握用回溯法解題的算法框架 ? （ 1）遞歸回溯 ? （ 2）迭代回溯 ? （ 3）子集樹算法框架 ? （ 4）排列樹算法框架 學習要點 2021年 11月 12日 3 提綱 一、回溯法的算法框架 二、裝載問題 三、 n后問題 四、 01背包問題 五、最大團問題 六、圖的 m著色問題 七、旅行售貨員問題 2021年 11月 12日 4 提綱 一、回溯法的算法框架 二、裝載問題 三、 n后問題 四、 01背包問題 五、最大團問題 六、圖的 m著色問題 七、旅行售貨員問題 2021年 11月 12日 5 深度優(yōu)先搜索算法 深度優(yōu)先搜索算法（ DepthFirstSearch），是搜索 算法 的一種。是沿著樹的深度遍歷樹的節(jié)點，盡可能深的搜索樹的分支，如果發(fā)現(xiàn)目標，則算法中止，屬于盲目搜索。 深度優(yōu)先搜索是圖論中的經典算法，利用深度優(yōu)先搜索算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的 圖論 問題，如最大路徑問題等等。 2021年 11月 12日 6 同時深度優(yōu)先搜索算法的時間復雜度不高（為線性時間復雜度），遍歷圖的效率往往非常高。因此，鑒于深度優(yōu)先搜索算法的強大功能以及高效性往往被研究圖論問題的專家所推崇，他們常建議在遇到未知性質的圖時，先對圖進行深度優(yōu)先遍歷，以了解未知圖的性質。 因發(fā)明 “ 深度優(yōu)先搜索算法 ” ，霍普克洛夫特與陶爾揚共同獲得計算機領域的最高獎： 圖靈獎 2021年 11月 12日 7 搜索與回溯是計算機解題中常用的算法，很多問題無法根據(jù)某種確定的計算法則來求解，可以利用搜索與回溯的技術求解?；厮菔撬阉魉惴ㄖ械囊环N控制策略。它的基本思想是：為了求得問題的解，先選擇某一種可能情況向前探索，在探索過程中，一旦發(fā)現(xiàn)原來的選擇是錯誤的，就退回一步重新選擇，繼續(xù)向前探索，如此反復進行，直至得到解或證明無解。 2021年 11月 12日 8 ?迷宮游戲 2021年 11月 12日 9 ?例： 迷宮游戲 2021年 11月 12日 10 例： N后問題 2021年 11月 12日 11 引言 ? 有許多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法。 ? 回溯法的基本做法是搜索，或是一種組織得井井有條的、能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當大的問題。 ?回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解：如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。 2021年 11月 12日 12 回溯法的算法框架 ? 本節(jié)介紹回溯法算法框架的有關問題： ?一、問題的解空間 ?二、回溯法的基本思想 ?三、遞歸回溯 ?四、迭代回溯 ?五、子集樹與排列樹 2021年 11月 12日 13 問題的解空間 ?問題所有可能的解構成了問題的解空間，解空間也就是進行窮舉的搜索空間。 ? 確定正確的解空間很重要！ 例如：桌子上有 6根火柴棒，要求以這 6根火柴棒為邊搭建 4個等邊三角形。 (a) 二維搜索空間無解 (b) 三維搜索空間的解 錯誤的解空間將不能搜索到正確答案！ 2021年 11月 12日 14 問題的解空間 ? 對于任何一個問題，可能解的 表示方式 和它相應的解釋 隱含了解空間及其大小。 ? 例如，對于有 n個物品的 0/1背包問題，其可能解的表示方式可以有以下兩種： （ 1）可能解由一個不等長向量組成，當物品 i(1≤i≤n)裝入背包時，解向量中包含分量 i，否則，解向量中不包含分量 i，當 n=3時，其解空間是： { ( ), (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3) } （ 2）可能解由一個等長向量 {x1, x2, …, x n}組成，其中xi=1(1≤i≤n)表示物品 i裝入背包， xi=0表示物品 i沒有裝入背包，當 n=3時，其解空間是： {(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1) } 2021年 11月 12日 15 ?問題的解向量：回溯法希望一個問題的解能夠表示成一個 n元式 (x1,x2,… ,xn)的形式。 ?顯約束：對分量 xi的取值限定。 ?隱約束：為滿足問題的解而對不同分量之間施加的約束。 ?解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構成了該實例的一個解空間。 注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更小（存儲量少，搜索方法簡單）。 2021年 11月 12日 16 問題的解空間 ? 為了用回溯法求解一個具有 n個輸入的問題，一般情況下，將其可能解表示為滿足某個約束條件的等長向量 X=(x1, x2, …, x n)，其中分量 xi (1≤i≤n)的取值范圍是某個有限集合 Si={ai1, ai2, …, a iri}，所有可能的解向量構成了問題的 解空間 。 ? 問題的解空間一般用 解空間樹 （ Solution Space Trees,也稱狀態(tài)空間樹）的方式組織，樹的根結點位于第 1層，表示搜索的初始狀態(tài)，第 2層的結點表示對解向量的第一個分量做出選擇后到達的狀態(tài)，第 1層到第 2層的邊上標出對第一個分量選擇的結果，依此類推，從樹的根結點到葉子結點的路徑就構成了解空間的一個可能解。 2021年 11月 12日 17 問題的解空間 ? 對于 n=3的 0/1背包問題，其解空間樹如下圖所示，樹中的 8個葉子結點分別代表該問題的 8個可能解。 對物品 1的選擇 對物品 3的選擇 對物品 2的選擇 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 2 3 4 5 7 8 11 12 14 15 3 10 6 9 2021年 11月 12日 18 2 旅行售貨員問題 ? 問題描述：某售貨員要到若干城市去推銷商品，一直各城市之間的路程，他要選定一條從駐地出發(fā)，經過每個城市一遍，最后回到住地的路線，使總的路程最短。 ? 該問題是一個 NP完全問題， 有 (n1)!條可選路線 ? 最優(yōu)解 (1,3,2,4,1)，最優(yōu)值 25 1 2 3 4 20 6 30 5 4 10 A B C D E F G H I J K L M N O P Q 1 2 3 4 3 4 4 3 4 2 3 2 2 4 2 3 2021年 11月 12日 19 回溯法的基本思想 ? 回溯法從根結點出發(fā)，按照 深度優(yōu)先 策略搜索（遍歷）解空間樹，搜索滿足約束條件的解。 ? 初始時，根結點成為一個 活結點 ，同時也稱為當前的 擴展結點 。在當前擴展結點處，搜索向縱深方向移至一個新結點。這個新結點成為一個新的活結點，并成為當前的擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前的擴展結點就成為一個 死結點 （即不再是一個活節(jié)點）。此時，應往回移動（回溯）至最近的一個活結點處，并使這個活結點成為當前的擴展結點。 2021年 11月 12日 20 回溯法的基本思想 ? 在搜