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

《《算法設(shè)計與分析》-第五章 回溯法》由會員上傳分享，免費在線閱讀，更多相關(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)致合法解的候選解，從而使求解時間大大縮短。（與蠻干算法相區(qū)別）回溯法以深度優(yōu)先的方式搜索解空間，而分支限界法以廣度優(yōu)先或最小耗費（最大收益）的方式搜索解空間。5.1回溯法的基本思想回溯法（backtracking）是一種系統(tǒng)地搜

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

3、）解空間例：0/1背包問題，S={0,1}，當(dāng)n=3時，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時，有2n種可能的解。5.1回溯法的基本思想（1）解空間例：貨郎擔(dān)(旅行商)問題，S={1,2,…,n}，當(dāng)n=3時，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時，它有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時，它有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)空間樹的動態(tài)搜索可行解和最優(yōu)解:可行解：滿足約束條件的解，解空間中的一個子集最優(yōu)解：使目標(biāo)函數(shù)取極值（極大或極?。┑目尚薪?，一個或少數(shù)幾個例：貨郎擔(dān)問題，有nn種可能解。n!種可行解，只有一個或幾個解是最優(yōu)解。例：背包問題，有2n種可能解，有些是可行解，只有一個或幾個是最優(yōu)解。有些問題，只要可行解，不需要最優(yōu)解，例如八后問題。5.1回溯法的基本思想（3）狀態(tài)空間樹的動態(tài)搜索狀

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

7、基本思想（3）狀態(tài)空間樹的動態(tài)搜索例：回溯法搜索解空間樹時，通常采用兩種策略避免無效搜索。其一，用約束函數(shù)在擴展結(jié)點出剪去不滿足約束的子樹；其二，用限界函數(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---;