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

9.5回溯法本章學(xué)習(xí)的主要內(nèi)容9.5.1回溯法基本思想9.5.2

n皇后問題9.5.3批處理作業(yè)調(diào)度9.5.1回溯法基本思想本節(jié)學(xué)習(xí)的主要內(nèi)容回顧0-1背包問題回溯法思想及搜索子集樹的一般算法旅行售貨員問題用回溯法搜索排列樹的算法框架回顧0-1背包問題問題：給定n種物品和一個(gè)背包，背包容量為c。物品i的重量是wi，其價(jià)值為vi。選擇物品裝入背包時(shí)不能選擇物品i的部分，問如何選擇裝入背包中的物品，使得裝入背包中物品總價(jià)值最大？0-1背包問題的形式化描述給定c>0，wi>0，vi>0，1in，要求找出一個(gè)n元向量

(x1,x2,…xn)，xi{0，1}，使得:

且達(dá)到最大。

1.問題的解空間例如：0-1背包問題，其解空間是長度為n的0-1向量。當(dāng)n=3時(shí)，其解空間是

{(0,0,0)，(0,1,0)，(0,0,1)，(1,0,0)，(0,1,1)，(1,0,1)，(1,1,0)，(1,1,1)}解空間的二叉樹表示CA01B01D01HIJ01NOE01JKF01LM10考慮0-1背包的一個(gè)實(shí)例每個(gè)物品的重量W=[16,15,15]每個(gè)物品的價(jià)值V=[45,25,25]背包容量,C=30重量W=[16,15,15]，價(jià)值V=[45,25,25]，背包容量C=30,SV表示總價(jià)值，r表示背包剩余容量CA01B01D01HIJ01NOE01JKF01LM10r=14,sv=45r=14<w2=15r=14,sv=45r=14<w3=15r=14,sv=45重量W=[16,15,15]，價(jià)值V=[45,25,25]，背包容量C=30,SV表示總價(jià)值，r表示背包剩余容量CA01B01D01HIJ01NOE01JKF01LM10r=14,sv=45r=30,sv=0r=15,sv=25r=0,sv=50重量W=[16,15,15]，價(jià)值V=[45,25,25]，背包容量C=30,SV表示總價(jià)值，r表示背包剩余容量CA01B01D01HIJ01NOE01JKF01LM10r=0,sv=50r=15,sv=25重量W=[16,15,15]，價(jià)值V=[45,25,25]，背包容量C=30,SV表示總價(jià)值，r表示背包剩余容量CA01B01D01HIJ01NOE01JKF01LM10r=0,sv=50r=30,sv=0r=15,sv=25重量W=[16,15,15]，價(jià)值V=[45,25,25]，背包容量C=30,SV表示總價(jià)值，r表示背包剩余容量CA01B01D01HIJ01NOE01JKF01LM10r=0,sv=50r=30,sv=0r=30,sv=0重量W=[16,15,15]，價(jià)值V=[45,25,25]，背包容量C=30,SV表示總價(jià)值，r表示背包剩余容量CA01B01D01HIJ01NOE01JKF01LM10r=0,sv=50返回回溯法的思想從開始結(jié)點(diǎn)(根結(jié)點(diǎn))出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間。開始結(jié)點(diǎn)是一個(gè)活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)就成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果當(dāng)前的擴(kuò)展結(jié)點(diǎn)不能再向縱深移動，則當(dāng)前的擴(kuò)展結(jié)點(diǎn)成為死結(jié)點(diǎn)?；厮莘ǖ目蚣?用回溯法搜索子集樹的一般算法voidBacktrack(intt){if(t>n)Output(x);else{x[t]=1;//進(jìn)入左子樹

if(Constraint(t)&&Bound(t))Backtrack(t+1);x[t]=0;//進(jìn)入右子樹

if(Constraint(t)&&Bound(t))Backtrack(t+1);}}//X[i]表示子集樹的邊上的值,樹根為第1層用回溯法搜索子集樹的一般算法Constraint(t)表示在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處的約束函數(shù)。如果返回true，則表示在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處x[1:t]的取值滿足問題的約束條件。如果返回false，則表示在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處x[1:t]的取值不滿足問題的約束條件。可以剪去相應(yīng)的子樹。用回溯法搜索子集樹的一般算法Bound(t)表示在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處的限界函數(shù)。如果返回true，則表示在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處x[1:t]的取值沒有使目標(biāo)函數(shù)越界。需要調(diào)用Backtrack(t+1)進(jìn)入其子樹進(jìn)一步搜索。如果返回false，則表示在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處x[1:t]的取值使目標(biāo)函數(shù)越界?？梢约羧ハ鄳?yīng)的子樹。返回旅行售貨員例子問題：某售貨員要到若干城市去推銷商品，已知各個(gè)城市之間的路程，要選定一條從駐地出發(fā)，經(jīng)過每個(gè)城市一次，最后回到駐地，要求總的路程最小。1324610203054解空間的樹表示CA24B43DHI3NOEJKF2LM44GPQ32423321111111周游解空間解旅行售貨員問題CA24B43DHI3NOEJKF2LM44GPQ3242332111111130355559周游解空間解旅行售貨員問題CA24B43DHI3NOEJKF2LM44GPQ32423321111111594060>59周游解空間解旅行售貨員問題CA24B43DHI3NOEJKF2LM44GPQ32423321111111596112125周游解空間解旅行售貨員問題CA24B43DHI3NOEJKF2LM44GPQ324233211111112526>25周游解空間解旅行售貨員問題CA24B43DHI3NOEJKF2LM44GPQ32423321111111254141925周游解空間解旅行售貨員問題CA24B43DHI3NOEJKF2LM44GPQ32423321111111252429>25周游解空間解旅行售貨員問題CA24B43DHI3NOEJKF2LM44GPQ3242332111111125返回用貪心策略不能得到旅行售貨員問題的最優(yōu)解1423321281貪心：1->3->4->2->1總開銷12最優(yōu)：1->2->3->4->1總開銷8用回溯法搜索排列樹的算法框架voidBacktrack(intt){if(t>n)Output(x);elsefor(inti=t;i<=n;i+1){Swap(x[t],x[i]);if(Constraint(t)&&Bound(t))Backtrack(t+1);Swap(x[t],x[i]);}}//X[i]表示排列樹的邊上的值(數(shù)字序號),樹根為第1層template<classType>voidSwap(Type&x,Type&y){Typetemp=x;x=y;y=temp;}通過排列問題理解排列樹框架設(shè)R={r1，r2，…，rn}是要進(jìn)行排列的n個(gè)元素，Ri=R-{ri}。集合X中元素的全排列記為Perm(X)。

