《人工智能》-課后習(xí)題答案

《人工智能》課后習(xí)題答案第一章緒論答：人工智能就是讓機(jī)器完成那些如果由人來做則需要智能的事情的科學(xué)。人工智能是相對于人的自然智能而言，即用人工的方法和技術(shù)，研制智能機(jī)器或智能系統(tǒng)來模仿延伸和擴(kuò)展人的智能，實(shí)現(xiàn)智能行為和“機(jī)器思維”，解決需要人類專家才能處理的問題。答：“智能”一詞源于拉丁“Legere”，意思是收集、匯集，智能通常用來表示從中進(jìn)行選擇、理解和感覺。所謂自然智能就是人類和一些動物所具有的智力和行為能力。智力是針對具體情況的，根據(jù)不同的情況有不同的含義?！爸橇Α笔侵笇W(xué)會某種技能的能力，而不是指技能本身。答：專家系統(tǒng)是一個智能的計算機(jī)程序，他運(yùn)用知識和推理步驟來解決只有專家才能解決的復(fù)雜問題。即任何解題能力達(dá)到了同領(lǐng)域人類專家水平的計算機(jī)程序度可以稱為專家系統(tǒng)。答：自然語言處理—語言翻譯系統(tǒng)，金山詞霸系列機(jī)器人—足球機(jī)器人模式識別—MicrosoftCartoonMaker博弈—圍棋和跳棋第二章知識表達(dá)技術(shù)解答：（1）狀態(tài)空間(StateSpace)是利用狀態(tài)變量和操作符號，表示系統(tǒng)或問題的有關(guān)知識的符號體系，狀態(tài)空間是一個四元組（S，O，S0，G）： S—狀態(tài)集合;O—操作算子集合;S0—初始狀態(tài),S0S;G—目的狀 態(tài),GS,(G可若干具體狀態(tài)，也可滿足某些性質(zhì)的路徑信息描述) 從S0結(jié)點(diǎn)到G結(jié)點(diǎn)的路徑被稱為求解路徑。狀態(tài)空間一解是一有限操作算子序列，它使初始狀態(tài)轉(zhuǎn)換為目標(biāo)狀態(tài)： O1O2O3Ok S0S1S2……G 其中O1，…，Ok即為狀態(tài)空間的一個解(解往往不是唯一的)（2）謂詞邏輯是命題邏輯的擴(kuò)充和發(fā)展，它將原子命題分解成客體和謂詞兩個部分。與命題邏輯中命題公式相對應(yīng)，謂詞邏輯中也有謂詞（命題函數(shù)）公式、原子謂詞公式、復(fù)合謂詞公式等概念。一階謂詞邏輯是謂詞邏輯中最直觀的一種邏輯。（3）語義網(wǎng)絡(luò)是一種采用網(wǎng)絡(luò)形式表示人類知識的方法。即用一個有向圖表示概念和概念之間的關(guān)系，其中節(jié)點(diǎn)代表概念，節(jié)點(diǎn)之間的連接弧(也稱聯(lián)想弧)代表概念之間的關(guān)系。常見的語義網(wǎng)絡(luò)形式有命題語義網(wǎng)絡(luò)、數(shù)據(jù)語義網(wǎng)絡(luò)：E-R圖（實(shí)體-關(guān)系圖）、語言語義網(wǎng)絡(luò)等。解答：（1）GSGSgMAHMANAREMORTALISAISAISAISA動作主體F動作對象（2）colocolorGSgCHWCLOUDHASLININGISAISAISAISA動作主體F動作對象SILVER(3)belongbelongGSgMPSMANAGERSPARTICIPATEPLANISAISAISAISA動作主體F動作對象BRANCHMANAGERSPROFIT-SHARINGPLANISADECISA解答：設(shè)有如下四個謂詞：HUMAN(X)X是人 LAWED(X)X受法律管制 COMMIT(X)X犯法PUNISHED(X)X受法律制裁前兩個謂詞可以變?yōu)椋篐UMAN(X)LAWED(X)，表示：人人都要受法律的管制；后兩個謂詞可以變?yōu)椋篊OMMIT(X)PUNISHED(X)，表示只要X犯了罪，X就要受到懲罰；進(jìn)一步，還可以把上述兩個謂詞聯(lián)結(jié)成如下形式：[HUMAN(X)LAWED(X)][COMMIT(X)PUNISHED(X)]本公式的含義是：如果由于某個X是人而受到法律管制，則這個人犯了罪就一定要受到懲罰。晁蓋是人，受法律的管制（老百姓受法律的管制）；所以晁蓋劫了生辰綱，違反了宋王朝的法律，一定要受到官府的追究。高衙內(nèi)是人，卻不受法律的管制（達(dá)官貴人和惡少不受法律的管制）；所以高衙內(nèi)強(qiáng)搶民女，同樣是違反了宋王朝的法律，卻可以橫行無忌。推得：李、徐、周、錢是同一性別解答：題中提供的條件可記為①②③④⑤，依次利用這些條件可得到如下結(jié)果：推得：李、徐、周、錢是同一性別（1）條件②：周和錢是同一性別； 條件⑤：李、徐、周是同一性別； 條件③：李的愛人是陳的愛人的表哥，則李的愛人性別是男，而李的性別是女推得：陳與錢是夫妻這樣可以初步推出：李、徐、周、錢均是女的，對應(yīng)的王、陳、孫、吳均是男的。推得：陳與錢是夫妻（2）條件④：陳與徐、周俊不構(gòu)成夫妻，則陳選擇的余地為錢或李； 條件③：李與陳不構(gòu)成夫妻； 條件④：吳與徐、周均不構(gòu)成夫妻，則吳選擇的余地為李；推得：吳與李是夫妻 條件①：王與周不構(gòu)成夫妻，則王選擇的余地為徐；推得：王與徐是夫妻排除上述已經(jīng)成立的條件，顯然可推得：孫與周是夫妻。解答：符號微積分基本公式為用產(chǎn)生式表示為：Iff(x)and(a,b)ThenF(b)-F(a)解答：題中描述的情況用謂詞形式可表達(dá)如下：DOG(X)X是狗SOUND(X)X會吠叫BIT(X,Y)X咬YANIMAL(X)X是動物題中各條推理則可以表示為：P1:xDOG(X)yBIT(X,Y)∨SOUND(X)P2::x（ANIMAL(X)∧SOUND(X)）yBIT(X,Y)P3:獵犬是狗，即DOG(X)種X的謂詞樣品是獵犬，同時也可得ANIMAL(獵犬)將P3帶入P1可得SOUND(獵犬)，再將SOUND(獵犬)和ANIMAL(獵犬)帶入P2可得yBIT(獵犬,Y)，即可以得到結(jié)果：獵犬是咬人的。解答：題中的三條規(guī)則側(cè)重點(diǎn)不同：R1規(guī)則的重點(diǎn)在于我?guī)煹娜蝿?wù)；R2規(guī)則的重點(diǎn)在于敵團(tuán)的配置；R3規(guī)則的重點(diǎn)在于我?guī)煹娜蝿?wù)和敵團(tuán)的配置同時滿足。它們之間的關(guān)系為R1R2R3。 所以根據(jù)沖突解決規(guī)則中的規(guī)模排序，可知首先應(yīng)該選擇規(guī)則R3，系統(tǒng)執(zhí)行才最有效。解答：ZZIBCLYDE是ISAISAISA動作主體動作對象知更鳥鳥ISACL-1ISACF會飛ISAISAHN占有巢ISATIMESTA春天到秋天ISAISAISA鴕鳥非解答：（1）搖搖海浪戰(zhàn)艦輕輕地動作主體動作對象動作方式（2）

