回溯法和分支限界法學習教案課件

會計學1回溯法和分支限界法會計學1回溯法和分支限界法2問題的解空間問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。顯約束：對分量xi的取值限定。隱約束：為滿足問題的解而對不同分量之間施加的約束。解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實例的一個解空間。注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可伲阉鞣椒ê唵危?。第1頁/共20頁2問題的解空間問題的解向量：回溯法希望一個問題的解能夠表示成3問題的解空間n=3時的0-1背包問題用完全二叉樹表示的解空間子集樹旅行商問題：某售貨員要到若干城市推銷商品，已知各個城市之間的路程（或旅費）。他要選定一條從駐地出發(fā)，經(jīng)過每個城市一遍，最后回到駐地的路線，使總的路線（或旅費）最小。排列樹12343061020第2頁/共20頁3問題的解空間n=3時的0-1背包問題用完全二叉樹表示的解空4生成問題狀態(tài)的基本方法擴展結(jié)點:一個正在產(chǎn)生兒子的結(jié)點稱為擴展結(jié)點活結(jié)點:一個自身已生成但其兒子還沒有全部生成的節(jié)點稱做活結(jié)點死結(jié)點:一個所有兒子已經(jīng)產(chǎn)生的結(jié)點稱做死結(jié)點深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴展結(jié)點R，一旦產(chǎn)生了它的一個兒子C，就把C當做新的擴展結(jié)點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結(jié)點，繼續(xù)生成R的下一個兒子（如果存在）寬度優(yōu)先的問題狀態(tài)生成法：在一個擴展結(jié)點變成死結(jié)點之前，它一直是擴展結(jié)點回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來處死那些實際上不可能產(chǎn)生所需解的活結(jié)點，以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法第3頁/共20頁4生成問題狀態(tài)的基本方法擴展結(jié)點:一個正在產(chǎn)生兒子的結(jié)點稱為5回溯法的基本思想(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴展結(jié)點處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結(jié)點到當前擴展結(jié)點的路徑。如果解空間樹中從根結(jié)點到葉結(jié)點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間。第4頁/共20頁5回溯法的基本思想(1)針對所給問題，定義問題的解空間；常用6遞歸回溯回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實現(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頁/共20頁6遞歸回溯回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用7迭代回溯采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。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頁/共20頁7迭代回溯采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一8子集樹與排列樹遍歷子集樹需O(2n)計算時間遍歷排列樹需要O(n!)計算時間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頁/共20頁8子集樹與排列樹遍歷子集樹需O(2n)計算時間遍歷排列樹需9n后問題在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價于在n×n格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。1234567812345678QQQQQQQQ第8頁/共20頁9n后問題在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照10解向量：(x1,x2,…,xn)顯約束：xi=1,2,…,n隱約束：

1)不同列：xixj2)不處于同一正、反對角線：|i-j||xi-xj|n后問題intn=8;intx[9];intnum=0;//解的個數(shù)//判斷第k個皇后能否放在第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頁/共20頁10解向量：(x1,x2,…,xn)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){//如果無解，最后一個皇后就會安排到格子外面去x[k]+=1;}if(x[k]<=n){//第k個皇后仍被放置在格子內(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個皇后已經(jīng)被放置到格子外了，沒解，回溯k--;//回溯}}int_tmain(intargc,_TCHAR*argv[]){nQueens(n);getchar();return0;}第10頁/共20頁voidnQueens(intn)else第10頁/共2120-1背包問題解空間：子集樹可行性約束函數(shù)：上界函數(shù)：privatestaticdoublebound(inti){//計算上界

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

doublebound=cp;//以物品單位重量價值遞減序裝入物品

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

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

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

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

第15頁/共20頁分支限界法

類似于回溯法，也是一種在問題的解空間樹T上

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

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

1）FIFO搜索

2）LIFO搜索

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

第16頁/共20頁

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

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

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

第17頁/共20頁

由于求解目標不同，導致分支限界法與回溯法在解空間樹T

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

第18頁/共20頁

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

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

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

兩種方法對解空間樹的搜索方式

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

