最近一段時(shí)間仔細(xì)地學(xué)習(xí)了搜索方面的書籍，對搜索有了一些新的體會(huì)。搜索的算法有很多，從最簡單的DFS、BFS，到稍稍有點(diǎn)優(yōu)化的迭代加深、迭代加寬，再到A*、IDA*……感覺對于搜索的學(xué)習(xí)和運(yùn)用，絕對不能只局限于這些常用的方法中，而應(yīng)該對各個(gè)方法有一個(gè)整體的把握，分析各種方法的優(yōu)點(diǎn)和缺點(diǎn)，學(xué)會(huì)比較各種方法的時(shí)空性能，針對題目的特點(diǎn)入手。

DFS

最常用的一種搜索方法，幾乎學(xué)過搜索的都會(huì)。適用于搜索的深度已知，比較適合搜索全部解。常用的優(yōu)化方法是在結(jié)點(diǎn)擴(kuò)展時(shí)加入剪枝策略。

BFS

相對與DFS可能用得少了點(diǎn)，但也是必會(huì)的基本方法。如果搜索的深度不知，DFS可能陷入死循環(huán)，同時(shí)，如果空間上可以承受，這時(shí)候可以考慮BFS。側(cè)重尋求最優(yōu)解。

雙向廣度優(yōu)先搜索

適用于知道目標(biāo)狀態(tài)，每次擴(kuò)展兩個(gè)結(jié)點(diǎn)，但不一定非要是交替擴(kuò)展，擴(kuò)展方式很多。如果目標(biāo)狀態(tài)始終不變，而有多個(gè)初始狀態(tài)，就可以“周界搜索”。要注意的是，如何判斷已經(jīng)擴(kuò)展結(jié)點(diǎn)是否在另一端的方法，是需要認(rèn)真考慮，選取最優(yōu)判斷方法的。

迭代加深搜索 ID

每次限制搜索的深度，找到解就停止，否則加大深度再次搜索。相對于DFS不會(huì)陷入死循環(huán)，相對于BFS不會(huì)在空間上有壓力，也可以用來尋求最優(yōu)解，不過缺點(diǎn)是重復(fù)搜索。

迭代加寬搜索 IB

沒有太多接觸，無視……

A*

按f(s)的值擴(kuò)展結(jié)點(diǎn)，是一種啟發(fā)式搜索。需要兩個(gè)表，每次判斷是否在表1中、是否在表二中、同時(shí)在表一表二中，判斷f(s)和f(s')的大小，選擇是否替換。其中f(s)=g(s)+h(s)，h(s)為估價(jià)函數(shù)。要求h函數(shù)相容，對于這種說法，我自己的理解就是，狀態(tài)每轉(zhuǎn)移一次，h減少量最多為1。A*算法求得的第一個(gè)解必是最優(yōu)解。缺點(diǎn)依然是空間需求太大。

IDA*

迭代加深的A*。每次搜索加上一個(gè)深度限制，擴(kuò)展的時(shí)候判斷最好情況是否會(huì)超過深度，也算是一種極端法的剪枝思想。適用與深度不定，最優(yōu)解的深度又不一定很深，而狀態(tài)轉(zhuǎn)移的方式又有很多，使得狀態(tài)空間無法承受。

關(guān)于剪枝：1、可行性剪枝 2、最優(yōu)性剪枝

具體操作時(shí)：1、極端法 2、數(shù)學(xué)方法