圖的搜索算法-資料下載頁
2025-07-25 03:44本頁面
【正文】 方法。 廣度優(yōu)先搜索算法，一般需存儲產(chǎn)生的所有結點，占用的存儲空間要比深度優(yōu)先搜索大得多，因此，程序設計中，必須考慮溢出和節(jié)省內存空間的問題。但廣度優(yōu)先搜索法一般無回溯操作，即入棧和出棧的操作，所以運行速度比深度優(yōu)先搜索要快些。 上一頁 下一頁 返回首頁 2. 2．回溯與分支限界法 回溯法以深度優(yōu)先的方式搜索解空間樹 T，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹 T。 由于它們在問題的解空間樹 T上搜索的方法不同，適合解決的問題也就不同。一般情況下，回溯法的求解目標是找出 T中滿足約束條件的所有解的方案，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使用某一目標函數(shù)值達到極大或極小的解，即在某種意義下的最優(yōu)解。 相對而言，分支限界算法的解空間比回溯法大得多， 因此當內存容量有限時，回溯法成功的可能性更大。 下表列出了回溯法和分支限界法的一些區(qū)別： 上一頁 下一頁 返回首頁 3. 上一頁 下一頁 返回首頁 4. 在處理最優(yōu)問題時 ， 采用窮舉法 、 回溯法或分支限界法都可以通過利用當前最優(yōu)解和上界函數(shù)加速 。 僅就對限界剪支的效率而言 ， 優(yōu)先隊列的分支限界法顯然要更充分一些 。 在窮舉法中通過上界函數(shù)與當前情況下函數(shù)值的比較可以直接略過不合要求的情況而省去了更進一步的枚舉和判斷；回溯法則因為層次的劃分 ，可以在上界函數(shù)值小于當前最優(yōu)解時 ， 剪去以該結點為根的子樹 ，也就是節(jié)省了搜索范圍；分支限界法在這方面除了可以做到回溯法能做到的之外 ， 同時若采用優(yōu)先隊列的分支限界法 ， 用上界函數(shù)作為活結點的優(yōu)先級 ， 一旦有葉結點成為當前擴展結點 ， 就意味著該葉結點所對應的解即為最優(yōu)解 ， 可以立即終止其余的過程 。在前面的例題中曾說明 ， 優(yōu)先隊列的分支限界法更象是有選擇 、有目的地進行深度優(yōu)先搜索 ， 時間效率 、 空間效率都是比較高的 。 上一頁 下一頁 返回首頁 5. 3．動態(tài)規(guī)劃與搜索算法 撇開時空效率的因素不談 ， 在解決最優(yōu)化問題的算法中 ， 搜索可以說是 “ 萬能 ” 的 。 所以動態(tài)規(guī)劃可以解決的問題 ， 搜索也一定可以解決 。 動態(tài)規(guī)劃要求階段決策具有無后向性 ， 而搜索算法沒有此限止 。 動態(tài)規(guī)劃是自底向上的遞推求解 ， 而無論深度優(yōu)先搜索或廣度優(yōu)先搜索都是自頂向下求解 。 利用動態(tài)規(guī)劃法進行算法設計時 ，設計者在進行算法設計前已經(jīng)用大腦自己構造好了問題的解空間 ，因此可以自底向上的遞推求解；而搜索算法是在搜索過程中根據(jù)一定規(guī)則自動構造 ， 并搜索解空間樹的 。 由于在很多情況下 ， 問題的解空間太復雜用大腦構造有一定困難 ， 仍然需要采用搜索算法 。 上一頁 下一頁 返回首頁 另外動態(tài)規(guī)劃在遞推求解過程中，需要用數(shù)組存儲有關信息，而數(shù)組的下標只能是整數(shù)，所以要求問題中相關的數(shù)據(jù)必須為整數(shù)（如 【 例 2】 “資源分配問題 ” 中的資金就必須為整數(shù)），對于這類信息非整數(shù)或不便于轉換為整數(shù)的問題，同樣需要采用搜索算法。 一般說來，動態(tài)規(guī)劃算法在時間效率上的優(yōu)勢是搜索無法比擬的，但動態(tài)規(guī)劃總要遍歷所有的狀態(tài)，而搜索可以排除一些無效狀態(tài)。更重要的是搜索還可以剪枝，可能剪去大量不必要的狀態(tài)，因此在空間開銷上往往比動態(tài)規(guī)劃要低很多。如何協(xié)調好動態(tài)規(guī)劃的高效率與高消費之間的矛盾呢？有一種折衷的辦法就是記憶化搜索算法 記憶化限界搜索算法在求解時，還是按著自頂向下的順序，但是每求解一個狀態(tài)，就將它的解保存下來，以后再次遇到這個狀態(tài)的時候，就不必重新求解了。這種方法綜合了搜索和動態(tài)規(guī)劃兩方面的優(yōu)點，因而還是很有實用價值的。記憶化限界搜索。它以搜索算法為核心，只不過使用 “ 記錄求過的狀態(tài) ”的辦法，來避免重復搜索，這樣，記憶化搜索的每一步，也可以對應到動態(tài)規(guī)劃算法中去。記憶化搜索有優(yōu)化方便、調試容易、思維直觀的優(yōu)點，但是效率上比循環(huán)的動態(tài)規(guī)劃差一個常數(shù)，但是時間和空間復雜度是同一數(shù)量級的（盡管空間上也差一個常數(shù)，那就是堆?？臻g）。當 n比較小的時候，我們可以忽略這個常數(shù)，從而記憶化搜索可以和動態(tài)規(guī)劃達到完全相同的效果。
黨政相關相關推薦
鄂ICP備17016276號-1