圖的搜索算法-免費(fèi)閱讀
【正文】 它以搜索算法為核心，只不過使用 “ 記錄求過的狀態(tài) ”的辦法，來避免重復(fù)搜索，這樣，記憶化搜索的每一步，也可以對(duì)應(yīng)到動(dòng)態(tài)規(guī)劃算法中去。 下一頁 返回首頁 下一頁 2. 2．回溯與分支限界法 回溯法以深度優(yōu)先的方式搜索解空間樹 T，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹 T。 將表 PT中目標(biāo)函數(shù)值超出 up的結(jié)點(diǎn)刪除； u=表 PT中 lb最小的結(jié)點(diǎn)的 v值； i=表 PT中 lb最小的結(jié)點(diǎn)的 i值； i++。 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è)一個(gè)表 ST，在表 PT中取出最小值結(jié)點(diǎn)進(jìn)行擴(kuò)充時(shí)，將最小值結(jié)點(diǎn)存儲(chǔ)到表ST中，表 PT和表 ST的數(shù)據(jù)結(jié)構(gòu)為 (第 i段， 第 i段頂點(diǎn) , 第 i+1段頂點(diǎn) lb)，在搜索過程中表 PT和表 ST的狀態(tài)如下： (b) 擴(kuò)展結(jié)點(diǎn) 3后的狀態(tài) (d) 擴(kuò)展結(jié)點(diǎn) 5后的狀態(tài) ， 最優(yōu)解為 0→ 3→ 5→ 8→ 9 多段圖的最短路徑問題最優(yōu)解的確定 (1,0,216) (1,0,315) (1,0,216) (2,2,416) (2,2,518) (2,2,618) (1,0,315) (2,2,416) (2,2,518) (2,2,618) (2,3,516) (2,3,618) (1,0,315) (1,0,216) (2,2,416) (2,2,518) (2,2,618) (2,3,618) (3,5,816) (1,0,315) (1,0,216) (2,3,516) (a) 擴(kuò)展根結(jié)點(diǎn)后的狀態(tài) PT ST ST PT (c) 擴(kuò)展結(jié)點(diǎn) 4后的狀態(tài) ST ST 回溯過程是： (3,5, 816)→( 2,3, 516)→( 1,0, 315)。 設(shè)圖 G=(V, E)是一個(gè)帶權(quán)有向連通圖 ， 如果把頂點(diǎn)集合 V劃分成 k個(gè)互不相交的子集 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) 。} //方案的葉結(jié)點(diǎn)存儲(chǔ)在 leaf中 } } 3）： 上一頁 返回首頁 E表示當(dāng)前擴(kuò)展的活結(jié)點(diǎn) ， x為 E的兒子 ， s(x)為結(jié)點(diǎn) x下界函數(shù) ， 當(dāng)其值比u大時(shí) ， 不可能為最優(yōu)解 ， 不繼續(xù)搜索此分支 ， 該結(jié)點(diǎn)不入隊(duì)；當(dāng)其值比 u小時(shí) ， 可能達(dá)到最優(yōu)解 ， 繼續(xù)搜索此分支 ， 該結(jié)點(diǎn)入隊(duì)； cost（ X） 為當(dāng)前葉結(jié)點(diǎn)所在分支的解 。 下一頁 LC搜索的過程如下： 1） 初始隊(duì)列中只有結(jié)點(diǎn) A； 2） 結(jié)點(diǎn) A變?yōu)?E結(jié)點(diǎn)擴(kuò)充 B入堆， bestw=10； 結(jié)點(diǎn) C的裝載上界為 30+50=80 bestw，也入堆；堆中 B上界為 90在優(yōu)先隊(duì)列首。 返回首頁 此題應(yīng)該采用最大堆來實(shí)現(xiàn)優(yōu)先隊(duì)列。i=n。 MaxLoading(c1)。 分枝 限界搜索算法 【 例 2】 有兩艘船， n 個(gè)貨箱。所謂 “ 分支 ” 是采用廣度優(yōu)先的策略，依次生成 E結(jié)點(diǎn)所有分支，也就是所有的兒子結(jié)點(diǎn)。 返回首頁 返回首頁 i++) if(
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1