大三-算法設(shè)計chap13回溯

回溯法要求在相對問題的輸入規(guī)模按照指數(shù)級增長的數(shù)據(jù)集中，找出一個具有指定特性的元素在圖的所有頂點排列中求一個哈密頓回路求背包中最有價值的物品子集蠻力方法：先生成所有的候選解，然后再找出那個具有需要特性的元素回溯法：每次只構(gòu)造解的一個分量，然后評估這個部分構(gòu)造解。若無法對下一個分量進行合法的選擇，則進行回溯，將部分構(gòu)造解的最后一個分量替換為它的下一個選擇?；厮莘ㄈ绻褑栴}的解組織成一棵樹的話，從根結(jié)點到達某個葉結(jié)點的路徑就可以看作問題的一個解，葉子就是搜索的目標。回溯法就是搜索出所有的葉結(jié)點，然后選擇一個滿足要求的葉結(jié)點?；厮莘梢韵到y(tǒng)地在所有可能的選擇中搜索問題的一個最優(yōu)解。若把做的決策序列用一個向量(x1,x2,…,xn)表示，回溯法就是以深度優(yōu)先的方式逐步確定xi的值，直到找到問題的解。回溯法通過枚舉所有的決策序列保證解的正確性。決策序列的多少，即解的多少極大地影響回溯法的效率?；厮莘ㄋ惴ㄋ枷霝榱双@得問題的解(x1,x2,…,xn)，從x1出發(fā)，逐步擴展部分解(x1,x2,…,xi)通過嘗試解元素xi+1的一個值，測試擴展出的(x1,x2,…,xi+1)是否還是一個部分解若是，繼續(xù)向下搜索若不是，嘗試xi+1的其它取值。若x的所有取值都已試過了，則回溯到xi，嘗試xi的下一個取值。依次類推，直到找到問題的一個解，或沒有解。回溯法的解題步驟1)定義問題的解空間令Si表示解元素xi的取值范圍，則問題的解空間為S1×S2×…×Sn

。通常解空間非常大，因此為了提高回溯法的效率，需要有效地組織解空間.2)組織解空間以便更容易地搜索問題的解，典型的解空間組織方式是一棵樹或一個圖.3)用深度優(yōu)先搜索的方式搜索問題的解，并用剪枝函數(shù)來避免去搜索一個無解的子空間。解空間問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。顯約束：對分量xi的取值進行限定。隱約束：為滿足問題的解而對不同分量之間施加的約束。解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實例的一個解空間。注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可?，搜索方法簡單）。問題舉例8－皇后問題：在一個8×8的棋盤上放8個皇后，且使得每兩個之間都不能互相“攻擊”，即都不出現(xiàn)在同一行、同一列及同一條斜對角線上。解的表示：假定第i個皇后放在第i行，用8－元組(x1,x2,…,x8)表示解，其中xi示放置皇后i的列號。顯示約束:Si=(1,2,3,…8),1i8隱示約束：沒有兩個xi(1i8)可以相同（在不同的列上），且沒有兩個皇后在同一斜對角線上?！痢痢痢痢痢痢痢痢痢痢痢痢痢粒保玻保玻常常矗保玻保玻常矗保保玻常埃担矗叮罚竼栴}舉例子集和數(shù)問題：已知n+1個正整數(shù)：w1,w2,…,wn和M，要求找出wi的和數(shù)等于M的所有子集。解的表示1：用其和數(shù)為M的wi的下標來表示解向量。則可以用k-元組(x1,x2,…,xk)來表示解(x表示下標),1kn。不同的解可以是大小不同的元組。顯示約束：xi{j|j是一個整數(shù)且1jn}.隱示約束：沒有兩個xi是相同的且對應(yīng)的wi的和數(shù)是M；為避免子集重復(fù)，要求xi<xi+1,1in.問題舉例子集和數(shù)問題：已知n+1個正整數(shù)：w1,w2,…,wn和M，要求找出wi的和數(shù)示M的所有子集。解的表示2：用n-元組(x1,x2,…,xn)來表示解,xi{0,1},1in。如果沒有選擇wi，則xi＝0，否則xi＝1。解是大小相同的元組。顯示約束：xi{0，1}.隱示約束：為1的xi對應(yīng)的wi的和數(shù)是M.生成問題狀態(tài)的基本方法擴展結(jié)點(E結(jié)點):一個正在產(chǎn)生兒子的結(jié)點稱為擴展結(jié)點活結(jié)點:一個自身已生成但其兒子還沒有全部生成的節(jié)點稱做活結(jié)點死結(jié)點:一個所有兒子已經(jīng)產(chǎn)生的結(jié)點稱做死結(jié)點深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴展結(jié)點R，一旦產(chǎn)生了它的一個兒子C，就把C當(dāng)做新的擴展結(jié)點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結(jié)點，繼續(xù)生成R的下一個兒子（如果存在）寬度優(yōu)先的問題狀態(tài)生成法：在一個擴展結(jié)點變成死結(jié)點之前，它一直是擴展結(jié)點回溯法回溯法:如果對一個擴展結(jié)點R，一旦產(chǎn)生了它的一個兒子C，就把C當(dāng)做新的擴展結(jié)點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結(jié)點，繼續(xù)生成R的下一個兒子（如果存在）為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來處死那些實際上不可能產(chǎn)生所需解的活結(jié)點，以減少問題的計算量。使用限界函數(shù)的深度優(yōu)先結(jié)點生成方法稱為回溯法.兩種形式的問題的解問題的解是所搜索集合的子集，以達到某種優(yōu)化目標問題的解是所搜索集合中元素的一個排列，以達到某種約束要求回溯法可以很方便地遍歷一個集合的所有子集或所有的排列應(yīng)用舉例應(yīng)用回溯法求解3著色問題；應(yīng)用回溯法求解哈密頓回路問題。子集樹當(dāng)問題是需要求n個元素的子集，以便達到某種優(yōu)化目標時，我們可以把這個解空間組織成一棵子集樹。若Si的大小為k，則有kn個子集。當(dāng)n很大時，解空間將非常巨大?！璖2S1SnS2第1層第2層第n層x1子集樹的回溯法偽碼Backtrack(i)

