人工智能教程習(xí)題及答案第2章習(xí)題參考解答

1、 第二章知識表示習(xí)題參考解答2.3練習(xí)題什么是知識?它有哪些特性?有哪幾種分類方法?何謂知識表示?陳述性知識表示法與過程性知識表示法的區(qū)別是什么?在選擇知識的表示方法時，應(yīng)該考慮哪些主要因素?一階謂詞邏輯表示法適合于表示哪種類型的知識?它有哪些特點?請寫出用一階謂詞邏輯表示法表示知識的步驟。設(shè)有下列語句，請用相應(yīng)的謂詞公式把它們表示出來：（1）有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花。（2）他每天下午都去玩足球。（3）太原市的夏天既干燥又炎熱。（4）所有人都有飯吃。（5）喜歡玩籃球的人必喜歡玩排球。（6）要想出國留學(xué)，必須通過外語考試。房內(nèi)有一只猴子、一個箱子，天花板上掛了一

2、串香蕉，其位置關(guān)系如圖2.11所示，猴子為了拿到香蕉，它必須把箱子推到香蕉下面，然后再爬到箱子上。請定義必要的謂詞寫出問題的初始狀態(tài)（即圖2.16所示的狀態(tài)）、目標(biāo)狀態(tài)（猴子拿到了香蕉，站在箱子上箱子位于位置b）。h圖2.11猴子摘香蕉問題對習(xí)題2.7中的猴子摘香蕉問題，利用一階謂詞邏輯表述一個行動規(guī)劃，使問題從初始狀態(tài)變化到目標(biāo)狀態(tài)。2.9產(chǎn)生式的基本形式是什么？它與謂詞邏輯中的蘊含式有什么共同處及不同處？2.10何謂產(chǎn)生式系統(tǒng)？它由哪幾部分組成？2.11產(chǎn)生式系統(tǒng)中，推理機的推理方式有哪幾種？在產(chǎn)生式推理過程中，如果發(fā)生策略沖突，如何解決？2.12設(shè)有下列八數(shù)碼難題：在一個3X3的方框內(nèi)放

3、有8個編號的小方塊，緊鄰空位的小方塊可以移入到空位上，通過平移小方塊可將某一布局變換為另一布局(如圖2.12所示)。請用產(chǎn)生式規(guī)則表示移動小方塊的操作。匚S0匚二Sg圖2.13習(xí)題2.13的圖圖2.12習(xí)題2.12的圖2.13推銷員旅行問題：設(shè)有五個相互可直達且距離已知的城市A、B、C、D、E,如圖2.13所示，推銷員從城市A出發(fā)，去其它四城市各旅行一次，最后再回到城市A,請找出一條最短的旅行路線。用產(chǎn)生式規(guī)則表示旅行過程。2.14何謂語義網(wǎng)絡(luò)？語義網(wǎng)絡(luò)表示法的特點是什么？2.15語義網(wǎng)絡(luò)表示法與產(chǎn)生式表示法、謂詞邏輯表示法之間的關(guān)系如何？2.16用語義網(wǎng)絡(luò)表示下列知識：所有的鴿子都是鳥；所有

4、的鴿子都有翅膀；信鴿是一種鴿子，它有翅膀，能識途。請對下列命題分別寫出它的語義網(wǎng)絡(luò)：（1）每個學(xué)生都有多本書。（2）孫老師從2月至7月給計算機應(yīng)用專業(yè)講網(wǎng)絡(luò)技術(shù)課程。（3）雪地上留下一串串腳印，有的大，有的小，有的深，有的淺。（4）王麗萍是天發(fā)電腦公司的經(jīng)理，她35歲，住在南內(nèi)環(huán)街68號。請把下列命題用一個語義網(wǎng)絡(luò)表示出來：（1）豬和羊都是動物；（2）豬和羊都是偶蹄動物和哺乳動物；（3）野豬是豬，但生長在森林中；（4）山羊是羊，且頭上長著角；（5）綿羊是一種羊，它能生產(chǎn)羊毛。何謂框架？框架的一般表示形式是什么？框架表示法有何特點？請敘述用框架表示法表示知識的步驟。試寫出“學(xué)生框架”的描述。框架

5、系統(tǒng)中求解問題的一般過程是什么？何謂對象？何謂類？封裝及繼承的含義是什么？什么是狀態(tài)空間？狀態(tài)空間是怎樣構(gòu)成的？請寫出用狀態(tài)空間表示法表示問題的一般步驟。修道士和野人問題。設(shè)有3個修道士和3個野人來到河邊，打算用一條船從河的左岸渡到河的右岸。但該船每次只能裝載兩個人，在任何岸邊野人的數(shù)目都不得超過修道士的人數(shù)，否則修道士就會被野人吃掉。假設(shè)野人服從任何一種過河安排，請問如何規(guī)劃過河計劃才能把所有人都安全地渡過河去。農(nóng)夫、狐貍、雞和小米過河問題。農(nóng)夫、狐貍、雞、小米都在一條河的左岸，現(xiàn)在要把它們?nèi)克偷接野度?，農(nóng)夫有一條船，過河時，除農(nóng)夫外，船上至多能載狐貍、雞和小米中的一樣。狐貍要吃雞，雞要吃

6、小米，除非農(nóng)夫在那里。試規(guī)劃出一個確保全部安全的過河計劃。（提示：a.用四元組（農(nóng)夫，狐貍，雞，小米）表示狀態(tài)，其中每個元素都可為0或1。1表示在左岸，0表示在右岸。b.把每次過河的一種安排作為一個算符，每次過河都必須有農(nóng)夫，因為只有他可以劃船。）用狀態(tài)空間表示法表示2.7題的“猴子摘香蕉問題”。2.2習(xí)題參考解答答:（略）答：（略）答：（略）答：（略）答：用一階謂詞邏輯法表示知識的步驟如下：（1）定義謂詞及個體，確定每個謂詞及個體的確切含義。（2）根據(jù)所要表達的事物或概念，為每個謂詞中的變元賦以特定的值。（3）根據(jù)所要表達的知識的語義，用適當(dāng)?shù)穆?lián)接符號將各個謂詞聯(lián)接起來，形成謂詞公式。解:（

7、1）有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花。定義謂詞及個體。設(shè)LIKE（x,y）表示x喜歡y,Meihua表示梅花，Juhua表示菊花，貝V：Gx）LIKE（x,Meihua）aGy）LIKE（y,Juhua）a（3z）（LIKE（z,Meihua）aLIKE（z,Juhua）（2）李明每天下午都去玩足球。定義謂詞及個體。設(shè)PLAYFB（x,y）表示x在y下午玩足球，Liming表示李明，貝V：（Vy）（PLAYFB（Liming,y）（3）太原市的夏天既干燥又炎熱。定義謂詞及個體。設(shè)STATE（x,y,z表示x市在y季節(jié)氣候處于z狀態(tài)。這是一個三元一階謂詞，所涉及的個體有

