圖的搜索算法(存儲(chǔ)版)
【正文】 bestx[i]=1) print(i，“，” )。 2）結(jié)點(diǎn)優(yōu)先級(jí)確定：優(yōu)先隊(duì)列中結(jié)點(diǎn)優(yōu)先級(jí)常規(guī)定為一個(gè)與該結(jié)點(diǎn)相關(guān)的數(shù)值 p，它一般表示其接近最優(yōu)解的程度，本例題就以當(dāng)前結(jié)點(diǎn)的所在分支的裝載上界為優(yōu)先值。其實(shí)看了下面的例子大家會(huì)發(fā)現(xiàn)，優(yōu)先隊(duì)列式擴(kuò)展結(jié)點(diǎn)的過(guò)程，一開(kāi)始實(shí)際是在進(jìn)行類似 “ 深度優(yōu)先 ” 的搜索。 返回首頁(yè) 7） 結(jié)點(diǎn) J變?yōu)?E結(jié)點(diǎn)，擴(kuò)展的層次為 4算法結(jié)束。 算法框架 上一小節(jié)的例子是求最大值的最優(yōu)化問(wèn)題 ， 下面我們以求找最小成本的最優(yōu)化問(wèn)題 ， 給出 FIFO分支搜索算法框架 。 初始化隊(duì)； ADDQ（ T）； //根結(jié)點(diǎn)入隊(duì) parent（ E） =0； //記錄擴(kuò)展路徑，當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn) while （隊(duì)不空） {DELETEQ(E) //隊(duì)首結(jié)點(diǎn)出隊(duì)為新的 E結(jié)點(diǎn)； for （ E的每個(gè)兒子 X） if (s（ X） u) //當(dāng)是可能的最優(yōu)解時(shí)入隊(duì) {ADD Q（ X） ； parent （ X ） =E。 print（ ” least cost=’， u）； while （ leaf0） //輸出最優(yōu)解方案 {print（ leaf）； leaf=parent（ leaf）； } } 找最小成本的 LC分支 限界算法 框架 與 FIFO分支 限界算法 框架結(jié)構(gòu)大致相同 ， 只是擴(kuò)展結(jié)點(diǎn)的順序不同 ， 因而存儲(chǔ)活結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不同 。 由于多段圖將頂點(diǎn)劃分為 k個(gè)互不相交的子集 ， 所以 ，多段圖劃分為 k段 ， 一旦某條路徑的一些段被確定后 ， 就可以并入這些信息并計(jì)算部分解的目標(biāo)函數(shù)值的下界 。 u=0。 上一頁(yè) 下一頁(yè) 在前面的例題中曾說(shuō)明 ， 優(yōu)先隊(duì)列的分支限界法更象是有選擇 、有目的地進(jìn)行深度優(yōu)先搜索 ， 時(shí)間效率 、 空間效率都是比較高的 。 利用動(dòng)態(tài)規(guī)劃法進(jìn)行算法設(shè)計(jì)時(shí) ，設(shè)計(jì)者在進(jìn)行算法設(shè)計(jì)前已經(jīng)用大腦自己構(gòu)造好了問(wèn)題的解空間 ，因此可以自底向上的遞推求解；而搜索算法是在搜索過(guò)程中根據(jù)一定規(guī)則自動(dòng)構(gòu)造 ， 并搜索解空間樹(shù)的 。如何協(xié)調(diào)好動(dòng)態(tài)規(guī)劃的高效率與高消費(fèi)之間的矛盾呢？有一種折衷的辦法就是記憶化搜索算法 記憶化限界搜索算法在求解時(shí)，還是按著自頂向下的順序，但是每求解一個(gè)狀態(tài)，就將它的解保存下來(lái)，以后再次遇到這個(gè)狀態(tài)的時(shí)候，就不必重新求解了。 。 一般說(shuō)來(lái)，動(dòng)態(tài)規(guī)劃算法在時(shí)間效率上的優(yōu)勢(shì)是搜索無(wú)法比擬的，但動(dòng)態(tài)規(guī)劃總要遍歷所有的狀態(tài)，而搜索可以排除一些無(wú)效狀態(tài)。 動(dòng)態(tài)規(guī)劃要求階段決策具有無(wú)后向性 ， 而搜索算法沒(méi)有此限止 。 僅就對(duì)限界剪支的效率而言 ， 優(yōu)先隊(duì)列的分支限界法顯然要更充分一些 。 相對(duì)而言，分支限界算法的解空間比回溯法大得多， 因此當(dāng)內(nèi)存容量有限時(shí)，回溯法成功的可能性更大。 廣度優(yōu)先搜索算法，一般需存儲(chǔ)產(chǎn)生的所有結(jié)點(diǎn)，占用的存儲(chǔ)空間要比深度優(yōu)先搜索大得多，因此，程序設(shè)計(jì)中，必須考慮溢出和節(jié)省內(nèi)存空間的問(wèn)題。 i++) x[i]=0。 把每一段最小的代價(jià)相加 ， 可以得到一個(gè)非常簡(jiǎn)單的下界 ， 其路徑長(zhǎng)度為 2+4+5+3=14。 search（ T） //為找出最小成本答案結(jié)點(diǎn)檢索 T。 返回首頁(yè) 5） 結(jié)點(diǎn) C變?yōu)?E結(jié)點(diǎn)擴(kuò)充 F入堆， bestw仍為 40； 結(jié)點(diǎn) G的裝載上界為 50 bestw，也入堆；此時(shí)堆中 E上界為 60為優(yōu)先隊(duì)列首。 FIFO限界搜索過(guò)程為： 上一頁(yè) 3）不同與算法 2，由于擴(kuò)展結(jié)點(diǎn)不是按層進(jìn)行的計(jì)算結(jié)點(diǎn)的所在分支的裝載上界時(shí)，要用數(shù)組變量 r記錄當(dāng)前層以下的最大重量，這樣可以隨時(shí)方便使用各層結(jié)點(diǎn)的裝載上界。 } 1）結(jié)點(diǎn)擴(kuò)展方式：無(wú)論那種分支限界法，都需要有一張活結(jié)點(diǎn)表。 for(i=1。若有的話，找出該方法 FIFO限界搜索算法 優(yōu)先隊(duì)列式分支限界法 上一頁(yè) 選擇下一個(gè) E節(jié)點(diǎn)的方式不同導(dǎo)致幾種不同的分支搜索方式： 1． FIFO搜索
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1