人工智能原理及其指導(dǎo)應(yīng)用(王萬森)第3版 課后習(xí)題問題詳解

《人工智能原理及其指導(dǎo)應(yīng)用(王萬森)第3版 課后習(xí)題問題詳解》由會員分享，可在線閱讀，更多相關(guān)《人工智能原理及其指導(dǎo)應(yīng)用(王萬森)第3版 課后習(xí)題問題詳解（56頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、word 第1章 人工智能概述課后題答案 什么是智能?智能包含哪幾種能力？ 解：智能主要是指人類的自然智能。一般認(rèn)為，智能是是一種認(rèn)識客觀事物和運用知識解決問題的綜合能力。 智能包含感知能力，記憶與思維能力，學(xué)習(xí)和自適應(yīng)能力，行為能力 人類有哪幾種思維方式?各有什么特點？ 解：人類思維方式有形象思維、抽象思維和靈感思維 形象思維也稱直感思維，是一種基于形象概念，根據(jù)感性形象認(rèn)識材料，對客觀對象進(jìn)展處理的一種思維方式。 抽象思維也稱邏輯思維，是一種基于抽象概念，根據(jù)邏輯規(guī)如此對信息或知識進(jìn)展處理的理性思維形式。 靈感思維也稱頓悟思維，是一種顯意識與潛意識相互作用的

2、思維方式。 什么是人工智能?它的研究目標(biāo)是什么？ 解：從能力的角度講，人工智能是指用人工的方法在機器〔計算機〕上實現(xiàn)智能；從學(xué)科的角度看，人工智能是一門研究如何構(gòu)造智能機器或智能系統(tǒng)，使它能模擬、延伸和擴(kuò)展人類智能的學(xué)科。 研究目標(biāo)： 對智能行為有效解釋的理論分析； 解釋人類智能； 構(gòu)造具有智能的人工產(chǎn)品； 什么是圖靈實驗？圖靈實驗說明了什么？ 解：圖靈實驗可描述如下，該實驗的參加者由一位測試主持人和兩個被測試對象組成。其中，兩個被測試對象中一個是人，另一個是機器。測試規(guī)如此為：測試主持人和每個被測試對象分別位于彼此不能看見的房間中，相互之間只能通過計算機終端進(jìn)展

3、會話。測試開始后，由測試主持人向被測試對象提出各種具有智能性的問題，但不能詢問測試者的物理特征。被測試對象在回答如下問題時,都應(yīng)盡量使測試者相信自己是“人〞，而另一位是〞機器〞。在這個前提下，要求測試主持人區(qū)分這兩個被測試對象中哪個是人，哪個是機器。如果無論如何更換測試主持人和被測試對象的人，測試主持人總能分辨出人和機器的概率都小于50%，如此認(rèn)為該機器具有了智能。 人工智能的開展經(jīng)歷了哪幾個階段？ 解：孕育期，形成期，知識應(yīng)用期，從學(xué)派分立走向綜合，智能科學(xué)技術(shù)學(xué)科的興起 人工智能研究的根本容有哪些？ 解： 與腦科學(xué)與認(rèn)知科學(xué)的交叉研究 智能模擬的方法和技術(shù)研究

4、 人工智能有哪幾個主要學(xué)派？各自的特點是什么？ 解： 符號主義：又稱為邏輯主義、心理學(xué)派或計算機學(xué)派，是基于物理符號系統(tǒng)假設(shè)和有限合理性原理的人工智能學(xué)派。符號主義認(rèn)為人工智能起源于數(shù)理邏輯，人類認(rèn)知〔智能〕的根本元素是符號，認(rèn)知過程是符號表示上的一種運算。 聯(lián)結(jié)主義：又稱為仿生學(xué)派或生理學(xué)派，是基于神經(jīng)網(wǎng)絡(luò)與網(wǎng)絡(luò)間的聯(lián)結(jié)機制與學(xué)習(xí)算法的人工智能學(xué)派。聯(lián)結(jié)主義認(rèn)為人工智能起源于仿生學(xué)，特別是人腦模型的研究。 行為主義：又稱進(jìn)化主義或控制論學(xué)派，是基于控制論和“感知-動作〞控制系統(tǒng)的人工智能學(xué)派。行為主義認(rèn)為人工智能起源于控制論，提出智能取決于感知和行為，取決于對外界復(fù)雜環(huán)境的適應(yīng)，而

5、不是表示和推理。 人工智能有哪些主要研究和應(yīng)用領(lǐng)域？其中哪些是新的研究熱點？ 解： 機器思維:推理、搜索、規(guī)劃 機器學(xué)習(xí)：符號學(xué)習(xí)、聯(lián)結(jié)學(xué)習(xí)、知識發(fā)現(xiàn)和數(shù)據(jù)挖掘 機器感知：機器視覺、模式識別、自然語言理解 機器行為：智能控制、智能制造 計算智能：神經(jīng)計算、進(jìn)化計算、模糊計算 分布智能 智能系統(tǒng)：專家系統(tǒng)、智能決策支持系統(tǒng) 人工心理與人工情感 研究熱點：智能機器人、智能檢索、智能游戲等。 1.9 人工智能未來開展有哪些值得思考和關(guān)注的重要問題？ 解： 多學(xué)科交叉研究 分布智能與社會智能研究 集成智能研究 智能網(wǎng)絡(luò)研究 認(rèn)知計算與情感計算研究

6、智能系統(tǒng)與智能服務(wù) 第2章 確定性知識系統(tǒng)參考答案 什么是知識？有哪幾種主要的知識分類方法？ 解：知識是人們在改造客觀世界的實踐中積累起來的認(rèn)識和經(jīng)驗；知識是對信息進(jìn)展智能性加工中形成的對客觀世界規(guī)律性的認(rèn)識。 分類： 按適用圍：常識性知識、領(lǐng)域性知識 按作用效果：述性知識、過程性知識、控制性知識 按確定性：確定性知識、不確定性知識 什么是知識表示？知識表示有哪些要求？ 解：知識表示就是對知識的描述，即用一些約定的符號把知識編碼成一組可以被計算機直接識別，并便于系統(tǒng)使用的數(shù)據(jù)結(jié)構(gòu)

7、 一介謂詞邏輯表示法 非結(jié)構(gòu)化方法 產(chǎn)生式 述性知識表示 語義網(wǎng)絡(luò) 結(jié)構(gòu)化方法 框架結(jié)構(gòu) 知識表示方法 過程性知識表示 要求：表示能力，可利用性，可組織性與可維護(hù)性，

