搜索策略

問題求解過程實際上是一個搜索過程。為了進行搜索，首先必須把問題用某種形式表示出來，其表示是否適當，將直接影響搜索效率。對一個確定的問題來説，與解題有關的狀態空間往往只是整個狀態空間的一部分。只要能生成並存儲這部分狀態空間，就可求得問題的解。在人工智能中通過運用搜索技術解決此問題的基本思想是：首先把問題的初始狀態（即初始節點）作為當前狀態，選擇適用的算符對其進行操作，生成一組子狀態（或後繼狀態、後繼節點、子節點），然後檢查目標狀態是否在其中出現。若出現，則搜索成功，找到了問題的解；若不出現，則按某種搜索策略從已生成的狀態中再選一個狀態作為當前狀態。重複上述過程，直到目標狀態出現或者不再有可供操作的狀態及算符時為止。

在搜索過程中，要建立兩個數據結構：OPEN表和 CLOSED表， OPEN表用於存放剛生成的節點，對不同的策略，節點在此表中的排列順序是不同的。例如對寬度優先搜索，是將擴展節點n的子節點放入到OPEN表的尾部，而深度優先搜索是把節點的子節點放入到OPEN表的首部。CLOSED表用於存放將要擴展或已擴展的節點（節點n的子節點）。所謂對一個節點進行擴展，是指用合適的算符對該節點進行操作，生成一組子節點。一個節點經一個算符操作後一般只生成一個子節點，但對一個可適用的算符可能有多個，故此時會生成一組子節點。需要注意的是：在這些子節點中，可能有些是當前擴展節點（即節點n）的父節點、祖父節點等，此時不能把這些先輩節點作為當前擴展節點的子節點。

搜索的一般過程如下：

（1）把初始節點S₀放入OPEN表中，並建立目前只包含S₀的搜索圖G。

（2）檢查OPEN表是否為空，若為空則問題無解，退出；否則進行下一步。

（3）把OPEN表的第一個節點取出放入CLODED表中，並記該節點為節點n。

（4）考慮節點n是否為目標節點，若是，則求得了問題的解，退出，此解可從目標節點開始直到初始節點的返回指針中得到；否則，繼續下一步。

（5）擴展節點n，若沒有後繼節點，則立即轉步驟（2）；否則生成一組子節點。把其中不是節點n先輩的那些子節點記作集合M={m_i}，並把這些子節點m_i作為節點n的子節點加入G中。

（6）針對M中子節點m_i的不同情況，分別進行如下處理：對於那些未曾在G中出現過的m_i設置一個指向父節點（即節點n）的指針，並把它們放入OPEN表中。對於那些先前已在G中出現過的m_i，確定是否需要修改它指向父節點的指針。對於那些先前已在G中出現並且已經擴展了的m_i，確定是否需要修改其後繼節點指向父節點的指針。

（7）按某種搜索策略對OPEN表中的節點進行排序。

（8）返回至第（2）步。

寬度優先搜索的基本思想是：從初始節點S₀開始，逐層地對節點進行擴展並考察它是否為目標節點，在第n層的節點沒有全部擴展並考察之前，不對第n+1層的節點進行擴展。OPEN表中的節點總是按進入的先後順序排列，先進入的節點排在前面，後進入的排在後面。其搜索過程如下。

（1）把初始節點S₀放入OPEN表中。

（2）若OPEN表為空，則問題無解，退出。

（3）把OPEN表的第一個節點（記為節點n）取出放入CLOSED表中。

（4）考察節點n是否為目標節點，若是，則問題解求得，退出。

（5）若節點n不可擴展，則轉步驟（2）。

（6）擴展節點n，將其子節點放入OPEN表的尾部，併為每一個子節點配置指向父節點的指針，然後轉步驟（2）。

深度優先搜索的基本思想是：從初始節點S₀開始擴展，若沒有得到目標節點，則選擇最後產生的子節點進行擴展，若還是不能到達目標節點，則再對剛才最後產生的子節點進行擴展，一直如此向下搜索。當到達某個子節點，且該子節點既不是目標節點又不能繼續擴展時，才選擇其兄弟節點進行考察。其搜索過程如下：

（1）初始節點S₀放入OPEN表中。

（2）若OPEN表為空，則問題無解，退出。

（3）把OPEN表的第一個節點（記為節點n）取出放入CLOSED表中。

（4）考察節點n是否為目標節點，若是，則問題解求得，退出。

（5）若節點n不可擴展，則轉步驟（2）。

（6）擴展節點n，將其子節點放入OPEN表的首部，併為其配置指向父節點的指針，然後轉步驟（2）。

該過程與寬度優先搜索的惟一區別是：寬度優先搜索時將節點n的子節點放入到OPEN表的尾部，而深度優先搜索時把節點n的子節點放入到OPEN表的首部。僅此一點不同，就使得搜索的路線完全不一樣。 ^[1] 

上述各種搜索策略的一個共同特點是它們的搜索路線是事先決定好的，沒有利用被求解問題的任何特徵信息，在決定要被擴展的節點時，沒有考慮該節點到底是否可能出現在解的路徑上，也沒有考慮它是否有利於問題的求解以及所求的解是否為最優解，因而這樣的搜索策略都具有較大的盲目性。盲目搜索所需擴展的節點數目很大，產生的無用節點肯定就很多，效率就會較低。啓發式搜索法的基本思想是在搜索路徑的控制信息中增加關於被解問題的某些特徵，用於指導搜索向最有希望到達目標結點的方向前進。它一般只要知道問題的部分狀態空間就可以求解該問題，搜索效率較高。 ^[2]