lecture-06-回溯算法-文庫吧
2025-07-09 12:34 本頁面
【正文】 r=30， V=0，活結(jié)點為 A、 C， C為當(dāng)前擴展結(jié)點 擴展 C，先到達 F Cr=Crw2=15， V=V+v2=25，此時活結(jié)點為 A、 C、 F，F(xiàn)成為當(dāng)前擴展結(jié)點 擴展 F，先到達 L Cr=Crw3=0， V=V+v3=50 L是葉結(jié)點，且 5045，皆得到一個可行解 x=(0,1,1)，V=50 L不可擴展，成為死結(jié)點，返回到 F 擴展 C，先到達 F(續(xù) ) 再擴展 F到達 M M是葉結(jié)點，且 2550，不是最優(yōu)解 M不可擴展，成為死結(jié)點，返回到 F F沒有可擴展結(jié)點，成為死結(jié)點，返回到 C 再擴展 C到達 G Cr=30， V=0，活結(jié)點為 A、 C、 G， G為當(dāng)前擴展結(jié)點 擴展 G，先到達 N， N是葉結(jié)點，且 2550，不是最優(yōu)解，又 N不可擴展，返回到 G 再擴展 G到達 O， O是葉結(jié)點，且 050，不是最優(yōu)解，又 O不可擴展，返回到 G G沒有可擴展結(jié)點，成為死結(jié)點，返回到 C C沒有可擴展結(jié)點，成為死結(jié)點，返回到 A A沒有可擴展結(jié)點，成為死結(jié)點，算法結(jié)束，最優(yōu)解 X=(0,1,1)，最優(yōu)值 V=50 例 2 旅行售貨員問題 問題描述： 某售貨員要到若干城市去推銷商品，一直各城市之間的路程，他要選定一條從駐地出發(fā)，經(jīng)過每個城市一遍，最后回到住地的路線，使總的路程最短 該問題是一個 NP完全問題， 有 (n1)!條可選路線 最優(yōu)解 (1,3,2,4,1)，最優(yōu)值 25 回溯法的基本思想 常用剪枝函數(shù)： 用約束函數(shù)在擴展結(jié)點處剪去不滿足約束的子樹； （用于求解所有解時，例如 01背包問題） 用限界函數(shù)剪去得不到最優(yōu)解的子樹。 （用于求解最優(yōu)解時，例如旅行售貨員問題） 回溯法搜索解空間樹時，需要避免無效搜索，提高回溯法的搜索效率，通常采用兩種策略。 回溯法的算法實現(xiàn)： 遞歸回溯 回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實現(xiàn)回溯法。 void backtrack (int t) { if (tn) output(x)。 else for (int i=f(n,t)。i=g(n,t)。i++) { x[t]=h(i)。 if (constraint(t)amp。amp。bound(t)) backtrack(t+1)。 } } 回溯法的算法實現(xiàn)： 迭代回溯 采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。 void iterativeBacktrack () { int t=1。 while (t0) { if (f(n,t)=g(n,t)) for (int i=f(n,t)。i=g(n,t)。i++) { x[t]=h(i)。 if (constraint(t)amp。amp。bound(t)) { if (solution(t)) output(x)。 else t++。} } else t。 } } 回溯法的解空間結(jié)構(gòu) :子集樹與排列樹 子集樹： 從 n個元素的集合 S中找出 S滿足某種性質(zhì)的子集時，相應(yīng)解空間樹稱為子集樹。 通常有 2n個葉結(jié)點，總結(jié)點個數(shù) 2n+1 1。 排列樹： 確定 n個元素滿足某種性質(zhì)的排列時，相應(yīng)的解空間樹稱為排列樹 通常有 n！個結(jié)點。 遍歷子集樹需 O(2n)計算時間 遍歷排列樹需要 O(n!)計算時間 void backtrack (int t) { if (tn) output(x)。 else for (int i=0。i=1。i++) { x[t]=i。 if (legal(t)) backtrack(t+1)。 } } void backtrack (int t) { if (tn) output(x)。 else for (int i=t。i=n。i++) { swap(x[t], x[i])。 if (legal(t)) backtrack(t+1)。 swap(x[t], x[i])。 } } 確定問題的解空間 子集樹問題： 裝載問題、 01背包問題、符號三角形問題、最大團問題 排列樹問題： 批處理作業(yè)調(diào)度、 n后問題、旅行售貨員問題、圓排列問題、電路板排列問題 其他：圖的 m著色問題 找出適當(dāng)?shù)募糁瘮?shù) 約束函數(shù) 限界函數(shù) 以深度優(yōu)先的方式搜索解空間 遞歸回溯 迭代回溯 裝載問題 有一批共 n個集裝箱要裝上 2艘載重量分別為 c1和 c2的輪船，其中集裝箱 i的重量為 wi，且 211ccwnii ????裝載問題要求確定是否有一個合理的裝載方案可
試題試卷相關(guān)推薦
鄂ICP備17016276號-1