0027算法筆記——【回溯法】回溯法與裝載問(wèn)題

1、1、回溯法(1)描述:回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法。原理：回溯法在問(wèn)題的解空間樹(shù)中，按 深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包 含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回 溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索 ?；厮莘ǖ幕咀龇ㄊ撬阉?，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的 問(wèn)題。有許多問(wèn)題，當(dāng)需要找出它的解集或者

2、要求回答什么解是滿足 某些約束條件的最佳解時(shí)，往往要使用回溯法。問(wèn)題的解空間問(wèn)題的解向量：回溯法希望一個(gè)問(wèn)題的解能夠表示成一個(gè)n元式 (x1,x2,xn的形式。顯約束：對(duì)分量xi的取值限定。隱約束：為滿足問(wèn)題的解而對(duì)不同分量之間施加的約束。解空間：對(duì)于問(wèn)題的一個(gè)實(shí)例，解向量滿足顯式約束條件的所有 多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。注意：同一個(gè)問(wèn)題可以有多種表示，有些表示方法更簡(jiǎn)單，所需表示的狀態(tài)空間更?。ù鎯?chǔ)量少，搜索方法簡(jiǎn)單）。例 1: n=3各城市之間的路程（旅費(fèi)），他要選定一條從駐地出發(fā)，經(jīng)過(guò)每個(gè)城的0 1背包問(wèn)題的回溯法搜索過(guò)程。市一遍，最后回到駐地的路線，使總的路程（總旅費(fèi)）最小。1

3、0(4)生成問(wèn)題狀態(tài)的基本方法擴(kuò)展結(jié)點(diǎn)：一個(gè)正在產(chǎn)生兒子的結(jié)點(diǎn)稱為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)：一個(gè)自身已生成但其兒子還沒(méi)有全部生成的節(jié)點(diǎn)稱做活結(jié) 點(diǎn)。死結(jié)點(diǎn)：一個(gè)所有兒子已經(jīng)產(chǎn)生的結(jié)點(diǎn)稱做死結(jié)點(diǎn)。深度優(yōu)先的問(wèn)題狀態(tài)生成法：如果對(duì)一個(gè)擴(kuò)展結(jié)點(diǎn)R，一旦產(chǎn)生了 它的一個(gè)兒子C,就把C當(dāng)做新的擴(kuò)展結(jié)點(diǎn)。在完成對(duì)子樹(shù) C (以C 為根的子樹(shù))的窮盡搜索之后，將 R重新變成擴(kuò)展結(jié)點(diǎn)，繼續(xù)生成 R 的下一個(gè)兒子(如果存在)。寬度優(yōu)先的問(wèn)題狀態(tài)生成法：在一個(gè)擴(kuò)展結(jié)點(diǎn)變成死結(jié)點(diǎn)之前，它一直是擴(kuò)展結(jié)點(diǎn)。回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問(wèn)題狀態(tài)，要不 斷地利用限界函數(shù)(bounding function)來(lái)處死那些