8、可理解性和可實現(xiàn)性 從心理學(xué)的角度看，推理有哪兩種比擬典型的觀點？它們的含義是什么？ 解：結(jié)構(gòu)觀點：這種觀點從結(jié)構(gòu)的角度出發(fā)，認(rèn)為推理由兩個以上判斷所組成，每個判斷所揭示的是概念之間的聯(lián)系和關(guān)系，推理過程是一種對客觀事物做出肯定或否點的思維活動。 過程觀點：這種觀點從過程的角度出發(fā)，認(rèn)為推理是在給定信息和已有知識的根底上所進(jìn)展的一系列加工操作，其代表人物克茨提出了如下人類推理的公式：y=F〔x，k〕 式中，x是推理時給出的信息，k是推理時可用的領(lǐng)域知識和特殊事例，F(xiàn)是可用的一系列操作，y是推理過程所得到的結(jié)論。 什么是推理？它有哪些分類方法？ 解：推理是由具體事例歸納出一

9、般規(guī)律，或者根據(jù)已有的知識推出新的結(jié)論的思維過程 分為演繹法和歸納法 推理中的控制策略包括哪幾個方面的容？主要解決哪些問題？ 解：包括推理策略和搜索策略 推理策略主要解決推理方向，求解策略，限制策略，沖突消解策略等 搜索策略主要解決推理線路，推理效果，推理效率等問題 什么是命題？什么是命題的真值？ 解：一個述句稱為一個斷言，凡有真假意義的斷言稱為命題。 命題的意義通常稱為真值，當(dāng)命題的意義為真時，如此稱該命題的真值為真。 什么是論域？什么是謂詞 解：論域是由所討論對象之全體構(gòu)成的非空集合。論域中的元素稱為個體，論域也常稱為個體域。 在謂詞邏輯中，命題是用

10、謂詞來表示的。一個謂詞可分為謂詞名和個體兩局部。 什么是自由變元？什么是約束變元？ 解：當(dāng)一個謂詞公式含有量詞時，區(qū)分個體變元是否受量詞的約束是很重要的。通常，把位于量詞后面的單個謂詞或者用括弧括起來的合式公式稱為該量詞的轄域，轄域與量詞中受約束的變元稱為約束變元，不受約束的變元稱為自由變元。 設(shè)有如下語句，請用相應(yīng)的謂詞公式分別把他們表示出來： (1) 有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花 。 解：定義謂詞 P(x)：x是人 L(x,y)：x喜歡y 其中，y的個體域是{梅花，菊花}。 將知識用謂詞表示為： (x )(P(x)→L(x, 梅

11、花)∨L(x, 菊花)∨(L(x, 梅花)∧L(x, 菊花))) (2)有人每天下午都去打籃球。 解：定義謂詞 P(x)：x是人 B(x)：x打籃球 A(y)：y是下午 將知識用謂詞表示為： (x )(y) (A(y)→B(x)∧P(x)) (3) 新型計算機速度又快，存儲容量又大。 解：定義謂詞 NC(x)：x是新型計算機 F(x)：x速度快 B(x)：x容量大 將知識用謂詞表示為： (x) (NC(x)→F(x)∧B(x)) (4)不是每個計算機系的學(xué)生都喜歡在計算機上編程序。 解：定義謂詞 S(x)：x是計算機系學(xué)生

12、L(x, pragramming)：x喜歡編程序 U(x,puter)：x使用計算機 將知識用謂詞表示為： ?(x) (S(x)→L(x, pragramming)∧U(x,puter)) (5)但凡喜歡編程序的人都喜歡計算機。 解：定義謂詞 P(x)：x是人 L(x, y)：x喜歡y 將知識用謂詞表示為： (x) (P(x)∧L(x,pragramming)→L(x, puter)) 用謂詞表示法求解機器人摞積木問題。設(shè)機器人有一只機械手，要處理的世界有一桌子，桌上可堆放假如干一樣的方積木塊。機械手有4個操作積木的典型動作：從桌上揀起一塊積木；將手中的積木放到

13、桌之上；在積木上再摞上一塊積木；從積木上面揀起一塊積木。積木世界的布局如如下圖所示。 A B C CA B 圖2.10 機器人摞積木問題 解：(1) 先定義描述狀態(tài)的謂詞 CLEAR(x)：積木x上面是空的。 ON(x, y)：積木x在積木y的上面。 ONTABLE(x)：積木x在桌子上。 HOLDING(x)：機械手抓住x。 HANDEMPTY：機械手是空的。 其中，x和y的個體域都是{A, B, C}。 問題的初始狀態(tài)是： ONTABLE(A) ONTABLE(B

14、) ON(C, A) CLEAR(B) CLEAR(C) HANDEMPTY 問題的目標(biāo)狀態(tài)是： ONTABLE(C) ON(B, C) ON(A, B) CLEAR(A) HANDEMPTY (2) 再定義描述操作的謂詞 在本問題中，機械手的操作需要定義以下4個謂詞： Pickup(x)：從桌面上揀起一塊積木x。 Putdown(x)：將手中的積木放到桌面上。 Stack(x, y)：在積木x上面再摞上一塊積木y。 Upstack(x, y)：從積木x上面揀起一塊積木y。 其中，每一個操作都可分為條件

15、和動作兩局部，具體描述如下： Pickup(x) 條件：ONTABLE(x)，HANDEMPTY，CLEAR(x) 動作：刪除表：ONTABLE(x)，HANDEMPTY 添加表：HOLDING〔x〕 Putdown(x) 條件：HOLDING〔x〕 動作：刪除表：HOLDING〔x〕 添加表：ONTABLE(x)，CLEAR(x) ，HANDEMPTY Stack(x, y) 條件：HOLDING〔x〕，CLEAR(y) 動作：刪除表：HOLDING〔x〕，CLEAR(y)

16、 添加表：HANDEMPTY，ON(x, y) ，CLEAR(x) Upstack(x, y) 條件：HANDEMPTY，CLEAR(x) ，ON(x,y) 動作：刪除表：HANDEMPTY，ON(x, y) 添加表：HOLDING(x)，CLEAR(x) (3) 問題求解過程 利用上述謂詞和操作，其求解過程為： ONTABLE(A) ONTABLE(B) ONTABLE(C) CLEAR(A) CLEAR(B) CLEAR(C) HANDEMPTY ONTABLE(A) ONTABLE

