回溯法和分支限界法學(xué)習(xí)教案課件

會(huì)計(jì)學(xué)1回溯法和分支限界法會(huì)計(jì)學(xué)1回溯法和分支限界法2問(wèn)題的解空間問(wèn)題的解向量：回溯法希望一個(gè)問(wèn)題的解能夠表示成一個(gè)n元式(x1,x2,…,xn)的形式。顯約束：對(duì)分量xi的取值限定。隱約束：為滿(mǎn)足問(wèn)題的解而對(duì)不同分量之間施加的約束。解空間：對(duì)于問(wèn)題的一個(gè)實(shí)例，解向量滿(mǎn)足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。注意：同一個(gè)問(wèn)題可以有多種表示，有些表示方法更簡(jiǎn)單，所需表示的狀態(tài)空間更?。ù鎯?chǔ)量少，搜索方法簡(jiǎn)單）。第1頁(yè)/共20頁(yè)2問(wèn)題的解空間問(wèn)題的解向量：回溯法希望一個(gè)問(wèn)題的解能夠表示成3問(wèn)題的解空間n=3時(shí)的0-1背包問(wèn)題用完全二叉樹(shù)表示的解空間子集樹(shù)旅行商問(wèn)題：某售貨員要到若干城市推銷(xiāo)商品，已知各個(gè)城市之間的路程（或旅費(fèi)）。他要選定一條從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市一遍，最后回到駐地的路線(xiàn)，使總的路線(xiàn)（或旅費(fèi)）最小。排列樹(shù)12343061020第2頁(yè)/共20頁(yè)3問(wèn)題的解空間n=3時(shí)的0-1背包問(wèn)題用完全二叉樹(shù)表示的解空4生成問(wèn)題狀態(tài)的基本方法擴(kuò)展結(jié)點(diǎn):一個(gè)正在產(chǎn)生兒子的結(jié)點(diǎn)稱(chēng)為擴(kuò)展結(jié)點(diǎn)活結(jié)點(diǎn):一個(gè)自身已生成但其兒子還沒(méi)有全部生成的節(jié)點(diǎn)稱(chēng)做活結(jié)點(diǎn)死結(jié)點(diǎn):一個(gè)所有兒子已經(jīng)產(chǎn)生的結(jié)點(diǎn)稱(chēng)做死結(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ù)(boundingfunction)來(lái)處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問(wèn)題的計(jì)算量。具有限界函數(shù)的深度優(yōu)先生成法稱(chēng)為回溯法第3頁(yè)/共20頁(yè)4生成問(wèn)題狀態(tài)的基本方法擴(kuò)展結(jié)點(diǎn):一個(gè)正在產(chǎn)生兒子的結(jié)點(diǎn)稱(chēng)為5回溯法的基本思想(1)針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿(mǎn)足約束的子樹(shù)；用限界函數(shù)剪去得不到最優(yōu)解的子樹(shù)。用回溯法解題的一個(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ì)算空間通常為O(h(n))。而顯式地存儲(chǔ)整個(gè)解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間。第4頁(yè)/共20頁(yè)5回溯法的基本思想(1)針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；常用6遞歸回溯回溯法對(duì)解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實(shí)現(xiàn)回溯法。voidbacktrack(intt){

if(t>n)output(x);

elsefor(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);if(constraint(t)&&bound(t))backtrack(t+1);}}第5頁(yè)/共20頁(yè)6遞歸回溯回溯法對(duì)解空間作深度優(yōu)先搜索，因此，在一般情況下用7迭代回溯采用樹(shù)的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個(gè)非遞歸迭代過(guò)程。voiditerativeBacktrack(){intt=1;

while(t>0){

if(f(n,t)<=g(n,t))for(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);

if(constraint(t)&&bound(t)){

if(solution(t))output(x);

elset++;}}

elset--;}}第6頁(yè)/共20頁(yè)7迭代回溯采用樹(shù)的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一8子集樹(shù)與排列樹(shù)遍歷子集樹(shù)需O(2n)計(jì)算時(shí)間遍歷排列樹(shù)需要O(n!)計(jì)算時(shí)間voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);swap(x[t],x[i]);}}第7頁(yè)/共20頁(yè)8子集樹(shù)與排列樹(shù)遍歷子集樹(shù)需O(2n)計(jì)算時(shí)間遍歷排列樹(shù)需9n后問(wèn)題在n×n格的棋盤(pán)上放置彼此不受攻擊的n個(gè)皇后。按照國(guó)際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線(xiàn)上的棋子。n后問(wèn)題等價(jià)于在n×n格的棋盤(pán)上放置n個(gè)皇后，任何2個(gè)皇后不放在同一行或同一列或同一斜線(xiàn)上。1234567812345678QQQQQQQQ第8頁(yè)/共20頁(yè)9n后問(wèn)題在n×n格的棋盤(pán)上放置彼此不受攻擊的n個(gè)皇后。按照10解向量：(x1,x2,…,xn)顯約束：xi=1,2,…,n隱約束：