解答：TVTVTP…TDTBZT…B圖書館框架A工業(yè)技術(shù)一般工業(yè)技術(shù)礦業(yè)工程自動化技術(shù)、計算機(jī)技術(shù)水利工程書名作者ISBN出版時間出版社解答：在產(chǎn)生式系統(tǒng)中，隨著產(chǎn)生式規(guī)則的數(shù)量的增加，系統(tǒng)設(shè)計者難以理解規(guī)則間的相互作用，究其原因，在于每條規(guī)則的自含性使得知識表示的力度過于細(xì)微。因此要提高產(chǎn)生式系統(tǒng)的可理解性，就應(yīng)當(dāng)按照軟件工程的思想，通過對規(guī)則的適當(dāng)劃分，將規(guī)則組織誠易于管理的功能模塊。由于框架系統(tǒng)具有組織成塊知識的良好特性，因此將兩者進(jìn)行有機(jī)結(jié)合，可以為產(chǎn)生式系統(tǒng)的開發(fā)、調(diào)試和管理提供有益的幫助。基于框架的表示機(jī)制可以用作產(chǎn)生式語言和推理機(jī)制設(shè)計的一個重要構(gòu)件。另外，框架可以直接用于表示規(guī)則，如果將每一個規(guī)則作為一個框架處理，一組用于解決特定問題的規(guī)則可組織成一類，且在這一類框架中表示這組規(guī)則的各種特性。解答：略解答：（1）題目描述可轉(zhuǎn)換為如下問題（N階漢諾塔問題）有編號為A、B、C的三個柱子和標(biāo)識為1、2、…、N的尺寸依次從小到大的N個有中心孔的金片；初始狀態(tài)下N個金片按1、2、…、N順序堆放在A號柱子上，目標(biāo)狀態(tài)下N個金片以同樣次序順序堆放在B號柱子上，金片的搬移須遵守以下規(guī)則：每次只能搬一個金片，且較大金片不能壓放在較小金片之上，可以借助于C針。（2）假設(shè)基本操作為move(x,A,C,B)，表示將x個金片從A移到B上，中間可借助于C。當(dāng)N=1時，則無需借助中間的C針，就可以直接實(shí)現(xiàn)將1個金片從A移到B上，這也是問題的最簡操作，可表示為move-one(1,A,B)；當(dāng)N>1時，需要用中間的C針作輔助。其操作又可分為以下三步：將N-1個金片從A移到C上，中間可借助于B，轉(zhuǎn)換為基本操作就是move(N-1,A,B,C)；將1個金片直接從A移到B上，轉(zhuǎn)換為基本操作就是move-one(1,A,B)；將N-1個金片從C移到B上，中間可借助于A，轉(zhuǎn)換為基本操作就是move(N-1,C,A,B)；這樣，就將問題的規(guī)模減小為N-1，依次遞歸求解就可以得到相應(yīng)的結(jié)果。（3）設(shè)M(x)表示移動x個金片所需要的操作次數(shù)，則上述N階漢諾塔問題可以表示成如下形式：M(1)=1M(N)=2M(N-1)+1最后可以解得M(N)=2N-1下面給出對梵塔問題給出產(chǎn)生式系統(tǒng)描述，并討論N為任意時狀態(tài)空間的規(guī)模。（1）綜合數(shù)據(jù)庫定義三元組：(A,B,C)，其中A,B,C分別表示三根立柱，均為表，表的元素為1～N之間的整數(shù)，表示N個不同大小的盤子，數(shù)值小的數(shù)表示小盤子，數(shù)值大的數(shù)表示大盤子。表的第一個元素表示立柱最上面的柱子，其余類推。（2）規(guī)則集為了方便表示規(guī)則集，引入以下幾個函數(shù)：first(L)：取表的第一個元素，對于空表，first得到一個很大的大于N的數(shù)值。tail(L)：取表除了第一個元素以外，其余元素組成的表。cons(x,L)：將x加入到表L的最前面。規(guī)則集：r1:IF(A,B,C)and(first(A)<first(B))THEN(tail(A),cons(first(A),B),C)r2:IF(A,B,C)and(first(A)<first(C))THEN(tail(A),B,cons(first(A),C))r3:IF(A,B,C)and(first(B)<first(C))THEN(A,tail(B),cons(first(B),C))r4:IF(A,B,C)and(first(B)<first(A))THEN(cons(first(B),A),tail(B),C)r5:IF(A,B,C)and(first(C)<first(A))THEN(cons(first(C),A),B,tail(C))r6:IF(A,B,C)and(first(C)<first(B))THEN(A,cons(first(C),B),tail(C))(3)初始狀態(tài)：（（1，2，...，N），（），（））

(4)結(jié)束狀態(tài)：（（），（），（1，2，...，N））

問題的狀態(tài)規(guī)模：每一個盤子都有三種選擇：在A上、或者在B上、或者在C上，共N個盤子，所以共有種可能。即問題的狀態(tài)規(guī)模為。解答：(1)定義謂詞G(x,y):x比y大，個體有張三（zhang）、李四（li），將這些個體帶入謂詞中，得到G(zhang,li)和G(zhang,li),根據(jù)語義用邏輯連接詞將它們聯(lián)結(jié)起來就得到表示上述知識的謂詞公式：G(zhang,li)G(zhang,li)。(2)定義謂詞Marry(x,y):x和y結(jié)婚，Male(x):x是男的，F(xiàn)emale(x)：x是女的。個體有甲(A)、乙(B)，將這些個體帶入謂詞中，得到Marry(A,B)、Male(A)、Female(B)以及Male(A)、Female(B),根據(jù)語義用邏輯連接詞將它們聯(lián)結(jié)起來就得到表示上述知識的謂詞公式：Marry(A,B)(Male(A)∧Female(B))∨(Male(B)∧Female(A))(3)定義謂詞Honest(x):x是誠實(shí)的，Lying(x):x會說謊。個體有張三（zhang），將這些個體帶入謂詞中，得到Honest(x)、Lying(x)、Lying(zhang)、Honest(zhang),根據(jù)語義用邏輯連接詞將它們聯(lián)結(jié)起來就得到表示上述知識的謂詞公式：x(Honest(x)Lying(x))(Lying(zhang)Honest(zhang))第三章問題求解方法答：深度優(yōu)先搜索與廣度優(yōu)先搜索的區(qū)別在于：在對節(jié)點(diǎn)n進(jìn)行擴(kuò)展時，其后繼節(jié)點(diǎn)在OPEN表中的存放位置不同。廣度優(yōu)先搜索是將后繼節(jié)點(diǎn)放入OPEN表的末端，而深度優(yōu)先搜索則是將后繼節(jié)點(diǎn)放入OPEN表的前端。廣度優(yōu)先搜索是一種完備搜索，即只要問題有解就一定能夠求出，而深度優(yōu)先搜索是不完備搜索。 在不要求求解速度且目標(biāo)節(jié)點(diǎn)的層次較深的情況下，廣度優(yōu)先搜索優(yōu)于深度優(yōu)先搜索；在要求求解速度且目標(biāo)節(jié)點(diǎn)的層次較淺的情況下，深度優(yōu)先搜索優(yōu)于廣度優(yōu)先搜索。 廣度優(yōu)先的正例：積木問題；深度優(yōu)先的正例：郵遞員問題，反例：國際象棋。答：衡量標(biāo)準(zhǔn)為：這組子狀態(tài)中有沒有目標(biāo)狀態(tài)，如果有，則選擇該節(jié)點(diǎn)并且搜索成功；若沒有，則按照某種控制策略從已生成的狀態(tài)中再選擇一個狀態(tài)作為當(dāng)前狀態(tài)重復(fù)搜索過程。答：(1)廣度優(yōu)先搜索：該程序必須找到解，并且最好是最優(yōu)解；(2)廣度優(yōu)先搜索：醫(yī)生要根據(jù)病人的各種病狀判斷病人的??；(3)深度優(yōu)先搜索：該程序要求一定要找到目標(biāo)路徑；(4)深度優(yōu)先搜索：該程序要求找到最優(yōu)解；(5)廣度優(yōu)先搜索：不能確定它們是否等同，既不能確定它們是否有等同解。答：對于四皇后問題，如果放一個皇后的耗散值為1的話，則任何一個解的耗散值都是4。因此如果h是對該耗散值的估計，是沒有意義的。對于像四皇后這樣的問題，啟發(fā)函數(shù)應(yīng)該是對找到解的可能性的評價。利用一個位置放皇后后，消去的對角線的長度來進(jìn)行評價。答：定義h1=M+C-2B，其中M，C分別是在河的左岸的傳教士人數(shù)和野人人數(shù)。B＝1表示船在左岸，B＝0表示船在右岸。也可以定義h2=M+C。h1是滿足A*條件的，而h2不滿足。要說明h2＝M+C不滿足A*條件是很容易的，只需要給出一個反例就可以了。比如狀態(tài)(1,1,1)，h2=M+C=1+1=2，而實(shí)際上只要一次擺渡就可以達(dá)到目標(biāo)狀態(tài)，其最優(yōu)路徑的耗散值為1。所以不滿足A*的條件。下面我們來證明h1＝M+C-2B是滿足A*條件的。我們分兩種情況考慮。先考慮船在左岸的情況。如果不考慮限制條件，也就是說，船一次可以將三人從左岸運(yùn)到右岸，然后再有一個人將船送回來。這樣，船一個來回可以運(yùn)過河2人，而船仍然在左岸。而最后剩下的三個人，則可以一次將他們?nèi)繌淖蟀哆\(yùn)到右岸。所以，在不考慮限制條件的情況下，也至少需要擺渡次。其中分子上的"－3"表示剩下三個留待最后一次運(yùn)過去。除以"2"是因?yàn)橐粋€來回可以運(yùn)過去2人，需要個來回，而"來回"數(shù)不能是小數(shù)，需要向上取整，這個用符號表示。而乘以"2"是因?yàn)橐粋€來回相當(dāng)于兩次擺渡，所以要乘以2。而最后的"＋1"，則表示將剩下的3個運(yùn)過去，需要一次擺渡。