17、(B) ON(C, A) CLEAR(B) CLEAR(C) HANDEMPTY ONTABLE(A) ONTABLE(B) HOLDING(C) CLEAR(A) CLEAR(B) Upstack(C,A) Putdown(C) Pickup(B) ONTABLE(A) ONTABLE(C) ON(B,C) CLEAR(A) CLEAR(B) HANDEMPTY ONTABLE(A) ONTABLE(C) HOLDING(B) CLEAR(A) CLEAR(B) CLEAR(C) ONTABLE(

18、C) ON(B,C) ON(A,B) CLEAR(A) HANDEMPT ONTABLE(C) ON(B,C) CLEAR(A) CLEAR(B) HOLDING(A) Stack(A,B) Stack(B,C) Pickup(A) 用謂詞表示法求解農(nóng)夫、狼、山羊、白菜問題。農(nóng)夫、狼、山羊、白菜全部放在一條河的左岸，現(xiàn)在要把他們?nèi)克偷胶拥挠野度?，農(nóng)夫有一條船，過河時，除農(nóng)夫外船上至多能載狼、山羊、白菜中的一種。狼要吃山羊，山羊要吃白菜，除非農(nóng)夫在那里。似規(guī)劃出一個確保全部安全過河的計劃。請寫出所用謂詞的定義，并給出每個謂詞的功能與變

19、量的個體域。 解：(1) 先定義描述狀態(tài)的謂詞 要描述這個問題，需要能夠說明農(nóng)夫、狼、羊、白菜和船在什么位置，為簡化問題表示，取消船在河中行駛的狀態(tài)，只描述左岸和右岸的狀態(tài)。并且，由于左岸和右岸的狀態(tài)互補，因此可僅對左岸或右岸的狀態(tài)做直接描述。此題選擇對左岸進(jìn)展直接描述的方法，即定義謂詞如下： AL(x)：x在左岸 其中，x的個體域是{農(nóng)夫，船，狼，羊，白菜}。對應(yīng)地，?AL(x)表示x在右岸。 問題的初始狀態(tài)： AL(農(nóng)夫) AL(船) AL(狼) AL(羊) AL(白菜) 問題的目標(biāo)狀態(tài)： ?AL(農(nóng)夫) ?AL(船) ?AL(狼) ?AL(羊

20、) ?AL(白菜) (2) 再定義描述操作的謂詞 此題需要以下4個描述操作的謂詞： L-R：農(nóng)夫自己劃船從左岸到右岸 L-R(x)：農(nóng)夫帶著x劃船從左岸到右岸 R-L：農(nóng)夫自己劃船從右岸到左岸 R-L(x) ：農(nóng)夫帶著x劃船從右岸到左岸 其中，x的個體域是{狼，羊，白菜}。 對上述每個操作，都包括條件和動作兩局部。它們對應(yīng)的條件和動作如下： L-R：農(nóng)夫劃船從左岸到右岸 條件：AL(船)，AL(農(nóng)夫)，?AL(狼)∨?AL(羊)，?AL(羊)∨?AL(白菜) 動作：刪除表：AL(船)，AL(農(nóng)夫) 添加表：?AL(船)，?AL(農(nóng)

21、夫) L-R(狼)：農(nóng)夫帶著狼劃船從左岸到右岸 條件：AL(船)，AL(農(nóng)夫)，AL(狼)，?AL(羊) 動作：刪除表：AL(船)，AL(農(nóng)夫)，AL(狼) 添加表：?AL(船)，?AL(農(nóng)夫)，?AL(狼) L-R(羊)：農(nóng)夫帶著羊劃船從左岸到右岸 條件：AL(船)，AL(農(nóng)夫)，AL(羊)， AL(狼)，AL(白菜) 或：AL(船)，AL(農(nóng)夫)，AL(羊)，?AL(狼)，?AL(白菜) 動作：刪除表：AL(船)，AL(農(nóng)夫)，AL(羊) 添加表：?AL(船)，?AL(農(nóng)夫)，?AL

22、(羊) L-R(白菜)：農(nóng)夫帶著白菜劃船從左岸到右岸 條件：AL(船)，AL(農(nóng)夫)，AL(白菜)，?AL(狼) 動作：刪除表：AL(船)，AL(農(nóng)夫)，AL(白菜) 添加表：?AL(船)，?AL(農(nóng)夫)，?AL(白菜) R-L：農(nóng)夫劃船從右岸到左岸 條件：?AL(船)，?AL(農(nóng)夫)，AL(狼)∨AL(羊)，AL(羊)∨AL(白菜) 或：?AL(船)，?AL(農(nóng)夫) ，?AL(狼)，?AL(白菜)，AL(羊) 動作：刪除表：?AL(船)，?AL(農(nóng)夫) 添加表：AL(船)

23、，AL(農(nóng)夫) R-L(羊) ：農(nóng)夫帶著羊劃船從右岸到左岸 條件：?AL(船)，?AL(農(nóng)夫)，?AL(羊) ，?AL(狼)，?AL(羊)，AL(白菜) 動作：刪除表：?AL(船)，?AL(農(nóng)夫)，?AL(羊) 添加表：AL(船)，AL(農(nóng)夫)，AL(羊) (3) 問題求解過程 AL(白菜) ?AL(農(nóng)夫) ?AL(船) ?AL(狼) ?AL(羊) AL(農(nóng)夫) AL(船) AL(狼) AL(白菜) ?AL(羊) AL(狼) AL(白菜) ?AL(農(nóng)夫) ?AL(船) ?AL(羊) AL(農(nóng)夫) R-L R-L

24、(羊) L-R(狼) L-R(羊) AL(船) AL(狼) AL(羊) AL(白菜) AL(農(nóng)夫) AL(船) AL(羊) AL(白菜) ?AL(狼) AL(農(nóng)夫) AL(船) AL(羊) ?AL(白菜) ?AL(狼) AL(羊) ?AL(農(nóng)夫) ?AL(船) ?AL(白菜) ?AL(狼) L-R(羊) ?AL(農(nóng)夫) ?AL(船) ?AL(羊) ?AL(白菜) ?AL(狼) R-L L-R(白菜) 用謂詞表示法求解修道士和野人問題。在河的北岸有三個修道士、三個野人和一條船，修道士們想用這條