1)不同列：xixj2)不處于同一正、反對(duì)角線(xiàn)：|i-j||xi-xj|n后問(wèn)題intn=8;intx[9];intnum=0;//解的個(gè)數(shù)//判斷第k個(gè)皇后能否放在第x[k]列boolPlace(intk){inti=1;while(i<k){if(x[i]==x[k]||(abs(x[i]-x[k])==abs(i-k)))returnfalse;i++;}returntrue;}第9頁(yè)/共20頁(yè)10解向量：(x1,x2,…,xn)n后問(wèn)題intvoidnQueens(intn){x[0]=x[1]=0;intk=1;while(k>0){x[k]+=1;//轉(zhuǎn)到下一行while(x[k]<=n&&Place(k)==false){//如果無(wú)解，最后一個(gè)皇后就會(huì)安排到格子外面去x[k]+=1;}if(x[k]<=n){//第k個(gè)皇后仍被放置在格子內(nèi)，有解if(k==n){num++;cout<<num<<":\t";for(inti=1;i<=n;i++){cout<<x[i]<<"\t";}cout<<endl;}else{k++;x[k]=0;//轉(zhuǎn)到下一行}}else//第k個(gè)皇后已經(jīng)被放置到格子外了，沒(méi)解，回溯k--;//回溯}}int_tmain(intargc,_TCHAR*argv[]){nQueens(n);getchar();return0;}第10頁(yè)/共20頁(yè)voidnQueens(intn)else第10頁(yè)/共2120-1背包問(wèn)題解空間：子集樹(shù)可行性約束函數(shù)：上界函數(shù)：privatestaticdoublebound(inti){//計(jì)算上界

doublecleft=c-cw;//剩余容量

doublebound=cp;//以物品單位重量?jī)r(jià)值遞減序裝入物品

while(i<=n&&w[i]<=cleft){cleft-=w[i];bound+=p[i];i++;}//裝滿(mǎn)背包

if(i<=n)bound+=p[i]/w[i]*cleft;