8、：太原，夏天，干燥，炎熱。將個體代入謂詞：STATE（太原，夏天，干燥），STATE（太原，夏天，炎熱），根據(jù)題意將各謂詞用適當(dāng)?shù)倪B接符連接起來。STATE（太原，夏天，干燥）ASTATE（太原，夏天，炎熱）（4）所有人都有飯吃。定義謂詞及個體。設(shè)Havefood(x)表示x有飯吃，則根據(jù)題意有：(Vx)(Havefood(x)(5)喜歡玩籃球的人必喜歡玩排球。定義謂詞及個體。設(shè)Likeplay(x,y)表示x喜歡玩y。所涉及的個體有：籃球，排球。將個體代入謂詞，并根據(jù)題意將各謂詞用適當(dāng)?shù)倪B接符連接起來。(3x)(Likeplay(x,籃球)tLikeplay(x,排球)(6)要想出國留學(xué)，必

9、須通過外語考試。定義謂詞及個體。設(shè)Want(x,y)表示x想y，Pass(x,y)表示x通過y。定義個體：goabrod表示出國學(xué)習(xí)，flanguage表示外語。將個體代入謂詞，并根據(jù)題意將各謂詞用適當(dāng)?shù)倪B接符連接起來。(Vx)(Pass(x,flanguage)twant(x,goabrod)解：根據(jù)謂詞知識表示的步驟求解問題如下：解法一：本問題涉及的常量定義為：猴子：Monkey,箱子：Box,香蕉:Banana,位置：a,b,c定義謂詞如下SITE(x,y):表示x在y處；HANG(x,y):表示x懸掛在y處；ON(x,y):表示x站在y上；HOLDS(y,w):表示y手里拿著w。根據(jù)問

10、題的描述將問題的初始狀態(tài)和目標(biāo)狀態(tài)分別用謂詞公式表示如下：問題的初始狀態(tài)表示:SITE(Monkey,a)AHANG(Banana,b)ASITE(Box,c)AON(Monkey,Box)AHOLDS(Monkey,Banana)問題的目標(biāo)狀態(tài)表示:SITE(Monkey,b)AHANG(Banana,b)ASITE(Box,b)AON(Monkey,Box)AHOLDS(Monkey,Banana)解法二：本問題涉及的常量定義為：猴子：Monkey,箱子：Box,香蕉:Banana,位置：a,b,c定義謂詞如下SITE(x,y):表示x在y處；ONBOX(x):表示x站在箱子頂上；HOLD

11、S(x):表示x摘到了香蕉。根據(jù)問題的描述將問題的初始狀態(tài)和目標(biāo)狀態(tài)分別用謂詞公式表示如下：問題的初始狀態(tài)表示:SITE(Monkey,a)ASITE(Box,c)AONBOX(Monkey)人HOLDS(Monkey)問題的目標(biāo)狀態(tài)表示:SITE(Box,b)ASITE(Monkey,b)AONBOX(Monkey)AHOLDS(Monkey)從上述兩種解法可以看出,只要謂詞定義不同,問題的初始狀態(tài)和目標(biāo)狀態(tài)就不同,所以,對于同樣的知識,不同的人表示的結(jié)果可能不同。解：本問題的關(guān)鍵就是制定一組操作,將初始狀態(tài)轉(zhuǎn)換為目標(biāo)狀態(tài)。為了用謂詞公式表示操作,可將操作分為條件(為完成相應(yīng)操作所必須具備的

12、條件)和動作兩部分。條件易于用謂詞公式表示,而動作則可通過執(zhí)行它前后的狀態(tài)變化表示出來,即由于動作的執(zhí)行,當(dāng)前狀態(tài)中刪去了某些謂詞公式而又增加一些謂詞公式從而得到了新的狀態(tài),通過這種狀態(tài)中謂詞公式的增減來描述動作。定義四個操作謂詞如下,操作的條件和動作可用謂詞公式的增刪表示：goto(x,y)：從x處走到y(tǒng)處。條件：SITE(Monkey,x)動作：刪除SITE(Monkey,x);增加SITE(Monkey,y)pushbox(x,y)：將箱子從x處推到y(tǒng)處。條件：SITE(Monkey,x)ASITE(Box,x)AONBOX(Monkey)動作：刪除SITE(Monkey,x),SITE

13、(Box,x);增加SITE(Monkey,y),SITE(Box,y)climbbox:爬到箱子頂上。條件：ONBOX(Monkey)動作：刪除ONBOX(Monkey)；增加ONBOX(Monkey)grasp：摘下香蕉。條件：HOLDS(Monkey)AONBOX(Monkey)ASITE(Monkey,b)動作：刪除HOLDS(Monkey)；增加HOLDS(Monkey)在執(zhí)行某一操作前，先檢查當(dāng)前狀態(tài)是否滿足其前提條件，若滿足，則執(zhí)行該操作，否則，檢查另一操作的條件是否被滿足。檢查的方法就是當(dāng)前的狀態(tài)中是否蘊含了操作所要求的條件。在定義了操作謂詞后，就可以給出從初始狀態(tài)到目標(biāo)狀態(tài)的

14、求解過程。在求解過程中，當(dāng)進行條件檢查時，要進行適當(dāng)?shù)淖兞看鷵Q。SITE(Monkey,a)SITE(Box,c)ONBOX(Monkey)、HOLDS(Monkey)_Ugoto(x,y),用a代X,用c代ySITE(Monkey,c)SITE(Box,c)ONBOX(Monkey)、HOLDS(Monkey)_Upushbox(x,y),用c代x,用b代ySITE(Monkey,b)SITE(Box,b)ONBOX(Monkey)、HOLDS(Monkey)_UclimboxSITE(Monkey,b)SITE(Box,b)ONBOX(Monkey)、HOLDS(Monkey)Ugrasp

