《算法設(shè)計(jì)與分析》-第五章 回溯法

《《算法設(shè)計(jì)與分析》-第五章 回溯法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第五章回溯法(backtracking)5.1回溯法的基本思想5.2回溯法的算法框架5.3回溯法的應(yīng)用—n后問題5.4回溯法的應(yīng)用—裝載問題第五章回溯法(Backtracking)回溯法和分支限界法都是通過系統(tǒng)地搜索解空間樹而求得問題解的搜索算法。在系統(tǒng)地檢查解空間的過程中，拋棄那些不可能導(dǎo)致合法解的候選解，從而使求解時(shí)間大大縮短。（與蠻干算法相區(qū)別）回溯法以深度優(yōu)先的方式搜索解空間，而分支限界法以廣度優(yōu)先或最小耗費(fèi)（最大收益）的方式搜索解空間。5.1回溯法的基本思想回溯法（backtracking）是一種系統(tǒng)地搜

2、索問題解的方法。為實(shí)現(xiàn)回溯，首先需要定義一個(gè)解空間（solutionspace），然后以易于搜索的方式組織解空間，最后用深度優(yōu)先的方法搜索解空間，獲得問題的解。5.1回溯法的基本思想回溯法求解的三個(gè)步驟：（1）定義一個(gè)解空間，它包含問題的解（2）用易于搜索的方式組織解空間（3）深度優(yōu)先搜索解空間，獲得問題的解。5.1回溯法的基本思想（1）解空間設(shè)問題的解向量為X=(x1,x2,…,xn)，xi的取值范圍為有窮集Si。把xi的所有可能取值組合，稱為問題的解空間。每一個(gè)組合是問題的一個(gè)可能解。5.1回溯法的基本思想（1

3、）解空間例：0/1背包問題，S={0,1}，當(dāng)n=3時(shí)，0/1背包問題的解空間是：{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}當(dāng)輸入規(guī)模為n時(shí)，有2n種可能的解。5.1回溯法的基本思想（1）解空間例：貨郎擔(dān)(旅行商)問題，S={1,2,…,n}，當(dāng)n=3時(shí)，S={1,2,3}，貨郎擔(dān)問題的解空間是：{(1,1,1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,2,3),┅,(3,3,1),(3,3,2),

4、(3,3,3)}當(dāng)輸入規(guī)模為n時(shí)，它有nn種可能的解?？紤]到約束方程xi≠xj。因此，貨郎擔(dān)問題的解空間壓縮為：{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)}當(dāng)輸入規(guī)模為n時(shí)，它有n!種可能的解。5.1回溯法的基本思想（2）狀態(tài)空間樹：問題解空間的樹形式表示例：n=3,0/1背包問題的狀態(tài)空間樹。ABCDEFGNOLMJKHI1111111000000----子集樹解空間大小:2n5.1回溯法的基本思想（2）狀態(tài)空間樹：問題解空間的樹形式表示例：n=4,旅行商問題

5、的狀態(tài)空間樹。ABCDEFGNOLMJKHI12PQ43334443224223----排列樹解空間大小:n!5.1回溯法的基本思想（3）狀態(tài)空間樹的動(dòng)態(tài)搜索可行解和最優(yōu)解:可行解：滿足約束條件的解，解空間中的一個(gè)子集最優(yōu)解：使目標(biāo)函數(shù)取極值（極大或極小）的可行解，一個(gè)或少數(shù)幾個(gè)例：貨郎擔(dān)問題，有nn種可能解。n!種可行解，只有一個(gè)或幾個(gè)解是最優(yōu)解。例：背包問題，有2n種可能解，有些是可行解，只有一個(gè)或幾個(gè)是最優(yōu)解。有些問題，只要可行解，不需要最優(yōu)解，例如八后問題。5.1回溯法的基本思想（3）狀態(tài)空間樹的動(dòng)態(tài)搜索狀

6、態(tài)空間樹的動(dòng)態(tài)搜索l_結(jié)點(diǎn)（活結(jié)點(diǎn)）：所搜索到的結(jié)點(diǎn)不是葉結(jié)點(diǎn)，且滿足約束條件和目標(biāo)函數(shù)的界，其兒子結(jié)點(diǎn)還未全部搜索完畢，e_結(jié)點(diǎn)（擴(kuò)展結(jié)點(diǎn)）：正在搜索其兒子結(jié)點(diǎn)的結(jié)點(diǎn)，它也是一個(gè)l_結(jié)點(diǎn)；d_結(jié)點(diǎn)（死結(jié)點(diǎn)）：不滿足約束條件、目標(biāo)函數(shù)、或其兒子結(jié)點(diǎn)已全部搜索完畢的結(jié)點(diǎn)、或者葉結(jié)點(diǎn)。以d_結(jié)點(diǎn)作為根的子樹，可以在搜索過程中刪除。5.1回溯法的基本思想（3）狀態(tài)空間樹的動(dòng)態(tài)搜索例：0/1背包問題，n=3,w=[16,15,15],p=[45,25,25],c=30例：旅行商問題，13246305420105.1回溯法的

7、基本思想（3）狀態(tài)空間樹的動(dòng)態(tài)搜索例：回溯法搜索解空間樹時(shí)，通常采用兩種策略避免無效搜索。其一，用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)出剪去不滿足約束的子樹；其二，用限界函數(shù)剪去得不到最優(yōu)解的子樹。這兩類函數(shù)通稱為剪枝函數(shù)。5.2回溯法的算法框架遞歸回溯的一般解法：Voidtraceback(intt){If(t>n)output(x);Elsefor(i=f(n,t);i<=g(n,t);i++){x[t]=h[i];if(constraint(t)&&bound(t))backtrack(t+1);}}5.2回溯法的算法框架迭代

8、回溯的一般解法：VoiditerativeBacktrack(intt){t=1;While(t>0){if(f(n,t)<=g(n,t))for(i=f(n,t);i<=g(n,t);i++){x[t]=h[i];if(constraint(t)&&bound(t)){if(solution(t))output(x);elset++;}}elset---;