25、船將所有的人都運過河去，但要受到以下條件限制： (1) 修道士和野人都會劃船，但船一次只能裝運兩個人。 (2) 在任何岸邊，野人數(shù)不能超過修道士，否如此修道士會被野人吃掉。 假定野人愿意服從任何一種過河安排，請規(guī)劃出一種確保修道士安全的過河方案。要求寫出所用謂詞的定義、功能與變量的個體域。 解：〔1〕定義謂詞 先定義修道士和野人人數(shù)關(guān)系的謂詞： G(x,y,S)： 在狀態(tài)S下x大于y GE(x,y,S)：在狀態(tài)S下x大于或等于y 其中，x,y分別代表修道士人數(shù)和野人數(shù)，他們的個體域均為{0,1,2,3}。 再定義船所在岸的謂詞和修道士不在該岸上的謂詞： Boat(z,S)：

26、狀態(tài)S下船在z岸 EZ(x,S)： 狀態(tài)S下x等于0，即修道士不在該岸上 其中，z的個體域是{L,R}，L表示左岸，R表示右岸。 再定義安全性謂詞： Safety(z,x,y,S)≡(G(x,0,S)∧GE(x,y,S))∨(EZ(x,S)) 其中，z,x,y的含義同上。該謂詞的含義是：狀態(tài)S下，在z岸，保證修道士安全，當(dāng)且僅當(dāng)修道士不在該岸上，或者修道士在該岸上，但人數(shù)超過野人數(shù)。該謂詞同時也描述了相應(yīng)的狀態(tài)。 再定義描述過河方案的謂詞： L-R(x, x1, y, y1,S)：x1個修道士和y1個野人渡船從河的左岸到河的右岸 條件：Safety(L,x-x1

27、,y-y1,S’)∧Safety(R,3-x+x1,3-y+y1,S’)∧Boat(L,S) 動作：Safety(L,x-x1,y-y1,S’)∧Safety(R,3-x+x1,3-y+y1,S’)∧Boat(R,S’) R-L (x, x1, y, y1,S)：x2個修道士和y2個野人渡船從河的左岸到河的右岸 條件：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(R,S) 動作：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(L,S’)

28、 (2) 過河方案 Safety(L,3,3,S0)∧Safety(R,0,0,S0)∧Boat(L,S0) L-R(3, 1, 3, 1,S0) L-R(3, 0, 3, 2,S0) Safety(L,2,2,S1)∧Safety(R,1,1,S1)∧Boat(R,S1) Safety(L,3,1,S1’)∧Safety(R,0,2,S1’)∧Boat(R,S1’) R-L (2, 1, 2, 0,S1) R-L (3,0, 1, 1,S1’

29、) Safety(L,3,2,S2)∧Safety(R,0,1,S2)∧Boat(L,S2) L-R(3, 0, 2, 2,S2) Safety(L,3,0,S3)∧Safety(R,0,3,S3)∧Boat(R,S3) R-L (3, 0, 0, 1,S3) Safety(L,3,1,S4)∧Safety(R,0,2,S1)∧Boat(L,S4) L-R(3, 2, 1, 0,S4) Safety(L,1,1,S5)∧Safety(R,2,2,S5)∧Boat(R,S5) R-L (1, 1, 1, 1,S5) Safety(L,2,2,S6)∧Safety(R,1,1,S

30、6)∧Boat(L,S6) L-R(2, 2, 2, 0,S6) Safety(L,0,2,S7)∧Safety(R,3,1,S7)∧Boat(R,S7) R-L (0, 0, 2, 1,S7) Safety(L,0,3,S8)∧Safety(R,3,0,S8)∧Boat(L,S8) L-R(0, 0, 3, 2,S8) Safety(L,0,1,S9)∧Safety(R,3,2,S9)∧Boat(R,S9) R-L (0, 1, 1, 0,S9) Safety(L,1,1,S10)∧Safety(R,2,2,S10)∧Boat(L,S10) L-R(1, 1, 1, 1,S

31、10) Safety(L,0,0,S11)∧Safety(R,3,3,S11)∧Boat(R,S11) 2.13 什么是產(chǎn)生式？它的根本形式是什么？代表什么含義？ 解：“產(chǎn)生式〞由美國數(shù)學(xué)家波斯特〔E.POST〕在1934年首先提出，它根據(jù)串代替規(guī)如此提出了一種稱為波斯特機的計算模型，模型中的每條規(guī)如此稱為產(chǎn)生式。 產(chǎn)生式的根本形式P→Q 或者 IF P THEN Q。P是產(chǎn)生式的前提，也稱為前件，它給出了該產(chǎn)生式可否使用的先決條件，由事實的邏輯組合來構(gòu)成；Q是一組結(jié)論或操作，也稱為產(chǎn)生式的后件，它指出當(dāng)前題P滿足時，應(yīng)該推出的結(jié)論或應(yīng)該執(zhí)行的動作。產(chǎn)生式的含義如果前提P滿足，如此

32、可推出結(jié)論Q或執(zhí)行Q所規(guī)定的操作。 2.14 產(chǎn)生式表示的特征是什么？ 解：優(yōu)點：自然性、模塊性、有效性 缺點：效率低性、不方便表示結(jié)構(gòu)性知識的有向圖 2.15 何謂語義網(wǎng)絡(luò)？它有哪些根本的語義關(guān)系？ 解：語義網(wǎng)絡(luò)：用實體以與語義關(guān)系來表達(dá)知識的有向圖 根本的語義關(guān)系： ① 實例關(guān)系〔ISA〕:(是一個)(一個事物是另一個事物的具體例子) ② 分類關(guān)系〔AKO〕:(是一種)子類與超類 ③ 成員關(guān)系 (A-member-of): 是一名 ④ 屬性關(guān)系:Have 有、Can 能、Age 年齡 ⑤ 包含關(guān)系 part-of-局部 (不具備屬性) ⑥ 位置關(guān)系:Befo

33、re，after ⑦ located-on located-under located-outside located-at located-inside ⑧ 相近關(guān)系 similar-to 相似 near-to 接近 2.16 請對如下命題分別寫出它們的語義網(wǎng)絡(luò)： (1) 每個學(xué)生都有一臺計算機。 AKO AKO 人 職業(yè) 學(xué)生 AKO 設(shè)備 計算機 owner owns 占有權(quán) AKO 情況 占有資格 AKO (2) 高教師從3月到7月給計算機系學(xué)生講《計算機網(wǎng)絡(luò)》課。 解：