遞歸描述1ifi>nthenupdate(x)2else3foreacha∈Sido4xi←a5ifC(i)andB(i)then6Backtrack(i+1)約束函數(shù)C(i)和界限函數(shù)B(i)決定(x1,x2,…,xi)是否是一個部分解，這兩個函數(shù)也統(tǒng)稱為剪枝函數(shù)子集樹的回溯法偽碼InterateBacktrack(i)迭代描述1i←12whilei>0do3whileSiisnotexhausteddo//對Si中的元素進行枚舉4xi←nextelementinSi5ifi=nthenUpdate(x)//搜索到葉結(jié)點6elseifC(i)andB(i)theni←i+1//滿足條件繼續(xù)搜索7i←i-1//進行回溯排列樹當(dāng)問題是需要求n個元素的一個排列，則可以將解空間組織成一棵排列樹。建一個含n個元素的數(shù)組A,xi的值是數(shù)組A中下標從1到n的一個元素，并且之前從未出現(xiàn)過。共有n!個排列?！?3n……23n……12n……S1S2S2SnnSniSn1第1層第2層第n層排列樹的回溯法偽碼BacktrackPerm(i)1ifi>nthenupdate(x)2else3forj←itondo4xi

?xj5ifC(i)andB(i)then6BacktrackPerm(i+1)7xi?xj搜索從一個給定的排列(x1,x2,…,xn)開始。假定已經(jīng)搜索到部分解(x1,x2,…,xi-1)，通過嘗試解元素xi的一個值，xi在{xi,xi+1,…,xn}中。為了保證排列中的每個元素不同，通過交換xi?xj來實現(xiàn)。再利用C(i)和B(i)來測試擴展出的解是否還是一個可行的部分解。提高搜索效率搜索能否繼續(xù)，取決于約束函數(shù)C(i)和界限函數(shù)B(i)?？梢岳肅(i)和B(i)來剪除無用的分支。改進搜索性能應(yīng)考慮的問題如何找到約束函數(shù)對于求最大值（最小值）問題，怎樣計算上界（下界），從而利用該信息構(gòu)造界限函數(shù)如何利用約束函數(shù)和界限函數(shù)來剪除無用的分支用約束函數(shù)在擴展結(jié)點處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。N皇后問題在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價于在n×n格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。1234567812345678QQQQQQQQN皇后的解空間從n2個位置中選n個位置，則解空間的大小為令xi表示皇后i的列位置，問題的解向量表示為(x1,x2,…,xn)，因為限制皇后在不同的行，故解空間的大小為nn，解空間可以組織為一棵子集樹進一步限制每個皇后在不同的列，解空間大小為n！,解空間可以組織為一棵排列樹。解向量：(x1,x2,…,xn)解空間：子集樹顯約束：xi=1,2,…,n隱約束：

