算法設計與分析課件_Algotiyhmsch05-回溯法 .ppt

《算法設計與分析課件_Algotiyhmsch05-回溯法 .ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、第5章回溯法計算機算法設計與分析內容提要每一步都非常關鍵，走好每一步！1理解深度優(yōu)先搜索策略2掌握回溯法的算法策略3學習應用范例歸納總結理解回溯法的深度優(yōu)先搜索策略通用算法、萬能算法？1它在問題的解空間樹中，按深度優(yōu)先策略，從根節(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結點時，先判斷該節(jié)點是否包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的搜索，逐層向其祖先節(jié)點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索回溯法—“通用解題法”—“萬能算法”?；厮莘梢韵到y(tǒng)的搜索一個問題的所有解或任一解?；厮莘ㄊ且粋€即帶有系統(tǒng)性又帶有跳躍性的搜索算法?；厮?/p>

2、法回溯法生成問題狀態(tài)的基本方法擴展結點:一個正在產生孩子的結點稱為擴展結點活結點:一個自身已生成但其孩子還沒有全部生成的節(jié)點稱做活結點死結點:一個所有孩子已經產生的結點稱做死結點深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴展結點R，一旦產生了它的一個孩子C，就把C當做新的擴展結點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結點，繼續(xù)生成R的下一個孩子（如果存在）寬度優(yōu)先的問題狀態(tài)生成法：在一個擴展結點變成死結點之前，它一直是擴展結點回溯法：為了避免生成那些不可能產生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)

3、來處死那些實際上不可能產生所需解的活結點，以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法問題的解空間回溯法的基本思想遞歸回溯迭代回溯子集樹與排列樹5.1回溯法的算法框架1問題的解空間5.1回溯算法的基本框架問題的解空間問題的解空間舉例回溯法的解空間為了用回溯法求解一個具有n個輸入的問題，一般情況下，將其可能的解表示為滿足某個約束條件的等長向量X=（x1,x2,…,xn)，其中分量xi（1<=i<=n)的取值范圍是某個有限集合Si={ai1,ai2,…,ain},所以有可能的解向量構成了問題的解空間?；厮莘ǖ慕饪臻g回溯法的解空間的組織回溯法的解

4、空間—0/1背包回溯法的解空間—旅行售貨員問題2回溯法的基本思想5.1回溯算法的基本框架回溯法的基本思想回溯法的基本思想距離—0/1背包旅行售貨員問題某個售貨員要到若干城市去推銷商品，已知各城市之間的路程（或旅費）。他要選定一條從駐地城市出發(fā)，經過每個城市一遍，最后回到駐地的路線，使總的路程（或總旅費）最小?；厮莘ǖ幕舅枷牖厮莘ǖ慕忸}基本步驟(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結構；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產生問題的解空間。在任何時刻，

5、算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內存空間。22回溯法的求解過程回溯法的求解過程3遞歸回溯5.1回溯算法的基本框架遞歸回溯4迭代回溯5.1回溯算法的基本框架迭代回溯5子集樹與排列樹5.1回溯算法的基本框架子集樹：當所給的問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間稱為子集樹。排列樹：當所給的問題是確定n個元素滿足某種性質的排列時，相應的解空間樹成為排列樹?；厮莘ǎ鹤蛹?/p>

6、樹和排列樹子集樹與排列樹遍歷子集樹需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]);}}2回溯法的應用例子裝載問題、作業(yè)

7、調度和0/1背包問題裝載問題有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且裝載問題要求確定：是否有一個合理的裝載方案可將這n個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。33n=3，c1=c2=50w1=[10,40,40]，w2=[20,40,40]，裝載例子有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且容易證明，如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。將第一艘輪船盡可能裝滿等價

8、于選取全體集裝箱的一個子集，使該子集中集裝箱重量之和最接近。由此可知，裝載問題等