. 搜尋
搜尋（Search），設法在龐大狀態空間圖中找到目標。
主要分為兩類性質的搜尋：
基本搜尋，是一種沒有任何經驗和知識起作用的、由某種規則所確定的非智慧性的搜尋；
啟發式搜尋（Heuristic Search）：其特點在於是一種有準備的、追求效率而有的放矢的智慧搜尋，它要求依據某種知識及資訊的指導，透過逐一狀態比較而找到符合規定條件的目標狀態解。
2. 問題的狀態空間圖搜尋
問題的狀態空間可用有向圖來表達，又常稱其為狀態樹(State Tree)。圖中，節點Sk表示狀態，狀態之間的連線採用有向弧(Arc)，弧上標以運算元OK來表示狀態之間的轉換關係。
圖1 問題求解的狀態樹表示
用狀態空間法搜尋求解問題:
首先要把待求解的問題表示為狀態空間圖;
把問題的解表示為目標節點Sg。
求解就是要找到從根節點S0到達目標節點Sg的搜尋路徑。
狀態空間圖在計算機中有兩種儲存方式：一種是圖的顯式儲存，另一種是圖的隱式儲存。
3. 狀態空間表示法
狀態空間
狀態，描述某一類事物在不同時刻所處於的資訊狀況
操作，描述狀態之間的關係
問題的狀態空間可用一個三元序組來表示：
：問題的全部初始狀態的集合
：操作的集合
：目標狀態的集合
利用狀態空間圖求解的具體思路和步驟：
（1）設定狀態變數及確定值域；
（2）確定狀態組，分別列出初始狀態集和目標狀態集；
（3）定義並確定操作集；
（4）估計全部狀態空間數，並儘可能列出全部狀態空間或予以描述之；
（5）當狀態數量不是很大時，按問題的有序元組畫出狀態空間圖，依照狀態空間圖搜尋求解。
傳教士和野人問題（The Missionaries and Cannibals Problem）
在河的左岸有三個傳教士、一條船和三個野人，傳教士們想用這條船將所有的成員都運過河去，但是受到以下條件的限制：
① 教士和野人都會划船，但船一次最多隻能裝運兩個；
② ②在任何岸邊野人數目都不得超過傳教士，否則傳教士就會遭遇危險：被野人攻擊甚至被吃掉。
此外，假定野人會服從任何一種過河安排，試規劃出一個確保全部成員安全過河的計劃。
（1）設定狀態變數及確定值域。
為了建立這個問題的狀態空間，設左岸傳教士數為m，則
m ={0,1,2,3}；
對應右岸的傳教士數為3－m； 左岸的野人數為c，則有
c ={0,1,2,3}；
對應右岸野人數為3－c；左岸船數為b，故又有b={0,1}，右岸的船數為1－b.
（2）確定狀態組，分別列出初始狀態集和目標狀態集。
問題的狀態可以用一個三元陣列來描述，以左岸的狀態來標記，即
Sk =（m,c,b），
右岸的狀態可以不必標出。
初始狀態一個： S0 =（3,3,1），初始狀態表示全部成員在河的左岸；
目標狀態也只一個： Sg =（0,0,0），表示全部成員從河左岸渡河完畢。
（3）定義並確定操作集。
仍然以河的左岸為基點來考慮，把船從左岸划向右岸定義為Pij操作。其中,第一下標i表示船載的傳教士數, 第二下標j表示船載的野人數；同理，從右岸將船劃回左岸稱之為Qij操作，下標的定義同前。則共有10種操作，操作集為
F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}
（4）估計全部的狀態空間數，並儘可能列出全部的狀態空間或予以描述之。
在這個問題世界中，S0 =（3,3,1）為初始狀態，S31 = Sg =（0,0,0）為目標狀態。全部的可能狀態共有32個，如表所示。
表1 傳教士和野人問題的全部可能狀態
注意：按題目規定條件，應劃去非法狀態，從而加快搜索效率。
1）首先可以劃去左岸邊野人數目超過傳教士的情況，即S4、S8、S9、S20、S24、S25等6種狀態是不合法的；
2）應劃去右岸邊野人數目超過修道士的情況，即S6、S7、S11、S22、S23、S27等情況；
3）應劃去4種不可能出現狀態：劃去S15和S16——船不可能停靠在無人的岸邊；劃去S3——傳教士不可能在數量佔優勢的野人眼皮底下把船安全地劃回來；劃去S28——傳教士也不可能在數量佔優勢的野人眼皮底下把船安全地划向對岸。可見，在狀態空間中，真正符合題目規定條件的只有16個合理狀態。
根據上述分析，共有16個合法狀態和允許的操作，可以劃出傳教士和食人者問題的狀態空間圖，如圖所示。
圖2 傳教士和野人問題的狀態空間
任何一條從S0到達S31的路徑都是該問題的解。
. 搜尋
搜尋（Search），設法在龐大狀態空間圖中找到目標。
主要分為兩類性質的搜尋：
基本搜尋，是一種沒有任何經驗和知識起作用的、由某種規則所確定的非智慧性的搜尋；
啟發式搜尋（Heuristic Search）：其特點在於是一種有準備的、追求效率而有的放矢的智慧搜尋，它要求依據某種知識及資訊的指導，透過逐一狀態比較而找到符合規定條件的目標狀態解。
2. 問題的狀態空間圖搜尋
問題的狀態空間可用有向圖來表達，又常稱其為狀態樹(State Tree)。圖中，節點Sk表示狀態，狀態之間的連線採用有向弧(Arc)，弧上標以運算元OK來表示狀態之間的轉換關係。
圖1 問題求解的狀態樹表示
用狀態空間法搜尋求解問題:
首先要把待求解的問題表示為狀態空間圖;
把問題的解表示為目標節點Sg。
求解就是要找到從根節點S0到達目標節點Sg的搜尋路徑。
狀態空間圖在計算機中有兩種儲存方式：一種是圖的顯式儲存，另一種是圖的隱式儲存。
3. 狀態空間表示法
狀態空間
狀態，描述某一類事物在不同時刻所處於的資訊狀況
操作，描述狀態之間的關係
問題的狀態空間可用一個三元序組來表示：
：問題的全部初始狀態的集合
：操作的集合
：目標狀態的集合
利用狀態空間圖求解的具體思路和步驟：
（1）設定狀態變數及確定值域；
（2）確定狀態組，分別列出初始狀態集和目標狀態集；
（3）定義並確定操作集；
（4）估計全部狀態空間數，並儘可能列出全部狀態空間或予以描述之；
（5）當狀態數量不是很大時，按問題的有序元組畫出狀態空間圖，依照狀態空間圖搜尋求解。
傳教士和野人問題（The Missionaries and Cannibals Problem）
在河的左岸有三個傳教士、一條船和三個野人，傳教士們想用這條船將所有的成員都運過河去，但是受到以下條件的限制：
① 教士和野人都會划船，但船一次最多隻能裝運兩個；
② ②在任何岸邊野人數目都不得超過傳教士，否則傳教士就會遭遇危險：被野人攻擊甚至被吃掉。
此外，假定野人會服從任何一種過河安排，試規劃出一個確保全部成員安全過河的計劃。
（1）設定狀態變數及確定值域。
為了建立這個問題的狀態空間，設左岸傳教士數為m，則
m ={0,1,2,3}；
對應右岸的傳教士數為3－m； 左岸的野人數為c，則有
c ={0,1,2,3}；
對應右岸野人數為3－c；左岸船數為b，故又有b={0,1}，右岸的船數為1－b.
（2）確定狀態組，分別列出初始狀態集和目標狀態集。
問題的狀態可以用一個三元陣列來描述，以左岸的狀態來標記，即
Sk =（m,c,b），
右岸的狀態可以不必標出。
初始狀態一個： S0 =（3,3,1），初始狀態表示全部成員在河的左岸；
目標狀態也只一個： Sg =（0,0,0），表示全部成員從河左岸渡河完畢。
（3）定義並確定操作集。
仍然以河的左岸為基點來考慮，把船從左岸划向右岸定義為Pij操作。其中,第一下標i表示船載的傳教士數, 第二下標j表示船載的野人數；同理，從右岸將船劃回左岸稱之為Qij操作，下標的定義同前。則共有10種操作，操作集為
F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}
（4）估計全部的狀態空間數，並儘可能列出全部的狀態空間或予以描述之。
在這個問題世界中，S0 =（3,3,1）為初始狀態，S31 = Sg =（0,0,0）為目標狀態。全部的可能狀態共有32個，如表所示。
表1 傳教士和野人問題的全部可能狀態
注意：按題目規定條件，應劃去非法狀態，從而加快搜索效率。
1）首先可以劃去左岸邊野人數目超過傳教士的情況，即S4、S8、S9、S20、S24、S25等6種狀態是不合法的；
2）應劃去右岸邊野人數目超過修道士的情況，即S6、S7、S11、S22、S23、S27等情況；
3）應劃去4種不可能出現狀態：劃去S15和S16——船不可能停靠在無人的岸邊；劃去S3——傳教士不可能在數量佔優勢的野人眼皮底下把船安全地劃回來；劃去S28——傳教士也不可能在數量佔優勢的野人眼皮底下把船安全地划向對岸。可見，在狀態空間中，真正符合題目規定條件的只有16個合理狀態。
（5）當狀態數量不是很大時，按問題的有序元組畫出狀態空間圖，依照狀態空間圖搜尋求解。
根據上述分析，共有16個合法狀態和允許的操作，可以劃出傳教士和食人者問題的狀態空間圖，如圖所示。
圖2 傳教士和野人問題的狀態空間
任何一條從S0到達S31的路徑都是該問題的解。