34、7月 8月 Start End 教師 ISA Object Subject 高教師 計算機系學(xué)生 講課事件 Action Caurse 計算機網(wǎng)絡(luò) 講課 (3) 學(xué)習(xí)班的學(xué)員有男、有女、有研究生、有本科生。 解： 女 男 研究生 本科生 Have Have Have 學(xué)員 (4) 創(chuàng)新公司在科海大街56號，洋是該公司的經(jīng)理，他32歲、碩士學(xué)位。 32 Age Work-for Address Isa 創(chuàng)新公司 X洋 經(jīng)理 56號

35、Have 碩士學(xué)位 (5) 紅隊與藍(lán)隊進(jìn)展足球比賽，最后以3：2的比分完畢。 解： 比賽 AKO Participants1 Oute 3:2 2 足球賽 紅隊 Participants 2 藍(lán)隊 2.17 請把如下命題用一個語義網(wǎng)絡(luò)表示出來： (1) 樹和草都是植物； 植物 解： AKO AKO 草 樹 (2) 樹和草都有葉和根； 根 葉 解： Have Have 植物 是一種 是一種 草 樹

36、 (3) 水草是草，且生長在水中； 解： Live AKO AKO 水草 水中 植物 草 (4) 果樹是樹，且會結(jié)果； 解： Can AKO AKO 果樹 結(jié)果 植物 樹 (5) 梨樹是果樹中的一種，它會結(jié)梨。 解： Can AKO AKO 梨樹 樹 果樹 結(jié)梨 2.18 試述語義網(wǎng)絡(luò)中求解問題的一般過程 解：語義網(wǎng)絡(luò)的推理過程主要有兩種，一種是繼承，另一種是匹配。 繼承是指把對事物的描述從抽象節(jié)點傳遞到具體節(jié)點。 匹配是指在知識庫的語義網(wǎng)絡(luò)中

37、尋找與待求解問題相符的語義網(wǎng)絡(luò)模式。 2.19 試述語義網(wǎng)絡(luò)表示法的特點 解：結(jié)構(gòu)性 聯(lián)想性 自然性 缺點：非嚴(yán)格性，復(fù)雜性 2.20 何謂框架？框架的一般形式是什么？ 解：框架表示法是在框架理論的根底上開展起來的一種結(jié)構(gòu)化知識表示方法。 框架通常由描述事物各個方面的假如干槽組成，每一個槽也可以根據(jù)實際情況擁有假如干個側(cè)面，每一個側(cè)面又可以擁有假如干個值。 2.21 何謂實例框架？它與框架有什么關(guān)系？ 解：當(dāng)人們把觀察或認(rèn)識到的具體細(xì)節(jié)填入框架后，就得到了該框架的一個具體實例，框架的這種具體實例被稱為實例框架。 通用結(jié)構(gòu)與具體實例，抽象與具體。 2.22

38、 何謂框架系統(tǒng)？何謂框架系統(tǒng)的橫向聯(lián)系？何謂框架系統(tǒng)的縱向聯(lián)系？ 解：在框架理論中，框架是知識的根本單位，把一組有關(guān)的框架連接起來便可形成一個框架系統(tǒng)。在框架系統(tǒng)中，系統(tǒng)的行為由該系統(tǒng)框架的變化來實現(xiàn)，系統(tǒng)的推理過程由框架之間的協(xié)調(diào)完成。 縱向聯(lián)系：表示那種具有演繹關(guān)系的知識結(jié)構(gòu)，下層框架與上層框架之間具有一種繼承關(guān)系，這種具有繼承關(guān)系的框架之間的聯(lián)系稱為縱向聯(lián)系。 橫向聯(lián)系：由于一個框架的槽值或側(cè)面值可以是另外一個框架的名字，這就在框架之間建立了另外一種聯(lián)系，稱為橫向聯(lián)系。 2.23 假設(shè)有以下一段天氣預(yù)報：“地區(qū)今天白天晴，偏北風(fēng)3級，最高氣溫12o，最低氣溫-2o，降水概率1

39、5%。〞請用框架表示這一知識。 解： Frame<天氣預(yù)報> 地域： 時段：今天白天 天氣：晴 風(fēng)向：偏北 風(fēng)力：3級 氣溫：最高：12度 最低：-2度 降水概率：15% 2.24 按“師生框架〞、“教師框架〞、“學(xué)生框架〞的形式寫出一個框架系統(tǒng)的描述。 解：師生框架 Frame Name：Unit〔Last-name，F(xiàn)irst-name〕 Sex：Area〔male，female〕 Default：male

40、 Age：Unit〔Years〕 Telephone：Home Unit〔Number〕 Mobile Unit〔Number〕 教師框架 Frame AKO Major：Unit〔Major-Name〕 Lectures：Unit〔Course-Name〕 Field：Unit〔Field-Name〕 Project ：Area〔National，Provincial，Other〕 Default：Provincial P

41、aper：Area〔SCI，EI，Core，General〕 Default：Core 學(xué)生框架 Frame AKO< Teachers-Students > Major：Unit〔Major-Name〕 Classes：Unit〔Classes-Name〕 Degree：Area〔doctor，mastor, bachelor〕 Default：bachelor 在框架系統(tǒng)中，問題求解的一般過程是什么？ 解：特性繼承 框架的匹配與填槽 框架表示法的特點

42、有哪些？ 解：優(yōu)點：結(jié)構(gòu)性，深層性，繼承性，自然性。 缺點：缺乏框架的形式理論，缺乏過程性知識表示，清晰性難以保證 何謂產(chǎn)生式系統(tǒng)？產(chǎn)生式推理的根本結(jié)構(gòu)由哪幾局部組成？ 解：利用產(chǎn)生式知識表示方法所進(jìn)展的推理稱為產(chǎn)生式推理，由此產(chǎn)生的系統(tǒng)為產(chǎn)生式系統(tǒng) 根本結(jié)構(gòu)：綜合數(shù)據(jù)庫，規(guī)如此庫，控制系統(tǒng) 什么是產(chǎn)生式的正向推理？其根本過程是什么？ 解：從事實出發(fā)，正向使用推理規(guī)如此的推理方法。 過程： 〔1〕把用戶提供的初始證據(jù)放入綜合數(shù)據(jù)庫； 〔2〕檢查綜合數(shù)據(jù)庫中是否包含了問題的解，假如已包含，如此求解完畢，并成功推出， 否如此

