【正文】 更重要的是搜索還可以剪枝，可能剪去大量不必要的狀態(tài)，因此在空間開(kāi)銷(xiāo)上往往比動(dòng)態(tài)規(guī)劃要低很多。 在窮舉法中通過(guò)上界函數(shù)與當(dāng)前情況下函數(shù)值的比較可以直接略過(guò)不合要求的情況而省去了更進(jìn)一步的枚舉和判斷；回溯法則因?yàn)閷哟蔚膭澐?，可以在上界函數(shù)值小于當(dāng)前最優(yōu)解時(shí) ， 剪去以該結(jié)點(diǎn)為根的子樹(shù) ，也就是節(jié)省了搜索范圍；分支限界法在這方面除了可以做到回溯法能做到的之外 ， 同時(shí)若采用優(yōu)先隊(duì)列的分支限界法 ， 用上界函數(shù)作為活結(jié)點(diǎn)的優(yōu)先級(jí) ， 一旦有葉結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn) ， 就意味著該葉結(jié)點(diǎn)所對(duì)應(yīng)的解即為最優(yōu)解 ， 可以立即終止其余的過(guò)程 。但廣度優(yōu)先搜索法一般無(wú)回溯操作，即入棧和出棧的操作，所以運(yùn)行速度比深度優(yōu)先搜索要快些。于是 ， 得到了目標(biāo)函數(shù)的界 [14, 18]。 {leaf=0。 FIFO限界算法搜索解空間的過(guò)程是按圖 526子集樹(shù)中字母序進(jìn)行的 ， 而優(yōu)先隊(duì)列限界搜索解空間的過(guò)程是： ABDCEJ 看了上面的例子大家會(huì)發(fā)現(xiàn) ， 優(yōu)先隊(duì)列法擴(kuò)展結(jié)點(diǎn)的過(guò)程 ，一開(kāi)始實(shí)際是在進(jìn)行類(lèi)似 “ 深度優(yōu)先 ” 的搜索 。 下一頁(yè) 優(yōu)先隊(duì)列的分支限界法將活結(jié)點(diǎn)組織成一個(gè)優(yōu)先隊(duì)列，并按優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)選取優(yōu)先級(jí)最高的下一個(gè)結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。 下一頁(yè) 和回溯法一樣，在生成的節(jié)點(diǎn)中，拋棄那些不滿足約束條件（或者說(shuō)不可能導(dǎo)出最優(yōu)可行解）的結(jié)點(diǎn)，其余節(jié)點(diǎn)加入活節(jié)點(diǎn)表。 if (s bestw =c2)。 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)： 1）要輸出解的方案，在搜索過(guò)程中仍需要生成解結(jié)構(gòu)樹(shù)，其結(jié)點(diǎn)信息包括指向父結(jié)點(diǎn)的指針和標(biāo)識(shí)物品取舍（或是父結(jié)點(diǎn)的左、右孩子）。 3） 結(jié)點(diǎn) B變?yōu)?E結(jié)點(diǎn)擴(kuò)充 D入堆， bestw=40； 結(jié)點(diǎn) E的裝載上界為 60 bestw，也入堆；此時(shí)堆中 D上界為 90為優(yōu)先隊(duì)列首。 算法框架如下： 上一頁(yè) 下一頁(yè) 算法 ——多段圖的最短路徑問(wèn)題 1． 根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的下界 down；采用貪心法得到上界 up； 2． 將待處理結(jié)點(diǎn)表 PT初始化為空； 3． for (i=1。 由于它們?cè)趩?wèn)題的解空間樹(shù) T上搜索的方法不同，適合解決的問(wèn)題也就不同。 5. 3．動(dòng)態(tài)規(guī)劃與搜索算法 撇開(kāi)時(shí)空效率的因素不談 ， 在解決最優(yōu)化問(wèn)題的算法中 ， 搜索可以說(shuō)是 “ 萬(wàn)能 ” 的 。記憶化搜索有優(yōu)化方便、調(diào)試容易、思維直觀的優(yōu)點(diǎn)，但是效率上比循環(huán)的動(dòng)態(tài)規(guī)劃差一個(gè)常數(shù)，但是時(shí)間和空間復(fù)雜度是同一數(shù)量級(jí)的（盡管空間上也差一個(gè)常數(shù)，那就是堆?？臻g）。 上一頁(yè) 3. 上一頁(yè) 若 lb=up， 則將 i,u,v,lb存儲(chǔ)在表 PT中； 如果 i= =k1且葉子結(jié)點(diǎn)的 lb值在表 PT中最小 ， 則輸出該葉子結(jié)點(diǎn)對(duì)應(yīng)的最優(yōu)解； 否則 ， 如果 i= =k1且表 PT中的葉子結(jié)點(diǎn)的 lb值不是最小 ， 則 up=表 PT中的葉子結(jié)點(diǎn)最小的 lb值 。且對(duì)于 LC分支 限界算法 ， 一當(dāng)擴(kuò)展到葉結(jié)點(diǎn)就已經(jīng)找到最優(yōu)解 ， 可以停止搜索 。 下一頁(yè) 上一頁(yè) 下一頁(yè) for(i=1。 print(“ 換行符 The second ship loading”, s bestw,“chose”)。 例如： W={10， 30， 50}， C1=60， 所構(gòu)成的子集樹(shù)如下圖所表示： 上一頁(yè) 雖然此時(shí)堆并不空，但可以確定已找到了最優(yōu)解。 2）： 上一頁(yè) FIFO分支 限界算法用隊(duì) 存儲(chǔ)活結(jié)點(diǎn) ， LC分支 限界算法用堆 存儲(chǔ)活結(jié)點(diǎn) ， 以保證比較優(yōu)良的結(jié)點(diǎn)先被擴(kuò)展 。 //求解第 i段 5． while (i=1) 對(duì)頂點(diǎn) u的所有鄰接點(diǎn) v 根據(jù)式 lb。 返回首頁(yè) 由于在很多情況下 ， 問(wèn)題的解空間太復(fù)雜用大腦構(gòu)造有一定困難 ， 仍然需要采用搜索算法 。當(dāng) n比較小的時(shí)候，我們可以忽略這個(gè)常數(shù)，從而記憶化搜索可以和動(dòng)態(tài)規(guī)劃達(dá)到完全相同的效果。 所以動(dòng)態(tài)規(guī)劃可以解決的問(wèn)題 ，