1. 搜索

搜索（Search），設(shè)法在龐大狀態(tài)空間圖中找到目標(biāo)。

主要分為兩類性質(zhì)的搜索：

• 基本搜索，是一種沒有任何經(jīng)驗(yàn)和知識起作用的、由某種規(guī)則所確定的非智能性的搜索；
• 啟發(fā)式搜索（Heuristic Search）：其特點(diǎn)在于是一種有準(zhǔn)備的、追求效率而有的放矢的智能搜索，它要求依據(jù)某種知識及信息的指導(dǎo)，通過逐一狀態(tài)比較而找到符合規(guī)定條件的目標(biāo)狀態(tài)解。

2. 問題的狀態(tài)空間圖搜索

問題的狀態(tài)空間可用有向圖來表達(dá)，又常稱其為狀態(tài)樹(State Tree)。圖中，節(jié)點(diǎn)Sk表示狀態(tài)，狀態(tài)之間的連接采用有向弧(Arc)，弧上標(biāo)以操作數(shù)OK來表示狀態(tài)之間的轉(zhuǎn)換關(guān)系。

圖1 問題求解的狀態(tài)樹表示

用狀態(tài)空間法搜索求解問題:

首先要把待求解的問題表示為狀態(tài)空間圖;

把問題的解表示為目標(biāo)節(jié)點(diǎn)Sg。

求解就是要找到從根節(jié)點(diǎn)S0到達(dá)目標(biāo)節(jié)點(diǎn)Sg的搜索路徑。

狀態(tài)空間圖在計(jì)算機(jī)中有兩種存儲(chǔ)方式：一種是圖的顯式存儲(chǔ)，另一種是圖的隱式存儲(chǔ)。

3. 狀態(tài)空間表示法

狀態(tài)空間

狀態(tài)，描述某一類事物在不同時(shí)刻所處于的信息狀況

操作，描述狀態(tài)之間的關(guān)系

問題的狀態(tài)空間可用一個(gè)三元序組來表示：

：問題的全部初始狀態(tài)的集合

：操作的集合

：目標(biāo)狀態(tài)的集合

利用狀態(tài)空間圖求解的具體思路和步驟：

（1）設(shè)定狀態(tài)變量及確定值域；

（2）確定狀態(tài)組，分別列出初始狀態(tài)集和目標(biāo)狀態(tài)集；

（3）定義并確定操作集；

（4）估計(jì)全部狀態(tài)空間數(shù)，并盡可能列出全部狀態(tài)空間或予以描述之；

（5）當(dāng)狀態(tài)數(shù)量不是很大時(shí)，按問題的有序元組畫出狀態(tài)空間圖，依照狀態(tài)空間圖搜索求解。

傳教士和野人問題（The Missionaries and Cannibals Problem）

在河的左岸有三個(gè)傳教士、一條船和三個(gè)野人，傳教士們想用這條船將所有的成員都運(yùn)過河去，但是受到以下條件的限制：

① 教士和野人都會(huì)劃船，但船一次最多只能裝運(yùn)兩個(gè)；

② ②在任何岸邊野人數(shù)目都不得超過傳教士，否則傳教士就會(huì)遭遇危險(xiǎn)：被野人攻擊甚至被吃掉。

此外，假定野人會(huì)服從任何一種過河安排，試規(guī)劃出一個(gè)確保全部成員安全過河的計(jì)劃。

（1）設(shè)定狀態(tài)變量及確定值域。

為了建立這個(gè)問題的狀態(tài)空間，設(shè)左岸傳教士數(shù)為m，則

m ={0,1,2,3}；

對應(yīng)右岸的傳教士數(shù)為3－m； 左岸的野人數(shù)為c，則有

c ={0,1,2,3}；

對應(yīng)右岸野人數(shù)為3－c；左岸船數(shù)為b，故又有b={0,1}，右岸的船數(shù)為1－b.

（2）確定狀態(tài)組，分別列出初始狀態(tài)集和目標(biāo)狀態(tài)集。

問題的狀態(tài)可以用一個(gè)三元數(shù)組來描述，以左岸的狀態(tài)來標(biāo)記，即

Sk =（m,c,b），

右岸的狀態(tài)可以不必標(biāo)出。

初始狀態(tài)一個(gè)： S0 =（3,3,1），初始狀態(tài)表示全部成員在河的左岸；

目標(biāo)狀態(tài)也只一個(gè)： Sg =（0,0,0），表示全部成員從河左岸渡河完畢。

（3）定義并確定操作集。

仍然以河的左岸為基點(diǎn)來考慮，把船從左岸劃向右岸定義為Pij操作。其中,第一下標(biāo)i表示船載的傳教士數(shù), 第二下標(biāo)j表示船載的野人數(shù)；同理，從右岸將船劃回左岸稱之為Qij操作，下標(biāo)的定義同前。則共有10種操作，操作集為

F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}

（4）估計(jì)全部的狀態(tài)空間數(shù)，并盡可能列出全部的狀態(tài)空間或予以描述之。

在這個(gè)問題世界中，S0 =（3,3,1）為初始狀態(tài)，S31 = Sg =（0,0,0）為目標(biāo)狀態(tài)。全部的可能狀態(tài)共有32個(gè)，如表所示。

表1 傳教士和野人問題的全部可能狀態(tài)

注意：按題目規(guī)定條件，應(yīng)劃去非法狀態(tài)，從而加快搜索效率。

1）首先可以劃去左岸邊野人數(shù)目超過傳教士的情況，即S4、S8、S9、S20、S24、S25等6種狀態(tài)是不合法的；

2）應(yīng)劃去右岸邊野人數(shù)目超過修道士的情況，即S6、S7、S11、S22、S23、S27等情況；

3）應(yīng)劃去4種不可能出現(xiàn)狀態(tài)：劃去S15和S16——船不可能停靠在無人的岸邊；劃去S3——傳教士不可能在數(shù)量占優(yōu)勢的野人眼皮底下把船安全地劃回來；劃去S28——傳教士也不可能在數(shù)量占優(yōu)勢的野人眼皮底下把船安全地劃向?qū)Π丁？梢?，在狀態(tài)空間中，真正符合題目規(guī)定條件的只有16個(gè)合理狀態(tài)。

（5）當(dāng)狀態(tài)數(shù)量不是很大時(shí)，按問題的有序元組畫出狀態(tài)空間圖，依照狀態(tài)空間圖搜索求解。

根據(jù)上述分析，共有16個(gè)合法狀態(tài)和允許的操作，可以劃出傳教士和食人者問題的狀態(tài)空間圖，如圖所示。

圖2 傳教士和野人問題的狀態(tài)空間

任何一條從S0到達(dá)S31的路徑都是該問題的解。

參考文獻(xiàn)：

[1] 李長河. 人工智能及其應(yīng)用. 北京: 機(jī)械工業(yè)大學(xué)出版社, 2006.8