43、，執(zhí)行下一步； 〔3〕檢查知識庫中是否有可用知識。假如有，形成當(dāng)前可用知識集，執(zhí)行下一步，否如此轉(zhuǎn)〔5〕； 〔4〕按照某種沖突消解策略，從當(dāng)前可用知識集中選出一條知識進(jìn)展推理，并將推出的新事實參加綜合數(shù)據(jù)庫中，然后轉(zhuǎn)〔2〕； 〔5〕詢問用戶是否可以進(jìn)一步補充新的事實，假如可補充，如此將補充的新事實參加綜合數(shù)據(jù)庫中，然后轉(zhuǎn)〔3〕，否如此表示無解，失敗退出。 2.29 什么是逆向推理？其根本過程是什么？ 解：以某個假設(shè)目標(biāo)作為出發(fā)點的推理方法 過程： （1） 將問題的初始證據(jù)和要求證的目標(biāo)〔稱為假設(shè)〕分別放入綜合數(shù)據(jù)庫和假設(shè)集； （2） 從假設(shè)集中選出一個假

44、設(shè)，檢查該假設(shè)是否在綜合數(shù)據(jù)庫中，假如在，如此該假設(shè)成立。此時，假如假設(shè)集為空，如此成功退出。否如此，扔執(zhí)行〔2〕。假如該假設(shè)不在數(shù)據(jù)庫中，如此執(zhí)行下一步； （3） 檢查該假設(shè)是否可由知識庫的某個知識導(dǎo)出，假如不能由某個知識導(dǎo)出，如此詢問用戶尋找新的假設(shè)。假如不是，如此轉(zhuǎn)〔5〕，假如能由某個知識導(dǎo)出，如此執(zhí)行下一步； （4） 將知識庫中可以導(dǎo)出該假設(shè)的所有知識構(gòu)成一個可用知識集； （5） 檢查可用知識集是否為空，假如空，失敗退出。否如此執(zhí)行下一步； （6） 按沖突消解策略從可用知識集中取出一個知識，繼續(xù)執(zhí)行下一步； （7） 將該知識的前提中的每個子條件都作為新的假設(shè)放入假設(shè)集，轉(zhuǎn)〔2

45、〕。 什么是混合推理？它由哪幾種實現(xiàn)方式？ 解：正向推理和逆向推理結(jié)合起來所進(jìn)展的推理稱為混合推理 實現(xiàn)：先正后逆，先逆后正，隨機 什么是置換？什么是合一？ 解：在不同謂詞公式中，往往會出現(xiàn)多個謂詞的謂詞名一樣但個體不同的情況，此時推理過程是不能直接進(jìn)展匹配的，需要先進(jìn)展變元的替換。這種利用項對變元進(jìn)展替換叫置換。 合一利用置換使兩個或多個謂詞的個體一致。 判斷如下公式是否為可合一，假如可合一，如此求出其相應(yīng)的置換 解：(1)??可合一，其最一般和一為：σ={a/x,?b/y}。 (2)??可合一，其最一般和一為：σ={ f(x)/y,?b/z}。 (3)

46、??可合一，其最一般和一為：σ={f(b)/y,?b/x}。 (4)??不可合一。 (5)??可合一，其最一般和一為：σ={?y/x}。 什么是自然演繹推理？它所依據(jù)的推理規(guī)如此是什么？ 從一組為真的事實出發(fā)，直接運用經(jīng)典邏輯中的推理規(guī)如此推出結(jié)論的過程稱為自然演繹推理 推理規(guī)如此：等價式，永真蘊涵式，置換，合一 什么是謂詞公式的可滿足性？什么是謂詞公式的不可滿足性？ 什么是謂詞公式的前束式？什么是謂詞公式的Skolem式？ 教材P56 什么是字句集？如何將謂詞公式化為字句集？ 2.37 把如下謂詞公式化成子句集： (1) (x)

47、(y)(P(x, y)∧Q(x, y)) (2) (x)(y)(P(x, y)→Q(x, y)) (3) (x)(y)(P(x, y)∨(Q(x, y)→R(x, y))) (4) (x) (y) (z)(P(x, y)→Q(x, y)∨R(x, z)) 解：(1) 由于(x)(y)(P(x, y)∧Q(x, y))已經(jīng)是Skolem標(biāo)準(zhǔn)型，且P(x, y)∧Q(x, y)已經(jīng)是合取式，所以可直接消去全稱量詞、合取詞，得 { P(x, y), Q(x, y)} 再進(jìn)展變元換名得子句集： S={ P(x, y), Q(u, v)}

48、 (2) 對謂詞公式(x)(y)(P(x, y)→Q(x, y))，先消去連接詞“→〞得： (x)(y)(?P(x, y)∨Q(x, y)) 此公式已為Skolem標(biāo)準(zhǔn)型。 再消去全稱量詞得子句集： S={?P(x, y)∨Q(x, y)} (3) 對謂詞公式(x)(y)(P(x, y)∨(Q(x, y)→R(x, y)))，先消去連接詞“→〞得： (x)(y)(P(x, y)∨(?Q(x, y)∨R(x, y))) 此公式已為前束式。 再消去存在量詞，即用Skolem函數(shù)f(x)替換y得： (x)(P(x, f(x))∨?Q(x, f(

49、x))∨R(x, f(x))) 此公式已為Skolem標(biāo)準(zhǔn)型。 最后消去全稱量詞得子句集： S={P(x, f(x))∨?Q(x, f(x))∨R(x, f(x))} (4) 對謂詞(x) (y) (z)(P(x, y)→Q(x, y)∨R(x, z))，先消去連接詞“→〞得： (x) (y) (z)(?P(x, y)∨Q(x, y)∨R(x, z)) 再消去存在量詞，即用Skolem函數(shù)f(x)替換y得： (x) (y) (?P(x, y)∨Q(x, y)∨R(x, f(x,y))) 此公式已為Skolem標(biāo)準(zhǔn)型。 最后消去全稱量詞得

50、子句集： S={?P(x, y)∨Q(x, y)∨R(x, f(x,y))} 魯濱遜歸結(jié)原理的根本思想是什么？ 解：魯濱遜歸結(jié)原理也稱為消解原理。其根本思想是把永真性的證明轉(zhuǎn)化為不可滿足性的證明。 即要證明P->Q永真，只要能夠證明P∧?Q為不可滿足即可。 2.39 判斷如下子句集中哪些是不可滿足的： (1) {?P∨Q, ?Q, P, ?P} (2) { P∨Q , ?P∨Q, P∨?Q, ?P∨?Q } (3) { P(y)∨Q(y) , ?P(f(x))∨R(a)} (4) {?P(x)∨Q(x) , ?P(y)∨R(y), P(a), S(a), ?S

51、(z)∨?R(z)} (5) {?P(x)∨Q(f(x),a) , ?P(h(y))∨Q(f(h(y)), a)∨?P(z)} (6) {P(x)∨Q(x)∨R(x) , ?P(y)∨R(y), ?Q(a), ?R(b)} 解：(1) 不可滿足，其歸結(jié)過程為： ?P∨Q ?Q ?P P NIL (2) 不可滿足，其歸結(jié)過程為： P∨Q ?P∨Q Q P∨?Q ?P∨?Q ?Q NIL (3) 不是不可滿足的，原因是不能由它導(dǎo)出空子句。 (4) 不可滿足，其歸結(jié)過程略 (5) 不是不可滿足的，原因是

