算法設(shè)計與分析 思政課件 第5、6章 回溯法、分支限界法

第5章回溯法5.1回溯法概述5.2基于子集樹框架的問題求解CONTENTS提綱5.3基于排列樹框架的問題求解1/105一個復(fù)雜問題的解決方案往往是由若干個小的決策（即選擇）步驟組成的決策序列。問題的解可以表示成解向量x=（x0，x1，…，xn-1），其中分量xi對應(yīng)第i步的選擇，xi∈Si（0≤i≤n-1）。x中各個分量xi所有的取值的組合構(gòu)成問題的解向量空間，簡稱為解空間，解空間一般用樹形式來組織，也稱為解空間樹或者狀態(tài)空間樹。5.1.1問題的解空間5.1回溯法概述2/105解空間的一般結(jié)構(gòu)x0=v01A2結(jié)點B1結(jié)點A1x1=v1,0x0=v0,ax0=v0,0x0∈S0……………x1∈S1…葉子結(jié)點根結(jié)點x1=v1,1xn-1∈Sn-1高度為n+1包含問題的解3/1055.1.2什么是回溯法求所有解類型：給定一個約束函數(shù)，需要求所有滿足約束條件的解。例如雞兔同籠問題中，所有雞兔頭數(shù)為a，所有腿數(shù)為b，求所有頭數(shù)為a、腿數(shù)為b的雞兔數(shù)，設(shè)雞兔數(shù)分別為x和y，則約束函數(shù)是x+y=a，2x+4y=b。求最優(yōu)解類型：除了約束條件外還包含目標(biāo)函數(shù)，最后是求使目標(biāo)函數(shù)最大或者最小的最優(yōu)解。例如雞兔同籠問題中，求所有雞兔頭數(shù)為a、所有腿數(shù)為b并且雞最少的解，這就是一個求最優(yōu)解問題，除了前面的約束函數(shù)外還包含目標(biāo)函數(shù)min(x)。問題類型4/105回溯法是在解空間樹中按照深度優(yōu)先搜索方法從根結(jié)點出發(fā)搜索解。x0=a0xn-1=an-1葉子結(jié)點根結(jié)點高度為n+1x1=a15/105幾個概念活結(jié)點：指自身已生成但其孩子結(jié)點沒有全部生成的結(jié)點。擴(kuò)展結(jié)點：指正在產(chǎn)生孩子結(jié)點的結(jié)點。死結(jié)點：指其所有子結(jié)點均已產(chǎn)生的結(jié)點，此時應(yīng)往回移動（回溯）至最近的一個活結(jié)點處?；厮葸^程×s1si…si+1回溯再找其他路徑6/105回溯算法設(shè)計關(guān)鍵點根據(jù)問題的特性確定結(jié)點是如何擴(kuò)展的，不同的問題擴(kuò)展方式是不同的。例如，在有向圖中搜索從頂點s到頂點t的一條路徑，其擴(kuò)展十分簡單，就是從一個頂點找所有相鄰頂點。在解空間中按什么方式搜索解，實際上樹的遍歷主要有先根遍歷和層次遍歷，前者就是深度優(yōu)先搜索（DFS），后者就是廣度優(yōu)先搜索（BFS）?；厮莘ň褪遣捎蒙疃葍?yōu)先搜索解，下一章介紹的分支限界法則是采用廣度優(yōu)先搜索解。解空間通常十分龐大，如何高效地找到問題的解，通常采用一些剪支的方法實現(xiàn)?；厮莘?DFS+剪支7/105剪支：在解空間中搜索時提早終止某些分支的無效搜索，減少搜索的結(jié)點個數(shù)但不影響最終結(jié)果，從而提高了算法的時間性能。剪支策略可行性剪支：在擴(kuò)展結(jié)點處剪去不滿足約束條件的分支。例如，在雞兔同籠問題中，若a=3，b=8為例，兔數(shù)的取值范圍只能是0～2，因為3只或者更多只兔子時腿數(shù)就超過8了，不再滿足約束條件。最優(yōu)性剪支：用限界函數(shù)剪去得不到最優(yōu)解的分支。例如，在雞兔同籠問題中求雞最少的解，若已經(jīng)求出一個可行解的雞數(shù)為3，后面就不必搜索雞數(shù)大于3的結(jié)點。交換搜索順序：在搜索中改變搜索的順序，比如原先是遞減順序，可以改為遞增順序，或者原先是無序，可以改為有序，這樣可能減少搜索的總結(jié)點。8/105針對給定的問題確定其解空間，其中至少包含問題的一個解或者最優(yōu)解。確定結(jié)點的擴(kuò)展規(guī)則。采用深度優(yōu)先搜索方法搜索解空間，并在搜索過程中盡可能采用剪支函數(shù)避免無效搜索?；厮莘ㄇ蠼獾囊话悴襟E9/105

【例5-1】農(nóng)夫（人）過河問題是這樣的，在河?xùn)|岸有一個農(nóng)夫、一只狼、一只雞和一袋谷子，只有當(dāng)農(nóng)夫在現(xiàn)場時，狼不會吃雞，雞也不會吃谷子，否則會出現(xiàn)狼吃雞或者雞吃谷子的沖突。另有一條小船，該船只能由農(nóng)夫操作，且最多只能載下農(nóng)夫和另一樣?xùn)|西。

設(shè)計一種將農(nóng)夫、狼、雞和谷子借助小船運到河西岸的過河方案。10/105解③④⑤⑥⑦②①人、狼、雞、谷雞、谷

人、狼狼、谷人、雞狼、雞

人、谷人、狼、谷雞谷人、狼、雞狼人、雞、谷人、雞、谷狼人、狼、谷

