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

DFS

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

BFS

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

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

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

迭代加深搜索 ID

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

迭代加寬搜索 IB

沒有太多接觸，無視……

A*

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

IDA*

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

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

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