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