雞雞人、狼、谷人、雞狼、谷人、狼、雞、谷人、狼、雞谷…………從東岸到西岸從西岸到東岸從東岸到西岸從西岸到東岸從東岸到西岸從東岸到西岸從西岸到東岸東岸西岸11/1055.1.3回溯法框架解空間類型子集樹：所給的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集。例如在整數(shù)數(shù)組a中求和為目標(biāo)值target的所有解，每個元素a[i]只有選擇和不選擇兩種方式。排列樹：所給的問題是確定n個元素滿足某種性質(zhì)的排列。例如求全排列問題的解空間就是典型的排列樹。12/1051.解空間為子集樹intx[n]; //x存放解向量，這里作為全局變量voidbacktrack(inti) //求解子集樹的遞歸框架{if(i>n) //搜索到葉子結(jié)點,輸出一個可行解

輸出一個解;else{for(j=下界;j<=上界;j++) //用j表示x[i]的所有可能候選值{x[i]=j; //產(chǎn)生一個可能的解分量

…

//其他操作if(constraint(i,j)&&bound(i,j)) //剪支

backtrack(i+1); //滿足條件,繼續(xù)下一層

回溯x[i];

…

}}}13/105

【例5-2】有一個含n個整數(shù)的數(shù)組a，所有元素均不相同，設(shè)計一個算法求其所有子集（冪集）。

例如，a={1，2，3}，所有子集是{}，{3}，{2}，{2，3}，{1}，{1，3}，{1，2}，{1，2，3}（輸出順序無關(guān)）。14/10501010101010101第0層第1層第2層第3層（葉子結(jié)點層）{1,2,3}{1,2}{1,3}{1}{2,3}{2}{3}{}解解向量為x，x[i]=1表示選取a[i]，x[i]=0表示不選取a[i]。15/105vector<int>x; //解向量,全局變量voiddisp(vector<int>&a) //輸出一個解{printf("{");for(inti=0;i<x.size();i++)if(x[i]==1)printf("%d",a[i]);printf("}");}16/105voiddfs(vector<int>&a,inti) //遞歸回溯算法{if(i>=a.size()) //到達(dá)一個葉子結(jié)點

disp(a);else //沒有到達(dá)葉子結(jié)點{x[i]=1;

dfs(a,i+1); //選擇a[i]x[i]=0;

dfs(a,i+1); //不選擇a[i]}}voidsubsets(vector<int>&a) //求a的冪集{intn=a.size();x.resize(n); //初始化x的長度為n

dfs(a,0);}既是結(jié)點層次，也是遍歷a的下標(biāo)17/105

【例5-3】設(shè)計一個算法在1，2，3，4，5（順序不能變）任意兩個數(shù)字之間插入'+'或者'-'運算符，使得表達(dá)式的計算結(jié)果為5，并輸出所有可能的表達(dá)式。18/105解用數(shù)組a[0..N-1]（N=5）存放1～5的整數(shù)，用字符數(shù)組x存放插入的運算符（解向量），其中x[i]表示在a[i]之前插入的運算符，x[i]只能取值'+'或者'-'（兩選一）。a[0] a[1] a[2] a[3] a[4]x[1] x[2] x[3] x[4]sum=a[0]x[1]a[1] x[2]

a[2] x[4]

a[3] x[4]

a[4]sum=a[0]，i從1到419/105+-+24-+3-+i=155-sum=1sum155+-7-3+-+455-9-1+-1-9+-+4-+355-111+-3-7+-+455-5-5+--3-13i=2i=3i=4i=520/105voiddfs(vector<int>&a,intsum,vector<char>&x,inti){if(i==N) //到達(dá)一個葉子結(jié)點(可能解){ if(sum==5) //找到一個可行解 {printf("%d",a[0]); //輸出一個解 for(intj=1;j<N;j++) { printf("%c",x[j]);printf("%d",a[j]);} printf("=5\n"); }}else{ x[i]='+'; //位置i插入'+' sum+=a[i]; //計算結(jié)果

dfs(a,sum,x,i+1); //繼續(xù)搜索 sum-=a[i]; //回溯 x[i]='-'; //位置i插入'-' sum-=a[i]; //計算結(jié)果

dfs(a,sum,x,i+1); //繼續(xù)搜索 sum+=a[i]; //回溯 }}21/105voidsolve(vector<int>&a) //求解算法{ vector<char>x(a.size()); //定義解向量

dfs(a,a[0],x,1);}22/1052.解空間為排列樹

【例5-4】有一個含n個整數(shù)的數(shù)組a，所有元素均不相同，求其所有元素的全排列。

例如，a={1，2，3}，得到結(jié)果是（1，2，3）、（1，3，2）、（2，3，1）、（2，1，3）、（3，1，2）、（3，2，1）。23/105解用數(shù)組a存放初始數(shù)組a的一個排列，采用遞歸法求解。設(shè)f(a，n，i)表示求a[i..n-1]（共n-i個元素）的全排列，為大問題，f(a，n，i+1)表示求a[i+1..n-1]（共n-i-1個元素）的全排列，為小問題。a0

a1…ai

f(a，n，i)：大問題f(a，n，i+1)：小問題ai+1…an-1ai位置取ai～an-1中每個元素，再組合f(a，n，i+1)得到f(a，n，i)ai： ai與ai交換，f(a，n，i+1)

以ai開頭的a[i..n-1]的全排列ai+1：ai與ai+1交換，f(a，n，i+1)

以ai+1開頭的a[i..n-1]的全排列…an-1：ai與an-1交換，f(a，n，i+1)

以an-1開頭的a[i..n-1]的全排列24/105求a的全排列的遞歸模型f(a，n，i)a0

a1…ai