52、不能由它導(dǎo)出空子句。 (6) 不可滿足，其歸結(jié)過程略 對如下各題分別證明G是否為F1,F2,…,Fn的邏輯結(jié)論： (1) F:(x)(y)(P(x, y) G: (y)(x)(P(x, y) (2) F: (x)(P(x)∧(Q(a)∨Q(b))) G: (x) (P(x)∧Q(x)) (3) F: (x)(y)(P(f(x))∧(Q(f(y))) G: P(f(a))∧P(y)∧Q(y) (4) F1: (x)(P(x)→(y)(Q(y)→L(x.y))) F2: (x) (P(x)∧(y)(R(y)→L(x.y))) G: (x)(R(x)→Q(x)) (5)

53、F1: (x)(P(x)→(Q(x)∧R(x))) F2: (x) (P(x)∧S(x)) G: (x) (S(x)∧R(x)) 解：(1) 先將F和?G化成子句集： S={P(a,b), ?P(x,b)} 再對S進(jìn)展歸結(jié)： ?P(x,b) P(a,b) NIL {a/x} 所以，G是F的邏輯結(jié)論 (2) 先將F和?G化成子句集 由F得：S1={P(x)，(Q(a)∨Q(b))} 由于?G為：?(x) (P(x)∧Q(x))，即 (x) (? P(x)∨? Q(x))， 可得： S2

54、={? P(x)∨? Q(x)} 因此，擴(kuò)大的子句集為： S={ P(x)，(Q(a)∨Q(b))，? P(x)∨? Q(x)} 再對S進(jìn)展歸結(jié)： Q(a)∨Q(b) Q(a) ? P(x)∨? Q(x) ? P(a) P(x) NIL Q(a)∨Q(b) {a/b} ? P(x)∨? Q(x) Q(a) {a/x} ? P(a) P(x) {a/x} NIL 所以，G是F的邏輯結(jié)論 同理可求得(3)、(4)和(5)，其求解過程略。 設(shè)：

55、(1) 如果x是y的父親，y是z的父親，如此x是z的祖父； (2) 每個人都有一個父親。 使用歸結(jié)演繹推理證明：對于某人u，一定存在一個人v，v是u的祖父。 解：先定義謂詞 F(x,y)：x是y的父親 GF(x,z)：x是z的祖父 P(x)：x是一個人 再用謂詞把問題描述出來： F1：(x)(y)(z)( F(x,y)∧F(y,z))→GF(x,z)) F2：(y)(P(x)→F(x,y)) 求證結(jié)論G：(u) (v)( P(u)→GF(v,u)) 然后再將F1，F(xiàn)2和?G化成子句集： ①?F(

56、x,y)∨?F(y,z)∨GF(x,z) ②?P(r)∨F(s,r) ③ P(u) ④?GF(v,u)) 對上述擴(kuò)大的子句集，其歸結(jié)推理過程如下： ?F(x,y)∨?F(y,z)∨GF(x,z) ?GF(v,u) ?F(x,y)∨?F(y,z) ?P(r)∨F(s,r) ?F(y,z)∨?P(y) ?P(r)∨F(s,r) ?P(y)∨?P(z) ?P(y) P(u) NIL {x/v,z/u} {x/s,y/r} {y/s,z/r}

57、 {y/z} {y/u} 由于導(dǎo)出了空子句，故結(jié)論得證。 2.42 假設(shè)被盜，公安局派出5個人去調(diào)查。案情分析時，貞察員A說：“與錢中至少有一個人作案〞，貞察員B說：“錢與中至少有一個人作案〞，貞察員C說：“與中至少有一個人作案〞，貞察員D說：“與中至少有一個人與此案無關(guān)〞，貞察員E說：“錢與中至少有一個人與此案無關(guān)〞。如果這5個偵察員的話都是可信的，使用歸結(jié)演繹推理求出誰是盜竊犯。 解：(1) 先定義謂詞和常量 設(shè)C(x)表示x作案，Z表示，Q表示錢，S表示，L表示 (2)

58、將事實用謂詞公式表示出來 與錢中至少有一個人作案：C(Z)∨C(Q) 錢與中至少有一個人作案：C(Q)∨C(S) 與中至少有一個人作案：C(S)∨C(L) 與中至少有一個人與此案無關(guān)：?(C (Z)∧C(S))，即 ?C (Z) ∨?C(S) 錢與中至少有一個人與此案無關(guān)：?(C (Q)∧C(L))，即 ?C (Q) ∨?C(L) (3) 將所要求的問題用謂詞公式表示出來，并與其否認(rèn)取析取。 設(shè)作案者為u，如此要求的結(jié)論是C(u)。將其與其否)取析取，得： ?C(u) ∨C(u) (4) 對上述擴(kuò)大的子句集，按歸結(jié)原理進(jìn)展歸結(jié)，其修改的證明樹如下： C(Z)∨C(Q

59、) ?C (Z) ∨?C(S) C(Q)∨?C(S) C(Q)∨C(S) C(Q) ?C(u)∨C(u) C(Q) {Q/u} 因此，錢是盜竊犯。實際上，本案的盜竊犯不止一人。根據(jù)歸結(jié)原理還可以得出： C(S)∨C(L) ?C (Q) ∨?C(L) C(S)∨?C(Q) C(Q)∨C(S) C(S) ?C(u)∨C(u) C(S) ?C (Q) ∨?C(L) C(S)∨C(L) C(Q)∨C(S) C(S)∨?C(Q) ?