15、SITE(Monkey,b)SITE(Box,b)ONBOX(Monkey)HOLDS(Monkey)答：(略)答：(略)答：(略)解：首先，建立棋盤變換的產(chǎn)生式規(guī)則。如果把棋盤的每一種布局看作是一個狀態(tài)矩陣，本題就變成了從初始狀態(tài)矩陣到目標(biāo)狀態(tài)矩陣的一種變化。所謂棋盤狀態(tài)的變化就是希望棋盤上空格周圍的棋子能走進空格，這也可以理解為移動空格，只要實現(xiàn)空格的上、下、左、右四種移動即可。可通過建立四個條件操作型的產(chǎn)生式規(guī)則，來實現(xiàn)這四種移動。設(shè)Sij為狀態(tài)矩陣中的第i行和第j列的數(shù)碼，i0,j0表示空格所在的行和列，如果在狀態(tài)矩陣中用0來表示空格的話，則建立如下四條產(chǎn)生式規(guī)則：R1：if(jo-1

16、1)thengin鼻妙二S必。)；Si0(j0-1):=0end空格左移R2：if(“11)thengin%。：=S加；S(i0-1)j0:=0end空格上移R3：if(jo+lW3)thenbeginsiojo：=Sio(o+1)；Si0(j0+1):=0end空格右移R4：if(io+1W3)thenbeginSiFS(詢+咖;S(i0+1)j0:=0end空格下移然后，建立綜合數(shù)據(jù)庫。將棋盤的布局表示為狀態(tài)矩陣的形式存入綜合數(shù)據(jù)庫，例如，可以將本題的初始布局和目標(biāo)布局以矩陣形式表示為：283123_160S=804g754765So=綜合數(shù)據(jù)庫中，存放初始和目標(biāo)狀態(tài)矩陣以及變換過程中的中

17、間矩陣。在建立了規(guī)則集和綜合數(shù)據(jù)庫后，就可以按照產(chǎn)生式規(guī)則進行狀態(tài)變換，實現(xiàn)推理求解。在進行推理時，可能會有多條產(chǎn)生式規(guī)則的條件部分和綜合數(shù)據(jù)庫中的已有事實相符，這樣就有可能激活多條規(guī)則，究竟采用哪一條規(guī)則作為啟用規(guī)則，這就是沖突解決策略問題。解決沖突的策略有專一性排序、規(guī)則順序等多種，也可以使用一些啟發(fā)性的信息，根據(jù)具體問題選擇。在本題中，我們采用一個啟發(fā)式函數(shù)h(x)，它表示節(jié)點x所對應(yīng)的棋盤中與目標(biāo)節(jié)點對應(yīng)的棋盤中棋子位置不同的個數(shù)。這里，綜合數(shù)據(jù)庫中的初始狀態(tài)矩陣，能滿足規(guī)則R1，R2，R4的條件，所以有三條匹配規(guī)則。利用啟發(fā)式函數(shù)決定哪一條規(guī)則為啟用規(guī)則因為規(guī)則R4的啟發(fā)式函數(shù)值h(

18、x)=5,規(guī)則R1的h(x)=6,規(guī)則R2的h(x)=7,也就是說，規(guī)則R4所得到的新狀態(tài)與目標(biāo)狀態(tài)差距最小，所以啟用規(guī)則R4,依此類推，可以得到到達目標(biāo)狀態(tài)的規(guī)則執(zhí)行序列：R4，R1，R2，R2，R1，R4，R3其執(zhí)行過程如圖2.14所示斗2；R654IS76S4E52、勿屮各節(jié)點畀發(fā)氏隔數(shù)-I.T)呃棒kI：所標(biāo)為所啟用2Xn16:F4圖2.14習(xí)題2.12執(zhí)行過程解：設(shè)綜合數(shù)據(jù)庫中包含了已訪問過的城市名的列表、未訪問過的城市名列表和各城市間的距離表。初始時刻，已訪問過的城市名列表中只有A,未訪問過的城市名列表中有B,C,D,E。定義如下謂詞：not-visit(x):表示未訪問過城市x;