f(a，n，i)：大問題f(a，n，i+1)：小問題ai+1…an-1ai位置取ai～an-1中每個元素，再組合f(a，n，i+1)得到f(a，n，i)f(a，n，i)

輸出產(chǎn)生的解

當(dāng)i=n-1時f(a，n，i)

對于j=i～n-1：

其他 a[i]與a[j]交換位置;

f(a，n，i+1);

將a[i]與a[j]交換位置（回溯）25/105a={1,2,3}a={1,2,3}a={1,2,3}a={1,3,2}a[1]

a[1]a[1]

a[2]輸出123輸出132a={2,1,3}a={2,1,3}a={2,3,1}a[1]

a[1]a[1]

a[2]輸出213輸出231a[0]

a[0]a[0]

a[1]a={3,2,1}a={3,2,1}a={3,1,2}a[1]

a[1]a[1]

a[2]輸出321輸出312a[0]

a[2]求a={1，2，3}全排列26/1053{1,2,3}2{1,2,3}{1,3,2}{1,3,2}{1,2,3}{1,2,3}3321{2,1,3}{2,3,1}{2,3,1}{2,1,3}{2,1,3}3312{3,2,1}{3,1,2}{3,1,2}{3,2,1}{3,2,1}11221第0層第1層第2層第3層（葉子結(jié)點）標(biāo)準(zhǔn)解空間27/105voiddfs(vector<int>&a,inti) //遞歸算法{intn=a.size();if(i>=n-1) //遞歸出口disp(a);else{for(intj=i;j<n;j++){ swap(a[i],a[j]); //交換a[i]與a[j]

dfs(a,i+1); swap(a[i],a[j]); //交換a[i]與a[j]：恢復(fù)}}}voidperm(vector<int>&a) //求a的全排列{

dfs(a,0);}28/105intx[n]; //x存放解向量，并初始化voidbacktrack(inti) //求解排列樹的遞歸框架{if(i>n) //搜索到葉子結(jié)點,輸出一個可行解

輸出結(jié)果;else{for(j=i;j<=n;j++) //用j枚舉x[i]所有可能候選值{ …

//第i層的結(jié)點選擇x[j]的操作

swap(x[i],x[j]);

//通過交換來實現(xiàn) if(constraint(i,j)&&bound(i,j))

backtrack(i+1); //滿足約束條件和限界函數(shù)，進(jìn)入下一層swap(x[i],x[j]);

//恢復(fù)狀態(tài):回溯

…

//第i層的結(jié)點選擇x[j]的恢復(fù)操作}}}排列樹算法基本框架29/1055.1.4回溯法算法時間分析解空間樹共有n+1層（根結(jié)點為第0層，葉子結(jié)點為第n層）。第1層有m0個結(jié)點，每個結(jié)點有m1個子結(jié)點。第2層有m0m1個結(jié)點，同理，第3層有m0m1m2個結(jié)點，依此類推，第n層有m0m1…mn-1個結(jié)點。則采用回溯法求所有解的算法的執(zhí)行時間為

T(n)=m0+m0m1+m0m1m2+…+m0m1m2…mn-1。例如，在子集樹中有m0=m1=…=mn-1=c，對應(yīng)算法的時間復(fù)雜度為O(cn)，在排列樹中有m0=n，m1=n-1，…，mn-1=1，對應(yīng)算法的時間復(fù)雜度為O(n!)。30/1055.2基于子集樹框架的問題求解5.2.1子集和問題給定n個不同的正整數(shù)集合a=（a0，a1，…，an-1）和一個正整數(shù)t，要求找出a的子集s，使該子集中所有元素的和為t。例如，當(dāng)n=4時，a=（3，1，5，2），t=8，則滿足要求的子集s為（3，5）和（1，5，2）。31/105解與求冪集問題一樣，該問題的解空間是一棵子集樹（因為每個整數(shù)要么選擇要么不選擇）。并且是求滿足約束函數(shù)的所有解。32/1051）無剪支a=（3，1，5，2），t=8010100101010101010101010101011086631117552000011996444108853333結(jié)點層次i=0i=1i=2i=3i=433/105voiddfs(intcs,vector<int>&x,inti) //遞歸算法{if(i>=n) //到達(dá)一個葉子結(jié)點{if(cs==t) //找到一個滿足條件的解,輸出

disp(x);}else //沒有到達(dá)葉子結(jié)點{ x[i]=1; //選取整數(shù)a[i]

dfs(cs+a[i],x,i+1); x[i]=0; //不選取整數(shù)a[i]

dfs(cs,x,i+1);}}voidsubs1() //求解子集和問題{ vector<int>x(n); //定義解向量

dfs(0,x,0); //i從0開始}34/1052）左剪支a=（3，1，5，2），t=8當(dāng)搜索到第i（0≤i<n）層結(jié)點時，cs表示當(dāng)前已經(jīng)選取的整數(shù)和（其中不包含a[i]），判斷選擇a[i]是否合適：若cs+a[i]>t，不必繼續(xù)該路徑，終止搜索，也就是左剪支。若cs+a[i]≤t，沿著該路徑繼續(xù)下去可能會找到解，不能終止。簡單地說，僅僅擴(kuò)展?jié)M足cs+a[i]≤t的左孩子結(jié)點。0101001010101010101010101011086631117552000096444108853333結(jié)點層次i=0i=1i=2i=3i=4cs=435/105voiddfs(intcs,vector<int>&x,inti) //遞歸算法{ if(i>=n) //找到一個葉子結(jié)點 { if(cs==t) //找到一個滿足條件的解,輸出

disp(x); } else //沒有到達(dá)葉子結(jié)點 { if(cs+a[i]<=t) //左剪支 { x[i]=1; //選取整數(shù)a[i]

dfs(cs+a[i],x,i+1); } x[i]=0; //不選取整數(shù)a[i]