結(jié)點存儲特性常用應用

回溯法：

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

被遍歷后才被從棧中彈出

找出滿足約束條件的所有解

分支限界法：

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

優(yōu)先隊列每個結(jié)點只有一次成為活結(jié)點的機會

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

有一些問題其實無論用回溯會計學21回溯法和分支限界法會計學1回溯法和分支限界法22問題的解空間問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。顯約束：對分量xi的取值限定。隱約束：為滿足問題的解而對不同分量之間施加的約束。解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實例的一個解空間。注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更小（存儲量少，搜索方法簡單）。第1頁/共20頁2問題的解空間問題的解向量：回溯法希望一個問題的解能夠表示成23問題的解空間n=3時的0-1背包問題用完全二叉樹表示的解空間子集樹旅行商問題：某售貨員要到若干城市推銷商品，已知各個城市之間的路程（或旅費）。他要選定一條從駐地出發(fā)，經(jīng)過每個城市一遍，最后回到駐地的路線，使總的路線（或旅費）最小。排列樹12343061020第2頁/共20頁3問題的解空間n=3時的0-1背包問題用完全二叉樹表示的解空24生成問題狀態(tài)的基本方法擴展結(jié)點:一個正在產(chǎn)生兒子的結(jié)點稱為擴展結(jié)點活結(jié)點:一個自身已生成但其兒子還沒有全部生成的節(jié)點稱做活結(jié)點死結(jié)點:一個所有兒子已經(jīng)產(chǎn)生的結(jié)點稱做死結(jié)點深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴展結(jié)點R，一旦產(chǎn)生了它的一個兒子C，就把C當做新的擴展結(jié)點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結(jié)點，繼續(xù)生成R的下一個兒子（如果存在）寬度優(yōu)先的問題狀態(tài)生成法：在一個擴展結(jié)點變成死結(jié)點之前，它一直是擴展結(jié)點回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來處死那些實際上不可能產(chǎn)生所需解的活結(jié)點，以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法第3頁/共20頁4生成問題狀態(tài)的基本方法擴展結(jié)點:一個正在產(chǎn)生兒子的結(jié)點稱為25回溯法的基本思想(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴展結(jié)點處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結(jié)點到當前擴展結(jié)點的路徑。如果解空間樹中從根結(jié)點到葉結(jié)點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間。第4頁/共20頁5回溯法的基本思想(1)針對所給問題，定義問題的解空間；常用26遞歸回溯回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實現(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頁/共20頁6遞歸回溯回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用27迭代回溯采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。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頁/共20頁7迭代回溯采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一28子集樹與排列樹遍歷子集樹需O(2n)計算時間遍歷排列樹需要O(n!)計算時間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頁/共20頁8子集樹與排列樹遍歷子集樹需O(2n)計算時間遍歷排列樹需29n后問題在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價于在n×n格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。1234567812345678QQQQQQQQ第8頁/共20頁9n后問題在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照30解向量：(x1,x2,…,xn)顯約束：xi=1,2,…,n隱約束：

1)不同列：xixj2)不處于同一正、反對角線：|i-j||xi-xj|n后問題intn=8;intx[9];intnum=0;//解的個數(shù)//判斷第k個皇后能否放在第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頁/共20頁10解向量：(x1,x2,…,xn)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){//如果無解，最后一個皇后就會安排到格子外面去x[k]+=1;}if(x[k]<=n){//第k個皇后仍被放置在格子內(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個皇后已經(jīng)被放置到格子外了，沒解，回溯k--;//回溯}}int_tmain(intargc,_TCHAR*argv[]){nQueens(n);getchar();return0;}第10頁/共20頁voidnQueens(intn)else第10頁/共2320-1背包問題解空間：子集樹可行性約束函數(shù)：上界函數(shù)：privatestaticdoublebound(inti){//計算上界

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

doublebound=cp;//以物品單位重量價值遞減序裝入物品

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

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

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

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

第15頁/共20頁分支限界法

類似于回溯法，也是一種在問題的解空間樹T上

所謂