化簡有：再考慮船在右岸的情況。同樣不考慮限制條件。船在右岸，需要一個人將船運(yùn)到左岸。因此對于狀態(tài)(M，C，0)來說，其所需要的最少擺渡數(shù)，相當(dāng)于船在左岸時狀態(tài)(M+1，C，1)或(M，C+1，1)所需要的最少擺渡數(shù)，再加上第一次將船從右岸送到左岸的一次擺渡數(shù)。因此所需要的最少擺渡數(shù)為：(M+C+1)-2+1。其中(M+C+1)的"＋1"表示送船回到左岸的那個人，而最后邊的"＋1"，表示送船到左岸時的一次擺渡?；営校?M+C+1)-2+1=M+C。綜合船在左岸和船在右岸兩種情況下，所需要的最少擺渡次數(shù)用一個式子表示為：M+C-2B。其中B＝1表示船在左岸，B＝0表示船在右岸。由于該擺渡次數(shù)是在不考慮限制條件下，推出的最少所需要的擺渡次數(shù)。因此，當(dāng)有限制條件時，最優(yōu)的擺渡次數(shù)只能大于等于該擺渡次數(shù)。所以該啟發(fā)函數(shù)h是滿足A*條件的。答：在搜索期間改善h函數(shù)，是一種動態(tài)改變h函數(shù)的方法。像改進(jìn)的A*算法中，對NEXT中的節(jié)點(diǎn)按g值的大小選擇待擴(kuò)展的節(jié)點(diǎn)，相當(dāng)于令這些節(jié)點(diǎn)的h＝0，就是動態(tài)修改h函數(shù)的一種方法。由定理2：若h(n)滿足單調(diào)限制，則由A*所擴(kuò)展的節(jié)點(diǎn)序列，其f值是非遞減的，即f(ni)≤f(nj)），當(dāng)h滿足單調(diào)條件時，A*所擴(kuò)展的節(jié)點(diǎn)序列，其f是非遞減的。對于任何節(jié)點(diǎn)i，j，如果j是i的子節(jié)點(diǎn)，則有f(i)≤f(j)。利用該性質(zhì)，我們可以提出另一種動態(tài)修改h函數(shù)的方法：f(j)=max(f(i),f(j))以f(j)作為節(jié)點(diǎn)j的f值。f值的改變，隱含了h值的改變。當(dāng)h不滿足單調(diào)條件時，經(jīng)過這樣修正后的h具有一定的單調(diào)性質(zhì)，可以減少重復(fù)節(jié)點(diǎn)的可能性。答：像這種類型的問題，由于涉及到城市距離或旅行費(fèi)用，所以利用代價樹廣度優(yōu)先搜索求解。為此，首先必須將旅行交通圖轉(zhuǎn)換為代價樹，轉(zhuǎn)換方法為：從初始節(jié)點(diǎn)A開始，把與它直接相鄰的節(jié)點(diǎn)作為他的后繼節(jié)點(diǎn)，對其他節(jié)點(diǎn)也作同樣的擴(kuò)展，但若一個節(jié)點(diǎn)以作為某節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，則它就不能再作為該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。另外，圖中節(jié)點(diǎn)除了初始節(jié)點(diǎn)A之外，其它的節(jié)點(diǎn)都有可能在代價樹中多次出現(xiàn)，為了區(qū)分它們的多次出現(xiàn)，分別用下標(biāo)1,2…標(biāo)出。但他們卻是圖中的同一個節(jié)點(diǎn)。設(shè)估價函數(shù)f(n)=d(n)+w(n)，其中d(n)為狀態(tài)的深度，w(n)為城市間的距離。代價樹如下所示：ACEBDA定義h1=n*k，其中n是還未走過的城市數(shù)，k是還未走過的城市間距離的最小值。h2＝，其中n是還未走過的城市數(shù)，ki是還未走過的城市間距離中n個最小的距離。顯然這兩個h函數(shù)均滿足A*條件。答：可定義h為：h＝B右邊的W的數(shù)目設(shè)j節(jié)點(diǎn)是i節(jié)點(diǎn)的子節(jié)點(diǎn)，則根據(jù)走法不同，h(i)-h(j)的值和C(i,j)分為如下幾種情況：

（1）B或W走到了相鄰的一個空格位置，此時：h(i)-h(j)=0,C(i,j)=1；

（2）W跳過了1或2個W，此時h(i)-h(j)=0,C(i,j)=1或2；

（3）W向右跳過了一個B（可能同時包含一個W），此時：h(i)-h(j)=-1,C(i,j)=1或2；

（4）W向右跳過了兩個B，此時：h(i)-h(j)=-2,C(i,j)=2；

（5）W向左跳過了一個B（可能同時包含一個W），此時：h(i)-h(j)=1,C(i,j)=1或2；

（6）W向左跳過了兩個B，此時：h(i)-h(j)=2,C(i,j)=2；

（7）B跳過了1或2個B，此時h(i)-h(j)=0,C(i,j)=1或2；

（8）B向右跳過了一個W（可能同時包含一個B），此時：h(i)-h(j)=1,C(i,j)=1或2；

（9）B向右跳過了兩個W，此時：h(i)-h(j)=2,C(i,j)=2；

（10）B向左跳過了一個W（可能同時包含一個B），此時：h(i)-h(j)=-1,C(i,j)=1或2；

（11）B向左跳過了兩個W，此時：h(i)-h(j)=-2,C(i,j)=2；