dfs(cs,x,i+1); }}voidsubs2() //求解子集和問題{ vector<int>x(n); //定義解向量

dfs(0,x,0); //i從0開始}36/1053）右剪支進(jìn)一步考慮是否擴(kuò)展右孩子結(jié)點。當(dāng)搜索到第i（0≤i<n）層的某個結(jié)點時，用rs表示余下的整數(shù)和，即rs=a[i]+…+a[n-1]（其中包含a[i]）。如果不選擇a[i]，此時剩余的所有整數(shù)和為rs=rs-a[i]（a[i+1]+…+a[n-1]），若cs+rs<t成立，說明即便選擇所有剩余整數(shù)其和都不可能達(dá)到t。右剪支就是僅僅擴(kuò)展?jié)M足cs+rs≥t的右孩子結(jié)點a=（3，1，5，2），t=801010010101010110,118,06,06,21,21,70,70,89,24,24,710,08,08,23,23,73,8rs=8,rs=rs-1=70+rs=7<t37/105voiddfs(intcs,intrs,vector<int>&x,inti) //遞歸算法{//cs為考慮整數(shù)a[i]時選取的整數(shù)和，rs為剩余整數(shù)和 if(i>=n) //找到一個葉子結(jié)點 { if(cs==t) //找到一個滿足條件的解,輸出

disp(x); } else //沒有到達(dá)葉子結(jié)點 { rs-=a[i]; //求剩余的整數(shù)和 if(cs+a[i]<=t) //左剪支 { x[i]=1; //選取第i個整數(shù)a[i]

dfs(cs+a[i],rs,x,i+1); } if(cs+rs>=t) //右剪支 { x[i]=0; //不選取第i個整數(shù)a[i]

dfs(cs,rs,x,i+1); } rs+=a[i]; //恢復(fù)剩余整數(shù)和(回溯) }}38/105盡管通過剪支提高了算法的性能，但究竟剪去了多少結(jié)點與具體的實例數(shù)據(jù)相關(guān)。上述算法最壞情況下算法的時間復(fù)雜度仍然為O(2n)。算法分析39/1055.2.2簡單裝載問題有n個集裝箱要裝上一艘載重量為t的輪船，其中集裝箱i（0≤i≤n-1）的重量為wi。不考慮集裝箱的體積限制，現(xiàn)要選出重量和小于等于t并且盡可能重的若干集裝箱裝上輪船。例如，n=5，t=10，w={5，2，6，4，3}時，其最佳裝載方案有兩種即（1，1，0，0，1）和（0，0，1，1，0），對應(yīng)集裝箱重量和達(dá)到最大值t。40/105解intn=5,t=10; //一個測試實例intw[]={5,2,6,4,3}; //各集裝箱重量,不用下標(biāo)0的元素vector<int>bestx; //存放最優(yōu)解向量intbestw=0; //存放最優(yōu)解的總重量，初始化為041/105voiddfs(intcw,intrw,vector<int>&x,inti) //遞歸算法{if(i>=n) //找到一個葉子結(jié)點{if(cw>bestw) //找到一個滿足條件的更優(yōu)解{ bestw=cw; //保存更優(yōu)解

bestx=x;}}else //沒有到達(dá)葉子結(jié)點{rw-=w[i]; //求剩余集裝箱的重量和if(cw+w[i]<=t) //左孩子結(jié)點剪支{ x[i]=1; //選取集裝箱i cw+=w[i]; //累計當(dāng)前所選集裝箱的重量和

dfs(cw,rw,x,i+1); cw-=w[i]; //恢復(fù)所選集裝箱的重量和(回溯)}if(cw+rw>bestw) //右孩子結(jié)點剪支{ x[i]=0; //不選擇集裝箱i

dfs(cw,rw,x,i+1);}rw+=w[i]; //恢復(fù)剩余集裝箱的重量和(回溯)}}42/105voidloading() //求解簡單裝載問題{bestx.resize(n);vector<int>x(n);intrw=0;for(inti=0;i<n;i++)rw+=w[i];

dfs(0,rw,x,0);}

該算法的解空間樹中有2n+1-1個結(jié)點，所以最壞情況下算法的時間復(fù)雜度為O(2n)。43/1055.2.30/1背包問題有n個編號為0～n-1的物品，重量為w={w0，w1，…，wn-1}，價值為v={v0，v1，…，vn-1}，給定一個容量為W的背包。從這些物品中選取全部或者部分物品裝入該背包中，每個物品要么選中要么不選中，即物品不能被分割，找到選中物品不僅能夠放到背包中而且價值最大的方案（最大價值）。W=6結(jié)果為8物品編號重量w價值v05413422331144/105解1）存儲結(jié)構(gòu)設(shè)計structGoods