(ri)Perm(Ri)表示在全排列Perm(Ri)的每一個(gè)排列前加上前綴ri得到的排列。R的全排列遞歸定義如下：當(dāng)n=1時(shí)，Perm(R)=(r1),r1是R中唯一的元素。當(dāng)n>1時(shí)，Perm(R)由(ri)Perm(Ri)(i=1,2,…,n)構(gòu)成template<classType>voidPerm(Typelist[],intk,intm){if(k>m){ for(inti=0;i<=m;i++)cout<<list[i]; cout<<endl; } else{ for(inti=k;i<=m;i++){ Swap(list[k],list[i]); Perm(list,k+1,m);Swap(list[k],list[i]); }}}//完成list中下標(biāo)索引從k到m的元素的排列。12341234k=1,表示集合起始索引m=4,表示集合終止索引集合起始索引為k+1=2m=4,表示集合終止索引listSwap(1,1)1234123412341234k=1,表示集合起始索引m=4,表示集合終止索引集合起始索引為k+1=2m=4,表示集合終止索引Swap(1,1)listSwap(1,2)Swap(1,1)1234123412341234k=1,表示集合起始索引m=4,表示集合終止索引集合起始索引為k+1=2m=4,表示集合終止索引Swap(1,1)listSwap(1,2)Swap(1,1)12342314Swap(1,2)Swap(1,3)1234123412341234k=1,表示集合起始索引m=4,表示集合終止索引集合起始索引為k+1=2m=4,表示集合終止索引Swap(1,1)listSwap(1,2)Swap(1,1)12342314Swap(1,2)Swap(1,3)12342431Swap(1,3)Swap(1,4)用回溯法搜索排列樹的算法框架對于旅行售貨員問題:調(diào)用Backtrack之前，應(yīng)將數(shù)組x初始化為(1,2,…,n)，即x[1]=1,x[2]=2,…,x[n]=n主程序應(yīng)調(diào)用Backtrack(2)回溯法解題步驟定義解空間確定易于搜索的解空間結(jié)構(gòu)以深度優(yōu)先方式搜索解空間，在搜索過程中，用剪枝函數(shù)避免無效搜索。子集樹和排列樹當(dāng)所給的問題是從n個(gè)元素的集合S中找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹稱為子集樹。當(dāng)所給問題是確定n個(gè)元素的滿足某種性質(zhì)的排列時(shí)，相應(yīng)的解空間樹稱為排列樹。0-1背包問題是一棵子集樹旅行售貨員問題是一棵排列樹返回9.5.2n皇后問題問題描述n后問題要求在一個(gè)n*n格的棋盤上放置n個(gè)皇后，使得他們彼此不受攻擊。按照國際象棋的規(guī)則，一個(gè)皇后可攻擊與之處在同一行或同一列或同一斜線上的其他任何棋子。因此，n后問題等價(jià)于要求在一個(gè)n*n格的棋盤上放置n個(gè)皇后，使得任何2個(gè)皇后不能被放在同一行或同一列或同一斜線上。算法設(shè)計(jì)對于n后問題，我們用n元組x[1:n]表示它的解。其中，x[i]表示第i個(gè)皇后放在棋盤的第i行的第x[i]列。由于不允許將任何2個(gè)皇后放在同一列上，所以解向量中的諸x[i]互不相同。在這里，任何兩個(gè)皇后不能放在同一斜線上是問題的隱約束。將n*n格的棋盤看作是一個(gè)二維方陣，其行號從上到下，列號從左到右依次編號為1、2…、n。123123456456若兩個(gè)皇后放置的位置分別為(i,j)和(k,l)，且i-j=k-l或i+j=k+l，則說明這兩個(gè)皇后處于同一斜線上。以上2個(gè)方程分別等價(jià)于i-k=j-l和i-k=l-j。由此可知，只要|i-k|=|j-l|成立，就表明這2個(gè)皇后位于同一條斜線上。據(jù)此我們可以設(shè)計(jì)一個(gè)函數(shù)Place來測試：若將皇后k放在第k行的第x[k]列是否與前面已放置的k-1個(gè)皇后都不在同一列，而且都不在同一斜線上。boolQueen::Place(intk) { for(intj=1;j<k;j++) if(abs(k-j)==abs(x[j]-x[k]))|| (x[j]==x[k])) returnfalse; returntrue; }用回溯法解n后問題時(shí)，可以用一棵完全n叉樹來表示其解空間。定義一個(gè)類Queen。函數(shù)Backtrack是類Queen的成員。遞歸函數(shù)Backtrack(1)實(shí)現(xiàn)對整個(gè)解空間的回溯搜索。Backtrack(t)搜索解空間中第t層子樹。 用可行性約束函數(shù)Place可剪去不滿足行、列和斜線約束的子樹。函數(shù)nQueen負(fù)責(zé)類Queen的私有變量的初始化。sum記錄當(dāng)前已找到的可行方案數(shù)。解n后問題的回溯算法可描述如下：

