圖的搜索算法-閱讀頁
2024-08-13 03:44本頁面
【正文】 ， 第 i段頂點 , 第 i+1段頂點 lb)，在搜索過程中表 PT和表 ST的狀態(tài)如下： (b) 擴展結(jié)點 3后的狀態(tài) (d) 擴展結(jié)點 5后的狀態(tài) ， 最優(yōu)解為 0→ 3→ 5→ 8→ 9 多段圖的最短路徑問題最優(yōu)解的確定 (1,0,216) (1,0,315) (1,0,216) (2,2,416) (2,2,518) (2,2,618) (1,0,315) (2,2,416) (2,2,518) (2,2,618) (2,3,516) (2,3,618) (1,0,315) (1,0,216) (2,2,416) (2,2,518) (2,2,618) (2,3,618) (3,5,816) (1,0,315) (1,0,216) (2,3,516) (a) 擴展根結(jié)點后的狀態(tài) PT ST ST PT (c) 擴展結(jié)點 4后的狀態(tài) ST ST 回溯過程是： (3,5, 816)→( 2,3, 516)→( 1,0, 315)。 i=k。 4． i=1。 //求解第 i段 5． while (i=1) 對頂點 u的所有鄰接點 v 根據(jù)式 lb。 將表 PT中目標函數(shù)值超出 up的結(jié)點刪除； u=表 PT中 lb最小的結(jié)點的 v值； i=表 PT中 lb最小的結(jié)點的 i值； i++。所以，當搜索樹的結(jié)點較多，用其它方法易產(chǎn)生內(nèi)存溢出時，深度優(yōu)先搜索不失為一種有效的求解方法。但廣度優(yōu)先搜索法一般無回溯操作，即入棧和出棧的操作，所以運行速度比深度優(yōu)先搜索要快些。 下一頁 2. 2．回溯與分支限界法 回溯法以深度優(yōu)先的方式搜索解空間樹 T，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹 T。一般情況下，回溯法的求解目標是找出 T中滿足約束條件的所有解的方案，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使用某一目標函數(shù)值達到極大或極小的解，即在某種意義下的最優(yōu)解。 下表列出了回溯法和分支限界法的一些區(qū)別： 上一頁 返回首頁 下一頁 4. 在處理最優(yōu)問題時 ， 采用窮舉法 、 回溯法或分支限界法都可以通過利用當前最優(yōu)解和上界函數(shù)加速 。 在窮舉法中通過上界函數(shù)與當前情況下函數(shù)值的比較可以直接略過不合要求的情況而省去了更進一步的枚舉和判斷；回溯法則因為層次的劃分 ，可以在上界函數(shù)值小于當前最優(yōu)解時 ， 剪去以該結(jié)點為根的子樹 ，也就是節(jié)省了搜索范圍；分支限界法在這方面除了可以做到回溯法能做到的之外 ， 同時若采用優(yōu)先隊列的分支限界法 ， 用上界函數(shù)作為活結(jié)點的優(yōu)先級 ， 一旦有葉結(jié)點成為當前擴展結(jié)點 ， 就意味著該葉結(jié)點所對應的解即為最優(yōu)解 ， 可以立即終止其余的過程 。 上一頁 返回首頁 所以動態(tài)規(guī)劃可以解決的問題 ， 搜索也一定可以解決 。 動態(tài)規(guī)劃是自底向上的遞推求解 ， 而無論深度優(yōu)先搜索或廣度優(yōu)先搜索都是自頂向下求解 。 由于在很多情況下 ， 問題的解空間太復雜用大腦構(gòu)造有一定困難 ， 仍然需要采用搜索算法 。 下一頁 另外動態(tài)規(guī)劃在遞推求解過程中，需要用數(shù)組存儲有關(guān)信息，而數(shù)組的下標只能是整數(shù)，所以要求問題中相關(guān)的數(shù)據(jù)必須為整數(shù)（如 【 例 2】 “資源分配問題 ” 中的資金就必須為整數(shù)），對于這類信息非整數(shù)或不便于轉(zhuǎn)換為整數(shù)的問題，同樣需要采用搜索算法。更重要的是搜索還可以剪枝，可能剪去大量不必要的狀態(tài)，因此在空間開銷上往往比動態(tài)規(guī)劃要低很多。這種方法綜合了搜索和動態(tài)規(guī)劃兩方面的優(yōu)點，因而還是很有實用價值的。它以搜索算法為核心，只不過使用 “ 記錄求過的狀態(tài) ”的辦法，來避免重復搜索，這樣，記憶化搜索的每一步，也可以對應到動態(tài)規(guī)劃算法中去。當 n比較小的時候，我們可以忽略這個常數(shù)，從而記憶化搜索可以和動態(tài)規(guī)劃達到完全相同的效
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1