//物品結(jié)構(gòu)體類型{intno; //物品的編號 intw; //物品的重量 intv; //物品的價值 Goods(intno1,intw1,intv1) //構(gòu)造函數(shù) { no=no1; w=w1; v=v1; } booloperator<(constGoods&s)const //用于按v/w遞減排序 { return(double)v/w>(double)s.v/s.w; } };解向量x=（x0，x1，…，xn-1），xi=1表示選擇物品i，xi=0表示不選擇物品i，最優(yōu)解向量用bestx表示，最大價值用bestv表示（初始為0）。45/1052）左剪支左剪支與子集和問題的類似。當(dāng)搜索到第i（0≤i<n）層的某個結(jié)點時，cw表示當(dāng)前選擇的物品重量和（其中不包含w[i]）。檢查當(dāng)前物品被選中后總重量是否超過W，若超過則剪支，即僅僅擴(kuò)展?jié)M足cw+w[i]≤W的左孩子結(jié)點。46/1053）右剪支采用限界函數(shù)（上界函數(shù)）。將所有物品g按單位重量價值遞減排序。例如前面表排序后的結(jié)果如下，序號i發(fā)生了改變，后面改為按i而不是物品編號no的順序搜索。序號i物品編號no重量w價值vv/w02231.511341.32311130540.847/105第i層結(jié)點：cw表示當(dāng)前選擇的物品重量和（不含w[i]），cv表示當(dāng)前選擇的物品價值和（不含v[i]）。此時背包剩余容量為rw=W-cw，如果按背包容量連續(xù)選擇物品i及其后面的物品，直到裝滿，其價值一定是最大的（因為物品按v/w遞減排序），最大價值為r(i)：第i層第i+1層第k-1層第k層cv，cw試探：物品i～k-1可以整個裝入，物品k只能部分裝入48/105第i層結(jié)點：如果不選擇物品i時，此時背包剩余容量為rw=W-cw。余下重量的物品的最大價值r(i+1)：x[i]=0第i層第i+1層…第k-1層第k層cvr(i+1)49/105doublebound(intcw,intcv,inti) //計算第i層結(jié)點的上界函數(shù)值{ intrw=W-cw; //背包的剩余容量 doubleb=cv; //表示物品價值的上界值 intj=i; while(j<n&&g[j].w<=rw) { rw-=g[j].w; //選擇物品j b+=g[j].v; //累計價值 j++; } if(j<n) //最后一個物品只能部分裝入 b+=(double)g[j].v/g[j].w*rw; returnb;}限界函數(shù)不選擇物品i時這條路徑走下去能夠選擇物品的最大價值為bound(cw,cv,i+1)。對于第i層結(jié)點實參為i+1剪支：僅僅擴(kuò)展bound(cw,cv,i+1)>bestv的右孩子結(jié)點。50/105序號i物品編號no重量w價值vv/w02231.511341.32311130540.8右剪支實例0,06,85,72,36,8,65,7,7.811,122,3,6.40,0,6.6(cw,cv)(cw,cv,ub)bestv=851/105voiddfs(intcw,intcv,vector<int>&x,inti) //回溯算法{if(i>=n) //找到一個葉子結(jié)點 { if(cw<=W&&cv>bestv) //找到一個滿足條件的更優(yōu)解,保存它 { bestv=cv; bestx=x; } } else //沒有到達(dá)葉子結(jié)點 { if(cw+g[i].w<=W) //左剪支 { x[i]=1; //選取物品i

dfs(cw+g[i].w,cv+g[i].v,x,i+1); } doubleb=bound(cw,cv,i+1); //計算上界時從物品i+1開始 if(b>bestv) //右剪支 { x[i]=0; //不選取物品i

dfs(cw,cv,x,i+1); } }}【算法分析】最壞情況下算法的時間復(fù)雜度為O(2n)。52/1055.2.4n皇后問題在n×n（n≥4）的方格棋盤上放置n個皇后，并且每個皇后不同行、不同列、不同左右對角線（否則稱為有沖突）。要求給出n個皇后全部解。53/105解解空間是一棵子集樹（每個皇后在1～n列中找到一個適合的列號，即n選一），并且要求所有解。采用整數(shù)數(shù)組q[N]存放n皇后問題的求解結(jié)果，因為每行只能放一個皇后，q[i]（1≤i≤n）的值表示第i個皇后所在的列號214365654321q[1..6]={2，4，6，1，3，5}54/105若在(i，j)位置上放第i個的皇后，是否與已放好的i-1個皇后(k，q[k])有沖突呢？如果(i，j)位置與前面某個皇后同列，則有q[k]==j成立。如果(i，j)位置與前面某個皇后同對角線，則恰好構(gòu)成一個等腰直角三角形，即有|q[k]-j|==|i-k|成立。q[k]-j(i，j)k-i(k，q[k])j-q[k]i-k(i，j)(k，q[k]（a）對角線1（b）對角線2歸納起來只要(i，j)位置滿足以下條件，則存在沖突，否則不沖突：(q[k]==j)||(abs(q[k]-j)==abs(i-k))

1≤k≤i-1沖突判斷55/105boolplace(inti,intj) //測試(i,j)位置能否放置皇后{ if(i==1)returntrue; //第一個皇后總是可以放置 intk=1; while(k<i) //k=1～i-1是已放置了皇后的行 { if((q[k]==j)||(abs(q[k]-j)==abs(i-k))) returnfalse; k++; } returntrue;}沖突條件：

(q[k]==j)||(abs(q[k]-j)==abs(i-k))1≤k≤i-156/105求解皇后問題所有解的遞歸模型queen(i，n)≡n個皇后放置完畢，輸出一個解

若i>nqueen(i，n)≡在第i行找到一個合適的位置(i，j)，

放置一個皇后; 其他 queen(i+1，n);57/105intq[MAXN]; //存放各皇后所在的列號,為全局變量intcnt=0; //累計解個數(shù)voidqueen11(intn,inti) //回溯算法{ if(i>n) disp(n); //所有皇后放置結(jié)束 else { for(intj=1;j<=n;j++) //在第i行上試探每一個列j { if(place(i,j)) //在第i行上找到一個合適位置(i,j) { q[i]=j;

queen11(n,i+1); q[i]=0; //回溯 } } }}voidqueen1(intn) //遞歸法求解n皇后問題{

queen11(n,1);}最壞情況下算法時間復(fù)雜度為O(nn)。58/105程序驗證59/1055.2.5任務(wù)分配問題問題描述：有n（n≥1）個任務(wù)需要分配給n個人執(zhí)行，每個任務(wù)只能分配給一個人，每個人只能執(zhí)行一個任務(wù)。第i個人執(zhí)行第j個任務(wù)的成本是c[i][j]（0≤i，j≤n-1）。求出總成本最小的一種分配方案。人員任務(wù)0任務(wù)1任務(wù)2任務(wù)309278164372581837694最小成本=1360/105解n個人和n個任務(wù)編號均用0～n-1表示。所謂一種分配方案就是由第i個人執(zhí)行第j個任務(wù)，也就是說每個人從n個任務(wù)中選擇一個任務(wù)，即n選一，所以本問題的解空間樹看成是一棵子集樹。求總成本最小的解（最優(yōu)解是最小值），屬于求最優(yōu)解類型。61/105used[j]=0xi=j表示人員i安排任務(wù)j第i層第i+1層第n層(葉子結(jié)點)…解空間中根結(jié)點層次i為0，當(dāng)搜索到第i層每個結(jié)點時，表示為第i個人分配一個沒有分配的任務(wù)，即選擇滿足used[j]=0（0≤j≤n-1）的任務(wù)j。62/105vector<int>bestx; //最優(yōu)解向量intbestc=INF; //最優(yōu)解的成本,初始值為∞boolused[MAXN]; //used[j]表示任務(wù)j是否已經(jīng)分配voiddfs(vector<int>&x,intcost,inti) //為第i個人員分配任務(wù){(diào) if(i>=n) //到達(dá)葉子結(jié)點 { if(cost<bestc) //比較求最優(yōu)解 { bestc=cost;bestx=x;} } else //沒有到達(dá)葉子結(jié)點 { for(intj=0;j<n;j++) //為人員i試探分配任務(wù) { if(used[j]==0) //若任務(wù)j還沒有分配 { x[i]=j;

