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