【正文】 (constraint(t)amp。i=n。 } } void backtrack (int t) { if (tn) output(x)。amp。i++) { x[t]=i。 else for (int i=0。} } else t。bound(t)) { //函數(shù) solution(t)判斷在當(dāng)前擴(kuò)展結(jié)點(diǎn)處是否找到問(wèn)題的一個(gè)可行解； if (solution(t)) output(x)。 if (constraint(t)amp。i=g(n,t)。 // constraint(t)和 bound(t)分別表示在當(dāng)前擴(kuò)展結(jié)點(diǎn)處的約束函數(shù) 和限界函數(shù)； } } 2021年 11月 12日 24 迭代回溯 void IterativeBacktrack () { int t=1。amp。i++) { //f(n,t)和 g(n,t)分別表示在當(dāng)前擴(kuò)展結(jié)點(diǎn)處未搜索過(guò)的子樹(shù)的起始 編號(hào)和終止編號(hào)； x[t]=h(i)。 //n表示解空間樹(shù)的高度； else for (int i=f(n,t)。 ?回溯法的基本思想是在一棵含有問(wèn)題全部可能解的狀態(tài)空間樹(shù)上進(jìn)行深度優(yōu)先搜索，解為葉子結(jié)點(diǎn)，搜索過(guò)程中，每到達(dá)一個(gè)結(jié)點(diǎn)時(shí)，則判斷該結(jié)點(diǎn)為根的子樹(shù)是否含有問(wèn)題的解，如果不含有問(wèn)題的解，則放棄對(duì)該子樹(shù)的搜索，退回到上層父結(jié)點(diǎn)，繼續(xù)下一步深度優(yōu)先搜索過(guò)程。 這兩類函數(shù)統(tǒng)稱為 剪枝函數(shù) （ Pruning Function） 。 2021年 11月 12日 20 回溯法的基本思想 ? 在搜索至樹(shù)中任一結(jié)點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)對(duì)應(yīng)的部分解是否滿足 約束條件 ，或者是否超出 限界函數(shù) 的界，也就是判斷該結(jié)點(diǎn)是否 包含 問(wèn)題的（最優(yōu)）解，如果肯定不包含，則跳過(guò)對(duì)以該結(jié)點(diǎn)為根的子樹(shù)的搜索，即所謂 剪枝 （ Pruning） ；否則，進(jìn)入以該結(jié)點(diǎn)為根的子樹(shù)，繼續(xù)按照深度優(yōu)先策略搜索。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，則當(dāng)前的擴(kuò)展結(jié)點(diǎn)就成為一個(gè) 死結(jié)點(diǎn) （即不再是一個(gè)活節(jié)點(diǎn)）。在當(dāng)前擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)。 ? 該問(wèn)題是一個(gè) NP完全問(wèn)題， 有 (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 回溯法的基本思想 ? 回溯法從根結(jié)點(diǎn)出發(fā)，按照 深度優(yōu)先 策略搜索（遍歷）解空間樹(shù)，搜索滿足約束條件的解。 2021年 11月 12日 17 問(wèn)題的解空間 ? 對(duì)于 n=3的 0/1背包問(wèn)題，其解空間樹(shù)如下圖所示，樹(shù)中的 8個(gè)葉子結(jié)點(diǎn)分別代表該問(wèn)題的 8個(gè)可能解。 2021年 11月 12日 16 問(wèn)題的解空間 ? 為了用回溯法求解一個(gè)具有 n個(gè)輸入的問(wèn)題，一般情況下，將其可能解表示為滿足某個(gè)約束條件的等長(zhǎng)向量 X=(x1, x2, …, x n)，其中分量 xi (1≤i≤n)的取值范圍是某個(gè)有限集合 Si={ai1, ai2, …, a iri}，所有可能的解向量構(gòu)成了問(wèn)題的 解空間 。 ?解空間：對(duì)于問(wèn)題的一個(gè)實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。 ?顯約束：對(duì)分量 xi的取值限定。 (a) 二維搜索空間無(wú)解 (b) 三維搜索空間的解 錯(cuò)誤的解空間將不能搜索到正確答案！ 2021年 11月 12日 14 問(wèn)題的解空間 ? 對(duì)于任何一個(gè)問(wèn)題，可能解的 表示方式 和它相應(yīng)的解釋 隱含了解空間及其大小。 2021年 11月 12日 12 回溯法的算法框架 ? 本節(jié)介紹回溯法算法框架的有關(guān)問(wèn)題： ?一、問(wèn)題的解空間 ?二、回溯法的基本思想 ?三、遞歸回溯 ?四、迭代回溯 ?五、子集樹(shù)與排列樹(shù) 2021年 11月 12日 13 問(wèn)題的解空間 ?問(wèn)題所有可能的解構(gòu)成了問(wèn)題的解空間，解空間也就是進(jìn)行窮舉的搜索空間。 ?回溯法在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。 ? 回溯法的基本做法是搜索，或是一種組織得井井有條的、能避免不必要搜索的窮舉式搜索法。它的基本思想是：為了求得問(wèn)題的解，先選擇某一種可能情況向前探索，在探索過(guò)程中，一旦發(fā)現(xiàn)原來(lái)的選擇是錯(cuò)誤的，就退回一步重新選擇，繼續(xù)向前探索，如此反復(fù)進(jìn)行，直至得到解或證明無(wú)解。 因發(fā)明 “ 深度優(yōu)先搜索算法 ” ，霍普克洛夫特與陶爾揚(yáng)共同獲得計(jì)算機(jī)領(lǐng)域的最高獎(jiǎng)： 圖靈獎(jiǎng) 2021年 11月 12日 7 搜索與回溯是計(jì)算機(jī)解題中常用的算法，很多問(wèn)題無(wú)法根據(jù)某種確定的計(jì)算法則來(lái)求解，可以利用搜索與回溯的技術(shù)求解。 2021年 11月 12日 6 同時(shí)深度優(yōu)先搜索算法的時(shí)間復(fù)雜度不高（為線性時(shí)間復(fù)雜度），遍歷圖的效率往往非常高。是沿著樹(shù)的深度遍歷樹(shù)的節(jié)點(diǎn)，盡可能深的搜索樹(shù)的分支，如果發(fā)現(xiàn)目標(biāo)，則算法中止，屬于盲目搜索。計(jì)算機(jī)算法設(shè)計(jì)與分析 Design and Analysis of Computer Algorithms 第五章 回溯算法 Backtrack Algorithm 王紅霞 理學(xué)院 2021年 11月 12日 2 ? 理解回溯法的深度優(yōu)先搜索策略。 ? 掌握用回溯法解題的算法框架 ? （ 1）遞歸回溯 ? （ 2）迭代回溯 ? （ 3）子集樹(shù)算法框架 ? （ 4）排列樹(shù)算法框架 學(xué)習(xí)要點(diǎn) 2021年 11月 12日 3 提綱 一、回溯法的算法框架 二、裝載問(wèn)題 三、 n后問(wèn)題 四、 01背包問(wèn)題 五、最大團(tuán)問(wèn)題 六、圖的 m著色問(wèn)題 七、旅行售貨員問(wèn)題 2021年 11月 12日 4 提綱 一、回溯法的算法框架 二、裝載問(wèn)題 三、 n后問(wèn)題 四、 01背包問(wèn)題 五、最大團(tuán)問(wèn)題 六、圖的 m著色問(wèn)題 七、旅行售貨員問(wèn)題 2021年 11月 12日 5 深度優(yōu)先搜索算法 深度優(yōu)先搜索算法（ DepthFirstSearch），是搜索 算法 的一種。 深度優(yōu)先搜索是圖論中的經(jīng)典算法，利用深度優(yōu)先搜索算法可以產(chǎn)生目標(biāo)圖的相應(yīng)拓?fù)渑判虮?，利用拓?fù)渑判虮砜梢苑奖愕慕鉀Q很多相關(guān)的 圖論 問(wèn)題，如最大路徑問(wèn)題等等。因此，鑒于深度優(yōu)先搜索算法的強(qiáng)大功能以及高效性往往被研究圖論問(wèn)題的專家所推崇，他們常建議在遇到未知性質(zhì)的圖時(shí)，先對(duì)圖進(jìn)行深度優(yōu)先遍歷，以了解未知圖的性質(zhì)。回溯是搜索算法中的一種控制策略。 2021年 11月 12日 8 ?迷宮游戲 2021年 11月 12日 9 ?例： 迷宮游戲 2021年 11月 12日 10 例： N后問(wèn)題 2021年 11月 12日 11 引言 ? 有許多問(wèn)題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時(shí)，往往要使用回溯法。這種方法適用于解一些組合數(shù)相當(dāng)大的問(wèn)題。算法搜索至解空間樹(shù)的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解：如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索。 ? 確定正確的解空間很重要！ 例如：桌子上有 6根火柴棒，要求以這 6根火柴棒為邊搭建 4個(gè)等邊三角形。 ? 例如，對(duì)于有 n個(gè)物品的 0/1背包問(wèn)題，其可能解的表示方式可以有以下兩種： （ 1）可能解由一個(gè)不等長(zhǎng)向量組成，當(dāng)物品 i(1≤i≤n)裝入背包時(shí)，解向量中包含分量 i，否則，解向量中不包含分量 i，當(dāng) n=3時(shí)，其解空間是： { ( ), (1), (2), (3), (1,