某些問題可以看作是在解空間中搜索答案的一個過程，比如從A地到B地尋找最短路徑。通常會把路徑用表示為樹，採用兩種方式遍歷樹中的節點，
深度優先和廣度優先。深度優先就是先順著一條路走到頭，如果沒有找到就往回走（回溯），再換另外一條路；廣度優先就是一層一層的遍歷樹的節點，像螃蟹一樣橫著走。尋找最短路徑最直接的方法就是每一條路去試，所有的路都走過了肯定能夠找到最短的一條，這就是大英博物館算法（蠻力遍歷法），也是入門小鳥們最常用的方法，這種方法的優點是肯定能夠找到最短的那條路徑，缺點是如果路徑中的節點很多則耗費的時間太長，路徑數可能隨節點數指數增長，那麼就想到有沒有優化的算法。根據兩種遍歷方式，有兩種優化的算法。首先是基於深度優先的爬山算法，爬山算法是總是選擇離終點比較近的一條路走，就像爬山的時候尋找最快的方式上山一樣，但是這種方法可能會導致我們走到了一個小山包上朝哪個方向走都是下山，或者走到了小平臺上梯度消失，或者走在了山脊上導致周圍梯度都是下山但的誤判；其次是廣度優先算法的束搜索算法，就是會限制廣度優先的時候橫著走的寬度不是一層，而是這一層中最有可能成為最短路徑的一部分節點，這個寬度就是束，也是這個算法叫做束搜索的原因；第三是 分支限界算法，分支限界算法是廣度優先算法的另一種優化，在遍歷節點的時候計算每個節點對終點的距離下界，然後選擇下界最小的進行深度的遍歷；最後是A*算法，A*算法是分支限界算法的優化，它加入了對已訪問節點列表，對於已訪問過的節點不再計算，這樣可以減少很大一部分重複的計算，達到優化的目標。常見的搜索算法都在這裡了，大家要知道搜索問題就是在問題的解空間中找到最優或者近似最優的部分，這個解空間往往可以用樹結構來表達，所以搜索的基礎都是基於樹的深度或者廣度優先遍歷，沒有優化過的搜索就是大英博物館搜索，而不同的優化方式產生了不同的搜索算法，各種算法之間的區別在於引入某種先驗以減少檢索分支的數量或者去除冗餘分支以提高搜索的效率。
分享到:
