圖的搜索算法(完整版)
【正文】 標(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，為一個(gè)可行解但超出目標(biāo)函數(shù)的界，將其丟棄；在結(jié)點(diǎn) 11，第 3段選擇邊 5, 8，可直接確定第 4段的邊 8, 9，目標(biāo)函數(shù)值為lb=3+4+6+3=16，為一個(gè)較好的可行解。 FIFO分支 限界算法用隊(duì) 存儲(chǔ)活結(jié)點(diǎn) ， LC分支 限界算法用堆 存儲(chǔ)活結(jié)點(diǎn) ， 以保證比較優(yōu)良的結(jié)點(diǎn)先被擴(kuò)展 。 if (X是解結(jié)點(diǎn) ) //x為葉結(jié)點(diǎn) {U=min（ cost（ X）， u） 。 2）： 上一頁(yè) 假定問(wèn)題解空間樹(shù)為 T， T至少包含一個(gè)解結(jié)點(diǎn) （ 即答案結(jié)點(diǎn) ） 。 雖然此時(shí)堆并不空，但可以確定已找到了最優(yōu)解。 例 1 例如： W={10， 30， 50}， C1=60， 所構(gòu)成的子集樹(shù)如下圖所表示： 上一頁(yè) 3）優(yōu)先隊(duì)列組織：結(jié)點(diǎn)優(yōu)先級(jí)確定后，簡(jiǎn)單地按結(jié)點(diǎn)優(yōu)先級(jí)進(jìn)行排序，就生成了優(yōu)先隊(duì)列。 print(“ 換行符 The second ship loading”, s bestw,“chose”)。 第五章 圖的搜索算法 分支限界法 分枝搜索算法 分枝 限界搜索算法 算法框架 圖的搜索算法小結(jié) 分枝搜索算法 1．基本思想 分支搜索法也是一種在問(wèn)題解空間上進(jìn)行嘗試搜索算法。 for(i=1。排序算法的時(shí)間復(fù)雜度較高，考慮到搜索算法每次只擴(kuò)展一個(gè)結(jié)點(diǎn)，回憶數(shù)據(jù)結(jié)構(gòu)中堆排序，適合這一特點(diǎn)且比較交換的次數(shù)最少。 下一頁(yè) 1） 初始隊(duì)列中只有結(jié)點(diǎn) A； 2） 結(jié)點(diǎn) A變?yōu)?E結(jié)點(diǎn)擴(kuò)充 B入隊(duì)， bestw=10； 結(jié)點(diǎn) C的裝載上界為 30+50=80 bestw，也入隊(duì)； 3） 結(jié)點(diǎn) B變?yōu)?E結(jié)點(diǎn)擴(kuò)充 D入隊(duì)， bestw=40； 結(jié)點(diǎn) E的裝載上界為 60 bestw，也入隊(duì)； 4） 結(jié)點(diǎn) C變?yōu)?E結(jié)點(diǎn)擴(kuò)充 F入隊(duì)， bestw仍為 40； 結(jié)點(diǎn) G的裝載上界為 50 bestw，也入隊(duì)； 5） 結(jié)點(diǎn) D變?yōu)?E結(jié)點(diǎn)，葉結(jié)點(diǎn) H超過(guò)容量， 葉結(jié)點(diǎn) I的裝載為 40， bestw仍為 40； 6） 結(jié)點(diǎn) E變?yōu)?E結(jié)點(diǎn)，葉結(jié)點(diǎn) J裝載量為 60， bestw為 60； 葉結(jié)點(diǎn) K被剪掉； 7） 結(jié)點(diǎn) F變?yōu)?E結(jié)點(diǎn)，葉結(jié)點(diǎn) L超過(guò)容量， bestw為 60； 葉結(jié)點(diǎn) M被剪掉； 8） 結(jié)點(diǎn) G變?yōu)?E結(jié)點(diǎn)，葉結(jié)點(diǎn) N、 O都被剪掉； 此時(shí)隊(duì)列空算法結(jié)束。 上一頁(yè) u為當(dāng)前的最優(yōu)解 ， 初值為一個(gè)較大的數(shù) 。 下一頁(yè) leaf=x。且對(duì)于 LC分支 限界算法 ， 一當(dāng)擴(kuò)展到葉結(jié)點(diǎn)就已經(jīng)找到最優(yōu)解 ， 可以停止搜索 。由于結(jié)點(diǎn) 11是葉子結(jié)點(diǎn)，并且其目標(biāo)函數(shù)值是表 PT中最小的，所以，結(jié)點(diǎn) 11代表的解即是問(wèn)題的最優(yōu)解，搜索過(guò)程結(jié)束。 若 lb=up， 則將 i,u,v,lb存儲(chǔ)在表 PT中； 如果 i= =k1且葉子結(jié)點(diǎn)的 lb值在表 PT中最小 ， 則輸出該葉子結(jié)點(diǎn)對(duì)應(yīng)的最優(yōu)解； 否則 ， 如果 i= =k1且表 PT中的葉子結(jié)點(diǎn)的 lb值不是最小 ， 則 up=表 PT中的葉子結(jié)點(diǎn)最小的 lb值 。 返回首頁(yè) 3. 上一頁(yè) 下一頁(yè) 上一頁(yè) 記憶化限界搜索。記憶化搜索有優(yōu)
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1