【正文】 搜索也一定可以解決 。一般情況下，回溯法的求解目標是找出 T中滿足約束條件的所有解的方案，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使用某一目標函數(shù)值達到極大或極小的解，即在某種意義下的最優(yōu)解。 i=k。 返回首頁 下一頁 4） 結(jié)點 D變?yōu)?E結(jié)點，葉結(jié)點 H超過容量，葉結(jié)點 I的裝載為 40入堆， bestw仍為 40；此時堆中 C上界為 80為優(yōu)先隊列首。 2）堆結(jié)點首先應該包括結(jié)點優(yōu)先級信息：結(jié)點的所在分支的裝載上界 uweight；堆中無法體現(xiàn)結(jié)點的層次信息（ level），只能存儲在結(jié)點中； AddLiveNode用于把 bbnode類型的活節(jié)點加到子樹中 ， 并把HeapNode類型的活節(jié)點插入最大堆 。 {print(“The first ship loading”, bestw ，“ chose：” )。然后從表中選擇一個節(jié)點作為下一個 E節(jié)點。若有的話，找出該方法 FIFO限界搜索算法 優(yōu)先隊列式分支限界法 上一頁 } 1）結(jié)點擴展方式：無論那種分支限界法，都需要有一張活結(jié)點表。 FIFO限界搜索過程為： 上一頁 search（ T） //為找出最小成本答案結(jié)點檢索 T。 把每一段最小的代價相加 ， 可以得到一個非常簡單的下界 ， 其路徑長度為 2+4+5+3=14。 廣度優(yōu)先搜索算法，一般需存儲產(chǎn)生的所有結(jié)點，占用的存儲空間要比深度優(yōu)先搜索大得多，因此，程序設(shè)計中，必須考慮溢出和節(jié)省內(nèi)存空間的問題。 僅就對限界剪支的效率而言 ， 優(yōu)先隊列的分支限界法顯然要更充分一些 。 一般說來，動態(tài)規(guī)劃算法在時間效率上的優(yōu)勢是搜索無法比擬的，但動態(tài)規(guī)劃總要遍歷所有的狀態(tài)，而搜索可以排除一些無效狀態(tài)。如何協(xié)調(diào)好動態(tài)規(guī)劃的高效率與高消費之間的矛盾呢？有一種折衷的辦法就是記憶化搜索算法 記憶化限界搜索算法在求解時，還是按著自頂向下的順序，但是每求解一個狀態(tài)，就將它的解保存下來，以后再次遇到這個狀態(tài)的時候，就不必重新求解了。在前面的例題中曾說明 ， 優(yōu)先隊列的分支限界法更象是有選擇 、有目的地進行深度優(yōu)先搜索 ， 時間效率 、 空間效率都是比較高的 。 上一頁 由于多段圖將頂點劃分為 k個互不相交的子集 ， 所以 ，多段圖劃分為 k段 ， 一旦某條路徑的一些段被確定后 ， 就可以并入這些信息并計算部分解的目標函數(shù)值的下界 。 初始化隊； ADDQ（ T）； //根結(jié)點入隊 parent（ E） =0； //記錄擴展路徑，當前結(jié)點的父結(jié)點 while （隊不空） {DELETEQ(E) //隊首結(jié)點出隊為新的 E結(jié)點； for （ E的每個兒子 X） if (s（ X） u) //當是可能的最優(yōu)解時入隊 {ADD Q（ X） ； parent （ X ） =E。 算法框架 上一小節(jié)的例子是求最大值的最優(yōu)化問題 ， 下面我們以求找最小成本的最優(yōu)化問題 ， 給出 FIFO分支搜索算法框架 。 返回首頁 2）結(jié)點優(yōu)先級確定：優(yōu)先隊列中結(jié)點優(yōu)先級常規(guī)定為一個與該結(jié)點相關(guān)的數(shù)值 p，它一般表示其接近最優(yōu)解的程度，本例題就以當前結(jié)點的所在分支的裝載上界為優(yōu)先值。 返回首頁 所謂 “ 分支 ” 是采用廣度優(yōu)先的策略，依次生成 E結(jié)點所有分支，也就是所有的兒子結(jié)點。 MaxLoading(c1)。此題應該采用最大堆來實現(xiàn)優(yōu)先隊列。 LC搜索的過程如下： 1） 初始隊列中只有結(jié)點 A； 2） 結(jié)點 A變?yōu)?E結(jié)點擴充 B入堆， bestw=10； 結(jié)點 C的裝載上界為 30+50=80 bestw，也入堆；堆中 B上界為 90在優(yōu)先隊列首。E表示當前擴展的活結(jié)點 ， x為 E的兒子 ， s(x)為結(jié)點 x下界函數(shù) ， 當其值比u大時 ， 不可能為最優(yōu)解 ， 不繼續(xù)搜索此分支 ， 該結(jié)點不入隊；當其值比 u小時 ， 可能達到最優(yōu)解 ， 繼續(xù)搜索此分支 ， 該結(jié)點入隊； cost（ X） 為當前葉結(jié)點所在分支的解 。} //方案