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