縱上所述，無論是哪一種情況，具有:h(i)-h(j)≤C(i,j)。且容易驗(yàn)證h(t)=0，所以該h是單調(diào)的。由于h滿足單調(diào)條件，所以也一定有h(n)≤h*(n)，即滿足A*條件。答：答：(1)余一棋的弈法如下：兩棋手可以從5個錢幣堆中輪流拿走一個、兩個或三個錢幣，揀起最后一個錢幣者算輸。試通過博弈證明，后走的選手必勝，并給出一個簡單的特征標(biāo)記來表示取勝策略。為了方便起見，用((AB)()())這樣的表表示一個狀態(tài)。這樣得到搜索圖如下：(2)八數(shù)碼問題空格：Up,Left,Down,Right答：(1)與/或圖的解圖：那些可解結(jié)點(diǎn)的子圖，包含一結(jié)點(diǎn)到目的結(jié)點(diǎn)集的、連通的可解結(jié)點(diǎn)的子圖。在問題的完整的隱含圖中擴(kuò)展生成出包含初始結(jié)點(diǎn)和目的結(jié)點(diǎn)集合的連通的明顯子圖。(2)算法AO*：必須對當(dāng)前已生成出的與或圖中的所有結(jié)點(diǎn)實(shí)施其每解點(diǎn)是否為可解結(jié)點(diǎn)的標(biāo)注過程，如果起始結(jié)點(diǎn)被標(biāo)注為可解的，則搜索過程可成功地結(jié)束；如果起始結(jié)點(diǎn)還不能被標(biāo)注為可解的，則應(yīng)當(dāng)繼續(xù)擴(kuò)展生成結(jié)點(diǎn)（盡可能地記錄，所有生成的結(jié)點(diǎn)中，哪些結(jié)點(diǎn)被標(biāo)注了可解的，以便減少下一次標(biāo)注過程的工作量）；同樣地，對不可解結(jié)點(diǎn)也同樣如此。利用結(jié)點(diǎn)的可解/不可解性質(zhì)，能從搜索圖中刪去可解結(jié)點(diǎn)的任何不可解結(jié)點(diǎn)的子結(jié)點(diǎn)；同樣地，能刪去不可解結(jié)點(diǎn)的所有的子結(jié)點(diǎn)（搜索這些被刪除的結(jié)點(diǎn)是沒有意義的，而只會降低搜索的效率）。兩個主要過程的反復(fù)：自上而下的圖生長過程，并通過跟蹤有標(biāo)記的連接符尋找一個候選局部解圖自下而上的估價函數(shù)值的修正、連接符的標(biāo)記和SOLVED的標(biāo)注過程(3)答：此題要求按照課中例題的方式，給出算法，以下是每個循環(huán)結(jié)束時的搜索圖。上面這種做法比較簡單，也可以如下做：答：略答：博弈搜索通常被限制在一定的范圍，搜索的目標(biāo)是確定一步好的走法（好棋），等對手回手后，再繼續(xù)搜索。因此，博弈搜索過程總是由當(dāng)前狀態(tài)向目標(biāo)狀態(tài)搜索，而不是由目標(biāo)狀態(tài)向當(dāng)前狀態(tài)搜索。這類博弈的實(shí)例有西洋跳棋等。答：8—{（3，0，8）}—{（7，8，3）、（0，6）、（8，9）}—{（7,6）、（8,6,5）、（2,3）、（0,-2）、（6,2）、（5,8）、（9,2）}答：見上圖答：略答：α－β剪裁算法.

α剪裁－若極小層的β<=α(先輩層)則中止這個MIN以下的搜索.

β剪裁－若極大層的α>β(先輩層)則中止這個MAX以下的搜索

算法如下：

doublealphabeta(intdepth,doublealpha,doublebeta,Positionp);

{/*

alpha是MAX的當(dāng)前值

beta是MIN的當(dāng)前值,depth

是在搜索樹中的深度,p是所求結(jié)點(diǎn)的位置*/

double

t;

if(depth=0)

return

evaluate(p);/*

如果P是葉結(jié)點(diǎn),算出P的值

*/

for(i=1;i<=w;i++)

{t=alphabeta(depth-1,beta,alpha,pi);

if(t>alpha&&MAX)

{if(t>beta)

return

t;

/*直接返回*/

else

alpha

=

t;}

if(t<alpha&&MIN)

{if(t<beta)

return

t;

/*直接返回*/

else

alpha=t;}

}

return

alpha;

}

答：略第四章基本的推理技術(shù)答：(1)推理：按照某種策略從已有事實(shí)和知識推出結(jié)論的過程。(2)正向推理 正向推理（事實(shí)驅(qū)動推理）是由已知事實(shí)出發(fā)向結(jié)論方向的推理。 基本思想是：系統(tǒng)根據(jù)用戶提供的初始事實(shí)，在知識庫中搜索能與之匹配的規(guī)則即當(dāng)前可用的規(guī)則，構(gòu)成可適用的規(guī)則集RS，然后按某種沖突解決策略從RS中選擇一條知識進(jìn)行推理，并將推出的結(jié)論作為中間結(jié)果加入到數(shù)據(jù)庫DB中作為下一步推理的事實(shí)，在此之后，再在知識庫中選擇可適用的知識進(jìn)行推理，如此重復(fù)進(jìn)行這一過程，直到得出最終結(jié)論或者知識庫中沒有可適用的知識為止。正向推理簡單、易實(shí)現(xiàn)，但目的性不強(qiáng)，效率低。需要用啟發(fā)性知識解除沖突并控制中間結(jié)果的選取，其中包括必要的回溯。由于不能反推，系統(tǒng)的解釋功能受到影響。(3)反向推理 反向推理是以某個假設(shè)目標(biāo)作為出發(fā)點(diǎn)的一種推理，又稱為目標(biāo)驅(qū)動推理或逆向推理。 反向推理的基本思想是：首先提出一個假設(shè)目標(biāo)，然后由此出發(fā)，進(jìn)一步尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則該假設(shè)成立，推理成功；若無法找到支持該假設(shè)的所有證據(jù)，則說明此假設(shè)不成立，需要另作新的假設(shè)。

與正向推理相比，反向推理的主要優(yōu)點(diǎn)是不必使用與目標(biāo)無關(guān)的知識，目的性強(qiáng)，同時它還有利于向用戶提供解釋。反向推理的缺點(diǎn)是在選擇初始目標(biāo)時具有很大的盲目性，若假設(shè)不正確，就有可能要多次提出假設(shè)，影響了系統(tǒng)的效率。 反向推理比較適合結(jié)論單一或直接提出結(jié)論要求證實(shí)的系統(tǒng)。(4)推理方式分類演繹推理、歸納推理、默認(rèn)推理確定性推理、不精確推理單調(diào)推理、非單調(diào)推理啟發(fā)式推理、非啟發(fā)式推理答：(1)在推理過程中，系統(tǒng)要不斷地用數(shù)據(jù)庫中的事實(shí)與知識庫中的規(guī)則進(jìn)行匹配，當(dāng)有一個以上規(guī)則的條件部分和當(dāng)前數(shù)據(jù)庫相匹配時，就需要有一種策略來決定首先使用哪一條規(guī)則，這就是沖突解決策略。沖突解決策略實(shí)際上就是確定規(guī)則的啟用順序。(2)沖突解決策略：專一性排序、規(guī)則排序、數(shù)據(jù)排序、就近排序、上下文限制、按匹配度排序、按條件個數(shù)排序答：歸結(jié)反演就是利用歸結(jié)和反演實(shí)現(xiàn)定理的證明。具體過程如下：(1)

將定理證明的前提謂詞公式轉(zhuǎn)化為子句集F。(2)

將求證的目標(biāo)表示成合適的謂詞公式G（目標(biāo)公式）。(3)

將目標(biāo)公式的否定式G轉(zhuǎn)化成子句的形式，并加入到子句集F中，得到子句集S。(4)應(yīng)用歸結(jié)原理對子句集S中的子句進(jìn)行歸結(jié)，并把每次歸結(jié)得到的歸結(jié)式都并入S中。如此反復(fù)進(jìn)行，若歸結(jié)得到一個空子句NIL，則停止歸結(jié)，證明了G為真。答：略答：（1）(x)(y)[P(x,y)→Q(x,y)]=(x)(y)[~P(x,y)∨Q(x,y)]={~P(x,y)∨Q(x,y)}子句集為~P(x,y)∨Q(x,y)（2）(x)(y)[P(x,y)Q(x,y)→R(x,y)]=(x))(y)[~P(x,y)∧~Q(x,y)R(x,y)]={~P(x)∨P(x)}=(x)[~P(x,f(x))∧~Q(x,f(x))R(x,f(x))]=~P(x,f(x))∧~Q(x,f(x))R(x,f(x))=[~P(x,f(x))R(x,f(x))]∧[~Q(x,f(x))R(x,f(x))]=[~P(x,f(x))R(x,f(x))]∧[~Q(y,f(y))R(y,f(y))]子句集為~P(x,f(x))R(x,f(x))和~Q(y,f(y))R(y,f(y))（3）(x){(y)P(x,y)→~(y)[Q(x,y)→R(x,y)]}=(x)){(y)~P(x,y)∨~(y)[Q(x,y)→R(x,y)]}=(x)[(y)~P(x,y)∨(y)[~Q(x,y)∨R(x,y)]=(x)[~P(x,f(x))∨[~Q(x,f(x))∨R(x,f(x))]=~P(x,f(x))∨~Q(x,f(x))∨R(x,f(x))子句集為~P(x,f(x))∨~Q(x,f(x))∨R(x,f(x))答：(1)(2){A/x,A/y,A/z,A/w,A/u}(3)答：（1）（x）{[P（x）→P（A）]∧[P（x）→P（B）]}

目標(biāo)取反化子句集：

~（x）{[P（x）→P（A）]∧[P（x）→P（B）]}

~（x）{[~P（x）∨P（A）]∧[~P（x）∨P（B）]}

（x）{[P（x）∧~P（A）]∨[P（x）∧~P（B）]}

（x）{[P（x）∧~P（A）]∨P（x）}∧{[P（x）∧~P（A）]∨~P（B）}}

（x）{P（x）∧[~P（A）∨P（x）]∧[P（x）∨~P（B）]∧[~P（A）∨~P（B）]}

P（x）∧[~P（A）∨P（x）]∧[P（x）∨~P（B）]∧[~P（A）∨~P（B）]

得子句集：

1,P(x1)

2,~P(A)∨P{x2}

3,P(x3)∨~P(B)

4,~P(A)∨~P(B)（2）（x）{P（x）∧[Q（A）∨Q（B）]}→（x）[P（x）∧Q（x）]

目標(biāo)取反化子句集：

~{(x){P(x)∧[Q(A)∨Q(B)]}→(x)[P(x)∧Q(x)]}

~{~{(x)P(x)∧[Q(A)∨Q(B)]}∨(x)[P(x)∧Q(x)]}

{(x)P(x)∧[Q(A)∨Q(B)]}∧(x)[~P(x)∨~Q(x)]}