//將任務(wù)j分配給人員i

used[j]=true;

//表示任務(wù)j已經(jīng)分配

cost+=c[i][j];

//累計成本

dfs(x,cost,i+1); //繼續(xù)為人員i+1分配任務(wù)

used[j]=false;

//used[j]回溯

x[i]=0;

//x[i]回溯

cost-=c[i][j];

//cost回溯 } } }}63/105程序驗證人員任務(wù)0任務(wù)1任務(wù)2任務(wù)309278164372581837694sum為dfs遞歸調(diào)用的次數(shù)64/105問題是求最小值，所以設(shè)計下界函數(shù)。第i層：此時部分解向量P=（x0，x1，…，xi），那么后面如何分配使得該路徑（一條從根到葉子結(jié)點的路徑對應(yīng)一個分配方案）的cost盡可能小呢？如果后面編號為i+1～n-1的每一個都分配一個最小成本的任務(wù)，其累計成本為剪

支costxi=j表示人員i安排任務(wù)j第i層第i+1層第n層(葉子結(jié)點)minsum…65/105剪支：僅僅擴(kuò)展bound(x,cost,i+1)<bestc的孩子結(jié)點。costxi=j表示人員i安排任務(wù)j第i層第i+1層第n層(葉子結(jié)點)minsum…bound(x,cost,i+1)=cost+minsumintbound(intcost,inti) //求下界算法{ intminsum=0; for(inti1=i;i1<n;i1++) //求c[i..n-1]行中最小元素和 { intminc=INF; //置為∞ for(intj1=0;j1<n;j1++) if(used[j1]==false&&c[i1][j1]<minc) minc=c[i1][j1]; minsum+=minc; } returncost+minsum;}66/105voiddfs(vector<int>&x,intcost,inti) //為第i個人員分配任務(wù){(diào) if(i>=n) //到達(dá)葉子結(jié)點 { if(cost<bestc) //比較求最優(yōu)解 { bestc=cost;bestx=x;} } else //沒有到達(dá)葉子結(jié)點 { for(intj=0;j<n;j++) //為人員i試探任務(wù)j { if(used[j]==0) //若任務(wù)j還沒有分配 { used[j]=true; x[i]=j; //任務(wù)j分配給人員i cost+=c[i][j]; if(bound(cost,i+1)<bestc) //剪支(考慮c[i+1..n-1]的行中最小成本)

dfs(x,cost,i+1); //繼續(xù)為人員i+1分配任務(wù) used[j]=false; //回溯 x[i]=0; cost-=c[i][j]; } } }}67/105程序驗證人員任務(wù)0任務(wù)1任務(wù)2任務(wù)309278164372581837694sum為dfs遞歸調(diào)用的次數(shù)68/1055.2.6出棧序列有一個含n個不同元素的進(jìn)棧序列a，求通過一個棧得到的所有合法的出棧序列。例如a={1，2，3}時，產(chǎn)生的5個合法的出棧序列是{3，2，1}，{2，3，1}，{2，1，3}，{1，3，2}，{1，2，3}。69/105解設(shè)計一個棧st，用i遍歷a的元素（初始時i=0），解向量為x=（x0，x1，…，xn-1），每個解向量對應(yīng)一個合法的出棧序列，j表示產(chǎn)生的出棧序列中的元素個數(shù)。狀態(tài)是由（a，st，x）確定的，由a和x可以確定st的狀態(tài)，所以可以簡化為用（a，x）表示狀態(tài)，a的狀態(tài)可以用其遍歷變量i表示，x的狀態(tài)可以用j表示，這樣實際狀態(tài)用（i，j）表示tmp出棧，即xj=tmpai進(jìn)棧a={ai,…,an-1}tmp┆棧stx={x0,…,xj-1}a={ai+1,…,an-1}aitmp┆x={x0,…,xj-1}a={ai,…,an-1}┆x={x0,…,xj-1,tmp}70/105intsum=0; //累計出棧序列的個數(shù)vector<int>a={1,2,3}; //進(jìn)棧序列intn=a.size(); //進(jìn)棧序列的元素個數(shù)stack<int>st;voiddisp(vector<int>&x) //輸出一個解{ printf("出棧序列%2d:",++sum); for(inti=0;i<n;i++) printf("%d",x[i]); printf("\n");}voidsolve() //求a的所有合法的出棧序列{ vector<int>x(n);