classQueen{ friendintnQueen(int); private: boolPlace(intk);

voidBackTrack(intt); intn,//皇后個(gè)數(shù) *x;//當(dāng)前解

longsum;//當(dāng)前已找到的可行方案數(shù)

};voidQueen::Backtrack(intt){ if(t>n)sum++; else for(inti=1;i<=n;i++) { x[t]=i; if(Place(t))Backtrack(t+1); }}在函數(shù)Backtrack中，當(dāng)t>n時(shí)，表示算法已搜索至一個(gè)葉結(jié)點(diǎn)，得到一個(gè)新的n皇后互不攻擊放置方案，因此當(dāng)前已找到的可行方案數(shù)sum增1。當(dāng)t<=n時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)Z是解空間中的一個(gè)內(nèi)部結(jié)點(diǎn)。該結(jié)點(diǎn)有x[t]=1,2,…,n共n個(gè)兒子結(jié)點(diǎn)。對當(dāng)前擴(kuò)展結(jié)點(diǎn)Z的每一個(gè)兒子結(jié)點(diǎn)，由函數(shù)Place檢查其可行性，并以深度優(yōu)先的方式遞歸地對可行子樹進(jìn)行搜索，或減去不可行子樹。intnQueen(intn){ QueenX; //初始化X X.n=n;X.sum=0; int*p=newint[n+1];

for(inti=0;i<=n;i++)p[i]=0;

X.x=p;X.Backtrack(1); delete[]p; ReturnX.sum;}313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123313123123123123123123123122123123123132012312331312312312312312312312312212312312313201231233131231231231231231231231221231231231320123123迭代回溯將上述回溯法表示成非遞歸的形式。這樣一來，可省去O(n)的遞歸?？臻g。解n后問題的非遞歸迭代回溯法Backtrack可描述如下.當(dāng)n為３時(shí)，用三叉樹回溯算法遍歷時(shí)無解。當(dāng)n為4時(shí)，用四叉樹回溯算法遍歷時(shí)有2個(gè)可行解。voidQueen::Backtrack(void){ x[1]=0; intk=1; while(k>0) { x[k]+=1; while((x[k]<=n)&&!(Place(k)))x[k]+=1; if(x[k]<=n){ if(k==n)sum++; else{ k++; x[k]=0; }} else k--; }}voidQueen::Backtrack(inti)//遞歸遍歷所有子樹{ if(i>n)sum++;//遍歷到最下端時(shí)，可行解加1 else for(intj=i;j<=n;j++){ Swap(x[i],x[j]); if(Place(i))Backtrack(i+1);//若可行進(jìn)下層

