圖的搜索算法-文庫吧
2025-07-10 03:44 本頁面
【正文】 下一頁 返回首頁 例 1 1） 初始隊列中只有結(jié)點 A； 2） 結(jié)點 A變?yōu)?E結(jié)點擴充 B入隊， bestw=10； 結(jié)點 C的裝載上界為 30+50=80 bestw，也入隊； 3） 結(jié)點 B變?yōu)?E結(jié)點擴充 D入隊， bestw=40； 結(jié)點 E的裝載上界為 60 bestw，也入隊； 4） 結(jié)點 C變?yōu)?E結(jié)點擴充 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é)束。 LC搜索的過程如下： 1） 初始隊列中只有結(jié)點 A； 2） 結(jié)點 A變?yōu)?E結(jié)點擴充 B入堆， bestw=10； 結(jié)點 C的裝載上界為 30+50=80 bestw，也入堆；堆中 B上界為 90在優(yōu)先隊列首。 3） 結(jié)點 B變?yōu)?E結(jié)點擴充 D入堆， bestw=40； 結(jié)點 E的裝載上界為 60 bestw，也入堆；此時堆中 D上界為 90為優(yōu)先隊列首。 4） 結(jié)點 D變?yōu)?E結(jié)點，葉結(jié)點 H超過容量，葉結(jié)點 I的裝載為 40入堆， bestw仍為 40；此時堆中 C上界為 80為優(yōu)先隊列首。 5） 結(jié)點 C變?yōu)?E結(jié)點擴充 F入堆， bestw仍為 40； 結(jié)點 G的裝載上界為 50 bestw，也入堆；此時堆中 E上界為 60為優(yōu)先隊列首。 6） 結(jié)點 E變?yōu)?E結(jié)點，葉結(jié)點 J裝載量為 60入堆， bestw變?yōu)?60； 葉結(jié)點 K上界為 10bestw被剪掉；此時堆中 J上界為 60為優(yōu)先隊列首。 7） 結(jié)點 J變?yōu)?E結(jié)點，擴展的層次為 4算法結(jié)束。 雖然此時堆并不空，但可以確定已找到了最優(yōu)解。 上一頁 下一頁 返回首頁 FIFO限界算法搜索解空間的過程是按圖 526子集樹中字母序進行的 ， 而優(yōu)先隊列限界搜索解空間的過程是： ABDCEJ 看了上面的例子大家會發(fā)現(xiàn) ， 優(yōu)先隊列法擴展結(jié)點的過程 ，一開始實際是在進行類似 “ 深度優(yōu)先 ” 的搜索 。 算法框架 上一小節(jié)的例子是求最大值的最優(yōu)化問題 ， 下面我們以求找最小成本的最優(yōu)化問題 ， 給出 FIFO分支搜索算法框架 。 假定問題解空間樹為 T， T至少包含一個解結(jié)點 （ 即答案結(jié)點 ） 。 u為當(dāng)前的最優(yōu)解 ， 初值為一個較大的數(shù) 。E表示當(dāng)前擴展的活結(jié)點 ， x為 E的兒子 ， s(x)為結(jié)點 x下界函數(shù) ， 當(dāng)其值比u大時 ， 不可能為最優(yōu)解 ， 不繼續(xù)搜索此分支 ， 該結(jié)點不入隊；當(dāng)其值比 u小時 ， 可能達到最優(yōu)解 ， 繼續(xù)搜索此分支 ， 該結(jié)點入隊； cost（ X） 為當(dāng)前葉結(jié)點所在分支的解 。 算法框架如下： 上一頁 下一頁 返回首頁 2）： 上一頁 下一頁 返回首頁 search（ T） //為找出最小成本答案結(jié)點檢索 T。 {leaf=0。 初始化隊； ADDQ（ T）； //根結(jié)點入隊 parent（ E） =0； //記錄擴展路徑，當(dāng)前結(jié)點的父結(jié)點 while （隊不空） {DELETEQ(E) //隊首結(jié)點出隊為新的 E結(jié)點； for （ E的每個兒子 X） if (s（ X） u) //當(dāng)是可能的最優(yōu)解時入隊 {ADD Q（ X） ； parent （ X ） =E。 if (X是解結(jié)點 ) /
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1