資源描述：
《計算機(jī)算法設(shè)計與分析 第5章 回溯法課件.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第5章回溯法1學(xué)習(xí)要點理解回溯法的深度優(yōu)先搜索策略。掌握用回溯法解題的算法框架（1）遞歸回溯最優(yōu)子結(jié)構(gòu)性質(zhì)（2）迭代回溯貪心選擇性質(zhì)（3）子集樹算法框架（4）排列樹算法框架2通過應(yīng)用范例學(xué)習(xí)回溯法的設(shè)計策略。（1）裝載問題；（2）批處理作業(yè)調(diào)度；（3）符號三角形問題（4）n后問題；（5）0-1背包問題；（6）最大團(tuán)問題；（7）圖的m著色問題（8）旅行售貨員問題（9）圓排列問題（10）電路板排列問題（11）連續(xù)郵資問題3有許多問題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法。回溯法的基本做法是搜索，或是一種組
2、織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題?；厮莘ㄔ趩栴}的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結(jié)點是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。回溯法4問題的解空間問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。顯約束：對分量xi的取值限定。隱約束：為滿足問題的解而對不同分量之間施加的約束。解空間：對于問題的一個實例，解向量
3、滿足顯式約束條件的所有多元組，構(gòu)成了該實例的一個解空間。注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可?，搜索方法簡單）。n=3時的0-1背包問題用完全二叉樹表示的解空間5生成問題狀態(tài)的基本方法擴(kuò)展結(jié)點:一個正在產(chǎn)生兒子的結(jié)點稱為擴(kuò)展結(jié)點活結(jié)點:一個自身已生成但其兒子還沒有全部生成的節(jié)點稱做活結(jié)點死結(jié)點:一個所有兒子已經(jīng)產(chǎn)生的結(jié)點稱做死結(jié)點深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴(kuò)展結(jié)點R，一旦產(chǎn)生了它的一個兒子C，就把C當(dāng)做新的擴(kuò)展結(jié)點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴(kuò)展結(jié)點，繼續(xù)生
4、成R的下一個兒子（如果存在）寬度優(yōu)先的問題狀態(tài)生成法：在一個擴(kuò)展結(jié)點變成死結(jié)點之前，它一直是擴(kuò)展結(jié)點回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來處死那些實際上不可能產(chǎn)生所需解的活結(jié)點，以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法6回溯法的基本思想(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的
5、子樹。用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結(jié)點到當(dāng)前擴(kuò)展結(jié)點的路徑。如果解空間樹中從根結(jié)點到葉結(jié)點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間。7遞歸回溯回溯法對解空間作深度優(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(cons
6、traint(t)&&bound(t))backtrack(t+1);}}8迭代回溯采用樹的非遞歸深度優(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--;}}9子集樹與排列樹遍歷子集樹需O(2n)計算時間遍歷
7、排列樹需要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]);}}10裝載問題有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i
8、的重量為wi，且裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。容易證明，如果一個給定裝