19、visit-all()：表示已沒有未訪問過的城市；goto(x):表示去訪問城市X,并將x加入已訪問的城市列表中，從未訪問過的城市列表中刪除。則建立如下的產(chǎn)生式規(guī)則：Rl:not-visit(x)fgoto(x)R2:visit-all()fgoto(A)當(dāng)未訪問過的城市列表不為空時，激活規(guī)則R1；否則，激活規(guī)則R2。如果未訪問過的城市列表中城市個數(shù)多于一個時，這時規(guī)則R1的實例就不止一個。比如，在剛開始時，就有四條規(guī)則（分別針對x=A,x=B,x=C,x=D）被激活，這時可以根據(jù)綜合數(shù)據(jù)庫中的城市間距離，構(gòu)造一個啟發(fā)式函數(shù)h（x）來解決規(guī)則沖突，決定某一條規(guī)則為啟用規(guī)則。例如在剛開始從A出發(fā)

20、時，決定下一訪問城市時，由于B與A的距離最近，所以x:=B。依此類推，推銷員走的路徑為E、D、C。這時未訪問過的城市列表中已經(jīng)為空，規(guī)則R2被激活，返回城市A。答：（略）答：（略）解：（1）本知識涉及的對象有3個：鳥、鴿子、信鴿。信鴿是一種鴿子，除了它們本身的屬性外，具有鴿子的一般特性。而鴿子又是一種鳥，鳥所具有的屬性它也具有。（2）信鴿與鴿子之間是一種類屬關(guān)系，鴿子和鳥之間也是一種類屬關(guān)系，它們都可以用AKO表示。（3）整理各對象節(jié)點之間的屬性，使上層節(jié)點所具有的屬性不再在下層節(jié)點中標(biāo)出。（4）將各對象作為一個節(jié)點，而它們之間的關(guān)系作為弧，則得到圖2.15所示的語義網(wǎng)絡(luò)。圖2.15有關(guān)鴿子的

21、語義網(wǎng)絡(luò)解：（1）這是一個帶有全稱量詞的語義網(wǎng)絡(luò)，如圖2.16所示。其中，s是全稱變量，代表任一個學(xué)生；h是存在變量，表示某次擁有；bs也是存在量詞，代表多本書；s,h，bs及其語義聯(lián)系構(gòu)成一個子網(wǎng)，是一個子空間，表示每個學(xué)生都擁有多本書；節(jié)點g代表該子空間，由弧F指向其所代表的子空間的具體形式，弧指出s是一個全稱變量。節(jié)點GS代表整個空間。圖2.16“每個學(xué)生都有多本書”的語義網(wǎng)絡(luò)根據(jù)題意得到如圖2.17所示的語義網(wǎng)絡(luò)，這里要指出的是，設(shè)立“講課”很有必要，由它向外引出的弧不僅可以指出講課的主體，而且可以指出講課的起止時間。主俸rf是2月份是客楝2客體1結(jié)束于7月他卜釗T譏彈機麗圖2.17有

22、關(guān)講課的語義網(wǎng)絡(luò)弩地在腳印(與或W|小的找的譽/狀養(yǎng)”(3)根據(jù)題意，這是一個有合取和析取的語義網(wǎng)絡(luò)，如圖2.18所示。探的圖2.18有關(guān)雪地上腳印的語義網(wǎng)絡(luò)4)此題較簡單，根據(jù)題意，其語義網(wǎng)絡(luò)如圖2.19所示圖2.19有關(guān)電腦公司的語義網(wǎng)絡(luò)解：按照語義網(wǎng)絡(luò)知識表示步驟來首先進行解題分析：（1）問題涉及的對象有動物、偶蹄動物、哺乳動物、豬、羊、野豬、山羊、綿羊共8個對象。各對象的屬性可以根據(jù)常識給出，不過，這里特別給出了山羊有角，綿羊能產(chǎn)羊毛的特點。（2）羊和豬與偶蹄動物、哺乳動物間是類屬關(guān)系，偶蹄動物、哺乳動物與動物間也是類屬關(guān)系，野豬與豬，山羊、綿羊與羊之間都是類屬關(guān)系，可用AKO表示。（

