復(fù)雜問題解法的提示16.1回溯算法的思想16.2回溯算法的應(yīng)

復(fù)雜問題解法的提示16.1回溯算法的思想16.2回溯算法的應(yīng)用貨箱裝船旅行商問題（TSP問題）Chapter16回溯2022/11/711、尋求問題解的常規(guī)思路首先列出所有候選解然后依次檢查每一個解，直到找到所需的解【可行性前提】：候選解數(shù)量有限，并且能夠通過檢查所有或部分候選解得到所需的解2022/11/72示例1：百元百雞問題使用枚舉法求解：百元買百雞問題公雞每只5元，母雞每只3元，小雞3只1元x+y+z=1005x+3y+z/3=1001<=x<=20，1<=y<=33解法：枚舉所有滿足條件的候選解缺點：運算量大；改進：找到限定規(guī)則2022/11/73對候選解進行系統(tǒng)檢查的常用方法回溯分支定界避免對很大的候選解集合進行檢查，同時能夠保證算法運行結(jié)束可以找到所需要的解；通常能夠用來求解規(guī)模很大的問題。2022/11/74回溯算法思想回溯算法，也叫試探算法。是一種系統(tǒng)的搜索問題的解的方法?！净舅枷搿繌囊粭l路往前走，能進則進，不能進則退回來，換一條路再試。2022/11/75示例2：n皇后問題在n行n列的國際象棋棋盤上，若兩個皇后位于同一行、同一列、同一對角線上，則稱它們?yōu)榛ハ喙??！緉皇后問題】找到這n個皇后的互不攻擊的布局。8x8Chessboard2022/11/76查找時間與問題規(guī)模相關(guān)4x48x82022/11/77用回溯算法解決問題的一般步驟一、定義一個解空間，這個解空間必須至少包含問題的一個解（可能最優(yōu)）；二、用易于搜索的方式組織該解空間。典型的組織方式是圖（如迷宮）或樹（如0/1背包）。三、按深度優(yōu)先法從開始節(jié)點進行搜索。四、利用限界函數(shù)避免移動到不可能產(chǎn)生解的子空間?！净厮菟惴ㄖ匾匦浴繂栴}的解空間通常是在搜索問題的解的過程中動態(tài)產(chǎn)生的。2022/11/78示例：3*3迷宮問題（圖16-1）1、定義解空間：包含從入口到出口的所有路徑；2、組織解空間：用圖的形式給出。從點(1,1)到(3,3)的每一條路徑都定義了3*3迷宮解空間中的一個元素；3、搜索解空間：從開始節(jié)點（1，1）進行深度優(yōu)先搜索。2022/11/79示例：n個對象的0/1背包問題（圖16-2）1、定義解空間：2n個長度為n的0/1向量集合；n=3時，解空間{(0,0,0),(0,1,0),(0,0,1,(1,0,0),(0,1,1),(1,0,1,(1,1,0),(1,1,1))}2、組織解空間：用樹的形式給出。第i層到第i+1層節(jié)點的一條邊上的數(shù)字：向量x中第i個分量的值xi；從根節(jié)點到葉節(jié)點的每一條路徑都定義了解空間中的一個元素。3、搜索解空間：開始節(jié)點為根節(jié)點進行深度優(yōu)先搜索。2022/11/710活節(jié)點、死節(jié)點和E-節(jié)點活節(jié)點：開始節(jié)點是活節(jié)點，也是E-節(jié)點。死節(jié)點E-節(jié)點（ExpansionNode）及回溯從E節(jié)點可移動到一個新的節(jié)點；如果能從當(dāng)前節(jié)點移動到一個新的節(jié)點，則這個新節(jié)點將變成一個活節(jié)點和新的E-節(jié)點；舊的E-節(jié)點仍然是個活節(jié)點。如果不能夠移到一個新節(jié)點，則該E-節(jié)點成為死節(jié)點，只能返回到最近被考察的活節(jié)點（回溯），這個活節(jié)點變成新的E-節(jié)點。當(dāng)已經(jīng)找到答案或者回溯盡了所有的活節(jié)點時，搜索過程結(jié)束。2022/11/711限界函數(shù)通過確定一個新近到達的節(jié)點能否導(dǎo)致一個比當(dāng)前最優(yōu)解還要好的解，可以加速對最優(yōu)解的搜索。如果不能，則移動到該節(jié)點的任何一個子樹都是無意義的，這個節(jié)點可被立即殺死。用來殺死活節(jié)點的策略稱為：限界函數(shù)（BoundingFunction）。2022/11/712解空間圖：3*3迷宮老鼠問題

（P185程序5-13回溯算法）尋找從(1，1)到(3，3)的一條路徑左圖中，從起點到終點的每一條路徑都定義了解空間中的一個元素。搜索結(jié)果：(1,1)-(2,1)-(3,1)-(3,2)-(3,3)2022/11/713解空間樹：0/1背包問題從n個物品中選擇裝入背包的物品約束條件：左圖為n=3時的解空間樹n=3時，0/1背包問題的求解過程w=[20,15,15],p=[40,25,25],c=30剩余容量收益1040當(dāng)前最優(yōu):ABEK1525050最優(yōu)解:ACFL【限界函數(shù)】殺死代表不可行解決方案的節(jié)點。示例：旅行商問題（TSP）旅行商需要找到一條從家里出發(fā)，訪問所有城市后返回原處的旅游環(huán)路。要求：路徑最短或耗費最小HomecityVisitcity2022/11/716旅行商問題的定義頂點：旅行商所要旅行的城市（包括起點）邊的耗費：給出了在兩個城市旅行所需的時間（或花費）旅行：表示當(dāng)旅行商游覽了所有城市再回到出發(fā)點時所走的路線例如：旅行1-3-2-4-1的耗費為25，最?。?022/11/717解空間描述：排列樹一個旅行：由樹中的一條從根到葉的路徑表示。例如：ABCFL表示旅行1-2-3-4-1

樹中葉節(jié)點的數(shù)目（n-1）!2022/11/718n=4時，旅行商問題的求解過程路徑耗費123415912431661324125【限界函數(shù)】如果目前建立的部分的費用大于或等于當(dāng)前最佳路徑的費用，則殺死當(dāng)前節(jié)點。例如：到達I時，部分旅行耗費1,3,4的耗費為26>25，所以，搜索以I為根節(jié)點的子樹毫無意義。2022/11/719回溯算法的解空間形式子集樹：當(dāng)問題解空間樹是n個元素的一個子集時，例如：0/1背包問題子集樹有2n個葉節(jié)點，遍歷耗時Ω(2n)排列樹：當(dāng)問題解空間樹是n個元素的一個排列時，例如：旅行商問題排列樹有n!個葉節(jié)點，遍歷耗時Ω(n!)2022/11/720回溯算法小結(jié)步驟：定義一個解空間，它包含問題的解；用適于搜索的方式組織該空間；用DFS法搜索該空間，并使用限界函數(shù)加速對最優(yōu)解的搜索，避免不必要的移動在搜索期間的任何時刻，僅保留從開始節(jié)點到當(dāng)前E節(jié)點的路徑，因此，回溯算法的空間需求為O（從開始節(jié)點起最長路徑的長度）；解空間的大小是該長度的指數(shù)或階乘！——全部存儲解空間，不夠用。2022/11/7213、回溯算法的應(yīng)用貨箱裝船問題：子集樹旅行商問題：排列樹2022/11/722（1）貨箱裝船問題有兩艘船，n個貨箱。第一艘船的載重量是c1，第二艘船的載重量是c2，Wi是貨箱i的重量且尋求一種將n個貨箱全部裝船的方法例如：當(dāng)n=3，c1=c2=50，w=[10,40,40]；可將貨箱1,2裝到第一艘船上，貨箱3裝到第二艘船上。再如：w=[20,40,40]，結(jié)果如何？解決策略存在一種方法能夠裝載所有n個貨箱時，可以驗證以下的裝船策略可以獲得成功：1)盡可能地將第一艘船裝至它的重量極限2)將剩余貨箱裝到第二艘船為了盡可能地將第一艘船裝滿，需要選擇一個貨箱的子集，它們的總重量盡可能接近c12022/11/724第一種回溯算法思想：尋找即尋找一個重量的子集盡量接近c1。限界函數(shù)：定義表示節(jié)點O的當(dāng)前重量；若cw>c1，則表示以O(shè)為根的子樹不能產(chǎn)生一個可行的解答，避免移動。n=4時，求解過程w=[8，6，2，3]，C1=12cw=8cw=10cw=8cw=11最優(yōu)解x:[1,0,0,1]2022/11/726第一種回溯算法-代碼分析Page498：程序16-1注意：一個可行節(jié)點的右孩子總是可行時間復(fù)雜度：O(2n)遞歸?？臻g：O(n)2022/11/727第二種回溯算法：優(yōu)化如果當(dāng)前節(jié)點的右子樹不可能包含比當(dāng)前最優(yōu)解更好的解時，就不移動到右子樹上！設(shè)bestw為當(dāng)前最優(yōu)解，Z為解空間樹的第i層的一個節(jié)點限界函數(shù)：為剩余貨箱的重量；當(dāng)cw+r<=bestw時，沒有必要去搜索Z的右子樹Page499：程序16-2尋找最優(yōu)子集Page500：程序16-3引入bestx，記錄當(dāng)前找到的最優(yōu)貨箱子集時間復(fù)雜度：O(n2n)降低復(fù)雜度的兩種方法：Page5012022/11/729（2）旅行商問題解空間是排列樹可采用Page8的Perm函數(shù)，產(chǎn)生n個元素表的所有排列作為類AdjacencyWDigraph的成員2022/11/730使用遞歸函數(shù)生成排列（P7例1-3）【例】a,b,c的排列方式有：abc，acb，bac，bca，cab，cba。共6種（n個元素的排列方式共有n！種）令E{e1，…，en}表示n個元素的集合。令Ei為移去元素i后所得的集合，perm(X)表示集合X中元素的排列方式，ei.perm(X)表示在perm(X)中的每個排列方式的前面均加上ei以后所得到的排列方式。例如，若E={a,b,c}，則E1={b,c},perm(E1)={bc,cb}, e1.perm(E1)={abc,acb}2022/11/731使用遞歸函數(shù)生成排列（P7例1-3）【遞歸出口】n=1。當(dāng)只有一個元素時，只可能產(chǎn)生一種排列方式，即perm(E)=e，其中e是E中唯一的元素。當(dāng)n>1時，perm(E)=e1.perm(E1)+e2.perm(E2)+e3.perm(E3)+…en.perm(En)即采用n個perm(X)來定義perm(E)，其中每個X包含n-1個元素?！纠慨?dāng)n=3，并且E={a，b，c}則，perm(E)=a.perm({b,c})+b.perm({a,c})+c.perm({a,b})perm({b,c})=b.perm(c)+c.perm(b)a.perm({b,c})=ab.perm(c)+ac.perm(b)=ab.c+ac.b=(abc,acb)2022/11/732使用遞歸函數(shù)生成排列（P7例1-3）a.perm({b,c})包含兩個排列式：abc和acb，a是它們的前綴，perm({b,c})是它們的后綴同樣，ac.perm()表示前綴ac，后綴為perm()的排列方式。程序1-10輸出所有前綴為list[0:k-1]，后綴為list[k,m]的排列方式。2022/11/733使用遞歸函數(shù)生成排列（程序1-10）template<classT>voidPerm(Tlist[],intk,intm){//Generateallpermutationsoflist[k:m].inti;if(k==m){//輸出一個排列方式for(i=0;i<=m;i++)cout<<list[i];cout<<endl;}

2022/11/734使用遞歸函數(shù)生成排列（程序1-10）else//list[k:m]hasmorethanonepermutation//generatetheserecursivelyfor(i=k;i<=m;i++){Swap(list[k],list[i]);Perm(list,k+1,m);Swap(list[k],list[i]);}}2022/11/735預(yù)處理程序：TSPtemplate<classT>TAdjacencyWDigraph<T>::TSP(intv[]){x=newint[n+1];保存到當(dāng)前節(jié)點的路徑for(inti=1;i<=n;i++)x[i]=i;bestc=NoEdge;bestx=v;保存最優(yōu)解路徑cc=0;tSP(2);搜索x[2:n]的各種排列delete[]x;returnbestc;返回最優(yōu)解耗費}2022/11/736tSP函數(shù)結(jié)構(gòu)與Perm函數(shù)相同。當(dāng)i=n時，處在排列樹的葉節(jié)點的父節(jié)點上，并且需要驗證從x[n-1]到x[n]有一條邊，從x[n]到起點x[1]也有一條邊。若兩邊都存在，則發(fā)現(xiàn)一個新旅行。若發(fā)現(xiàn)的旅行是目前發(fā)現(xiàn)的最優(yōu)旅行，則將旅行和它的耗費分別存入bestx和bestc中。當(dāng)i<n時，檢查當(dāng)前i-1層節(jié)點的孩子節(jié)點，并且僅當(dāng)以下情況出現(xiàn)時，移動到孩子節(jié)點之一：（1）有從x[i-1]到x[i]的一條邊（如果是的話，x[1:i]定義了網(wǎng)絡(luò)中的一條路徑）；（2）路徑x[1:i]的耗費小于當(dāng)前的最優(yōu)解的耗費.變量cc保存目前所構(gòu)造的路徑的耗費。2022/11/737迭代回溯算法：tSPtemplate<classT>a[N][N]表示兩個節(jié)點之間是否有邊voidAdjacencyWDigraph<T>::tSP(inti){if(i==n)位于葉子節(jié)點的父節(jié)點{if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&&(cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc==NoEdge)){找到更優(yōu)的旅行路徑for(intj=1;j<=n;j++)bestx[j]=x[j];bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];}}2022/11/738迭代回溯算法：tSPcont.else{for(intj=i;j<=n;j++)判斷是否能移到子樹x[j]if(a[x[i-1]][x[j]]!=NoEdge&&(cc+a[x[i-1]][x[i]]<bestc||bestc==NoEdge)){類perm的排列法搜索Swap(x[i],x[j]);cc+=a[x[i-1]][x[i]];tSP(i+1);cc-=a[x[i-1]][x[i]];Swap(x[i],x[j]);}}}2022/11/739本章小結(jié)