【正文】 化方便、調(diào)試容易、思維直觀的優(yōu)點(diǎn)，但是效率上比循環(huán)的動(dòng)態(tài)規(guī)劃差一個(gè)常數(shù)，但是時(shí)間和空間復(fù)雜度是同一數(shù)量級(jí)的（盡管空間上也差一個(gè)常數(shù)，那就是堆棧空間）。 返回首頁 5. 3．動(dòng)態(tài)規(guī)劃與搜索算法 撇開時(shí)空效率的因素不談 ， 在解決最優(yōu)化問題的算法中 ， 搜索可以說是 “ 萬能 ” 的 。 返回首頁 由于它們?cè)趩栴}的解空間樹 T上搜索的方法不同，適合解決的問題也就不同。 圖的搜索算法小結(jié) 1．深度優(yōu)先搜索與廣度優(yōu)先搜索算法有何區(qū)別 通常深度優(yōu)先搜索法不全部保留結(jié)點(diǎn)，擴(kuò)展完的結(jié)點(diǎn)從數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)棧中彈出刪去，這樣，一般在數(shù)據(jù)棧中存儲(chǔ)的結(jié)點(diǎn)數(shù)就是解空間樹的深度，因此它占用空間較少。 算法 ——多段圖的最短路徑問題 1． 根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的下界 down；采用貪心法得到上界 up； 2． 將待處理結(jié)點(diǎn)表 PT初始化為空； 3． for (i=1。 1 2 0 3 4 5 6 7 8 9 4 9 2 3 8 7 6 8 4 7 5 6 8 6 6 5 3 7 多段圖的最短路徑問題是求從源點(diǎn)到終點(diǎn)的最小代價(jià)路徑。 下一頁 算法框架如下： 上一頁 返回首頁 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ì)列首。 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)： 1）要輸出解的方案，在搜索過程中仍需要生成解結(jié)構(gòu)樹，其結(jié)點(diǎn)信息包括指向父結(jié)點(diǎn)的指針和標(biāo)識(shí)物品取舍（或是父結(jié)點(diǎn)的左、右孩子）。i++) if(bestx[i]=1) print(i,”,”)。 if (s bestw =c2)。第一艘船的載重量是 c1，第二艘船的載重量是 c2， wi 是貨箱 i 的重量 ,且 w 1+w2+…… +wn≤c1+c2 。和回溯法一樣，在生成的節(jié)點(diǎn)中，拋棄那些不滿足約束條件（或者說不可能導(dǎo)出最優(yōu)可行解）的結(jié)點(diǎn)，其余節(jié)點(diǎn)加入活節(jié)點(diǎn)表。 下一頁 下一頁 i=n。優(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)。 小結(jié)討論： FIFO搜索或 LIFO搜索也可以通過加入 “ 限界 ” 策略加速搜索嗎？ 那與優(yōu)先隊(duì)列式分支限界法 ——LC—檢索的區(qū)別在哪兒呢？ 答案：由于 FIFO搜索或 LIFO搜索是盲目擴(kuò)展地結(jié)點(diǎn)，當(dāng)前最優(yōu)解距真正的最優(yōu)解距離較大，作為 “ 界 ” 所起到的剪枝作用很有限，不能有效提高搜索速度。 下一頁 6） 結(jié)點(diǎn) E變?yōu)?E結(jié)點(diǎn)，葉結(jié)點(diǎn) J裝載量為 60入堆， bestw變?yōu)?60； 葉結(jié)點(diǎn) K上界為 10bestw被剪掉；此時(shí)堆中 J上界為 60為優(yōu)先隊(duì)列首。 FIFO限界算法搜索解空間的過程是按圖 526子集樹中字母序進(jìn)行的 ， 而優(yōu)先隊(duì)列限界搜索解空間的過程是： ABDCEJ 看了上面的例子大家會(huì)發(fā)現(xiàn) ， 優(yōu)先隊(duì)列法擴(kuò)展結(jié)點(diǎn)的過程 ，一開始實(shí)際是在進(jìn)行類似 “ 深度優(yōu)先 ” 的搜索 。 {leaf=0。 于是 ， 得到了目標(biāo)函數(shù)的界 [14, 18]。 4． i=1。但廣度優(yōu)先搜索法一般無回溯操作，即入棧和出棧的操作，所以運(yùn)行速度比深度優(yōu)先搜索要快些。 下表列出了回溯法和分支限界法的一些區(qū)別： 上一頁 在窮舉法中通過上界函數(shù)與當(dāng)前情況下函數(shù)值的比較可以直接略過不合要求的情況而省去了更進(jìn)一步的枚舉和判斷；回溯法則因?yàn)閷哟蔚膭澐?，可以在上界函數(shù)值小于當(dāng)前最優(yōu)解時(shí) ， 剪去以該結(jié)點(diǎn)為根的子樹 ，也就是節(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)解 ， 可以立即終止其余的過程 。 動(dòng)態(tài)規(guī)劃是自底向上的遞推求解 ， 而無論深度優(yōu)先搜索或廣度優(yōu)先搜索都是自頂向下求解 。更重要的是搜索還可以剪枝，可能剪去大量不必要的狀態(tài)，因此在空間開銷上往往比動(dòng)態(tài)規(guī)劃要低很