圖的搜索算法-文庫吧在線文庫
【正文】 2． LIFO搜索 3．優(yōu)先隊(duì)列式搜索 上一頁 然后從表中選擇一個(gè)節(jié)點(diǎn)作為下一個(gè) E節(jié)點(diǎn)。 我們希望確定是否有一種可將所有 n 個(gè)貨箱全部裝船的方法。 {print(“The first ship loading”, bestw ，“ chose：” )。 } else print(“no solution”)。 2）堆結(jié)點(diǎn)首先應(yīng)該包括結(jié)點(diǎn)優(yōu)先級(jí)信息：結(jié)點(diǎn)的所在分支的裝載上界 uweight；堆中無法體現(xiàn)結(jié)點(diǎn)的層次信息（ level），只能存儲(chǔ)在結(jié)點(diǎn)中； AddLiveNode用于把 bbnode類型的活節(jié)點(diǎn)加到子樹中 ， 并把HeapNode類型的活節(jié)點(diǎn)插入最大堆 。 4） 結(jié)點(diǎn) D變?yōu)?E結(jié)點(diǎn)，葉結(jié)點(diǎn) H超過容量，葉結(jié)點(diǎn) I的裝載為 40入堆， bestw仍為 40；此時(shí)堆中 C上界為 80為優(yōu)先隊(duì)列首。 下一頁 返回首頁 多段圖的最短路徑問題 對(duì) 所 示 的 多 段 圖 應(yīng) 用 貪 心 法 求 得 近 似 解 為0→ 2→ 5→ 8→ 9， 其路徑代價(jià)為 2+7+6+3=18， 這可以作為多段圖最短路徑問題的上界 。 i=k。所以，當(dāng)搜索樹的結(jié)點(diǎn)較多，用其它方法易產(chǎn)生內(nèi)存溢出時(shí)，深度優(yōu)先搜索不失為一種有效的求解方法。一般情況下，回溯法的求解目標(biāo)是找出 T中滿足約束條件的所有解的方案，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使用某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。 4. 在處理最優(yōu)問題時(shí) ， 采用窮舉法 、 回溯法或分支限界法都可以通過利用當(dāng)前最優(yōu)解和上界函數(shù)加速 。 所以動(dòng)態(tài)規(guī)劃可以解決的問題 ， 搜索也一定可以解決 。 另外動(dòng)態(tài)規(guī)劃在遞推求解過程中，需要用數(shù)組存儲(chǔ)有關(guān)信息，而數(shù)組的下標(biāo)只能是整數(shù)，所以要求問題中相關(guān)的數(shù)據(jù)必須為整數(shù)（如 【 例 2】 “資源分配問題 ” 中的資金就必須為整數(shù)），對(duì)于這類信息非整數(shù)或不便于轉(zhuǎn)換為整數(shù)的問題，同樣需要采用搜索算法。當(dāng) n比較小的時(shí)候，我們可以忽略這個(gè)常數(shù)，從而記憶化搜索可以和動(dòng)態(tài)規(guī)劃達(dá)到完全相同的效果。這種方法綜合了搜索和動(dòng)態(tài)規(guī)劃兩方面的優(yōu)點(diǎn)，因而還是很有實(shí)用價(jià)值的。 由于在很多情況下 ， 問題的解空間太復(fù)雜用大腦構(gòu)造有一定困難 ， 仍然需要采用搜索算法 。 上一頁 返回首頁 下一頁 //求解第 i段 5． while (i=1) 對(duì)頂點(diǎn) u的所有鄰接點(diǎn) v 根據(jù)式 lb。 一般情況下 ， 對(duì)于一個(gè)正在生成的路徑 ， 假設(shè)已經(jīng)確定了 i段（ 1≤i≤k） ， 其路徑為 (r1, r2, … , ri, ri+1)， 此時(shí) ， 該部分解的目標(biāo)函數(shù)值的計(jì)算方法即限界函數(shù)如下 ： ? ? + = + ? = + + = + k i j p i E v r i j j j j v r c r r c lb p i 2 1 , 1 1 ]} ][ [ { min ] ][ [ 1 段的最短邊 第 ＋ 具體的搜索過程如下 （ 加黑表示該路徑上已經(jīng)確定的邊 ） ： （ 1） 在根結(jié)點(diǎn) 1， 根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的值為 18； （ 2）在結(jié)點(diǎn) 2，第 1段選擇邊 0, 1，目標(biāo)函數(shù)值為lb=4+8+5+3=20，超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn) 2丟棄；在結(jié)點(diǎn) 3，第 1段選擇邊 0, 2，目標(biāo)函數(shù)值為 lb=2+6+5+3=16，將結(jié)點(diǎn) 3加入待處理結(jié)點(diǎn)表 PT中；在結(jié)點(diǎn) 4，第 1段選擇邊 0, 3，目標(biāo)函數(shù)值為 lb=3+4+5+3=15，將結(jié)點(diǎn) 4加入表 PT中； （ 3） 在表 PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn) 4優(yōu)先進(jìn)行搜索； （ 4）在結(jié)點(diǎn) 5，第 2段選擇邊 3, 5，目標(biāo)函數(shù)值為lb=3+4+6+3=16，將結(jié)點(diǎn) 5加入表 PT中；在結(jié)點(diǎn) 6，第 2段選擇邊 3, 6，目標(biāo)函數(shù)值為 lb=3+7+5+3=18，將結(jié)點(diǎn) 6加入表 PT中； （ 5） 在表 PT中選取目
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1