returnbound;}第11頁(yè)/共20頁(yè)120-1背包問(wèn)題解空間：子集樹(shù)privatestatic13進(jìn)一步改進(jìn)算法的建議選擇合適的搜索順序，可以使得上界函數(shù)更有效的發(fā)揮作用。例如在搜索之前可以將頂點(diǎn)按度從小到大排序。這在某種意義上相當(dāng)于給回溯法加入了啟發(fā)性。定義Si={vi,vi+1,...,vn}，依次求出Sn,Sn-1,...,S1的解。從而得到一個(gè)更精確的上界函數(shù)，若cn+Si<=max則剪枝。同時(shí)注意到：從Si+1到Si，如果找到一個(gè)更大的團(tuán)，那么vi必然屬于找到的團(tuán)，此時(shí)有Si=Si+1+1，否則Si=Si+1。因此只要max的值被更新過(guò)，就可以確定已經(jīng)找到最大值，不必再往下搜索了。第12頁(yè)/共20頁(yè)13進(jìn)一步改進(jìn)算法的建議選擇合適的搜索順序，可以使得上界函數(shù)14回溯法效率分析通過(guò)前面具體實(shí)例的討論容易看出，回溯算法的效率在很大程度上依賴(lài)于以下因素：(1)產(chǎn)生x[k]的時(shí)間；(2)滿(mǎn)足顯約束的x[k]值的個(gè)數(shù)；(3)計(jì)算約束函數(shù)constraint的時(shí)間；(4)計(jì)算上界函數(shù)bound的時(shí)間；(5)滿(mǎn)足約束函數(shù)和上界函數(shù)約束的所有x[k]的個(gè)數(shù)。好的約束函數(shù)能顯著地減少所生成的結(jié)點(diǎn)數(shù)。但這樣的約束函數(shù)往往計(jì)算量較大。因此，在選擇約束函數(shù)時(shí)通常存在生成結(jié)點(diǎn)數(shù)與約束函數(shù)計(jì)算量之間的折衷。第13頁(yè)/共20頁(yè)14回溯法效率分析通過(guò)前面具體實(shí)例的討論容易看出，回溯算法的15重排原理對(duì)于許多問(wèn)題而言，在搜索試探時(shí)選取x[i]的值順序是任意的。在其他條件相當(dāng)?shù)那疤嵯?，讓可取值最少的x[i]優(yōu)先。從圖中關(guān)于同一問(wèn)題的2棵不同解空間樹(shù)，可以體會(huì)到這種策略的潛力。圖(a)中，從第1層剪去1棵子樹(shù)，則從所有應(yīng)當(dāng)考慮的3元組中一次消去12個(gè)3元組。對(duì)于圖(b)，雖然同樣從第1層剪去1棵子樹(shù)，卻只從應(yīng)當(dāng)考慮的3元組中消去8個(gè)3元組。前者的效果明顯比后者好。(a)(b)第14頁(yè)/共20頁(yè)15重排原理對(duì)于許多問(wèn)題而言，在搜索試探時(shí)選取x[i]的值順?lè)种藿绶?/p>

類(lèi)似于回溯法，也是一種在問(wèn)題的解空間樹(shù)T上搜索問(wèn)題解的算法。但在一般情況下，分支限界法與回溯法的求解目標(biāo)不同。回溯法的求解目標(biāo)是找出T中滿(mǎn)足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿(mǎn)足約束條件的一個(gè)解，或是在滿(mǎn)足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。

第15頁(yè)/共20頁(yè)分支限界法

類(lèi)似于回溯法，也是一種在問(wèn)題的解空間樹(shù)T上

所謂“分支”就是采用廣度優(yōu)先的策略，依次搜索E-結(jié)點(diǎn)的所有分支，也就是所有相鄰結(jié)點(diǎn)，拋棄不滿(mǎn)足約束條件的結(jié)點(diǎn)，其余結(jié)點(diǎn)加入活結(jié)點(diǎn)表。然后從表中選擇一個(gè)結(jié)點(diǎn)作為下一個(gè)E-結(jié)點(diǎn)，繼續(xù)搜索。

選擇下一個(gè)E-結(jié)點(diǎn)的方式不同，則會(huì)有幾種不同的分支搜索方式。

1）FIFO搜索

2）LIFO搜索

3）優(yōu)先隊(duì)列式搜索

第16頁(yè)/共20頁(yè)

所謂“分支”就是采用廣度優(yōu)先的策略，依次搜索E-結(jié)點(diǎn)

由于求解目標(biāo)不同，導(dǎo)致分支限界法與回溯法在解空間樹(shù)T上的搜索方式也不相同?；厮莘ㄒ陨疃葍?yōu)先的方式搜索解空間樹(shù)T，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)T。

分支限界法的搜索策略是：在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)（分支），然后再?gòu)漠?dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展對(duì)點(diǎn)。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，以加速搜索的進(jìn)程，在每一活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值（限界），并根據(jù)這些已計(jì)算出的函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹(shù)上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。

第17頁(yè)/共20頁(yè)

由于求解目標(biāo)不同，導(dǎo)致分支限界法與回溯法在解空間樹(shù)T