{(x)P(x)∧[Q(A)∨Q(B)]}∧(y)[~P(y)∨~Q(y)]}

(x)(y){P(x)∧[Q(A)∨Q(B)]∧[~P(y)∨~Q(y)]}

P(x)∧[Q(A)∨Q(B)]∧[~P(y)∨~Q(y)]

得子句集：

1，P(x)

2，Q(A)∨Q(B)

3，~P(y)∨~Q(y)答：答：答：我們用Skier(x)表示x是滑雪運(yùn)動員，Alpinist(x)表示x是登山運(yùn)動員，Alpine(x)表示x是Alpine俱樂部的成員。

問題用謂詞公式表示如下：

已知：

(1)Alpine(Tony)

(2)Alpine(Mike)

(3)Alpine(John)

(4)(x){Alpine(x)→[Skier(x)∨Alpinist(x)]}

(5)(x){Alpinist(x)→~Like(x,Rain)}

(6)(x){~Like(x,Snow)→~Skier(x)}

(7)(x){Like(Tony,x)→~Like(Mike,x)}

(8)(x){~Like(Tony,x)→Like(Mike,x)}

(9)Like(Tony,Snow)

(10)Like(Tony,Rain)

目標(biāo)：(x){Alpine(x)∧Alpinist(x)∧~Skier(x)}

化子句集：

(1)Alpine(Tony)

(2)Alpine(Mike)

(3)Alpine(John)

(4)(x){Alpine(x)→[Skier(x)∨Alpinist(x)]}=(x){~Alpine(x)∨[Skier(x)∨Alpinist(x)]}=>~Alpine(x)∨Skier(x)∨Alpinist(x)

(5)(x){Alpinist(x)→~Like(x,Rain)}=(x){~Alpinist(x)∨~Like(x,Rain)}=>~Alpinist(x)∨~Like(x,Rain)

(6)(x){~Like(x,Snow)→~Skier(x)}=(x){Like(x,Snow)∨~Skier(x)}=>Like(x,Snow)∨~Skier(x)

(7)(x){Like(Tony,x)→~Like(Mike,x)}=(x){~Like(Tony,x)∨~Like(Mike,x)}=>~Like(Tony,x)∨~Like(Mike,x)

(8)(x){~Like(Tony,x)→Like(Mike,x)}=(x){Like(Tony,x)∨Like(Mike,x)}=>Like(Tony,x)∨Like(Mike,x)

(9)Like(Tony,Snow)(10)Like(Tony,Rain)

目標(biāo)取反：

~(x){Alpine(x)∧Alpinist(x)∧~Skier(x)}

=(x){~Alpine(x)∨~Alpinist(x)∨Skier(x)}

=>~Alpine(x)∨~Alpinist(x)∨Skier(x)

經(jīng)變量換名后，得到子句集：