dfs(x,0,0); //i,j均從0開始}狀態(tài)（i，j）71/105voiddfs(vector<int>&x,inti,intj) //遞歸算法{ if(i==n&&j==n) //輸出一種可能的方案

disp(x); else { if(i<n) //剪支:i<n時a[i]進(jìn)棧 { st.push(a[i]); //a[i]進(jìn)棧

dfs(x,i+1,j); st.pop(); //回溯:出棧 } if(!st.empty()) //剪支:棧不空時出棧tmp { inttmp=st.top();st.pop(); //出棧tmp x[j]=tmp; //將tmp添加到x中 j++; //j增加1

dfs(x,i,j); j--; //回溯:j減少1 st.push(tmp); //回溯:x進(jìn)棧以恢復(fù)環(huán)境 } }}72/105程序驗證a={1,2,3,4};73/1055.2.7圖的m著色給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。如果有一種著色法使G中每條邊的兩個頂點著不同顏色，則稱這個圖是m可著色的。圖的m著色問題是對于給定圖G和m種顏色，找出所有不同的著色法。74/105解含n個頂點的無向連通圖G，頂點編號是0～n-1.采用vector<int>數(shù)組的鄰接表A存儲，其中A[i]向量為頂點i的所有相鄰頂點。m種顏色的編號為0～m-1。題目就是為每個頂點i選擇m種顏色中的一種（m選一），使得任意兩個相鄰頂點的著色不同，所以解空間樹看成是一棵子集樹，并且求解個數(shù)，屬于求所有解類型。0213A[0..3]={{1,2,3},{0},{0,3},{0,2}}75/105設(shè)計解向量為x=（x0，x1，…，xn-1），其中xi表示頂點i的著色（0≤xi≤m-1），初始時置x的所有元素為-1表示所有頂點均沒有著色，用cnt累計解個數(shù)（初始為0）。頂點i：所有可能的著色j為0到m-1中的一種，如果頂點i的所有相鄰頂點的顏色均不等于j，說明頂點i著色j是合適的，只要有一個相鄰頂點的顏色等于j，則頂點i著色j是不合適的，需要回溯。76/105intcnt; //全局變量，累計解個數(shù)intx[MAXN]; //全局變量，x[i]表示頂點i的著色booljudge(inti,intj) //判斷頂點i是否可以著上顏色j{ for(intk=0;k<A[i].size();k++) { if(x[A[i][k]]==j) //存在相同顏色的頂點 returnfalse; } returntrue;}021377/105voiddfs(intm,inti) //遞歸回溯算法{ if(i>=n) //達(dá)到一個葉子結(jié)點 cnt++; else { for(intj=0;j<m;j++) { x[i]=j; //置頂點i為顏色j if(judge(i,j)) //若頂點i可以著上顏色j

dfs(m,i+1); x[i]=-1; //回溯 } }}78/105intColors(intm) //求圖的m著色問題{ cnt=0; memset(x,0xff,sizeof(x)); //所以元素初始化為-1

dfs(m,0); //從頂點0開始搜索 returncnt;}【算法分析】該算法中每個頂點試探編號為0～m-1著色，共n個頂點，對應(yīng)解空間樹是一棵m叉樹（子集樹），所有算法的最壞時間復(fù)雜度為O(mn)。79/1055.2.7實戰(zhàn)—救援問題（HDU1242）問題描述：A被抓進(jìn)了監(jiān)獄，監(jiān)獄被描述為一個N×M（N，M≤200）個方格的網(wǎng)格，監(jiān)獄里有圍墻、道路和守衛(wèi)。A的朋友們想要救他（可能有多個朋友），只要有一個朋友找到A（就是到達(dá)A所在的位置）那么A將被救了。在找A的過程中只能向上、向下、向左和向右移動，若遇到有守衛(wèi)的方格時必須殺死守衛(wèi)才能進(jìn)入該方格。假設(shè)每次向上、向下、向右、向左移動需要一個單位時間，而殺死一個守衛(wèi)也需要一個單位時間。你需要幫助A的朋友們計算救援A的最短時間。輸入格式：第一行包含兩個整數(shù)，分別代表N和M。然后是N行，每行有M個字符，其中'#'代表墻，'.'代表道路，'a'代表A，'r'代表A的朋友，'x'代表守衛(wèi)。處理到文件末尾。輸出格式：對于每個測試用例，輸出一個表示所需最短時間的整數(shù)。如果這樣的整數(shù)不存在，輸出一行包含"PoorANGELhastostayintheprisonallhislife"的字符串。80/105輸入樣例：78#.#####.#.a#..r.#..#x.....#..#.##...##...#..............輸出樣例：13'#'代表墻，'.'代表道路，'a'代表A，'r'代表A的朋友，'x'代表守衛(wèi)。81/105解與迷宮問題類似，看成無向圖搜索。A只有一個人，而他的朋友可能有多個，所以從A出發(fā)搜他的最近的朋友。len表示當(dāng)前路徑的長度，bestlen表示最優(yōu)解即最短路徑長度（初始置為∞），每次找到一個朋友（對應(yīng)解空間的葉子結(jié)點）時將最短路徑長度保存在bestlen中。路徑搜索時遇到道路'.'走一步路徑長度len增加1，遇到守衛(wèi)'x'時除了走一步還需要殺死守衛(wèi)，所以路徑長度len增加2。解空間搜索完畢，若bestlen為∞，說明沒有找到任何朋友，按題目要求輸出一個字符串，否則說明最少找到一個朋友，輸出bestlen即可。82/105#include<iostream>#include<cstring>usingnamespacestd;#defineINF0x3f3f3f3f#defineMAXN202intdx[]={0,0,1,-1}; //水平方向偏移量intdy[]={1,-1,0,0}; //垂直方向偏移量chargrid[MAXN][MAXN]; //存放網(wǎng)格intvisited[MAXN][MAXN]; //訪問標(biāo)記數(shù)組intn,m;intbestlen;83/105voiddfs(intx,inty,intlen){ if(grid[x][y]=='r') //找到朋友

bestlen=min(bestlen,len); //求最短路徑長度 else { for(intdi=0;di<4;di++) //枚舉四個方位 { intnx=x+dx[di];intny=y+dy[di]; if(nx<0||nx>=n||ny<0||ny>=m) //(nx,ny)超界時跳過 continue; if(visited[nx][ny]==1) //(nx,ny)已訪問時跳過 continue; if(grid[x][y]=='#') //(nx,ny)為墻時跳過 continue; if(grid[nx][ny]=='x') //(nx,ny)為守衛(wèi)的情況 { visited[nx][ny]=1; //標(biāo)記(nx,ny)已經(jīng)訪問

dfs(nx,ny,len+2); //走一步+殺死守衛(wèi) visited[nx][ny]=0; //路徑回溯 } else //(nx,ny)為道路的情況 { visited[nx][ny]=1;

dfs(nx,ny,len+1); //走一步 visited[nx][ny]=0; } }}}84/105intmain(){ intsx,sy; //標(biāo)記A的位置 while(cin>>n>>m) { for(inti=0;i<n;i++) //輸入矩陣 { for(intj=0;j<m;j++) { cin>>grid[i][j]; if(grid[i][j]=='a') { sx=i;sy=j;} } }

bestlen=INF; memset(visited,0,sizeof(visited));

dfs(sx,sy,0); if(bestlen==INF) //bestlen為INF說明沒找到路徑 cout<<"PoorANGELhastostayintheprisonallhislife."<<endl; else cout<<bestlen<<endl; } return0;}85/1055.3.1任務(wù)分配問題問題描述：有n（n≥1）個任務(wù)需要分配給n個人執(zhí)行，每個任務(wù)只能分配給一個人，每個人只能執(zhí)行一個任務(wù)。第i個人執(zhí)行第j個任務(wù)的成本是c[i][j]（0≤i，j≤n-1）。求出總成本最小的一種分配方案。人員任務(wù)0任務(wù)1任務(wù)2任務(wù)3092781643725818376945.3基于排列樹框架的問題求解86/105解n個人和n個任務(wù)編號均用0～n-1表示。每個合適的分配方案x一定是0～n-1的一個排列，可以求出0～n-1的全排列，每個排列作為一個分配方案，求出其成本，比較找到一個最小成本bestc即可。87/105cost這里swap(x[i],x[j])即xi=xj表示人員i安排任務(wù)xj第i層第i+1層第n層(葉子結(jié)點)minsum…剪支：僅僅擴(kuò)展bound(x,cost,i+1)<bestc的孩子結(jié)點。intbound(vector<int>&x,intcost,inti) //求下界算法{ intminsum=0; for(inti1=i;i1<n;i1++) //求c[i..n-1]行中未分配的最小成本和 { intminc=INF; for(intj1=0;j1<n;j1++) if(used[x[j1]]==false&&c[i1][x[j1]]<minc) minc=c[i1][x[j1]]; minsum+=minc; } returncost+minsum;}88/105intn=4; //一個測試實例intc[MAXN][MAXN]={{9,2,7,8},{6,4,3,7},{5,8,1,8},{7,6,9,4}};vector<int>bestx; //最優(yōu)解向量intbestc=INF; //最優(yōu)解的成本,，初始置為∞boolused[MAXN]; //used[j]表示任務(wù)j是否已經(jīng)分配人員89/105voiddfs(vector<int>&x,intcost,inti) //遞歸回溯（排列樹）算法{ if(i>=n) //到達(dá)葉子結(jié)點 { if(cost<bestc) //比較求最優(yōu)解 { bestc=cost;bestx=x;} } else //沒有到達(dá)葉子結(jié)點 { for(intj=i;j<n;j++) //為人員i試探任務(wù)x[j] { if(used[x[j]])continue; //若任務(wù)x[j]已經(jīng)分配，則跳過

swap(x[i],x[j]);

//為人員i分配任務(wù)x[j]

used[x[i]]=true;

cost+=c[i][x[i]]; if(bound(x,cost,i+1)<bestc) //剪支

dfs(x,cost,i+1); //繼續(xù)為人員i+1分配任務(wù)

cost-=c[i][x[i]];

//cost回溯

used[x[i]]=false;

//used回溯

swap(x[i],x[j]); } }}90/105voidalloction() //基于排列樹的遞歸回溯算法{ memset(used,false,sizeof(used)); vector<int>x; //當(dāng)前解向量 for(inti=0;i<n;i++) //將x[0..n-1]分別設(shè)置為0到n-1值 x.push_back(i); intcost=0; //當(dāng)前解的成本

dfs(x,cost,0); //從人員1開始}【算法分析】

解空間是一棵排列樹，所以最壞的時間復(fù)雜度為O(n!)。91/1055.3.2貨郎擔(dān)問題（TSP）假設(shè)有一個貨郎擔(dān)要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市，要求路徑長度最短的路徑。89736858602135875路徑1：0→1→2→3→0：28路徑2：0→1→3→2→0：29路徑3：0→2→1→3→0：26路徑4：0→2→3→1→0：23路徑5：0→3→2→1→0：59路徑6：0→3→1→2→0：5992/10