Swap(x[i],x[j]); }}把n叉樹變成排列樹C13A32DHI2NOEJKF1LM33GPQ21312213皇后問題的解空間樹9.5.3批處理作業(yè)調(diào)度問題描述：給定n個(gè)作業(yè)的集合J=(J1,J2,…,Jn)。每一個(gè)作業(yè)Ji都有2項(xiàng)任務(wù)分別在2臺機(jī)器上完成。每一個(gè)作業(yè)必須先由機(jī)器1處理，然后再由機(jī)器2處理。例如：先計(jì)算，再打印作業(yè)Ji需要機(jī)器j的處理時(shí)間為tij，i=1,2,…,n;j=1,2。例子tij機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323對于一個(gè)確定的作業(yè)調(diào)度(即n個(gè)作業(yè)的某個(gè)執(zhí)行順序)，F(xiàn)ij是作業(yè)i從提交到在機(jī)器j上完成處理所需要的時(shí)間。特別地，F(xiàn)i2是作業(yè)i從提交到在機(jī)器2上完成處理所需要的時(shí)間，實(shí)際上，F(xiàn)i2是在這一調(diào)度下作業(yè)Ji從提交到徹底完成所需的時(shí)間。為該作業(yè)調(diào)度下，所有作業(yè)完成時(shí)間和。對于給定的作業(yè)集合J，制訂一個(gè)最佳作業(yè)調(diào)度方案，使f達(dá)到最小。調(diào)度方案為(1,2,3)，作業(yè)調(diào)度完成時(shí)間和計(jì)算過程123456089107213123F12=3F22=6F32=10對于調(diào)度方案(1,2,3)作業(yè)調(diào)度完成時(shí)間和為：f=F12+F22+F32

=3+6+10=19tij機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323調(diào)度方案為(1,3,2)，作業(yè)調(diào)度完成時(shí)間和計(jì)算過程123456089107212331F32=7F22=8對于調(diào)度方案(1,3,2)作業(yè)調(diào)度完成時(shí)間和為：f=F12+F22+F32

=3+7+8=18tij機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323F12=3調(diào)度方案為(2,3,1)，作業(yè)調(diào)度完成時(shí)間和計(jì)算過程123456089107312321F22=4F32=8F12=9對于調(diào)度方案(2,3,1)作業(yè)調(diào)度完成時(shí)間和為：f=F12+F22+F32

=9+4+8=21tij機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323調(diào)度方案為(3,1,2)，作業(yè)調(diào)度完成時(shí)間和計(jì)算過程123456089107232131F32=5F12=6F22=8對于調(diào)度方案(3,1,2)作業(yè)調(diào)度完成時(shí)間和為：f=F12+F22+F32