4、實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問(wèn)題的計(jì)算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回 溯法。(5)回溯法的基本思想基本思想:用回溯法解題的一個(gè)顯著特征是在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解 空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹(shù)中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度為h(n)，則回溯法所需的計(jì)算空間通常為0（h（n）。而顯式地存儲(chǔ)整個(gè)解空間則需要0(2h(n)或 0(h(n)!)內(nèi)存空間。解題步驟:1）針對(duì)所給問(wèn)題，定義問(wèn)題的 解空間;2）確定易于搜索的解空間結(jié)構(gòu);3）以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用 剪枝函數(shù)避免無(wú)效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪

5、去不滿足約束的子樹(shù)；用限界函數(shù)剪去得不到最優(yōu)解的子樹(shù)。遞歸回溯:回溯法對(duì)解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法 實(shí)現(xiàn)回溯法。cpp view plain copy..9.10.void backtrack ( int t)if (t>n)out put(x);elsefor ( int i=f(n,t);iv=g(n,t);i+) x【t=h(i);if (constraint(t)&&bound(t) backtrack(t+1);/已到葉子結(jié)點(diǎn)，輸出結(jié)果f(n,t) , g(n,t):表示當(dāng)前擴(kuò)展結(jié)點(diǎn)處未搜索過(guò)的子樹(shù)的起始編號(hào)和

6、終止編號(hào)。h(i):表示在當(dāng)前擴(kuò)展結(jié)點(diǎn)處xt的第i個(gè)可選值。迭代回溯:采用樹(shù)的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個(gè)非遞歸迭代過(guò)程。cpp view plain copy1.2.3.void iterativeBacktrack ()int t=1;4.5.6.while (t>0) if (f(n,t)<=g(n,t)(int i=f(n,t);iv=g(n,t);i+) for7.8.if9.10.(constraint(t)&&bound(t) if (solution(t) output(x); else t+;xt=h(i);11.12.else t

7、-;13.14.15.子集樹(shù)與排列樹(shù):子集樹(shù)：當(dāng)所給的問(wèn)題是從n個(gè)元素的集合S中找出滿足某種性質(zhì)25個(gè)葉節(jié)的子集時(shí)，相應(yīng)的解空間稱為 子集樹(shù)。例如，那個(gè)物品的0-1背包問(wèn)題所相應(yīng)的解空間樹(shù)就是一顆子集樹(shù)。這類(lèi)子集問(wèn)題通常有點(diǎn)，其節(jié)點(diǎn)總個(gè)數(shù)為2八(n+1)-1。遍歷子集樹(shù)的任何算法均需要0(2八n)的計(jì)算時(shí)間。..9.void backtrack ( int t)解空間樹(shù)稱為排列樹(shù)。排列樹(shù)通常有n!個(gè)葉子節(jié)點(diǎn)。因此遍歷排列樹(shù)需用回溯法遍歷子集樹(shù)的一般算法可描述如下:cpp view plain copyif (t>n) output(x);elsefor ( i

8、nt i=0;iv=1;i+) xt=i;if (legal(t) backtrack(t+1);排列樹(shù)：當(dāng)所給問(wèn)題是確定n個(gè)元素滿足某種性質(zhì)的排列時(shí)，相應(yīng)的要0(n!)的計(jì)算時(shí)間。用回溯法遍歷排列樹(shù)的一般算法可描述如下:cpp view plain copy..9.10.void backtrack ( int t)if (t>n) output(x);elsefor ( int i=t;iv=n;i+) swap (xt, xi);if (legal(t) backtrack(t+1);swap (xt, xi);2、裝載問(wèn)題問(wèn)題描述：有一批共n個(gè)集裝箱要

9、裝上2艘載重量分別為c1和c2的 輪船，其中集裝箱i的重量為wi，且臺(tái)'是否有一個(gè)合理的裝載方案可將這些集裝箱裝上這，裝載問(wèn)題要求確定2艘輪船。如果有，找出一種裝載方案。例如：當(dāng)n=3,c仁c2=50,且w二10,40,40時(shí)，則可以將集裝箱 1和2裝到第一艘輪船上，而將集裝箱 3裝到第二艘輪船上；如果w二20,40,40，則無(wú)法將這3個(gè)集裝箱都裝上輪船。基本思路：容易證明，如果一個(gè)給定裝載問(wèn)題有解，則采用下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿;(2)將剩余的集裝箱裝上第二艘輪船。將第一艘輪船盡可能裝滿等價(jià)于選取全體集裝箱的一個(gè)子集，使該子集中集裝箱重量之和最接

10、近 C1。由此可知，裝載問(wèn)題等價(jià)于以下特 殊的0-1背包問(wèn)題。ftmax 工 vf. .rr-ls t.工叫M < C/=!心W 0< Z < /P用回溯法設(shè)計(jì)解裝載問(wèn)題的0（2八n）計(jì)算時(shí)間算法。在某些情況下該算法優(yōu)于動(dòng)態(tài)規(guī)劃算法。算法設(shè)計(jì):用回溯法解裝載問(wèn)題時(shí)，用子集樹(shù)表示其解空間顯然是最合適的。用可行性約束函數(shù)可剪去不滿足約束條件工W鍛< ClZ的子樹(shù)。在子 集樹(shù)的第j+1層的結(jié)點(diǎn)z處，用cw記當(dāng)前的裝載重量，即cw=工W曲，則當(dāng)cw>c1時(shí)，以結(jié)點(diǎn)z為根的子樹(shù)中所有結(jié)點(diǎn)都不滿足=1 約束條件，因而該子樹(shù)中的解均為不可行解，故可將該子樹(shù)剪去。（該約束函數(shù)去除

11、不可行解，得到所有可行解）?？梢砸胍粋€(gè)上界函數(shù)，用于剪去不含最優(yōu)解的子樹(shù)，從而改進(jìn)算法在平均情況下的運(yùn)行效率。設(shè)z是解空間樹(shù)第i層上的當(dāng)前擴(kuò)展結(jié)點(diǎn)。cw是當(dāng)前載重量；bestw是當(dāng)前最優(yōu)載重量；r是剩余集裝箱的重量，即r=。定義上界函數(shù)為cw+r。在以z為根的子樹(shù)中任一葉結(jié)點(diǎn)所相應(yīng)的載重量均不超過(guò) cw+r。因此，當(dāng)cw+rv二bestw時(shí)，可將z的 右子樹(shù)剪去。遞歸回溯具體代碼如下:cpp view plain copy11.#include "stdafx.h"2.#include viostream3.using names pace std;4.5.tempi a

12、te < class Type6.class Loading7.8./friend Type MaxLoading(T yp e,T yp e,int,int );9./p rivate:10.public :11.void Backtrack(inti);12.int n,/集裝箱數(shù)13.*x,/當(dāng)前解14.*bestx;/當(dāng)前最優(yōu)解15.Type *w,/集裝箱重量數(shù)組16.c,/第一艘輪船的載重量17.cw,/當(dāng)前載重量18.bestw,/當(dāng)前最優(yōu)載重量19.r;/剩余集裝箱重量20.；21.22.tempi ate < class Type23.voidLoading vT

13、yp e>:Backtrack (int i);24.25.tempi ate vclass Type26.Type MaxLoading(T ype w, Type c,int n,27.28.intmain()29.30.int n=3,m;31.int c=50,c2=50;int bestx);32.33.int w4=0,10,40,40;34.int bestx4;35.36.m=MaxLoading(w, c, n, bestx);37.38.coutvv"輪船的載重量分別為："vvendl;39.coutvv"c(1)="<&

14、lt;c<< ",c(2)="vvc2vvendl;40.41.coutvv"待裝集裝箱重量分別為："vvendl;42.coutvv"w(i)="43.for ( int i=1;iv=n;i+)44.45.coutvvwivv""46.47.coutvvendl;48.49.coutvv"回溯選擇結(jié)果為："vvendl;50.coutvv"m(1)=" vvmvvendl;51.coutvv"x(i)="52.53.for ( int i=

15、1;iv=n;i+)54.55.coutvvbestxivv""56.57.coutvvendl;58.59.int m2=0;60.for ( int j=1;jv=n;j+)61.62.m2=m2+wj*(1-bestxj);63.64.coutvv"m(2)=" vvm2vvendl;65.66.if (m2>c2)67.68.coutvv"因?yàn)閙(2)大于c(2),所以原問(wèn)題無(wú)解！"69.70.return 0;71.72.73.tempi ate v class Type74.void Loading vTyp e&g

16、t;:Backtrack (int i) /搜索第75.wendl;i層結(jié)點(diǎn)76.if (i > n)/到達(dá)葉結(jié)點(diǎn)77.78.if (cw>bestw)79.80.for (int j=1；jv=n;j+)81.82.bestxj=xj;/更新最優(yōu)解83.bestw=cw;84.85.86.return ;87.88.89.r-=wi;90.if (cw + wi <= c)/搜索左子樹(shù)91.92.xi = 1;93.cw += wi;94.Backtrack(i+1);95.cw-=wi;96.97.98.if (cw + r > bestw)99.100.xi =

17、0;/搜索右子樹(shù)101.Backtrack(i + 1);102.103.葉=wi;104.105.106.tempi ate <class Type107.Type MaxLoading(T ype w, Type c,int n,108.109.LoadingvT yp e>X;110./初始化X111.X.x= new int n+1;112.X.w=w;113.X.c=c;114.X.n=n;115.X.bestx=bestx;116.X.bestw=0;117.X.cw=0;118./初始化rJ119.X.r=0;int bestx) /返回最優(yōu)載重量120.121.fo

18、r ( int i=i；iv=n;i+)122.123.X+=wi;124.125.126.X.Backtrack(1);127.128.delete X.x; return X.bestw;129.迭代回溯具體代碼如下:cpp view plain copy1.#include "stdafx.h"2.#include <iostream>3.using names pace std;4.5.tempi ate <class Type6.Type MaxLoading(T ype w , Type c,int n, int bestx);7.8.intm

19、ain()9.10.intn=3,m;11.intc=50,c2=50;12.intw4=0,10,40,40;13.intbestx4;15.14.m=MaxLoading(w, c, n, bestx);16.17.cout<<"輪船的載重量分別為:"<<endl;18.cout<<"c(1)="<<c<< ",c(2)="<<c2<<endl;19.20.cout<<"待裝集裝箱重量分別為:"<<end

20、l;21.cout<<"w(i)="22.for (int i=1;i<=n;i+)23.24.cout<<wi<<25.26.coutwendl;28.cout<<"回溯選擇結(jié)果為：-29.cout<<"m(1)=" <<m<<endl;J30.cout<<"x(i)="27.<<endl;31.32.for ( int i=1;iv=n;i+)33.34.cout<<bestxi<<3

21、5.36.coutwendl;37.38.int m2=0;39.for ( int j=1;jv=n;j+)40.41.m2=m2+wj*(1-bestxj);42.43.coutvv "m(2)=" vvm2vvendl;44.45.if (m2>c2)46.47.cout<<"因?yàn)閙(2)大于c(2),所以原問(wèn)題無(wú)解！" vvendl;48.49.return 0;3.tempi ate < class Type54.Type MaxLoading(T ype w,T ype c,及其相應(yīng)解，初始化根結(jié)點(diǎn)int n, int bestx) /迭代回溯法，返回最優(yōu)載重量55.56.int i=1