60、C(u)∨C(u) C(S) {S/u} C(S) 因此，也是盜竊犯。 2.43 設(shè)： (1) 能閱讀的人是識字的； (2) 海豚不識字； (3) 有些海豚是很聰明的。 請用歸結(jié)演繹推理證明：有些很聰明的人并不識字。 解：第一步，先定義謂詞， 設(shè)R(x)表示x是能閱讀的； K(y)表示y是識字的； W(z) 表示z是很聰明的； 第二步，將事實和目標(biāo)用謂詞公式表示出來 能閱讀的人是識字的：(x)(R(x))→K(x)) 海豚不識字：(y)(?K (y)) 有些海豚是很聰明的：(

61、z) W(z) 有些很聰明的人并不識字：(x)( W(z)∧?K(x)) 第三步，將上述事實和目標(biāo)的否認(rèn)化成子句集： ?R(x))∨K(x) ?K (y) W(z) ?W(z)∨K(x)) 第四步，用歸結(jié)演繹推理進(jìn)展證明 W(z) ?W(z)∨K(x)) W(z) K(z) NIL 第3章 確定性推理局部參考答案 3.1 什么是搜索？有哪兩大類不同的搜索方法？兩者的區(qū)別是什么？ 解：像這種根據(jù)問題的實際情況，不斷尋找可利用知識，從而構(gòu)造一條最小的推理路線，使問題得以解決的過程稱為搜索 可根據(jù)搜索過程是

62、否使用啟發(fā)式信息分為盲目搜索和啟發(fā)式搜索，也可根據(jù)問題的表示方式分為狀態(tài)空間搜索和與/或搜索 盲目搜索是按預(yù)定的控制策略進(jìn)展搜索，在搜索過程中獲得的中間信息并不改變控制策略 啟發(fā)式搜索是在搜索中參加了與問題有關(guān)的啟發(fā)性信息，用于指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問題的求解過程，并找到最優(yōu)解。 狀態(tài)空間搜索是指用狀態(tài)空間法來表示問題所進(jìn)展的搜索。 與/或搜索是指用問題歸約法來表示問題時所進(jìn)展的搜索。 什么是狀態(tài)空間？用狀態(tài)空間表示問題時，什么是問題的解？什么是最優(yōu)解？最優(yōu)解唯一嗎？ 解：狀態(tài)空間〔state space〕是由一個問題的全部狀態(tài)，以與這些狀態(tài)之間的相互關(guān)系所構(gòu)成

63、的集合，它可用一個三元祖〔S,F,G〕來表示，其中,S為問題的所有初始狀態(tài)的集合；F為操作的集合；G為目標(biāo)狀態(tài)的集合。 由初始狀態(tài)到目標(biāo)狀態(tài)所使用的算符序列就是該問題的一個解。 使某目標(biāo)函數(shù)達(dá)到最優(yōu)值〔最大值或最小值〕的任一可行解，都稱為該問題的一個最優(yōu)解。 最優(yōu)解不唯一。 什么是與樹？什么是或樹？什么是與/或樹？什么是可解節(jié)點？什么是解樹？ 解：把一個原問題分解為假如干個子問題可用一個“與樹〞來表示。 把一個原問題變換為假如干個子問題可用一個“或樹〞來表示。 如果一個問題既需要通過分解，有需要通過變換才能得到其本原問題，如此其歸約過程可用一個“與/或樹〞來表示 在與/或樹

64、中，滿足以下三個條件之一的節(jié)點為可解節(jié)點： （1） 任何終止節(jié)點都是可解節(jié)點 （2） 對“或〞節(jié)點，當(dāng)其子節(jié)點中至少有一個為可解節(jié)點時，如此該或節(jié)點就是可解節(jié)點 （3） 對“與〞節(jié)點，只有當(dāng)其子節(jié)點全部為可解節(jié)點時，該與節(jié)點才是可解節(jié)點。 解樹：由可解節(jié)點構(gòu)成，并且有這些可解節(jié)點可以推出初始節(jié)點為可解節(jié)點的子樹為解樹。 在狀態(tài)空間一般搜索過程中，open表與closed表的作用與區(qū)別是什么？ 解：open表中存放待考察節(jié)點，close表存放考察過的節(jié)點。 有一農(nóng)夫帶一條狼，一只羊和一筐菜從河的左岸乘船到右岸，但受如下條件限制： 〔1〕船太小，

65、農(nóng)夫每次只能帶一樣?xùn)|西過河 〔2〕如果沒有農(nóng)夫看管，如此狼要吃羊，羊要吃菜 請設(shè)計一個過河方案，使得農(nóng)夫、狼羊都能不受損失的過河，畫出相應(yīng)的狀態(tài)空間圖 有一農(nóng)夫帶一條狼，一只羊和一框青菜與從河的左岸乘船倒右岸，但受到如下條件的限制： (1) 船太小，農(nóng)夫每次只能帶一樣?xùn)|西過河； (2) 如果沒有農(nóng)夫看管，如此狼要吃羊，羊要吃菜。 請設(shè)計一個過河方案，使得農(nóng)夫、浪、羊都能不受損失的過河，畫出相應(yīng)的狀態(tài)空間圖。 題示：(1) 用四元組〔農(nóng)夫，狼，羊，菜〕表示狀態(tài)，其中每個元素都為0或1，用0表示在左岸，用1表示在右岸。 (2) 把每次過河的一種安排作為一種操作，每次過河都必須

66、有農(nóng)夫，因為只有他可以劃船。 解：第一步，定義問題的描述形式 用四元組S=〔f，w，s，v〕表示問題狀態(tài)，其中，f，w，s和v分別表示農(nóng)夫，狼，羊和青菜是否在左岸，它們都可以取1或0，取1表示在左岸，取0表示在右岸。 第二步，用所定義的問題狀態(tài)表示方式，把所有可能的問題狀態(tài)表示出來，包括問題的初始狀態(tài)和目標(biāo)狀態(tài)。 由于狀態(tài)變量有4個，每個狀態(tài)變量都有2種取值，因此有以下16種可能的狀態(tài)： S0=(0,0,0,0)，S1=(0,0,0,1)，S2=(0,0,1,0)，S3=(0,0,1，1) S4=(0,1,0,0)，S5=(0,1,0,1)，S6=(0,1,1,0)，S7=(0,1,1,1) S8=(1,0,0,0)，S9=(1,0,0,1)，S10=(1,0,1,0)，S11=(1,0,1,1) S12=(1,1,0,0)，S13=(1,1,0,1)，S14=(1,1,1,0)，S15=(1,1,1,1) 其中，狀態(tài)S3，S6，S7，S8，S9，S12是不合法狀態(tài)，S0和S15分別是初始狀態(tài)和目標(biāo)狀態(tài)。 第三步，定義操作，即用于狀態(tài)變換的算符組F 由于每次過河船