圖的搜索算法小結(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ù)就是解空間樹的深度，因此它占用空間較少。所以，當(dāng)搜索樹的結(jié)點(diǎn)較多，用其它方法易產(chǎn)生內(nèi)存溢出時(shí)，深度優(yōu)先搜索不失為一種有效的求解方法。
　　廣度優(yōu)先搜索算法，一般需存儲(chǔ)產(chǎn)生的所有結(jié)點(diǎn)，占用的存儲(chǔ)空間要比深度優(yōu)先搜索大得多，因此，程序設(shè)計(jì)中，必須考慮溢出和節(jié)省內(nèi)存空間的問題。但廣度優(yōu)先搜索法一般無回溯操作，即入棧和出棧的操作，所以運(yùn)行速度比深度優(yōu)先搜索要快些。

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ū)別：

　　在處理最優(yōu)問題時(shí)，采用窮舉法、回溯法或分支限界法都可以通過利用當(dāng)前最優(yōu)解和上界函數(shù)加速。僅就對(duì)限界剪支的效率而言，優(yōu)先隊(duì)列的分支限界法顯然要更充分一些。在窮舉法中通過上界函數(shù)與當(dāng)前情況下函數(shù)值的比較可以直接略過不合要求的情況而省去了更進(jìn)一步的枚舉和判斷；回溯法則因?yàn)閷哟蔚膭澐?#xff0c;可以在上界函數(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í)間效率、空間效率都是比較高的。

?

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ù)（如4.5.3節(jié)【例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ù)，那就是堆棧空間）。當(dāng)n比較小的時(shí)候，我們可以忽略這個(gè)常數(shù)，從而記憶化搜索可以和動(dòng)態(tài)規(guī)劃達(dá)到完全相同的效果。

?

轉(zhuǎn)載于:https://www.cnblogs.com/gd-luojialin/p/10384924.html

總結(jié)

以上是生活随笔為你收集整理的19图的搜索算法总结与比较的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。