分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹(shù)。問(wèn)題的解空間樹(shù)是表示問(wèn)題解空間的一棵有序樹(shù)，常見(jiàn)的有子集樹(shù)和排列樹(shù)。在搜索問(wèn)題的解空間樹(shù)時(shí)，分支限界法與回溯法對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)所使用的擴(kuò)展方式不同。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被子加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所求的解或活結(jié)點(diǎn)表為空時(shí)為止。

第18頁(yè)/共20頁(yè)

分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的回溯法和分支限界法的一些區(qū)別

有一些問(wèn)題其實(shí)無(wú)論用回溯法還是分支限界法都可以得到很好的解決，但是另外一些則不然。也許我們需要具體一些的分析——到底何時(shí)使用分支限界而何時(shí)使用回溯呢？

回溯法和分支限界法的一些區(qū)別：

兩種方法對(duì)解空間樹(shù)的搜索方式

存儲(chǔ)結(jié)點(diǎn)的常用數(shù)據(jù)結(jié)構(gòu)

結(jié)點(diǎn)存儲(chǔ)特性常用應(yīng)用

回溯法：

深度優(yōu)先搜索堆棧活結(jié)點(diǎn)的所有可行子結(jié)點(diǎn)

被遍歷后才被從棧中彈出

找出滿(mǎn)足約束條件的所有解

分支限界法：

廣度優(yōu)先或最小消耗優(yōu)先搜索隊(duì)列

優(yōu)先隊(duì)列每個(gè)結(jié)點(diǎn)只有一次成為活結(jié)點(diǎn)的機(jī)會(huì)

找出滿(mǎn)足約束條件的一個(gè)解或特定意義下的最優(yōu)解第19頁(yè)/共20頁(yè)回溯法和分支限界法的一些區(qū)別