=6+8+5=19tij機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323批處理作業(yè)調(diào)度的算法設(shè)計(jì)(1)由于我們要從n個(gè)作業(yè)的所有排列中找出具有最小完成時(shí)間和的作業(yè)調(diào)度，所以批處理調(diào)度問題的解空間是一棵排列樹。按照回溯法搜索排列樹的算法框架，初始時(shí)X[1:n]=[1,2,3,…,n]，則相應(yīng)的排列樹為X[1:n]的所有排列構(gòu)成。3個(gè)作業(yè)的解空間樹C13A32DHI2NOEJKF1LM33GPQ2131221批處理作業(yè)調(diào)度的算法設(shè)計(jì)(2)當(dāng)i<n時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)位于排列樹的第i層。此時(shí)，算法需要選擇下一個(gè)要安排的作業(yè)，以深度優(yōu)先的方式遞歸地對相應(yīng)子樹進(jìn)行搜索。f表示當(dāng)前完成作業(yè)的時(shí)間和，bestf表示完成作業(yè)的時(shí)間和的當(dāng)前最優(yōu)值。如果f>=bestf，則以當(dāng)前擴(kuò)展結(jié)點(diǎn)為根的子樹被剪切。批處理作業(yè)調(diào)度的算法設(shè)計(jì)(3)在遞歸函數(shù)Backtrack中，當(dāng)i>n時(shí)，表示算法已搜索至一個(gè)葉子結(jié)點(diǎn)，得到一個(gè)新的調(diào)度方案。此時(shí)需要更新最優(yōu)調(diào)度值bestx和當(dāng)前最佳作業(yè)調(diào)度完成時(shí)間和bestf。f表示當(dāng)前完成作業(yè)的時(shí)間和，bestf表示完成作業(yè)的時(shí)間和的最優(yōu)值。初始:f=0,bestf=tifC13A32DHI2NOEJKF1LM33GPQ2131221tij機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323F12=3,f=3,bestf=tifF22=6,f=9,bestf=tifF32=10,f=19,bestf=19f表示當(dāng)前完成作業(yè)的時(shí)間和，bestf表示完成作業(yè)的時(shí)間和的最優(yōu)值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323F32=10,f=19,bestf=19f表示當(dāng)前完成作業(yè)的時(shí)間和，bestf表示完成作業(yè)的時(shí)間和的最優(yōu)值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323F32=10,f=19,bestf=19F12=3,f=3,bestf=19F32=7,f=10,bestf=19F22=8,f=18,bestf=1818<19f表示當(dāng)前完成作業(yè)的時(shí)間和，bestf表示完成作業(yè)的時(shí)間和的最優(yōu)值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323F22=8,f=18,bestf=18f表示當(dāng)前完成作業(yè)的時(shí)間和，bestf表示完成作業(yè)的時(shí)間和的最優(yōu)值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323F22=8,f=18,bestf=18F22=4,f=4,bestf=18F12=6,f=10,bestf=18F32=10,f=20,bestf=18f>bestff表示當(dāng)前完成作業(yè)的時(shí)間和，bestf表示完成作業(yè)的時(shí)間和的最優(yōu)值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323F22=8,f=18,bestf=18f表示當(dāng)前完成作業(yè)的時(shí)間和，bestf表示完成作業(yè)的時(shí)間和的最優(yōu)值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323F22=8,f=18,bestf=18F22=4,f=4,bestf=18F32=8,f=12,bestf=18F12=9,f=21,bestf=18f>bestff表示當(dāng)前完成作業(yè)的時(shí)間和，bestf表示完成作業(yè)的時(shí)間和的最優(yōu)值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323F22=8,f=18,bestf=18f表示當(dāng)前完成作業(yè)的時(shí)間和，bestf表示完成作業(yè)的時(shí)間和的最優(yōu)值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323F22=8,f=18,bestf=18F32=5,f=5,bestf=18F12=6,f=11,bestf=18F22=9,f=20,bestf=18f>bestff表示當(dāng)前完成作業(yè)的時(shí)間和，bestf表示完成作業(yè)的時(shí)間和的最優(yōu)值。初始:f=0,bestf=0C13A32DHI2NOEJKF1LM33GPQ2131221tij機(jī)器1機(jī)器2作業(yè)121作