搜索策略是什么
搜索是人工智能中的一個核心技術，是推理不可分割的一部分，它直接關系到智能系統的性能和運行效率。搜索問題中，主要的工作是找到正確的搜索策略。搜索策略反映了狀態空間或問題空間擴展的方法，也決定了狀態或問題的訪問順序。搜索策略的不同，人工智能中的搜索問題的命名也不同。
狀態空間的—般搜索過程
問題求解過程實際上是一個搜索過程。為了進行搜索，首先必須把問題用某種形式表示出來，其表示是否適當，將直接影響搜索效率。對一個確定的問題來說，與解題有關的狀態空間往往只是整個狀態空間的一部分。只要能生成并存儲這部分狀態空間，就可求得問題的解。在人工智能中通過運用搜索技術解決此問題的基本思想是：首先把問題的初始狀態（即初始節點）作為當前狀態，選擇適用的算符對其進行操作，生成一組子狀態（或后繼狀態、后繼節點、子節點），然后檢查目標狀態是否在其中出現。若出現，則搜索成功，找到了問題的解；若不出現，則按某種搜索策略從已生成的狀態中再選一個狀態作為當前狀態。重復上述過程，直到目標狀態出現或者不再有可供操作的狀態及算符時為止。
在搜索過程中，要建立兩個數據結構：OPEN 表和 CLOSED 表， OPEN 表用于存放剛生成的節點，對不同的策略，節點在此表中的排列順序是不同的。例如對寬度優先搜索，是將擴展節點 n 的子節點放入到 OPEN 表的尾部，而深度優先搜索是把節點的子節點放入到 OPEN 表的首部。CLOSED 表用于存放將要擴展或已擴展的節點（節點 n 的子節點）。所謂對一個節點進行擴展，是指用合適的算符對該節點進行操作，生成一組子節點。一個節點經一個算符操作后一般只生成一個子節點，但對一個可適用的算符可能有多個，故此時會生成一組子節點。需要注意的是：在這些子節點中，可能有些是當前擴展節點（即節點 n）的父節點、祖父節點等，此時不能把這些先輩節點作為當前擴展節點的子節點。
搜索的一般過程如下：
（1）把初始節點 S0 放入 OPEN 表中，并建立目前只包含 S0 的搜索圖 G。
（2）檢查 OPEN 表是否為空，若為空則問題無解，退出；否則進行下一步。
（3）把 OPEN 表的第一個節點取出放入 CLODED 表中，并記該節點為節點 n。
（4）考慮節點 n 是否為目標節點，若是，則求得了問題的解，退出，此解可從目標節點開始直到初始節點的返回指針中得到；否則，繼續下一步。
（5）擴展節點 n，若沒有后繼節點，則立即轉步驟（2）；否則生成一組子節點。把其中不是節點 n 先輩的那些子節點記作集合 M={mi}，并把這些子節點 mi 作為節點 n 的子節點加入 G 中。
（6）針對 M 中子節點 mi 的不同情況，分別進行如下處理：對于那些未曾在 G 中出現過的 mi 設置一個指向父節點（即節點 n）的指針，并把它們放入 OPEN 表中。對于那些先前已在 G 中出現過的 mi，確定是否需要修改它指向父節點的指針。對于那些先前已在 G 中出現并且已經擴展了的 mi，確定是否需要修改其后繼節點指向父節點的指針。
（7）按某種搜索策略對 OPEN 表中的節點進行排序。
（8）返回至第（2）步。
分類
寬度優先搜索策略
寬度優先搜索的基本思想是：從初始節點 S0 開始，逐層地對節點進行擴展并考察它是否為目標節點，在第 n 層的節點沒有全部擴展并考察之前，不對第 n+1 層的節點進行擴展。OPEN 表中的節點總是按進入的先后順序排列，先進入的節點排在前面，后進入的排在后面。其搜索過程如下。
（1）把初始節點 S0 放入 OPEN 表中。
（2）若 OPEN 表為空，則問題無解，退出。
（3）把 OPEN 表的第一個節點（記為節點 n）取出放入 CLOSED 表中。
（4）考察節點 n 是否為目標節點，若是，則問題解求得，退出。
（5）若節點 n 不可擴展，則轉步驟（2）。
（6）擴展節點 n，將其子節點放入 OPEN 表的尾部，并為每一個子節點配置指向父節點的指針，然后轉步驟（2）。
深度優先搜索策略
深度優先搜索的基本思想是：從初始節點 S0 開始擴展，若沒有得到目標節點，則選擇最后產生的子節點進行擴展，若還是不能到達目標節點，則再對剛才最后產生的子節點進行擴展，一直如此向下搜索。當到達某個子節點，且該子節點既不是目標節點又不能繼續擴展時，才選擇其兄弟節點進行考察。其搜索過程如下：
（1）初始節點 S0 放入 OPEN 表中。
（2）若 OPEN 表為空，則問題無解，退出。
（3）把 OPEN 表的第一個節點（記為節點 n）取出放入 CLOSED 表中。
（4）考察節點 n 是否為目標節點，若是，則問題解求得，退出。
（5）若節點 n 不可擴展，則轉步驟（2）。
（6）擴展節點 n，將其子節點放入 OPEN 表的首部，并為其配置指向父節點的指針，然后轉步驟（2）。
該過程與寬度優先搜索的惟一區別是：寬度優先搜索時將節點 n 的子節點放入到 OPEN 表的尾部，而深度優先搜索時把節點 n 的子節點放入到 OPEN 表的首部。僅此一點不同，就使得搜索的路線完全不一樣。
啟發式搜索策略
上述各種搜索策略的一個共同特點是它們的搜索路線是事先決定好的，沒有利用被求解問題的任何特征信息，在決定要被擴展的節點時，沒有考慮該節點到底是否可能出現在解的路徑上，也沒有考慮它是否有利于問題的求解以及所求的解是否為最優解，因而這樣的搜索策略都具有較大的盲目性。盲目搜索所需擴展的節點數目很大，產生的無用節點肯定就很多，效率就會較低。啟發式搜索法的基本思想是在搜索路徑的控制信息中增加關于被解問題的某些特征，用于指導搜索向最有希望到達目標結點的方向前進。它一般只要知道問題的部分狀態空間就可以求解該問題，搜索效率較高。