有一些問(wèn)題其實(shí)無(wú)論用回溯會(huì)計(jì)學(xué)21回溯法和分支限界法會(huì)計(jì)學(xué)1回溯法和分支限界法22問(wèn)題的解空間問(wèn)題的解向量：回溯法希望一個(gè)問(wèn)題的解能夠表示成一個(gè)n元式(x1,x2,…,xn)的形式。顯約束：對(duì)分量xi的取值限定。隱約束：為滿(mǎn)足問(wèn)題的解而對(duì)不同分量之間施加的約束。解空間：對(duì)于問(wèn)題的一個(gè)實(shí)例，解向量滿(mǎn)足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。注意：同一個(gè)問(wèn)題可以有多種表示，有些表示方法更簡(jiǎn)單，所需表示的狀態(tài)空間更?。ù鎯?chǔ)量少，搜索方法簡(jiǎn)單）。第1頁(yè)/共20頁(yè)2問(wèn)題的解空間問(wèn)題的解向量：回溯法希望一個(gè)問(wèn)題的解能夠表示成23問(wèn)題的解空間n=3時(shí)的0-1背包問(wèn)題用完全二叉樹(shù)表示的解空間子集樹(shù)旅行商問(wèn)題：某售貨員要到若干城市推銷(xiāo)商品，已知各個(gè)城市之間的路程（或旅費(fèi)）。他要選定一條從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市一遍，最后回到駐地的路線(xiàn)，使總的路線(xiàn)（或旅費(fèi)）最小。排列樹(shù)12343061020第2頁(yè)/共20頁(yè)3問(wèn)題的解空間n=3時(shí)的0-1背包問(wèn)題用完全二叉樹(shù)表示的解空24生成問(wèn)題狀態(tài)的基本方法擴(kuò)展結(jié)點(diǎn):一個(gè)正在產(chǎn)生兒子的結(jié)點(diǎn)稱(chēng)為擴(kuò)展結(jié)點(diǎn)活結(jié)點(diǎn):一個(gè)自身已生成但其兒子還沒(méi)有全部生成的節(jié)點(diǎn)稱(chēng)做活結(jié)點(diǎn)死結(jié)點(diǎn):一個(gè)所有兒子已經(jīng)產(chǎn)生的結(jié)點(diǎn)稱(chēng)做死結(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ù)(boundingfunction)來(lái)處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問(wèn)題的計(jì)算量。具有限界函數(shù)的深度優(yōu)先生成法稱(chēng)為回溯法第3頁(yè)/共20頁(yè)4生成問(wèn)題狀態(tài)的基本方法擴(kuò)展結(jié)點(diǎn):一個(gè)正在產(chǎn)生兒子的結(jié)點(diǎn)稱(chēng)為25回溯法的基本思想(1)針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿(mǎn)足約束的子樹(shù)；用限界函數(shù)剪去得不到最優(yōu)解的子樹(shù)。用回溯法解題的一個(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ì)算空間通常為O(h(n))。而顯式地存儲(chǔ)整個(gè)解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間。第4頁(yè)/共20頁(yè)5回溯法的基本思想(1)針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；常用26遞歸回溯回溯法對(duì)解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實(shí)現(xiàn)回溯法。voidbacktrack(intt){

if(t>n)output(x);

elsefor(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);if(constraint(t)&&bound(t))backtrack(t+1);}}第5頁(yè)/共20頁(yè)6遞歸回溯回溯法對(duì)解空間作深度優(yōu)先搜索，因此，在一般情況下用27迭代回溯采用樹(shù)的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個(gè)非遞歸迭代過(guò)程。voiditerativeBacktrack(){intt=1;

while(t>0){

if(f(n,t)<=g(n,t))for(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);

if(constraint(t)&&bound(t)){

if(solution(t))output(x);

elset++;}}

elset--;}}第6頁(yè)/共20頁(yè)7迭代回溯采用樹(shù)的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一28子集樹(shù)與排列樹(shù)遍歷子集樹(shù)需O(2n)計(jì)算時(shí)間遍歷排列樹(shù)需要O(n!)計(jì)算時(shí)間voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);swap(x[t],x[i]);}}第7頁(yè)/共20頁(yè)8子集樹(shù)與排列樹(shù)遍歷子集樹(shù)需O(2n)計(jì)算時(shí)間遍歷排列樹(shù)需29n后問(wèn)題在n×n格的棋盤(pán)上放置彼此不受攻擊的n個(gè)皇后。按照國(guó)際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線(xiàn)上的棋子。n后問(wèn)題等價(jià)于在n×n格的棋盤(pán)上放置n個(gè)皇后，任何2個(gè)皇后不放在同一行或同一列或同一斜線(xiàn)上。1234567812345678QQQQQQQQ第8頁(yè)/共20頁(yè)9n后問(wèn)題在n×n格的棋盤(pán)上放置彼此不受攻擊的n個(gè)皇后。按照30解向量：(x1,x2,…,xn)顯約束：xi=1,2,…,n隱約束：

1)不同列：xixj2)不處于同一正、反對(duì)角線(xiàn)：|i-j||xi-xj|n后問(wèn)題intn=8;intx[9];intnum=0;//解的個(gè)數(shù)//判斷第k個(gè)皇后能否放在第x[k]列boolPlace(intk){inti=1;while(i<k){if(x[i]==x[k]||(abs(x[i]-x[k])==abs(i-k)))returnfalse;i++;}returntrue;}第9頁(yè)/共20頁(yè)10解向量：(x1,x2,…,xn)n后問(wèn)題intvoidnQueens(intn){x[0]=x[1]=0;intk=1;while(k>0){x[k]+=1;//轉(zhuǎn)到下一行while(x[k]<=n&&Place(k)==false){//如果無(wú)解，最后一個(gè)皇后就會(huì)安排到格子外面去x[k]+=1;}if(x[k]<=n){//第k個(gè)皇后仍被放置在格子內(nèi)，有解if(k==n){num++;cout<<num<<":\t";for(inti=1;i<=n;i++){cout<<x[i]<<"\t";}cout<<endl;}else{k++;x[k]=0;//轉(zhuǎn)到下一行}}else//第k個(gè)皇后已經(jīng)被放置到格子外了，沒(méi)解，回溯k--;//回溯}}int_tmain(intargc,_TCHAR*argv[]){nQueens(n);getchar();return0;}第10頁(yè)/共20頁(yè)voidnQueens(intn)else第10頁(yè)/共2320-1背包問(wèn)題解空間：子集樹(shù)可行性約束函數(shù)：上界函數(shù)：privatestaticdoublebound(inti){//計(jì)算上界