1)不同列：xixj2)不處于同一正、反對角線：|i-j||xi-xj|Place(k)1forj←1tok-1do2if|xk-xj|==|k-j|or(xk==xj)then3returnfalse;4returntrue;BacktNqueens(t)1ift>nthensum++;2else3fori←1tondo

4xt←i;5if(Place(t))BacktNqueens(t+1);BacktNqueens()x[1]←0k←1whilek>0do

whilex[k]<=n-1dox[k]←x[k]+1

ifPlace(k)=truethen

ifk==nthensum++

elsek←k+1x[k]←0k←k-10-1背包問題

解空間：子集樹，大小為2n

解向量：(x1,x2,…,xn),xi∈{0,1}cw(i)表示部分解(x1,x2,…,xn)的重量

第i-1層結(jié)點取1分支的約束函數(shù)為C(i)=cw(i-1)+wi,若C(i)>W，則停止搜索該分支，否則繼續(xù)搜索只考慮約束函數(shù)的0/1背包問題BtKnapsack(i)

遞歸描述1ifi>nthen//到達葉結(jié)點，則找到一個解2ifcv>bestvthen//比當(dāng)前最好的bestv價值更大3bestv←cv//則更新最好價值4else//沒有搜索到葉結(jié)點5ifC(i)<=Wthen//試探走1分支6cw←cw+w(i)7BtKnapsack(i+1)

8elsecw←cw-w(i)9BtKnapsack(i+1)//對于0分支，無條件回溯，嘗試下一個i約束函數(shù)C(i)=cw+w[i]引入界限函數(shù)的0/1背包問題僅利用約束函數(shù)，搜索效率不高，因此需引進界限函數(shù)

B(i)=cv(i)+r(i)cv(i)表示目前到第i層結(jié)點已經(jīng)裝入背包的物品價值r(i)表示剩余物品的總價值bestv表示目前所得到的最好的價值若B(i)<=bestv，則停止搜索第i層及其下面的層當(dāng)r(i)越小時，B(i)越小，剪掉的分支越多。引入界限函數(shù)的0/1背包問題如何構(gòu)造更小的r(i)?首先將物品以單位重量價值遞減的順序進行排序v1/w1>=v2/w2>=…>=vn/wn考慮第i層，背包的剩余容量為W-cw(i)，用貪心算法把剩余的物品放入背包，直到裝不進背包的物品k為止，即物品k放不進去。則依上式計算是r(i)是最優(yōu)的，不存在比貪心裝載更優(yōu)的方案引入界限函數(shù)的0/1背包問題r(i)1rw←W-cw2b←cv3whilei+1<=nandw[i+1]<=rwdo4rw←rw-w[i+1]5b←b+v[i+1]6i←i+17ifi+1<=nthenb←b+v[i+1]/w[i+1]*rw8returnb結(jié)合約束函數(shù)和界限函數(shù)的背包回溯算法BtKnapsack(i)1ifi>nthen2ifcv>bestvthen3bestv←cv4forj←1tondo5bestx[j]←x[j]6else7ifC(i)<=Wthenx[i]←18cw←cw+w[i];vc←cv+v[i]9BtKnapsack(i+1)10cw←cw-w[i];vc←cv-v[i]11ifB(i)>bestvthenx[i]←012BtKnapsack(i+1)哈密頓回路哈密頓回路:設(shè)G=(V,E)是一個n結(jié)點的連通圖.一個哈密頓回路是一條沿著圖G的n條邊環(huán)行的路徑,它訪問每個結(jié)點一次并且回到它的原始位置.找出一個圖中哈密頓回路的回溯算法.解的表示:(x1,…,xn)表示解,其中,xi是找到的回路中第i個被訪問的結(jié)點.約束:x(1)=1,如果1<k<n,則x(k)可以是不同于x(1),…,x(k-1)且和x(k-1)有邊相連的任一結(jié)點.x(n)只能是必須與x(n-1)和x(1)有邊相連的結(jié)點.12343010206541342422334232434旅行商問題BtTSP(i)1ifi=nthen2ifw[x[n-1],x[n]]<>∞andw[x[n],1]<>∞then3ifcw+w[x[n-1],x[n]]+w[x[n],1]<bestwthen4bestw←cw+w[x[n-1],x[n]]+w[x[n],1]5forj←1tondo6bestx[j]←x[j]7elseforj←itondo8ifw[x[i-1],x[j]]<>∞andcw+w[x[i-1],x[j]]<bestwthen9xi

?xj10cw←cw+w[x[i-1],x[i]];11