23、3）根據(jù)信息繼承性原則，各上層節(jié)點的屬性下層都具有，在下層都不再標(biāo)出，以避免屬性信息重復(fù)。（4）根據(jù)上面的分析，本題共涉及8個對象，各對象的屬性以及它們之間的關(guān)系已在上面指出，所以本題的語義網(wǎng)絡(luò)應(yīng)是由8個節(jié)點構(gòu)成的有向圖，弧上的標(biāo)注以及各節(jié)點的標(biāo)圖2.20有關(guān)豬和羊的語義網(wǎng)絡(luò)答：框架是一種描述所論對象屬性的數(shù)據(jù)結(jié)構(gòu)。所論的對象可以是一個事物、一個事件或者一個概念。一個框架由若干個“槽”組成，每個“槽”又可劃分為若干個“側(cè)面”。一個槽用于描述所論及對象的某一方面的屬性，一個側(cè)面用于描述相應(yīng)屬性的一個方面。槽和側(cè)面所具有的屬性值分別稱為槽值和側(cè)面值。槽值可以是邏輯型或數(shù)字型的，具體的值可以是程序、

24、條件、默認值或是一個子框架?？蚣芤话憧杀硎境扇缦滦问娇蚣苊?11-值121y值ln2ln2答：（略）解：由于學(xué)生框架類似于一個變量，并未指定某個具體的學(xué)生，所以，其定義應(yīng)該如下，若要描述某個具體的學(xué)生，則只要將他的相應(yīng)屬性填入到這個框架的各個槽中即可框架名：姓名：單位（姓和名）年齡：單位（歲）性別：范圍（男，女）缺?。校┙】禒顩r：范圍（健康，一般，差）缺省（一般）所在系別：單位（系）專業(yè)：范圍(系中所包含的專業(yè))入學(xué)時間：單位(年，月)畢業(yè)時間：單位(年，月)成績：范圍(優(yōu)，良，中，差)缺省(良)是否學(xué)生干部：范圍(是，否)缺省(否)答：(略)答：(略)答：由表示一個問題的全部狀態(tài)及一切可

25、用算符構(gòu)成的集合稱為該問題的狀態(tài)空間它一般由三部分構(gòu)成：問題的所有可能初始狀態(tài)構(gòu)成的集合S；算符集合F；目標(biāo)狀態(tài)集合G。即可用一個三元組(S,F,G)表示問題的狀態(tài)空間。答：(略)解：用狀態(tài)空間法進行表示。根據(jù)狀態(tài)空間表示問題的步驟，問題求解如下：第一步，定義問題狀態(tài)的描述形式。設(shè)SK=(Nx,Ny,C)表示修道士和野人在河的左岸的狀態(tài)，其中，Nx表示修道士在左岸的實際人數(shù)，Ny表示也人在左岸的實際人數(shù)，C用來指示船是否在左岸(C=l表示在左岸，C=0表示不在左岸)。第二步，用所定義的狀態(tài)描述形式把問題的所有可能狀態(tài)都表示出來，并確定出問題的初始狀態(tài)集和目標(biāo)狀態(tài)集。對于狀態(tài)SK=(Nx,Ny,

26、C)來說，由于Nx,Ny的取值有0，1，2,3四種可能，C的取值有0和1兩種可能，所以本問題所有可能的狀態(tài)共有4X4X2=32種。各狀態(tài)的形式描述如下：S0=(3,3,1),S=(3,2,1),S2=(3,1,1),S3=(3,0,1),S4=(3,3,0),S5=(3,2,0),S6=(3,1,0),S7=(3,0,0),S8=(2,3,1),S9=(2,2,1),S10=(2,1,1),S11=(2,0,1),S12=(2,3,0),S13=(2,2,0),S14=(2,1,0),S15=(2,0,0),S16=(1,3,1),S17=(1,2,1),S18=(1,1,1),S19=(1,

27、0,1),S20=(1,3,O),S21=(l,2,0),S22=(l,l,0),S23=(l,0,0),S24=(0,3,l),S25=(0,2,1),S26=(0,1,1),S27=(0,0,1),S28=(0,3,0),S29=(020),S30=(0丄0),S31=(0,0,0).在這些狀態(tài)中，由于有安全約束條件任何岸邊野人的數(shù)量都不得超過傳教士的數(shù)量(即N三N),所以只有20個狀態(tài)是合法的，像(1,2,1)(1,3,1)和(2,3,1)等都是不合法的xy狀態(tài)。而由于這些不合法狀態(tài)的存在，又會導(dǎo)致某些合法狀態(tài)是不可到達的。這樣，這個問題總共只有16種可到達的合法狀態(tài)，以下劃線表示。問題

