圖的搜索算法-全文預(yù)覽
【正文】 展結(jié)點的順序不同 ， 因而存儲活結(jié)點的數(shù)據(jù)結(jié)構(gòu)不同 。 下一頁 初始化隊； ADDQ（ T）； //根結(jié)點入隊 parent（ E） =0； //記錄擴(kuò)展路徑，當(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。 算法框架如下： 上一頁 算法框架 上一小節(jié)的例子是求最大值的最優(yōu)化問題 ， 下面我們以求找最小成本的最優(yōu)化問題 ， 給出 FIFO分支搜索算法框架 。 返回首頁 7） 結(jié)點 J變?yōu)?E結(jié)點，擴(kuò)展的層次為 4算法結(jié)束。 3） 結(jié)點 B變?yōu)?E結(jié)點擴(kuò)充 D入堆， bestw=40； 結(jié)點 E的裝載上界為 60 bestw，也入堆；此時堆中 D上界為 90為優(yōu)先隊列首。 返回首頁 其實看了下面的例子大家會發(fā)現(xiàn)，優(yōu)先隊列式擴(kuò)展結(jié)點的過程，一開始實際是在進(jìn)行類似 “ 深度優(yōu)先 ” 的搜索。 數(shù)據(jù)結(jié)構(gòu)設(shè)計： 1）要輸出解的方案，在搜索過程中仍需要生成解結(jié)構(gòu)樹，其結(jié)點信息包括指向父結(jié)點的指針和標(biāo)識物品取舍（或是父結(jié)點的左、右孩子）。 2）結(jié)點優(yōu)先級確定：優(yōu)先隊列中結(jié)點優(yōu)先級常規(guī)定為一個與該結(jié)點相關(guān)的數(shù)值 p，它一般表示其接近最優(yōu)解的程度，本例題就以當(dāng)前結(jié)點的所在分支的裝載上界為優(yōu)先值。i++) if(bestx[i]=1) print(i,”,”)。i++) if(bestx[i]=1) print(i，“，” )。 if (s bestw =c2)。 返回首頁 第一艘船的載重量是 c1，第二艘船的載重量是 c2， wi 是貨箱 i 的重量 ,且 w 1+w2+…… +wn≤c1+c2 。 返回首頁 和回溯法一樣，在生成的節(jié)點中，拋棄那些不滿足約束條件（或者說不可能導(dǎo)出最優(yōu)可行解）的結(jié)點，其余節(jié)點加入活節(jié)點表。所謂 “ 分支 ” 是采用廣度優(yōu)先的策略，依次生成 E結(jié)點所有分支，也就是所有的兒子結(jié)點。 下一頁 分枝 限界搜索算法 【 例 2】 有兩艘船， n 個貨箱。 下一頁 MaxLoading(c1)。i=n。i=n。優(yōu)先隊列的分支限界法將活結(jié)點組織成一個優(yōu)先隊列，并按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當(dāng)前擴(kuò)展結(jié)點。此題應(yīng)該采用最大堆來實現(xiàn)優(yōu)先隊列。 小結(jié)討論： FIFO搜索或 LIFO搜索也可以通過加入 “ 限界 ” 策略加速搜索嗎？ 那與優(yōu)先隊列式分支限界法 ——LC—檢索的區(qū)別在哪兒呢？ 答案：由于 FIFO搜索或 LIFO搜索是盲目擴(kuò)展地結(jié)點，當(dāng)前最優(yōu)解距真正的最優(yōu)解距離較大，作為 “ 界 ” 所起到的剪枝作用很有限，不能有效提高搜索速度。 返回首頁 下一頁 LC搜索的過程如下： 1） 初始隊列中只有結(jié)點 A； 2） 結(jié)點 A變?yōu)?E結(jié)點擴(kuò)充 B入堆， bestw=10； 結(jié)點 C的裝載上界為 30+50=80 bestw，也入堆；堆中 B上界為 90在優(yōu)先隊列首。 6） 結(jié)點 E變?yōu)?E結(jié)點，葉結(jié)點 J裝載量為 60入堆， bestw變?yōu)?60； 葉結(jié)點 K上界為 10bestw被剪掉；此時堆中 J上界為 60為優(yōu)先隊列首。 下一頁 FIFO限界算法搜索解空間的過程是按圖 526子集樹中字母序進(jìn)行的 ， 而優(yōu)先隊列限界搜索解空間的過程是： ABDCEJ 看了上面的例子大家會發(fā)現(xiàn) ， 優(yōu)先隊列法擴(kuò)展結(jié)點的過程 ，一開始實際是在進(jìn)行類似 “ 深度優(yōu)先 ” 的搜索 。E表示當(dāng)前擴(kuò)展的活結(jié)點 ， x為 E的兒子 ， s(x)為結(jié)點 x下界函數(shù) ， 當(dāng)其值比u大時 ， 不可能為最優(yōu)解 ， 不繼續(xù)搜索此分支 ， 該結(jié)點不入隊；當(dāng)其值比 u小時 ， 可能達(dá)到最優(yōu)解 ， 繼續(xù)搜索此分支 ， 該結(jié)點入隊； cost（ X） 為當(dāng)前葉結(jié)點所在分支的
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1