《人工智能原理及其應(yīng)用(王萬(wàn)森)第3版 課后習(xí)題答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《人工智能原理及其應(yīng)用(王萬(wàn)森)第3版 課后習(xí)題答案（62頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

. 第1章 人工智能概述課后題答案 1.1 什么是智能?智能包含哪幾種能力？ 解：智能主要是指人類的自然智能。一般認(rèn)為，智能是是一種認(rèn)識(shí)客觀事物和運(yùn)用知識(shí)解決問題的綜合能力。 智能包含感知能力，記憶與思維能力，學(xué)習(xí)和自適應(yīng)能力，行為能力 1.2 人類有哪幾種思維方式?各有什么特點(diǎn)？ 解：人類思維方式有形象思維、抽象思維和靈感思維 形象思維也稱直感思維，是一種基于形象概念，根據(jù)感性形象認(rèn)識(shí)材料，對(duì)客觀對(duì)象進(jìn)行處理的一種思維方式。 抽象思維也稱邏輯思維，是一種基于抽象概念，根據(jù)邏輯規(guī)則對(duì)信息或知識(shí)進(jìn)行處理的理性思維形式。 靈感思維也稱頓悟思維，是一種顯意識(shí)與潛意識(shí)相互作用的思維方式。 1.3什么是人工智能?它的研究目標(biāo)是什么？ 解：從能力的角度講，人工智能是指用人工的方法在機(jī)器（計(jì)算機(jī)）上實(shí)現(xiàn)智能；從學(xué)科的角度看，人工智能是一門研究如何構(gòu)造智能機(jī)器或智能系統(tǒng)，使它能模擬、延伸和擴(kuò)展人類智能的學(xué)科。 研究目標(biāo)： 對(duì)智能行為有效解釋的理論分析； 解釋人類智能； 構(gòu)造具有智能的人工產(chǎn)品； 1.4 什么是圖靈實(shí)驗(yàn)？圖靈實(shí)驗(yàn)說(shuō)明了什么？ 解：圖靈實(shí)驗(yàn)可描述如下，該實(shí)驗(yàn)的參加者由一位測(cè)試主持人和兩個(gè)被測(cè)試對(duì)象組成。其中，兩個(gè)被測(cè)試對(duì)象中一個(gè)是人，另一個(gè)是機(jī)器。測(cè)試規(guī)則為：測(cè)試主持人和每個(gè)被測(cè)試對(duì)象分別位于彼此不能看見的房間中，相互之間只能通過(guò)計(jì)算機(jī)終端進(jìn)行會(huì)話。測(cè)試開始后，由測(cè)試主持人向被測(cè)試對(duì)象提出各種具有智能性的問題，但不能詢問測(cè)試者的物理特征。被測(cè)試對(duì)象在回答問題時(shí),都應(yīng)盡量使測(cè)試者相信自己是“人”，而另一位是”機(jī)器”。在這個(gè)前提下，要求測(cè)試主持人區(qū)分這兩個(gè)被測(cè)試對(duì)象中哪個(gè)是人，哪個(gè)是機(jī)器。如果無(wú)論如何更換測(cè)試主持人和被測(cè)試對(duì)象的人，測(cè)試主持人總能分辨出人和機(jī)器的概率都小于50%，則認(rèn)為該機(jī)器具有了智能。 1.5 人工智能的發(fā)展經(jīng)歷了哪幾個(gè)階段？ 解：孕育期，形成期，知識(shí)應(yīng)用期，從學(xué)派分立走向綜合，智能科學(xué)技術(shù)學(xué)科的興起 1.6 人工智能研究的基本內(nèi)容有哪些？ 解： 與腦科學(xué)與認(rèn)知科學(xué)的交叉研究 智能模擬的方法和技術(shù)研究 1.7 人工智能有哪幾個(gè)主要學(xué)派？各自的特點(diǎn)是什么？ 解： 符號(hào)主義：又稱為邏輯主義、心理學(xué)派或計(jì)算機(jī)學(xué)派，是基于物理符號(hào)系統(tǒng)假設(shè)和有限合理性原理的人工智能學(xué)派。符號(hào)主義認(rèn)為人工智能起源于數(shù)理邏輯，人類認(rèn)知（智能）的基本元素是符號(hào)，認(rèn)知過(guò)程是符號(hào)表示上的一種運(yùn)算。 聯(lián)結(jié)主義：又稱為仿生學(xué)派或生理學(xué)派，是基于神經(jīng)網(wǎng)絡(luò)及網(wǎng)絡(luò)間的聯(lián)結(jié)機(jī)制與學(xué)習(xí)算法的人工智能學(xué)派。聯(lián)結(jié)主義認(rèn)為人工智能起源于仿生學(xué)，特別是人腦模型的研究。 行為主義：又稱進(jìn)化主義或控制論學(xué)派，是基于控制論和“感知-動(dòng)作”控制系統(tǒng)的人工智能學(xué)派。行為主義認(rèn)為人工智能起源于控制論，提出智能取決于感知和行為，取決于對(duì)外界復(fù)雜環(huán)境的適應(yīng)，而不是表示和推理。 1.8人工智能有哪些主要研究和應(yīng)用領(lǐng)域？其中哪些是新的研究熱點(diǎn)？ 解： 機(jī)器思維:推理、搜索、規(guī)劃 機(jī)器學(xué)習(xí)：符號(hào)學(xué)習(xí)、聯(lián)結(jié)學(xué)習(xí)、知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘 機(jī)器感知：機(jī)器視覺、模式識(shí)別、自然語(yǔ)言理解 機(jī)器行為：智能控制、智能制造 計(jì)算智能：神經(jīng)計(jì)算、進(jìn)化計(jì)算、模糊計(jì)算 分布智能 智能系統(tǒng)：專家系統(tǒng)、智能決策支持系統(tǒng) 人工心理與人工情感 研究熱點(diǎn)：智能機(jī)器人、智能檢索、智能游戲等。 1.9 人工智能未來(lái)發(fā)展有哪些值得思考和關(guān)注的重要問題？ 解： 多學(xué)科交叉研究 分布智能與社會(huì)智能研究 集成智能研究 智能網(wǎng)絡(luò)研究 認(rèn)知計(jì)算與情感計(jì)算研究 智能系統(tǒng)與智能服務(wù)  第2章 確定性知識(shí)系統(tǒng)參考答案 2.1 什么是知識(shí)？有哪幾種主要的知識(shí)分類方法？ 解：知識(shí)是人們?cè)诟脑炜陀^世界的實(shí)踐中積累起來(lái)的認(rèn)識(shí)和經(jīng)驗(yàn)；知識(shí)是對(duì)信息進(jìn)行智能性加工中形成的對(duì)客觀世界規(guī)律性的認(rèn)識(shí)。 分類： 按適用范圍：常識(shí)性知識(shí)、領(lǐng)域性知識(shí) 按作用效果：陳述性知識(shí)、過(guò)程性知識(shí)、控制性知識(shí) 按確定性：確定性知識(shí)、不確定性知識(shí) 2.2 什么是知識(shí)表示？知識(shí)表示有哪些要求？ 解：知識(shí)表示就是對(duì)知識(shí)的描述，即用一些約定的符號(hào)把知識(shí)編碼成一組可以被計(jì)算機(jī)直接識(shí)別，并便于系統(tǒng)使用的數(shù)據(jù)結(jié)構(gòu) 一介謂詞邏輯表示法 非結(jié)構(gòu)化方法 產(chǎn)生式 陳述性知識(shí)表示 語(yǔ)義網(wǎng)絡(luò) 結(jié)構(gòu)化方法 框架結(jié)構(gòu) 知識(shí)表示方法 過(guò)程性知識(shí)表示 要求：表示能力，可利用性，可組織性與可維護(hù)性，可理解性和可實(shí)現(xiàn)性 2.3 從心理學(xué)的角度看，推理有哪兩種比較典型的觀點(diǎn)？它們的含義是什么？ 解：結(jié)構(gòu)觀點(diǎn)：這種觀點(diǎn)從結(jié)構(gòu)的角度出發(fā)，認(rèn)為推理由兩個(gè)以上判斷所組成，每個(gè)判斷所揭示的是概念之間的聯(lián)系和關(guān)系，推理過(guò)程是一種對(duì)客觀事物做出肯定或否點(diǎn)的思維活動(dòng)。 過(guò)程觀點(diǎn)：這種觀點(diǎn)從過(guò)程的角度出發(fā)，認(rèn)為推理是在給定信息和已有知識(shí)的基礎(chǔ)上所進(jìn)行的一系列加工操作，其代表人物克茨提出了如下人類推理的公式：y=F（x，k） 式中，x是推理時(shí)給出的信息，k是推理時(shí)可用的領(lǐng)域知識(shí)和特殊事例，F(xiàn)是可用的一系列操作，y是推理過(guò)程所得到的結(jié)論。 2.4 什么是推理？它有哪些分類方法？ 解：推理是由具體事例歸納出一般規(guī)律，或者根據(jù)已有的知識(shí)推出新的結(jié)論的思維過(guò)程 分為演繹法和歸納法 2.5 推理中的控制策略包括哪幾個(gè)方面的內(nèi)容？主要解決哪些問題？ 解：包括推理策略和搜索策略 推理策略主要解決推理方向，求解策略，限制策略，沖突消解策略等 搜索策略主要解決推理線路，推理效果，推理效率等問題 2.6 什么是命題？什么是命題的真值？ 解：一個(gè)陳述句稱為一個(gè)斷言，凡有真假意義的斷言稱為命題。 命題的意義通常稱為真值，當(dāng)命題的意義為真時(shí)，則稱該命題的真值為真。 2.7 什么是論域？什么是謂詞 解：論域是由所討論對(duì)象之全體構(gòu)成的非空集合。論域中的元素稱為個(gè)體，論域也常稱為個(gè)體域。 在謂詞邏輯中，命題是用謂詞來(lái)表示的。一個(gè)謂詞可分為謂詞名和個(gè)體兩部分。 2.8 什么是自由變?cè)?？什么是約束變?cè)? 解：當(dāng)一個(gè)謂詞公式含有量詞時(shí)，區(qū)分個(gè)體變?cè)欠袷芰吭~的約束是很重要的。通常，把位于量詞后面的單個(gè)謂詞或者用括弧括起來(lái)的合式公式稱為該量詞的轄域，轄域內(nèi)與量詞中受約束的變?cè)Q為約束變?cè)?，不受約束的變?cè)Q為自由變?cè)? 2.9 設(shè)有如下語(yǔ)句，請(qǐng)用相應(yīng)的謂詞公式分別把他們表示出來(lái)： (1) 有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花 。 解：定義謂詞 P(x)：x是人 L(x,y)：x喜歡y 其中，y的個(gè)體域是{梅花，菊花}。 將知識(shí)用謂詞表示為： (x )(P(x)→L(x, 梅花)∨L(x, 菊花)∨(L(x, 梅花)∧L(x, 菊花))) (2) 有人每天下午都去打籃球。 解：定義謂詞 P(x)：x是人 B(x)：x打籃球 A(y)：y是下午 將知識(shí)用謂詞表示為： (x )(y) (A(y)→B(x)∧P(x)) (3) 新型計(jì)算機(jī)速度又快，存儲(chǔ)容量又大。 解：定義謂詞 NC(x)：x是新型計(jì)算機(jī) F(x)：x速度快 B(x)：x容量大 將知識(shí)用謂詞表示為： (x) (NC(x)→F(x)∧B(x)) (4) 不是每個(gè)計(jì)算機(jī)系的學(xué)生都喜歡在計(jì)算機(jī)上編程序。 解：定義謂詞 S(x)：x是計(jì)算機(jī)系學(xué)生 L(x, pragramming)：x喜歡編程序 U(x,computer)：x使用計(jì)算機(jī) 將知識(shí)用謂詞表示為： (x) (S(x)→L(x, pragramming)∧U(x,computer)) (5) 凡是喜歡編程序的人都喜歡計(jì)算機(jī)。 解：定義謂詞 P(x)：x是人 L(x, y)：x喜歡y 將知識(shí)用謂詞表示為： (x) (P(x)∧L(x,pragramming)→L(x, computer)) 2.10 用謂詞表示法求解機(jī)器人摞積木問題。設(shè)機(jī)器人有一只機(jī)械手，要處理的世界有一張桌子，桌上可堆放若干相同的方積木塊。機(jī)械手有4個(gè)操作積木的典型動(dòng)作：從桌上揀起一塊積木；將手中的積木放到桌之上；在積木上再摞上一塊積木；從積木上面揀起一塊積木。積木世界的布局如下圖所示。 A B C CA B 圖2.10 機(jī)器人摞積木問題 解：(1) 先定義描述狀態(tài)的謂詞 CLEAR(x)：積木x上面是空的。 ON(x, y)：積木x在積木y的上面。 ONTABLE(x)：積木x在桌子上。 HOLDING(x)：機(jī)械手抓住x。 HANDEMPTY：機(jī)械手是空的。 其中，x和y的個(gè)體域都是{A, B, C}。 問題的初始狀態(tài)是： ONTABLE(A) ONTABLE(B) ON(C, A) CLEAR(B) CLEAR(C) HANDEMPTY 問題的目標(biāo)狀態(tài)是： ONTABLE(C) ON(B, C) ON(A, B) CLEAR(A) HANDEMPTY (2) 再定義描述操作的謂詞 在本問題中，機(jī)械手的操作需要定義以下4個(gè)謂詞： Pickup(x)：從桌面上揀起一塊積木x。 Putdown(x)：將手中的積木放到桌面上。 Stack(x, y)：在積木x上面再摞上一塊積木y。 Upstack(x, y)：從積木x上面揀起一塊積木y。 其中，每一個(gè)操作都可分為條件和動(dòng)作兩部分，具體描述如下： Pickup(x) 條件：ONTABLE(x)，HANDEMPTY，CLEAR(x) 動(dòng)作：刪除表：ONTABLE(x)，HANDEMPTY 添加表：HOLDING（x） Putdown(x) 條件：HOLDING（x） 動(dòng)作：刪除表：HOLDING（x） 添加表：ONTABLE(x)，CLEAR(x) ，HANDEMPTY Stack(x, y) 條件：HOLDING（x），CLEAR(y) 動(dòng)作：刪除表：HOLDING（x），CLEAR(y) 添加表：HANDEMPTY，ON(x, y) ，CLEAR(x) Upstack(x, y) 條件：HANDEMPTY，CLEAR(x) ，ON(x,y) 動(dòng)作：刪除表：HANDEMPTY，ON(x, y) 添加表：HOLDING(x)，CLEAR(x) (3) 問題求解過(guò)程 利用上述謂詞和操作，其求解過(guò)程為： ONTABLE(A) ONTABLE(B) ONTABLE(C) CLEAR(A) CLEAR(B) CLEAR(C) HANDEMPTY ONTABLE(A) ONTABLE(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(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) 2.11 用謂詞表示法求解農(nóng)夫、狼、山羊、白菜問題。農(nóng)夫、狼、山羊、白菜全部放在一條河的左岸，現(xiàn)在要把他們?nèi)克偷胶拥挠野度?，農(nóng)夫有一條船，過(guò)河時(shí)，除農(nóng)夫外船上至多能載狼、山羊、白菜中的一種。狼要吃山羊，山羊要吃白菜，除非農(nóng)夫在那里。似規(guī)劃出一個(gè)確保全部安全過(guò)河的計(jì)劃。請(qǐng)寫出所用謂詞的定義，并給出每個(gè)謂詞的功能及變量的個(gè)體域。 解：(1) 先定義描述狀態(tài)的謂詞 要描述這個(gè)問題，需要能夠說(shuō)明農(nóng)夫、狼、羊、白菜和船在什么位置，為簡(jiǎn)化問題表示，取消船在河中行駛的狀態(tài)，只描述左岸和右岸的狀態(tài)。并且，由于左岸和右岸的狀態(tài)互補(bǔ)，因此可僅對(duì)左岸或右岸的狀態(tài)做直接描述。本題選擇對(duì)左岸進(jìn)行直接描述的方法，即定義謂詞如下： AL(x)：x在左岸 其中，x的個(gè)體域是{農(nóng)夫，船，狼，羊，白菜}。對(duì)應(yīng)地，AL(x)表示x在右岸。 問題的初始狀態(tài)： AL(農(nóng)夫) AL(船) AL(狼) AL(羊) AL(白菜) 問題的目標(biāo)狀態(tài)： AL(農(nóng)夫) AL(船) AL(狼) AL(羊) AL(白菜) (2) 再定義描述操作的謂詞 本題需要以下4個(gè)描述操作的謂詞： L-R：農(nóng)夫自己劃船從左岸到右岸 L-R(x)：農(nóng)夫帶著x劃船從左岸到右岸 R-L：農(nóng)夫自己劃船從右岸到左岸 R-L(x) ：農(nóng)夫帶著x劃船從右岸到左岸 其中，x的個(gè)體域是{狼，羊，白菜}。 對(duì)上述每個(gè)操作，都包括條件和動(dòng)作兩部分。它們對(duì)應(yīng)的條件和動(dòng)作如下： L-R：農(nóng)夫劃船從左岸到右岸 條件：AL(船)，AL(農(nóng)夫)，AL(狼)∨AL(羊)，AL(羊)∨AL(白菜) 動(dòng)作：刪除表：AL(船)，AL(農(nóng)夫) 添加表：AL(船)，AL(農(nóng)夫) L-R(狼)：農(nóng)夫帶著狼劃船從左岸到右岸 條件：AL(船)，AL(農(nóng)夫)，AL(狼)，AL(羊) 動(dòng)作：刪除表：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(白菜) 動(dòng)作：刪除表：AL(船)，AL(農(nóng)夫)，AL(羊) 添加表：AL(船)，AL(農(nóng)夫)，AL(羊) L-R(白菜)：農(nóng)夫帶著白菜劃船從左岸到右岸 條件：AL(船)，AL(農(nóng)夫)，AL(白菜)，AL(狼) 動(dòng)作：刪除表：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(羊) 動(dòng)作：刪除表：AL(船)，AL(農(nóng)夫) 添加表：AL(船)，AL(農(nóng)夫) R-L(羊) ：農(nóng)夫帶著羊劃船從右岸到左岸 條件：AL(船)，AL(農(nóng)夫)，AL(羊) ，AL(狼)，AL(羊)，AL(白菜) 動(dòng)作：刪除表：AL(船)，AL(農(nóng)夫)，AL(羊) 添加表：AL(船)，AL(農(nóng)夫)，AL(羊) (3) 問題求解過(guò)程 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(羊) 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(白菜) 2.12 用謂詞表示法求解修道士和野人問題。在河的北岸有三個(gè)修道士、三個(gè)野人和一條船，修道士們想用這條船將所有的人都運(yùn)過(guò)河去，但要受到以下條件限制： (1) 修道士和野人都會(huì)劃船，但船一次只能裝運(yùn)兩個(gè)人。 (2) 在任何岸邊，野人數(shù)不能超過(guò)修道士，否則修道士會(huì)被野人吃掉。 假定野人愿意服從任何一種過(guò)河安排，請(qǐng)規(guī)劃出一種確保修道士安全的過(guò)河方案。要求寫出所用謂詞的定義、功能及變量的個(gè)體域。 解：（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ù)，他們的個(gè)體域均為{0,1,2,3}。 再定義船所在岸的謂詞和修道士不在該岸上的謂詞： Boat(z,S)：狀態(tài)S下船在z岸 EZ(x,S)： 狀態(tài)S下x等于0，即修道士不在該岸上 其中，z的個(gè)體域是{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ù)超過(guò)野人數(shù)。該謂詞同時(shí)也描述了相應(yīng)的狀態(tài)。 再定義描述過(guò)河方案的謂詞： L-R(x, x1, y, y1,S)：x1個(gè)修道士和y1個(gè)野人渡船從河的左岸到河的右岸 條件：Safety(L,x-x1,y-y1,S’)∧Safety(R,3-x+x1,3-y+y1,S’)∧Boat(L,S) 動(dòng)作：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個(gè)修道士和y2個(gè)野人渡船從河的左岸到河的右岸 條件：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(R,S) 動(dòng)作：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(L,S’) (2) 過(guò)河方案 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’) 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,S6)∧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,S10) Safety(L,0,0,S11)∧Safety(R,3,3,S11)∧Boat(R,S11) 2.13 什么是產(chǎn)生式？它的基本形式是什么？代表什么含義？ 解：“產(chǎn)生式”由美國(guó)數(shù)學(xué)家波斯特（E.POST）在1934年首先提出，它根據(jù)串代替規(guī)則提出了一種稱為波斯特機(jī)的計(jì)算模型，模型中的每條規(guī)則稱為產(chǎn)生式。 產(chǎn)生式的基本形式P→Q 或者 IF P THEN Q。P是產(chǎn)生式的前提，也稱為前件，它給出了該產(chǎn)生式可否使用的先決條件，由事實(shí)的邏輯組合來(lái)構(gòu)成；Q是一組結(jié)論或操作，也稱為產(chǎn)生式的后件，它指出當(dāng)前題P滿足時(shí)，應(yīng)該推出的結(jié)論或應(yīng)該執(zhí)行的動(dòng)作。產(chǎn)生式的含義如果前提P滿足，則可推出結(jié)論Q或執(zhí)行Q所規(guī)定的操作。 2.14 產(chǎn)生式表示的特征是什么？ 解：優(yōu)點(diǎn)：自然性、模塊性、有效性 缺點(diǎn)：效率低性、不方便表示結(jié)構(gòu)性知識(shí)的有向圖 2.15 何謂語(yǔ)義網(wǎng)絡(luò)？它有哪些基本的語(yǔ)義關(guān)系？ 解：語(yǔ)義網(wǎng)絡(luò)：用實(shí)體以及語(yǔ)義關(guān)系來(lái)表達(dá)知識(shí)的有向圖 基本的語(yǔ)義關(guān)系： ① 實(shí)例關(guān)系（ISA）:(是一個(gè))(一個(gè)事物是另一個(gè)事物的具體例子) ② 分類關(guān)系（AKO）:(是一種)子類與超類 ③ 成員關(guān)系 (A-member-of): 是一名 ④ 屬性關(guān)系:Have 有、Can 能、Age 年齡 ⑤ 包含關(guān)系 part-of-部分 (不具備屬性) ⑥ 位置關(guān)系:Before，after ⑦ located-on located-under located-outside located-at located-inside ⑧ 相近關(guān)系 similar-to 相似 near-to 接近 2.16 請(qǐng)對(duì)下列命題分別寫出它們的語(yǔ)義網(wǎng)絡(luò)： (1) 每個(gè)學(xué)生都有一臺(tái)計(jì)算機(jī)。 AKO AKO 人 職業(yè) 學(xué)生 AKO 設(shè)備 計(jì)算機(jī) owner owns 占有權(quán) AKO 情況 占有資格 AKO (2) 高老師從3月到7月給計(jì)算機(jī)系學(xué)生講《計(jì)算機(jī)網(wǎng)絡(luò)》課。 解： 7月 8月 Start End 老師 ISA Object Subject 高老師 計(jì)算機(jī)系學(xué)生 講課事件 Action Caurse 計(jì)算機(jī)網(wǎng)絡(luò) 講課 (3) 學(xué)習(xí)班的學(xué)員有男、有女、有研究生、有本科生。 解： 女 男 研究生 本科生 Have Have Have 學(xué)員 (4) 創(chuàng)新公司在科海大街56號(hào)，劉洋是該公司的經(jīng)理，他32歲、碩士學(xué)位。 32 Age Work-for Address Isa 創(chuàng)新公司 劉洋 經(jīng)理 56號(hào) Have 碩士學(xué)位 (5) 紅隊(duì)與藍(lán)隊(duì)進(jìn)行足球比賽，最后以3：2的比分結(jié)束。 解： 比賽 AKO Participants1 Outcome 3:2 2 足球賽 紅隊(duì) Participants 2 藍(lán)隊(duì) 2.17 請(qǐng)把下列命題用一個(gè)語(yǔ)義網(wǎng)絡(luò)表示出來(lái)： (1) 樹和草都是植物； 植物 解： AKO AKO 草 樹 (2) 樹和草都有葉和根； 根 葉 解： Have Have 植物 是一種 是一種 草 樹 (3) 水草是草，且生長(zhǎng)在水中； 解： Live AKO AKO 水草 水中 植物 草 (4) 果樹是樹，且會(huì)結(jié)果； 解： Can AKO AKO 果樹 結(jié)果 植物 樹 (5) 梨樹是果樹中的一種，它會(huì)結(jié)梨。 解： Can AKO AKO 梨樹 樹 果樹 結(jié)梨 2.18 試述語(yǔ)義網(wǎng)絡(luò)中求解問題的一般過(guò)程 解：語(yǔ)義網(wǎng)絡(luò)的推理過(guò)程主要有兩種，一種是繼承，另一種是匹配。 繼承是指把對(duì)事物的描述從抽象節(jié)點(diǎn)傳遞到具體節(jié)點(diǎn)。 匹配是指在知識(shí)庫(kù)的語(yǔ)義網(wǎng)絡(luò)中尋找與待求解問題相符的語(yǔ)義網(wǎng)絡(luò)模式。 2.19 試述語(yǔ)義網(wǎng)絡(luò)表示法的特點(diǎn) 解：結(jié)構(gòu)性 聯(lián)想性 自然性 缺點(diǎn)：非嚴(yán)格性，復(fù)雜性 2.20 何謂框架？框架的一般形式是什么？ 解：框架表示法是在框架理論的基礎(chǔ)上發(fā)展起來(lái)的一種結(jié)構(gòu)化知識(shí)表示方法。 框架通常由描述事物各個(gè)方面的若干槽組成，每一個(gè)槽也可以根據(jù)實(shí)際情況擁有若干個(gè)側(cè)面，每一個(gè)側(cè)面又可以擁有若干個(gè)值。 2.21 何謂實(shí)例框架？它與框架有什么關(guān)系？ 解：當(dāng)人們把觀察或認(rèn)識(shí)到的具體細(xì)節(jié)填入框架后，就得到了該框架的一個(gè)具體實(shí)例，框架的這種具體實(shí)例被稱為實(shí)例框架。 通用結(jié)構(gòu)與具體實(shí)例，抽象與具體。 2.22 何謂框架系統(tǒng)？何謂框架系統(tǒng)的橫向聯(lián)系？何謂框架系統(tǒng)的縱向聯(lián)系？ 解：在框架理論中，框架是知識(shí)的基本單位，把一組有關(guān)的框架連接起來(lái)便可形成一個(gè)框架系統(tǒng)。在框架系統(tǒng)中，系統(tǒng)的行為由該系統(tǒng)內(nèi)框架的變化來(lái)實(shí)現(xiàn)，系統(tǒng)的推理過(guò)程由框架之間的協(xié)調(diào)完成。 縱向聯(lián)系：表示那種具有演繹關(guān)系的知識(shí)結(jié)構(gòu)，下層框架與上層框架之間具有一種繼承關(guān)系，這種具有繼承關(guān)系的框架之間的聯(lián)系稱為縱向聯(lián)系。 橫向聯(lián)系：由于一個(gè)框架的槽值或側(cè)面值可以是另外一個(gè)框架的名字，這就在框架之間建立了另外一種聯(lián)系，稱為橫向聯(lián)系。 2.23 假設(shè)有以下一段天氣預(yù)報(bào)：“北京地區(qū)今天白天晴，偏北風(fēng)3級(jí)，最高氣溫12，最低氣溫-2，降水概率15%?！闭?qǐng)用框架表示這一知識(shí)。 解： Frame<天氣預(yù)報(bào)> 地域：北京 時(shí)段：今天白天 天氣：晴 風(fēng)向：偏北 風(fēng)力：3級(jí) 氣溫：最高：12度 最低：-2度 降水概率：15% 2.24 按“師生框架”、“教師框架”、“學(xué)生框架”的形式寫出一個(gè)框架系統(tǒng)的描述。 解：師生框架 Frame Name：Unit（Last-name，F(xiàn)irst-name） Sex：Area（male，female） Default：male 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 Paper：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 2.25 在框架系統(tǒng)中，問題求解的一般過(guò)程是什么？ 解：特性繼承 框架的匹配與填槽 2.26 框架表示法的特點(diǎn)有哪些？ 解：優(yōu)點(diǎn)：結(jié)構(gòu)性，深層性，繼承性，自然性。 缺點(diǎn)：缺乏框架的形式理論，缺乏過(guò)程性知識(shí)表示，清晰性難以保證 2.27 何謂產(chǎn)生式系統(tǒng)？產(chǎn)生式推理的基本結(jié)構(gòu)由哪幾部分組成？ 解：利用產(chǎn)生式知識(shí)表示方法所進(jìn)行的推理稱為產(chǎn)生式推理，由此產(chǎn)生的系統(tǒng)為產(chǎn)生式系統(tǒng) 基本結(jié)構(gòu)：綜合數(shù)據(jù)庫(kù)，規(guī)則庫(kù)，控制系統(tǒng) 2.28 什么是產(chǎn)生式的正向推理？其基本過(guò)程是什么？ 解：從已知事實(shí)出發(fā)，正向使用推理規(guī)則的推理方法。 過(guò)程： （1）把用戶提供的初始證據(jù)放入綜合數(shù)據(jù)庫(kù)； （2）檢查綜合數(shù)據(jù)庫(kù)中是否包含了問題的解，若已包含，則求解結(jié)束，并成功推出， 否則，執(zhí)行下一步； （3）檢查知識(shí)庫(kù)中是否有可用知識(shí)。若有，形成當(dāng)前可用知識(shí)集，執(zhí)行下一步，否則轉(zhuǎn)（5）； （4）按照某種沖突消解策略，從當(dāng)前可用知識(shí)集中選出一條知識(shí)進(jìn)行推理，并將推出的新事實(shí)加入綜合數(shù)據(jù)庫(kù)中，然后轉(zhuǎn)（2）； （5）詢問用戶是否可以進(jìn)一步補(bǔ)充新的事實(shí)，若可補(bǔ)充，則將補(bǔ)充的新事實(shí)加入綜合數(shù)據(jù)庫(kù)中，然后轉(zhuǎn)（3），否則表示無(wú)解，失敗退出。 2.29 什么是逆向推理？其基本過(guò)程是什么？ 解：以某個(gè)假設(shè)目標(biāo)作為出發(fā)點(diǎn)的推理方法 過(guò)程： （1） 將問題的初始證據(jù)和要求證的目標(biāo)（稱為假設(shè)）分別放入綜合數(shù)據(jù)庫(kù)和假設(shè)集； （2） 從假設(shè)集中選出一個(gè)假設(shè)，檢查該假設(shè)是否在綜合數(shù)據(jù)庫(kù)中，若在，則該假設(shè)成立。此時(shí)，若假設(shè)集為空，則成功退出。否則，扔執(zhí)行（2）。若該假設(shè)不在數(shù)據(jù)庫(kù)中，則執(zhí)行下一步； （3） 檢查該假設(shè)是否可由知識(shí)庫(kù)的某個(gè)知識(shí)導(dǎo)出，若不能由某個(gè)知識(shí)導(dǎo)出，則詢問用戶尋找新的假設(shè)。若不是，則轉(zhuǎn)（5），若能由某個(gè)知識(shí)導(dǎo)出，則執(zhí)行下一步； （4） 將知識(shí)庫(kù)中可以導(dǎo)出該假設(shè)的所有知識(shí)構(gòu)成一個(gè)可用知識(shí)集； （5） 檢查可用知識(shí)集是否為空，若空，失敗退出。否則執(zhí)行下一步； （6） 按沖突消解策略從可用知識(shí)集中取出一個(gè)知識(shí)，繼續(xù)執(zhí)行下一步； （7） 將該知識(shí)的前提中的每個(gè)子條件都作為新的假設(shè)放入假設(shè)集，轉(zhuǎn)（2）。 2.30 什么是混合推理？它由哪幾種實(shí)現(xiàn)方式？ 解：正向推理和逆向推理結(jié)合起來(lái)所進(jìn)行的推理稱為混合推理 實(shí)現(xiàn)：先正后逆，先逆后正，隨機(jī) 2.31 什么是置換？什么是合一？ 解：在不同謂詞公式中，往往會(huì)出現(xiàn)多個(gè)謂詞的謂詞名相同但個(gè)體不同的情況，此時(shí)推理過(guò)程是不能直接進(jìn)行匹配的，需要先進(jìn)行變?cè)奶鎿Q。這種利用項(xiàng)對(duì)變?cè)M(jìn)行替換叫置換。 合一利用置換使兩個(gè)或多個(gè)謂詞的個(gè)體一致。 2.32 判斷下列公式是否為可合一，若可合一，則求出其相應(yīng)的置換 解：(1)可合一，其最一般和一為：σ={a/x,b/y}。 (2)可合一，其最一般和一為：σ={ f(x)/y,b/z}。 (3)可合一，其最一般和一為：σ={f(b)/y,b/x}。 (4)不可合一。 (5)可合一，其最一般和一為：σ={y/x}。 2.33 什么是自然演繹推理？它所依據(jù)的推理規(guī)則是什么？ 從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論的過(guò)程稱為自然演繹推理 推理規(guī)則：等價(jià)式，永真蘊(yùn)涵式，置換，合一 2.34 什么是謂詞公式的可滿足性？什么是謂詞公式的不可滿足性？ 教材P55.56頁(yè) 2.35 什么是謂詞公式的前束范式？什么是謂詞公式的Skolem范式？ 教材P56 2.36 什么是字句集？如何將謂詞公式化為字句集？ 教材P56.57 2.37 把下列謂詞公式化成子句集： (1) (x)(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)行變?cè)獡Q名得子句集： S={ P(x, y), Q(u, v)} (2) 對(duì)謂詞公式(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) 對(duì)謂詞公式(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(x))∨R(x, f(x))) 此公式已為Skolem標(biāo)準(zhǔn)型。 最后消去全稱量詞得子句集： S={P(x, f(x))∨Q(x, f(x))∨R(x, f(x))} (4) 對(duì)謂詞(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)型。 最后消去全稱量詞得子句集： S={P(x, y)∨Q(x, y)∨R(x, f(x,y))} 2.38 魯濱遜歸結(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(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é)過(guò)程為： P∨Q Q P P NIL (2) 不可滿足，其歸結(jié)過(guò)程為： P∨Q P∨Q Q P∨Q P∨Q Q NIL (3) 不是不可滿足的，原因是不能由它導(dǎo)出空子句。 (4) 不可滿足，其歸結(jié)過(guò)程略 (5) 不是不可滿足的，原因是不能由它導(dǎo)出空子句。 (6) 不可滿足，其歸結(jié)過(guò)程略 2.40 對(duì)下列各題分別證明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) 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)} 再對(duì)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={ P(x)∨ Q(x)} 因此，擴(kuò)充的子句集為： S={ P(x)，(Q(a)∨Q(b))， P(x)∨ Q(x)} 再對(duì)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)，其求解過(guò)程略。 2.41 設(shè)已知： (1) 如果x是y的父親，y是z的父親，則x是z的祖父； (2) 每個(gè)人都有一個(gè)父親。 使用歸結(jié)演繹推理證明：對(duì)于某人u，一定存在一個(gè)人v，v是u的祖父。 解：先定義謂詞 F(x,y)：x是y的父親 GF(x,z)：x是z的祖父 P(x)：x是一個(gè)人 再用謂詞把問題描述出來(lái)： 已知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(x,y)∨F(y,z)∨GF(x,z) ② P(r)∨F(s,r) ③ P(u) ④ GF(v,u)) 對(duì)上述擴(kuò)充的子句集，其歸結(jié)推理過(guò)程如下： 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} {y/z} {y/u} 由于導(dǎo)出了空子句，故結(jié)論得證。 2.42 假設(shè)張被盜，公安局派出5個(gè)人去調(diào)查。案情分析時(shí)，貞察員A說(shuō)：“趙與錢中至少有一個(gè)人作案”，貞察員B說(shuō)：“錢與孫中至少有一個(gè)人作案”，貞察員C說(shuō)：“孫與李中至少有一個(gè)人作案”，貞察員D說(shuō)：“趙與孫中至少有一個(gè)人與此案無(wú)關(guān)”，貞察員E說(shuō)：“錢與李中至少有一個(gè)人與此案無(wú)關(guān)”。如果這5個(gè)偵察員的話都是可信的，使用歸結(jié)演繹推理求出誰(shuí)是盜竊犯。 解：(1) 先定義謂詞和常量 設(shè)C(x)表示x作案，Z表示趙，Q表示錢，S表示孫，L表示李 (2) 將已知事實(shí)用謂詞公式表示出來(lái) 趙與錢中至少有一個(gè)人作案：C(Z)∨C(Q) 錢與孫中至少有一個(gè)人作案：C(Q)∨C(S) 孫與李中至少有一個(gè)人作案：C(S)∨C(L) 趙與孫中至少有一個(gè)人與此案無(wú)關(guān)： (C (Z)∧C(S))，即 C (Z) ∨C(S) 錢與李中至少有一個(gè)人與此案無(wú)關(guān)： (C (Q)∧C(L))，即 C (Q) ∨C(L) (3) 將所要求的問題用謂詞公式表示出來(lái)，并與其否定取析取。 設(shè)作案者為u，則要求的結(jié)論是C(u)。將其與其否)取析取，得： C(u) ∨C(u) (4) 對(duì)上述擴(kuò)充的子句集，按歸結(jié)原理進(jìn)行歸結(jié)，其修改的證明樹如下： C(Z)∨C(Q) C (Z) ∨C(S) C(Q)∨C(S) C(Q)∨C(S) C(Q) C(u)∨C(u) C(Q) {Q/u} 因此，錢是盜竊犯。實(shí)際上，本案的盜竊犯不止一人。根據(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) C(u)∨C(u) C(S) {S/u} C(S) 因此，孫也是盜竊犯。 2.43 設(shè)已知： (1) 能閱讀的人是識(shí)字的； (2) 海豚不識(shí)字； (3) 有些海豚是很聰明的。 請(qǐng)用歸結(jié)演繹推理證明：有些很聰明的人并不識(shí)字。 解：第一步，先定義謂詞， 設(shè)R(x)表示x是能閱讀的； K(y)表示y是識(shí)字的； W(z) 表示z是很聰明的； 第二步，將已知事實(shí)和目標(biāo)用謂詞公式表示出來(lái) 能閱讀的人是識(shí)字的：(x)(R(x))→K(x)) 海豚不識(shí)字：(y)(K (y)) 有些海豚是很聰明的：(z) W(z) 有些很聰明的人并不識(shí)字：(x)( W(z)∧K(x)) 第三步，將上述已知事實(shí)和目標(biāo)的否定化成子句集： 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 什么是搜索？有哪兩大類不同的搜索方法？?jī)烧叩膮^(qū)別是什么？ 解：像這種根據(jù)問題的實(shí)際情況，不斷尋找可利用知識(shí)，從而構(gòu)造一條最小的推理路線，使問題得以解決的過(guò)程稱為搜索 可根據(jù)搜索過(guò)程是否使用啟發(fā)式信息分為盲目搜索和啟發(fā)式搜索，也可根據(jù)問題的表示方式分為狀態(tài)空間搜索和與/或搜索 盲目搜索是按預(yù)定的控制策略進(jìn)行搜索，在搜索過(guò)程中獲得的中間信息并不改變控制策略 啟發(fā)式搜索是在搜索中加入了與問題有關(guān)的啟發(fā)性信息，用于指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問題的求解過(guò)程，并找到最優(yōu)解。 狀態(tài)空間搜索是指用狀態(tài)空間法來(lái)表示問題所進(jìn)行的搜索。 與/或搜索是指用問題歸約法來(lái)表示問題時(shí)所進(jìn)行的搜索。 3.2 什么是狀態(tài)空間？用狀態(tài)空間表示問題時(shí)，什么是問題的解？什么是最優(yōu)解？最優(yōu)解唯一嗎？ 解：狀態(tài)空間（state space）是由一個(gè)問題的全部狀態(tài)，以及這些狀態(tài)之間的相互關(guān)系所構(gòu)成的集合，它可用一個(gè)三元祖（S,F,G）來(lái)表示，其中,S為問題的所有初始狀態(tài)的集合；F為操作的集合；G為目標(biāo)狀態(tài)的集合。 由初始狀態(tài)到目標(biāo)狀態(tài)所使用的算符序列就是該問題的一個(gè)解。 使某目標(biāo)函數(shù)達(dá)到最優(yōu)值（最大值或最小值）的任一可行解，都稱為該問題的一個(gè)最優(yōu)解。 最優(yōu)解不唯一。 3.3什么是與樹？什么是或樹？什么是與/或樹？什么是可解節(jié)點(diǎn)？什么是解樹？ 解：把一個(gè)原問題分解為若干個(gè)子問題可用一個(gè)“與樹”來(lái)表示。 把一個(gè)原問題變換為若干個(gè)子問題可用一個(gè)“或樹”來(lái)表示。 如果一個(gè)問題既需要通過(guò)分解，有需要通過(guò)變換才能得到其本原問題，則其歸約過(guò)程可用一個(gè)“與/或樹”來(lái)表示 在與/或樹中，滿足以下三個(gè)條件之一的節(jié)點(diǎn)為可解節(jié)點(diǎn)： （1） 任何終止節(jié)點(diǎn)都是可解節(jié)點(diǎn) （2） 對(duì)“或”節(jié)點(diǎn)，當(dāng)其子節(jié)點(diǎn)中至少有一個(gè)為可解節(jié)點(diǎn)時(shí)，則該或節(jié)點(diǎn)就是可解節(jié)點(diǎn) （3） 對(duì)“與”節(jié)點(diǎn)，只有當(dāng)其子節(jié)點(diǎn)全部為可解節(jié)點(diǎn)時(shí)，該與節(jié)點(diǎn)才是可解節(jié)點(diǎn)。 解樹：由可解節(jié)點(diǎn)構(gòu)成，并且有這些可解節(jié)點(diǎn)可以推出初始節(jié)點(diǎn)為可解節(jié)點(diǎn)的子樹為解樹。 3.4 在狀態(tài)空間一般搜索過(guò)程中，open表與closed表的作用與區(qū)別是什么？ 解：open表中存放待考察節(jié)點(diǎn)，close表存放考察過(guò)的節(jié)點(diǎn)。 3.5 有一農(nóng)夫帶一條狼，一只羊和一筐菜從河的左岸乘船到右岸，但受下列條件限制： （1）船太小，農(nóng)夫每次只能帶一樣?xùn)|西過(guò)河 （2）如果沒有農(nóng)夫看管，則狼要吃羊，羊要吃菜 請(qǐng)?jiān)O(shè)計(jì)一個(gè)過(guò)河方案，使得農(nóng)夫、狼羊都能不受損失的過(guò)河，畫出相應(yīng)的狀態(tài)空間圖 有一農(nóng)夫帶一條狼，一只羊和一框青菜與從河的左岸乘船倒右岸，但受到下列條件的限制： (1) 船太小，農(nóng)夫每次只能帶一樣?xùn)|西過(guò)河； (2) 如果沒有農(nóng)夫看管，則狼要吃羊，羊要吃菜。 請(qǐng)?jiān)O(shè)計(jì)一個(gè)過(guò)河方案，使得農(nóng)夫、浪、羊都能不受損失的過(guò)河，畫出相應(yīng)的狀態(tài)空間圖。 題示：(1) 用四元組（農(nóng)夫，狼，羊，菜）表示狀態(tài)，其中每個(gè)元素都為0或1，用0表示在左岸，用1表示在右岸。 (2) 把每次過(guò)河的一種安排作為一種操作，每次過(guò)河都必須有農(nóng)夫，因?yàn)橹挥兴梢詣澊? 解：第一步，定義問題的描述形式 用四元組S=（f，w，s，v）表示問題狀態(tài)，其中，f，w，s和v分別表示農(nóng)夫，狼，羊和青菜是否在左岸，它們都可以取1或0，取1表示在左岸，取0表示在右岸。 第二步，用所定義的問題狀態(tài)表示方式，把所有可能的問題狀態(tài)表示出來(lái)，包括問題的初始狀態(tài)和目標(biāo)狀態(tài)。 由于狀態(tài)變量有4個(gè)，每個(gè)狀態(tài)變量都有2種取值