28、的初始狀態(tài)集為：S=S0=(3,3,1),目標(biāo)狀態(tài)集為：G=S31=(0,0,0)第三步，定義一組用于狀態(tài)變換算符F。定義算符L(i，j)表示劃船將i個傳教士和j個野人送到右岸的操作；算符R(i，j)表示劃船從右岸將i個傳教士和j個野人帶回左岸的操作。由于過河的船每次最多載兩個人，所以，i+jW2，這樣定義的算符組F中只可能有如下10個算符：F：L(1,0)，L(2,0)，L(1,1)，L(0,1)，L(0,2)R(1,0)，R(2,0)，R(1,1)，R(0,1)，R(0,2)至此，該問題的狀態(tài)空間(S,F,G)構(gòu)造完成。這就完成了對問題的狀態(tài)空間表示。為了求解該問題，根據(jù)該狀態(tài)空間的16種

29、可到達合法狀態(tài)和10種算符，構(gòu)造它的狀態(tài)轉(zhuǎn)換圖，如圖2.21所示。、兮2圖2.21傳教士和野人問題的狀態(tài)轉(zhuǎn)換圖在圖2.21所示的狀態(tài)空間圖中，每個節(jié)點只能取L、R操作之一，這取決于變量C的取值，即船是在左岸還是在右岸，若船在左岸(即C=1)，則只能取L操作，若船在右岸,則只能取R操作。從初始節(jié)點(3,3,1)(狀態(tài)S0)到目標(biāo)節(jié)點(0,0,0)(狀態(tài)S31)的任何一條通路都是問題的一個解。其中：L(1,1)，R(1,0)，L(0,2)，R(0,1)，L(2,0)，R(1,1)，L(2,0)，R(0,1)，L(0,2)，R(0,1)，L(0,2)是算符最少的解之一。解：用狀態(tài)空間法進行表示。根據(jù)

30、狀態(tài)空間表示問題的步驟，問題求解如下：第一步，定義問題狀態(tài)的描述形式。以四元組SK=(1，h,j,m)作為狀態(tài)變量，表示農(nóng)夫、狐貍、雞和小米是否在左岸，每個元素共有兩個取值1或0，1表示在左岸，0表示不在左岸。第二步，用所定義的狀態(tài)變量把問題的所有可能狀態(tài)都表示出來，并確定出問題的初始狀態(tài)集和目標(biāo)狀態(tài)集。由于狀態(tài)變量有4個元素，每個元素有2種取值，所以共有16種可能狀態(tài)。各狀態(tài)的形式描述如下：S0=(1,1,1,1),S1=(1,1,1,0),S2=(1,1,0,1),S3=(1,1,0,0)S4=(1,0,1,1),S5=(1,0,1,0),S6=(1,0,0,1),S7=(1,0,0,0)

31、S8=(0,1,1,1),S9=(0,1,1,0),S10=(0,1,0,1),S11=(0,1,0,0)S12=(0,0,1,1),S13=(0,0,1,0),S14=(0,0,0,1),S15=(0,0,0,0)問題的初始狀態(tài)集為：S=S=(1,1,1,1),目標(biāo)狀態(tài)集為：G=S5=(0,0,0,0)第三步，定義一組用于狀態(tài)變換的算符F。由于船上除了農(nóng)夫外，每次只能載狐貍、雞和小米中的一樣，且每次農(nóng)夫都必須在船上，故定義算符如下：L(f,j)表示從左岸將第j樣?xùn)|西送到右岸(j=1表示狐貍，j=2表示雞，j=3表示小米，j=0表示除農(nóng)夫外不載任何東西)，f表示農(nóng)夫始終在船上。R(f,j)表示從右岸將第j樣?xùn)|西帶回左岸。所以，所定義的算符組F中可能有8種算符：F：L(f,0)，L(f,1)，L(f,2)，L(f,3)，R(f,0)，R(f,1)，R(f,2)，R(f,3)這里要指出的是，操作算符中的f可以不要，也就是說，完全可以把操作算符定義成L(