{Alpine(Tony),Alpine(Mike),Alpine(John),~Alpine(x1)∨Skier(x1)∨Alpinist(x1),~Alpinist(x2)∨~Like(x2,Rain),Like(x3,Snow)∨~Skier(x3),~Like(Tony,x4)∨~Like(Mike,x4),Like(Tony,x5)∨Like(Mike,x5),Like(Tony,Snow),Like(Tony,Rain),~Alpine(x)∨~Alpinist(x)∨Skier(x)}歸結(jié)樹如下：答：基于規(guī)則的演繹推理可分為正向演繹推理、反向演繹推理和正反向混合演繹推理。在正向演繹推理中，作為F規(guī)則用的蘊(yùn)含式對事實(shí)的總數(shù)據(jù)庫進(jìn)行操作運(yùn)算，直至得到該目標(biāo)公式的一個終止條件為止。事實(shí)目標(biāo)公式在反向演繹推理中，作為B規(guī)則用的蘊(yùn)含式對目標(biāo)的總數(shù)據(jù)庫進(jìn)行操作運(yùn)算，直至得到包含這些事實(shí)的終止條件為止。目標(biāo)公式事實(shí)答：第五章不精確推理答：不精確推理是建立在非經(jīng)典邏輯基礎(chǔ)上的一種推理，是基于不確定性知識的推理。不精確推理就是從不確定性的初始事實(shí)（證據(jù)）出發(fā)，通過運(yùn)用不確定性的知識，最終推出具有一定程度的不確定性卻是合理或者近乎合理的結(jié)論的思維過程。在不精確推理中，知識和證據(jù)都具有不確定性，這為推理機(jī)的設(shè)計與實(shí)現(xiàn)增加了復(fù)雜度和難度。它除了必須解決推理方向、推理方法和控制策略等基本問題外，一般還需要解決不確定性的表示、不確定性的匹配和不確定性的更新算法等問題。答：有明確定義但不一定出現(xiàn)的事件中包含的不確定性稱為隨機(jī)性，他不因人的主觀意思變化，由事物本身的因果律決定。不精確推理就是表示和處理隨機(jī)性的推理方法。答：(1)當(dāng)有一個證據(jù)E1時，根據(jù)Bayes公式，可得==*（*+*+*）==同理可得：====這說明，由于證據(jù)E1的出現(xiàn)，H1和H3成立的可能性有所增加，而H2成立的可能性有所下降。(2)當(dāng)證據(jù)E1、E2同時出現(xiàn)時，根據(jù)多證據(jù)情況下的Bayes公式，可得=（++）=同理可得：這說明，由于證據(jù)E1和E2的出現(xiàn)，H1和H2成立的可能性有不同程度的增加，而H3成立的可能性則有了較大幅度的下降。答：①LSLS為規(guī)則的充分性量度，它反映E的出現(xiàn)對H的支持程度。當(dāng)LS=1時，O(H|E)=O(H)，說明E對H沒有影響；當(dāng)LS>1時，O(H|E)>O(H)，說明E支持H，且LS越大，E對H的支持越充分，若LS為∞，則E為真時H就為真；當(dāng)LS<1時，O(H|E)<O(H)，說明E排斥H，若LS為0，則O(H|E)=0，即E為真時H就為假②LNLN為規(guī)則的必要性量度，它反映E對H的支持程度，即E的出現(xiàn)對H的必要性。當(dāng)LN=1時，O(H|E)=O(H)，說明E對H沒有影響；當(dāng)LN>1時，O(H|E)>O(H)，說明E支持H，且LN越大，E對H的支持越充分，若LN為∞，則E為真時H就為真；當(dāng)LN<1時，O(H|E)<O(H)，說明E排斥H，若LS為0，則O(H|E)=0，即E為真時H就為假③LS和LN的關(guān)系由于E和E不會同時支持或排斥H，所以只有以下三種情況存在： 情形1：LS>1且LN<1 情形2：LS<1且LN>1 情形3：LS=LN=1 答：答：根據(jù)經(jīng)驗(yàn)對一個事物或現(xiàn)象為真的相信程度稱為可信度。規(guī)則的一般形式為：IFETHENH（CF(H,E)）。其中，CF(H,E)是該規(guī)則的可信度，稱為可信度因子或規(guī)則強(qiáng)度。CF(H,E)在[-1，1]上取值，它表示在已知證據(jù)E的情況下對假設(shè)H為真的支持程度。CF(H,E)定義如下：CF(H,E)=MB(H,E)－MD(H,E)。其中，MB（MeasureBelief）稱為信任增長度，表示因證據(jù)E的出現(xiàn)而增加對假設(shè)H為真的信任增加程度[MB(H,E)>0P(H|E)>P(H)]；MD（MeasureDisbelief）稱為不信任增長度，表示因證據(jù)E的出現(xiàn)對假設(shè)H為假的信任減少的程度[MD(H,E)>0P(H|E)<P(H)]。答：HHE2E1E5E6E7E3E4R2R1R3R4ANDORR5（1）求證據(jù)E3、E4邏輯組合的可信度 CF(E3ANDE4)=min{CF(E3),CF(E4)}=min{,09}=(2）根據(jù)規(guī)則R3求CF(E1) CF(E1)=×max{0,CF(E3ANDE4)}=×=（3）求證據(jù)E6、E7邏輯組合的可信度 CF(E6ORE7)=max{CF(E6),CF(E7)}=max{,}=（4）根據(jù)規(guī)則R5求CF1(E2) CF1(E2)=×max{0,CF(E6ORE7)}=×0.5=（5）根據(jù)規(guī)則R4求CF2(E2) CF2(E2)=×max{0,CF(E5)}=×0.8=（6）根據(jù)規(guī)則R5求CF1(E2) CF1(E2)=×max{0,CF(E6ORE7)}=×0.5=（7）組合由獨(dú)立證據(jù)導(dǎo)出的假設(shè)E2的可信度CF1(E2)、CF2(E2)，得到E2的綜合可信度CF(E2) CF(E2)=CF1(H)+CF2(H)=（8）根據(jù)規(guī)則R1求CF1(H1) CF1(H1)=×max{0,CF(E1)}=×0.72=（8）根據(jù)規(guī)則R2求CF2(H1) CF2(H1)=×max{0,CF(E2)}=×0.41=（9）組合由獨(dú)立證據(jù)導(dǎo)出的假設(shè)H1的可信度CF1(H1)、CF2(H1)，得到H1的綜合可信度CF(H1) CF(H)=CF1(H)+CF2(H)-CF1(H)·CF2(H)=+答：已經(jīng)出現(xiàn)但難以給出精確定義的事件中包含的不確定性稱為模糊性，是由事物的概念界限模糊和人的主觀推理與判斷產(chǎn)生的。而有明確定義但不一定出現(xiàn)的事件中包含的不確定性稱為隨機(jī)性，他不因人的主觀意思變化，由事物本身的因果律決定。不精確推理就是表示和處理隨機(jī)性的推理方法。兩者之間有著本質(zhì)的區(qū)別。答：=x1+x2+x3+x4+x5；=x1+x2+x3+x4+x5； =x1+x2+x3+x4+x5。答：=答：模糊推理實(shí)質(zhì)上是在模糊集合上進(jìn)行操作。在同一論域中，證據(jù)的“與”、“或”、“非”運(yùn)算通常可以對應(yīng)于模糊集的交、并、求補(bǔ)操作；不同論域中的邏輯運(yùn)算一般需拓廣至笛卡爾意義下的相應(yīng)操作。邏輯推理是通過邏輯蘊(yùn)含實(shí)現(xiàn)的。設(shè)U和V為兩個論域，A是U上的模糊子集，B是V上的模糊子集，則規(guī)則IFATHENB可以定義為U×V上的一個模糊關(guān)系：或等價表示成：第六章PROLOG語言答：（1）目標(biāo)不成功（2）目標(biāo)不成功（3）目標(biāo)成功，x,y,z被例化為x1,y1,z1（4）目標(biāo)不成功（5）目標(biāo)不成功答：poglog規(guī)則Is_mother(x):_mother(x,y)Is_father(x):_father(x,y)Is_son(x):_father(y,x),male(x)Grandpa(x,y):_father(x,y1),father(y1,y)Sibling(x,y):_diff(x,y),mother(z1,x),mother(z1,y),father(z2,x),father(z2,y),parent(x,y)答：(1)文件頭:/*****************************************************************************Copyright(c)SabuFrancisAssociates******************************************************************************/classfamily1opencorepredicatesclassInfo:core::classInfo.%@shortClassinformationpredicate.%@detailThispredicaterepresentsinformationpredicateofthisclass.%@endpredicatesrun:core::runnable.endclassfamily1(2)文件頭:/*****************************************************************************Copyright(c)SabuFrancisAssociates******************************************************************************/#include@""%privatelyusedpackages#include@"pfc\filesystem\"#include@"pfc\application\exe\"#include@"pfc\console\"#include@"pfc\exception\"%privateinterfaces%privateclasses%implementations#include@""(3)文件頭:/*****************************************************************************Copyright(c)SabuFrancisAssociates******************************************************************************/#requires@""%publiclyusedpackages#include@"pfc\"%exportedinterfaces%exportedclasses#include@""

(4)

文件頭:/*****************************************************************************Copyright(c)SabuFrancisAssociates******************************************************************************/implementfamily1opencoreconstantsclassName="family1".classVersion="$JustDate:$$Revision:$".clausesclassInfo(className,classVersion).domainsgender=female();male().classfacts-familyDBperson:(stringName,genderGender).parent:(stringPerson,stringParent).classpredicatesfather:(stringPerson,stringFather)nondetermanyflow.clausesfather(Person,Father):-parent(Person,Father),person(Father,male()).classpredicatesgrandFather:(stringPerson,stringGrandFather)nondeterm(o,o).clausesgrandFather(Person,GrandFather):-parent(Persoicates)文件尾:reconsult:(stringFileName).clausesreconsult(FileName):-retractFactDB(familyDB),file::consult(FileName,familyDB).clausesrun():-console::init(),stdIO::write("Loaddata\n"),reconsult("..\\"),stdIO::write("\nfathertest\n"),father(X,Y),stdIO::writef("%isthefatherof%\n",Y,X),fail.run():-stdIO::write("\ngrandFathertest\n"),grandFather(X,Y),stdIO::writef("%isthegrandfatherof%\n",Y,X),fail.run():-stdIO::write("\nancestorofPamtest\n"),X="Pam",ancestor(X,Y),stdIO::writef("%istheancestorof%\n",Y,X),fail.run():-stdIO::write("Endoftest\n").endimplementfamily1goalmainExe::run(family1::run).

(5)補(bǔ)充習(xí)題：1.編寫一Prolog程序使得你能和計算機(jī)“交談”（Conversationswithacomputer）。下圖顯示了對話時的情景，字體加粗的語句表示用戶從鍵盤輸入的內(nèi)容，其他則是計算機(jī)的回答。HELLOHIDOYOUWANTTOTALKNOIWANTTOSLEEPYOUAREASTUPIDCOMPUTERIAMANICECOMPUTER1.答：domains/*領(lǐng)域段，說明程序要用到的數(shù)據(jù)類型*/words=stringsentence=words*predicates/*謂詞段，說明程序要用到的謂詞名和參數(shù)*/nondetermtalknondetermhuman(sentence)nondetermanswer(sentence)nondetermtolist(words,sentence)nondetermprocess(words)nondetermchange(words,words)clauses/*子句段，說明程序要用到的事實(shí)和規(guī)則*/talk:-human(X),answer(X),talk.human(Y):-readln(X),tolist(X,Y).tolist(Str,[H|T]):-fronttoken(Str,H,Str1),!,tolist(Str1,T).tolist(_,[]).answer([]):-nl,nl.answer([Y|Z]):-process(Y),answer(Z).process(X):-change(X,Y),write(Y),write("").change("HELLO","HI").change("DO","NO").change("YOU","I").change("TALK","SLEEP").change("ARE","AM").change("STUPID","NICE").change(X,X).goal/*目標(biāo)段，說明程序要求解的目標(biāo)*/talk.2.有一個農(nóng)夫帶著一只狼、一只山羊和一筐白菜過河，要從南岸過河到北岸。岸邊有一條小船，農(nóng)夫可以獨(dú)自劃著小船過河，或者每次帶其中的一樣?xùn)|西過河。問題是如果他留下狼和羊在一起，那么狼就會把羊吃掉；如果留下羊和白菜，那么羊就會把白菜吃掉。農(nóng)夫如何才能安全地將全部東西運(yùn)到河對岸2.答：設(shè)計方案可以用farmer、wolf、goat和cabbage分別表示問題中的農(nóng)夫、狼、山羊和白菜等對象。狀態(tài)描述了各個成員的位置，可以用字母n和s分別表示北岸和南岸，例如，可以用location(s,n,n,s)表示農(nóng)夫、狼、山羊和白菜分別在南岸、北岸、北岸和南岸。動作描述了農(nóng)夫的擺渡操作，根據(jù)題意，一共只有四種動作，分別是農(nóng)夫獨(dú)自劃船、農(nóng)夫帶著狼劃船、農(nóng)夫帶著山羊劃船和農(nóng)夫帶著白菜劃船。問題求解的目標(biāo)是一個特定的動作序列（即渡河程序），而每個動作都將當(dāng)前狀態(tài)轉(zhuǎn)變成另一個新的狀態(tài)，所以狀態(tài)的變化過程?？梢苑磻?yīng)出動作執(zhí)行的過程。因此，可以將求解動作序列的問題轉(zhuǎn)換成求解狀態(tài)變化過程的問題，狀態(tài)變化過程求出來后，只要用某種方法將狀態(tài)變化轉(zhuǎn)換成相應(yīng)的動作序列輸出即可。我們用一個表X表示這個未知的狀態(tài)變化過程，X的條件是它必須由和平的狀態(tài)（即不會出現(xiàn)一個對象將另一個對象吃掉的情況）組成。開始時所有對象都在南岸，到最后所有對象都在北岸。用Prolog規(guī)則表示就是legal_states(location(s,s,s,s),location(n,n,n,n),States,X)，其中States是用來記錄狀態(tài)變化過程的動態(tài)表，在問題的開始，即農(nóng)夫還沒做任何事時，States存儲的應(yīng)該是初始狀態(tài)；到最后，即農(nóng)夫擺渡結(jié)束時，States中所存儲的就是目標(biāo)動作序列所對應(yīng)的狀態(tài)變化過程。實(shí)施方案domains/*領(lǐng)域段，說明程序要用到的數(shù)據(jù)類型*/bt=boat(symbol,symbol)ln=location(symbol,symbol,symbol,symbol)lists=ln*predicates/*謂詞段，說明程序要用到的謂詞名和參數(shù)*/opposite(symbol,symbol)safe_goat(symbol,symbol,symbol,symbol)safe_cabbage(symbol,symbol,symbol,symbol)is_peaceful(symbol,symbol,symbol,symbol)transform(ln,ln)legal_states(ln,ln,lists,lists)member(ln,lists)write_state(ln,ln)write_actions(lists)boat(ln,ln)clauses/*子句段，說明程序要用到的事實(shí)和規(guī)則*/opposite(s,n).opposite(n,s).safe_goat(X,_,X,_).safe_goat(F,X,Y,_):-opposite(X,Y),F<>Y.safe_cabbage(X,_,_,X).safe_cabbage(F,_,X,Y):-opposite(X,Y),F<>Y.is_peaceful(F,W,G,C):-safe_goat(F,W,G,C),safe_cabbage(F,W,G,C).member(X,[X|_]).member(X,[_|T]):-member(X,T).transform(location(X,W,G,C),location(Y,W,G,C)):-opposite(X,Y).transform(location(X,X,G,C),location(Y,Y,G,C)):-opposite(X,Y).transform(location(X,W,X,C),location(Y,W,Y,C)):-opposite(X,Y).transform(location(X,W,G,X),location(Y,W,G,Y)):-opposite(X,Y).legal_states(location(F0,W0,G0,C0),location(F,W,G,C),States,X):-transform(location(F0,W0,G0,C0),location(F1,W1,G1,C1)),is_peaceful(F1,W1,G1,C1),not(member(location(F1,W1,G1,C1),States)),legal_states(location(F1,W1,G1,C1),location(F,W,G,C),[location(F1,W1,G1,C1)|States],X).legal_states(location(F,W,G,C),location(F,W,G,C),L,L).write_state(location(X,W,G,C),location(Y,W,G,C)):-!,write("Thefarmercrossestheriverhimself"),nl.write_state(location(X,X,G,C),location(Y,Y,G,C)):-!,write("Thefarmercrossestheriverwiththewolf"),nl.write_state(location(X,W,X,C),location(Y,W,Y,C)):-!,write("Thefarmercrossestheriverwiththegoat"),nl.write_state(location(X,W,G,X),location(Y,W,G,Y)):-!,write("Thefarmercrossestheriverwiththecabbage"),nl.write_actions([]).write_actions([H1,H2|T]):-write_state(H1,H2),write_actions([H2|T]).boat(location(F0,W0,G0,C0),location(F,W,G,C)):-legal_states(location(F0,W0,G0,C0),location(F,W,G,C),[location(F0,W0,G0,C0)],X),write_actions(X).3.某機(jī)器人需要在一間大商店里巡邏，由于商品每天都在流動，商店的平面圖經(jīng)常變化。一個典型的平面路徑如圖所示，在這個圖中，點(diǎn)代表機(jī)器人的工作站，線表示點(diǎn)與點(diǎn)之間適于巡邏的通道。在機(jī)器人的內(nèi)部數(shù)據(jù)庫中，將通過一組事實(shí)表示圖的路徑，例如：joined_to(a,b);joined_to(b,c);joined_to(b,d);joined_to(d,c);joined_to(c,e)。機(jī)器人必須能夠判斷連接兩個點(diǎn)的路線，例如，它應(yīng)該識別出這個序列代表從e到b的一條路線。請寫出一個程序，用來證明或者反證某一個給定序列是兩個給定點(diǎn)之間的路線。3.答：理解問題已知一個序列和一對點(diǎn)，要求證明（或反證）這個序列是這兩個點(diǎn)之間一條可能的路線。可以看出，這是一個證明型問題：即證明給出的序列是給定的兩點(diǎn)之間的一條路線。那么什么是路線結(jié)合圖2，我們來看幾個有用的例子。（1）bdc這個序列是a和c兩點(diǎn)之間的路線嗎顯然不是，因?yàn)樗钠鹗键c(diǎn)不對。（2）dce這個序列是d和b兩點(diǎn)之間的路線嗎當(dāng)然不是：它的終止點(diǎn)不對。（3）abe是a和e之間的路線嗎不是，因?yàn)樵谄矫鎴D上，b和e兩個點(diǎn)之間不是直接相連的?？梢?，對于一個給定的點(diǎn)序列，要使它成為某對特定的點(diǎn)之間的路線，需要滿足以下三個條件：·序列應(yīng)該從點(diǎn)對的第一點(diǎn)開始。·序列應(yīng)該以點(diǎn)對的第二點(diǎn)結(jié)束。·序列應(yīng)該是連通的（連通序列）——也就是說，序列中任意兩個連續(xù)的點(diǎn)在平面圖中應(yīng)該是相連的。對于給定的一個序列和一對端點(diǎn)，如果這三個條件都滿足，那么可以確信這個序列是這兩個點(diǎn)之間的路線。這三個條件是證明該假設(shè)的充分條件，同時也是必要條件。設(shè)計方案在Prolog中可以用一個表來表示一個點(diǎn)序列，例如，序列可以表示為[e,c,d,b]；一對端點(diǎn)也可以用一個表表示。因此，route_between([e,c,d,b],[e,b])可以表示egcgdgb是e、b兩點(diǎn)之間的路線。將是我們所關(guān)心的關(guān)系的一個實(shí)例。目標(biāo)是什么我們可以寫成route_between(X,[Y,Z])，這里序列X和一對端點(diǎn)[Y,Z]是給定的，我們關(guān)心的是目標(biāo)能否取得成功。為了給route_between寫出一條規(guī)則，我們只需要將上面寫下的三個條件轉(zhuǎn)換成Prolog就可以了，如下所示：route_between(X,[Y,Z]):-begins_with(X,Y),ends_with(X,Z),is_connected(X).如果能夠?qū)懗鯾egins_with、ends_with和is_connected這三個謂詞的檢驗(yàn)定義，我們應(yīng)該能夠輸入詢問，如route_between([a,d,e,c,b],[a,b])，并得到一個是還是否的回答。執(zhí)行方案(1)begins_with該關(guān)系的一個實(shí)例就是begins_with([b,a,d],b)。顯然，這個關(guān)系要成立，端點(diǎn)與表頭必須是完全相同的。用規(guī)則表示就是begins_with([X|Y],X)?？梢杂靡恍┰儐栠M(jìn)行試驗(yàn)，例如begins_with([b,a,d,],b)等。(2)ends_withends_with([b,a,d],d)就是該關(guān)系的一個實(shí)例。與begins_with相比，這個關(guān)系就不是那么容易定義了，因?yàn)楸淼淖詈笠粋€元素看起來并不像第一個元素那樣特別。不過，你可以想出一個表，使得它與表[b,a,d]相關(guān)，又是從它的最后一個元素開始的嗎將原表倒置一下，變成[d,a,b]如何所以我們可以這樣描述ends_with：表X以點(diǎn)Y結(jié)束，如果X的逆序從點(diǎn)Y開始。表的倒置，即求一個表的逆序表是關(guān)于表的一個最常見的問題，這里我們不做具體討論，其完整程序如圖4所示?，F(xiàn)在，我們就可以用reverse關(guān)系和剛才已經(jīng)定義好的begins_with關(guān)系，將上面的描述用Prolog表示成：ends_with(X,Y):-reverse(X,Z),begins_with(Z,Y).可以用一些合適的詢問來試驗(yàn)一下。domainss_list=symbol*predicatesappend(s_list,s_list,s_list)reverse(s_list,s_list)clausesappend([],L,L).append([H|T],L2,[H|Tn]):-append(T,L2,Tn).reverse([],[]).reverse([H|T],L):-reverse(T,L1),append(L1,[H],L).(3)is_connected給這個關(guān)系舉出幾個例子并不困難，例如，通過圖3我們可以看出，表[c,d,b,a]是一個連通序列，而[b,d,c,e,a]不是。用一般序列的表示方法，即[X|Y]來表示可以嗎為了使得[X|Y]是一個連通序列，對于X有什么要求呢顯然，X必須與序列中下一個出現(xiàn)的點(diǎn)在平面圖中是直接相連的；因此要把這個“下一個”點(diǎn)展開。所以我們應(yīng)該用[X1,X2|Y]來表示一般序列，而不是[X|Y]；如果X1與X2相連，并且[X2|Y]是一個連通序列，那么這就是一個連通的序列。（注意這里的第二個條件，為什么只問Y是否連通是不夠的呢）因此，我們寫出如下規(guī)則is_connected([X1,X2|Y]):-linked_to(X1,X2),is_connected([X2|Y]).這里我們已經(jīng)特意用linked_to替代joined_to了，為什么呢舉例來說，前面給出的joined_to事實(shí)聲明a是連到b的，但是沒有事實(shí)對應(yīng)于b連到a。所以需要使用關(guān)系linked_to，以使Prolog能夠做出明顯的推論。我們用下面兩條規(guī)則來定義：linked_to(X,Y):-joined_to(X,Y).linked_to(X,Y):-joined_to(Y,X).然而，我們還沒有完成is_connected的定義。上面的規(guī)則是遞歸的，所以我們需要一個特殊的、非遞歸的情況。[X1,X2|Y]這個模式是包含兩個或兩個以上成員的表，一個只有一個點(diǎn)的表當(dāng)然是“連通的”，所以我們加上is_connected([X])，這個語句提供了一個“直接的答案”?，F(xiàn)在程序已經(jīng)完成了，接下來就是檢驗(yàn)我們的計算機(jī)現(xiàn)在確實(shí)能夠解決機(jī)器人巡邏問題了，用一些詢問，如route_between([d,b,c,e],[d,e])試驗(yàn)一下。機(jī)器人巡邏問題的完整程序如圖5所示，該程序在TurboProlog環(huán)境下運(yùn)行通過。domains/*領(lǐng)域段，說明程序要用到的數(shù)據(jù)類型*/s_list=symbol*predicates/*謂詞段，說明程序要用到的謂詞名和參數(shù)*/append(s_list,s_list,s_list)reverse(s_list,s_list)joined_to(symbol,symbol)linked_to(symbol,symbol)begins_with(s_list,symbol)ends_with(s_list,symbol)is_connected(s_list)route_between(s_list,s_list)clauses/*子句段，說明程序要用到的事實(shí)和規(guī)則*/append([],L,L).append([H|T],L2,[H|Tn]):-append(T,L2,Tn).reverse([],[]).reverse([H|T],L):-reverse(T,L1),append(L1,[H],L).joined_to(a,b).joined_to(b,a).joined_to(b,c).joined_to(c,b).joined_to(b,d).joined_to(d,b).joined_to(d,c).joined_to(c,d).joined_to(c,e).joined_to(e,c).linked_to(X,Y):-joined_to(X,Y).linked_to(X,Y):-joined_to(Y,X).begins_with([X|_],X).ends_with(X,Y):-reverse(X,Z),begins_with(Z,Y).is_connected([_]).is_connected([X1,X2|Y]):-linked_to(X1,X2),is_connected([X2|Y]).route_between(X,[Y,Z]):-begins_with(X,Y),ends_with(X,Z),is_connected(X).第七章專家系統(tǒng).答：（1）專家系統(tǒng)的定義費(fèi)根鮑姆（E．A．Feigenbaum）：“專家系統(tǒng)是一種智能的計算機(jī)程序，它運(yùn)用知識和推理步驟來解決只有專家才能解決的復(fù)雜問題”專家系統(tǒng)是基于知識的系統(tǒng)，用于在某種特定的領(lǐng)域中運(yùn)用領(lǐng)域?qū)＜叶嗄攴e累的經(jīng)驗(yàn)和專門知識，求解需要專家才能解決的困難問題保存和大面積推廣各種專家的寶貴知識博采眾長比人類專家更可靠，更靈活（2）專家系統(tǒng)的特點(diǎn)①具有專家水平的專門知識 專家系統(tǒng)中的知識按其在問題求解中的作用可分為三個層次：數(shù)據(jù)級、知識庫級和控制級數(shù)據(jù)級知識（動態(tài)數(shù)據(jù)）：具體問題所提供的初始事實(shí)及在問題求解過程中所產(chǎn)生的中間結(jié)論、最終結(jié)論 數(shù)據(jù)級知識通常存放于數(shù)據(jù)庫中知識庫級知識：專家的知識，這一類知識是構(gòu)成專家系統(tǒng)的基礎(chǔ) 一個系統(tǒng)性能高低取決于這種知識質(zhì)量和數(shù)量控制級知識（元知識）：關(guān)于如何運(yùn)用前兩種知識的知識 在問題求解中的搜索策略、推理方法②能進(jìn)行有效的推理 推理機(jī)構(gòu)——能根據(jù)用戶提供的已知事實(shí)，通過運(yùn)用知識庫中的知識，進(jìn)行有效的推理，以實(shí)現(xiàn)問題的求解。專家系統(tǒng)的核心是知識庫和推理機(jī)③具有啟發(fā)性 除能利用大量專業(yè)知識外，還必須利用經(jīng)驗(yàn)判斷知識來對求解問題作出多個假設(shè)（依據(jù)某些條件選定一個假設(shè)，使推理繼續(xù)進(jìn)行）④能根據(jù)不確定（不精確）的知識進(jìn)行推理 綜合利用模糊的信息和知識進(jìn)行推理，得出結(jié)論⑤具有靈活性 知識庫與推理機(jī)相互獨(dú)立，使系統(tǒng)易于擴(kuò)充，具有較大的靈活性⑥具有透明性一般有解釋機(jī)構(gòu)，所以具有較好的透明性解釋機(jī)構(gòu)向用戶解釋推理過程，回答“Why”、“How”等