圖的搜索算法(文件)
【正文】 點(diǎn)檢索 T。 leaf=x。 且對于 LC分支 限界算法 ， 一當(dāng)擴(kuò)展到葉結(jié)點(diǎn)就已經(jīng)找到最優(yōu)解 ， 可以停止搜索 。 把每一段最小的代價(jià)相加 ， 可以得到一個(gè)非常簡單的下界 ， 其路徑長度為 2+4+5+3=14。由于結(jié)點(diǎn) 11是葉子結(jié)點(diǎn)，并且其目標(biāo)函數(shù)值是表 PT中最小的，所以，結(jié)點(diǎn) 11代表的解即是問題的最優(yōu)解，搜索過程結(jié)束。 i++) x[i]=0。 若 lb=up， 則將 i,u,v,lb存儲(chǔ)在表 PT中； 如果 i= =k1且葉子結(jié)點(diǎn)的 lb值在表 PT中最小 ， 則輸出該葉子結(jié)點(diǎn)對應(yīng)的最優(yōu)解； 否則 ， 如果 i= =k1且表 PT中的葉子結(jié)點(diǎn)的 lb值不是最小 ， 則 up=表 PT中的葉子結(jié)點(diǎn)最小的 lb值 。 廣度優(yōu)先搜索算法，一般需存儲(chǔ)產(chǎn)生的所有結(jié)點(diǎn)，占用的存儲(chǔ)空間要比深度優(yōu)先搜索大得多，因此，程序設(shè)計(jì)中，必須考慮溢出和節(jié)省內(nèi)存空間的問題。 返回首頁 相對而言，分支限界算法的解空間比回溯法大得多， 因此當(dāng)內(nèi)存容量有限時(shí)，回溯法成功的可能性更大。 3. 上一頁 僅就對限界剪支的效率而言 ， 優(yōu)先隊(duì)列的分支限界法顯然要更充分一些 。 下一頁 動(dòng)態(tài)規(guī)劃要求階段決策具有無后向性 ， 而搜索算法沒有此限止 。 上一頁 一般說來，動(dòng)態(tài)規(guī)劃算法在時(shí)間效率上的優(yōu)勢是搜索無法比擬的，但動(dòng)態(tài)規(guī)劃總要遍歷所有的狀態(tài)，而搜索可以排除一些無效狀態(tài)。記憶化限界搜索。 。記憶化搜索有優(yōu)化方便、調(diào)試容易、思維直觀的優(yōu)點(diǎn)，但是效率上比循環(huán)的動(dòng)態(tài)規(guī)劃差一個(gè)常數(shù)，但是時(shí)間和空間復(fù)雜度是同一數(shù)量級的（盡管空間上也差一個(gè)常數(shù)，那就是堆?？臻g）。如何協(xié)調(diào)好動(dòng)態(tài)規(guī)劃的高效率與高消費(fèi)之間的矛盾呢？有一種折衷的辦法就是記憶化搜索算法 記憶化限界搜索算法在求解時(shí)，還是按著自頂向下的順序，但是每求解一個(gè)狀態(tài)，就將它的解保存下來，以后再次遇到這個(gè)狀態(tài)的時(shí)候，就不必重新求解了。 返回首頁 利用動(dòng)態(tài)規(guī)劃法進(jìn)行算法設(shè)計(jì)時(shí) ，設(shè)計(jì)者在進(jìn)行算法設(shè)計(jì)前已經(jīng)用大腦自己構(gòu)造好了問題的解空間 ，因此可以自底向上的遞推求解；而搜索算法是在搜索過程中根據(jù)一定規(guī)則自動(dòng)構(gòu)造 ， 并搜索解空間樹的 。 5. 3．動(dòng)態(tài)規(guī)劃與搜索算法 撇開時(shí)空效率的因素不談 ， 在解決最優(yōu)化問題的算法中 ， 搜索可以說是 “ 萬能 ” 的 。在前面的例題中曾說明 ， 優(yōu)先隊(duì)列的分支限界法更象是有選擇 、有目的地進(jìn)行深度優(yōu)先搜索 ， 時(shí)間效率 、 空間效率都是比較高的 。 返回首頁 下一頁 由于它們在問題的解空間樹 T上搜索的方法不同，適合解決的問題也就不同。 上一頁 圖的搜索算法小結(jié) 1．深度優(yōu)先搜索與廣度優(yōu)先搜索算法有何區(qū)別 通常深度優(yōu)先搜索法不全部保留結(jié)點(diǎn)，擴(kuò)展完的結(jié)點(diǎn)從數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)棧中彈出刪去，這樣，一般在數(shù)據(jù)棧中存儲(chǔ)的結(jié)點(diǎn)數(shù)就是解空間樹的深度，因此它占用空間較少。 u=0。 算法 ——多段圖的最短路徑問題 1． 根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的下界 down；采用貪心法得到上界 up； 2． 將待處理結(jié)點(diǎn)表 PT初始化為空； 3． for (i=1。 由于多段圖將頂點(diǎn)劃分為 k個(gè)互不相交的子集 ， 所以 ，多段圖劃分為 k段 ， 一旦某條路徑的一些段被確定后 ， 就可以并入這些信息并計(jì)算部分解的目標(biāo)函數(shù)值的下界 。 1 2 0 3 4 5 6 7 8 9 4 9 2 3 8 7 6 8 4 7 5 6 8 6 6 5 3 7 多段圖的最短路徑問題是求從源點(diǎn)到終點(diǎn)的最小代價(jià)路徑。 print（ ” least cost=’， u）； while （ leaf0） //輸出最優(yōu)解方案 {print（ leaf）； leaf=parent（ leaf）； } } 找最小成本的 LC分支 限界算法 框架 與 FIFO分支 限界算法 框架結(jié)構(gòu)大致相同 ， 只是擴(kuò)
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1