圖的搜索算法-在線瀏覽
2024-09-04 03:44本頁面
【正文】 {U=min（ cost（ X）， u） 。} //方案的葉結(jié)點(diǎn)存儲在 leaf中 } } 3）： 上一頁 返回首頁 FIFO分支 限界算法用隊(duì) 存儲活結(jié)點(diǎn) ， LC分支 限界算法用堆 存儲活結(jié)點(diǎn) ， 以保證比較優(yōu)良的結(jié)點(diǎn)先被擴(kuò)展 。 設(shè)圖 G=(V, E)是一個帶權(quán)有向連通圖 ， 如果把頂點(diǎn)集合 V劃分成 k個互不相交的子集 Vi（ 2≤k≤n, 1≤i≤k） ， 使得 E中的任何一條邊 (u, v)， 必有 u∈ Vi， v∈ Vi+m（ 1≤i＜ k, 1＜ i+m≤k） ， 則稱圖 G為多段圖 ， 稱 s∈ V1為源點(diǎn) ， t∈ Vk為終點(diǎn) 。 多段圖的最短路徑問題 對 所 示 的 多 段 圖 應(yīng) 用 貪 心 法 求 得 近 似 解 為0→ 2→ 5→ 8→ 9， 其路徑代價(jià)為 2+7+6+3=18， 這可以作為多段圖最短路徑問題的上界 。于是 ， 得到了目標(biāo)函數(shù)的界 [14, 18]。 一般情況下 ， 對于一個正在生成的路徑 ， 假設(shè)已經(jīng)確定了 i段（ 1≤i≤k） ， 其路徑為 (r1, r2, … , ri, ri+1)， 此時 ， 該部分解的目標(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中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn) 3優(yōu)先進(jìn)行搜索； （ 6）在結(jié)點(diǎn) 7，第 2段選擇邊 2, 4，目標(biāo)函數(shù)值為lb=2+6+5+3=16，將結(jié)點(diǎn) 7加入表 PT中；在結(jié)點(diǎn) 8，第 2段選擇邊 2, 5，目標(biāo)函數(shù)值為 lb=2+7+6+3=18，將結(jié)點(diǎn) 8加入表 PT中；在結(jié)點(diǎn) 9，第 2段選擇邊 2, 6，目標(biāo)函數(shù)值為 lb=2+8+5+3=18，將結(jié)點(diǎn) 9加入表 PT中； （ 7）在表 PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn) 5優(yōu)先進(jìn)行搜索； （ 8）在結(jié)點(diǎn) 10，第 3段選擇邊 5, 7，可直接確定第 4段的邊7, 9，目標(biāo)函數(shù)值為 lb=3+4+8+7=22，為一個可行解但超出目標(biāo)函數(shù)的界，將其丟棄；在結(jié)點(diǎn) 11，第 3段選擇邊 5, 8，可直接確定第 4段的邊 8, 9，目標(biāo)函數(shù)值為lb=3+4+6+3=16，為一個較好的可行解。 6 4 0→ 1 lb=20 2 3 1 start lb=18 0→ 2 lb=16 0→ 3 lb=15 分支限界法求解多段圖的最短路徑問題示例 ( 表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序 ) 7 2→ 4 lb=16 8 2→ 5 lb=18 9 2→ 6 lb=18 5 3→ 5 lb=16 3→ 6 lb=18 11 10 5→ 7 lb=22 5→ 8 lb=16 為了在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，設(shè)一個表 ST，在表 PT中取出最小值結(jié)點(diǎn)進(jìn)行擴(kuò)充時，將最小值結(jié)點(diǎn)存儲到表ST中，表 PT和表 ST的數(shù)據(jù)結(jié)構(gòu)為 (第 i段
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1