doublecleft=c-cw;//剩余容量

doublebound=cp;//以物品單位重量?jī)r(jià)值遞減序裝入物品

while(i<=n&&w[i]<=cleft){cleft-=w[i];bound+=p[i];i++;}//裝滿(mǎn)背包

if(i<=n)bound+=p[i]/w[i]*cleft;

returnbound;}第11頁(yè)/共20頁(yè)120-1背包問(wèn)題解空間：子集樹(shù)privatestatic33進(jìn)一步改進(jìn)算法的建議選擇合適的搜索順序，可以使得上界函數(shù)更有效的發(fā)揮作用。例如在搜索之前可以將頂點(diǎn)按度從小到大排序。這在某種意義上相當(dāng)于給回溯法加入了啟發(fā)性。定義Si={vi,vi+1,...,vn}，依次求出Sn,Sn-1,...,S1的解。從而得到一個(gè)更精確的上界函數(shù)，若cn+Si<=max則剪枝。同時(shí)注意到：從Si+1到Si，如果找到一個(gè)更大的團(tuán)，那么vi必然屬于找到的團(tuán)，此時(shí)有Si=Si+1+1，否則Si=Si+1。因此只要max的值被更新過(guò)，就可以確定已經(jīng)找到最大值，不必再往下搜索了。第12頁(yè)/共20頁(yè)13進(jìn)一步改進(jìn)算法的建議選擇合適的搜索順序，可以使得上界函數(shù)34回溯法效率分析通過(guò)前面具體實(shí)例的討論容易看出，回溯算法的效率在很大程度上依賴(lài)于以下因素：(1)產(chǎn)生x[k]的時(shí)間；(2)滿(mǎn)足顯約束的x[k]值的個(gè)數(shù)；(3)計(jì)算約束函數(shù)constraint的時(shí)間；(4)計(jì)算上界函數(shù)bound的時(shí)間；(5)滿(mǎn)足約束函數(shù)和上界函數(shù)約束的所有x[k]的個(gè)數(shù)。好的約束函數(shù)能顯著地減少所生成的結(jié)點(diǎn)數(shù)。但這樣的約束函數(shù)往往計(jì)算量較大。因此，在選擇約束函數(shù)時(shí)通常存在生成結(jié)點(diǎn)數(shù)與約束函數(shù)計(jì)算量之間的折衷。第13頁(yè)/共20頁(yè)14回溯法效率分析通過(guò)前面具體實(shí)例的討論容易看出，回溯算法的35重排原理對(duì)于許多問(wèn)題而言，在搜索試探時(shí)選取x[i]的值順序是任意的。在其他條件相當(dāng)?shù)那疤嵯?，讓可取值最少的x[i]優(yōu)先。從圖中關(guān)于同一問(wèn)題的2棵不同解空間樹(shù)，可以體會(huì)到這種策略的潛力。圖(a)中，從第1層剪去1棵子樹(shù)，則從所有應(yīng)當(dāng)考慮的3元組中一次消去12個(gè)3元組。對(duì)于圖(b)，雖然同樣從第1層剪去1棵子樹(shù)，卻只從應(yīng)當(dāng)考慮的3元組中消去8個(gè)3元組。前者的效果明顯比后者好。(a)(b)第14頁(yè)/共20頁(yè)15重排原理對(duì)于許多問(wèn)題而言，在搜索試探時(shí)選取x[i]的值順?lè)种藿绶?/p>

類(lèi)似于回溯法，也是一種在問(wèn)題的解空間樹(shù)T上搜索問(wèn)題解的算法。但在一般情況下，分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出T中滿(mǎn)足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿(mǎn)足約束條件的一個(gè)解，或是在滿(mǎn)足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。

第15頁(yè)/共20頁(yè)分支限界法

類(lèi)似于回溯法，也是一種在問(wèn)題的解空間樹(shù)T上

所謂