王士同版人工智能教程答案46_第1頁
王士同版人工智能教程答案46_第2頁
王士同版人工智能教程答案46_第3頁
王士同版人工智能教程答案46_第4頁
王士同版人工智能教程答案46_第5頁
已閱讀5頁,還剩68頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

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

2.10解答:TVTVTP…TDTBZT…B圖書館框架A工業(yè)技術一般工業(yè)技術礦業(yè)工程自動化技術、計算機技術水利工程書名作者ISBN出版時間出版社2.11解答:在產(chǎn)生式系統(tǒng)中,隨著產(chǎn)生式規(guī)則的數(shù)量的增加,系統(tǒng)設計者難以理解規(guī)則間的相互作用,究其原因,在于每條規(guī)則的自含性使得知識表示的力度過于細微。因此要提高產(chǎn)生式系統(tǒng)的可理解性,就應當按照軟件工程的思想,通過對規(guī)則的適當劃分,將規(guī)則組織誠易于管理的功能模塊。由于框架系統(tǒng)具有組織成塊知識的良好特性,因此將兩者進行有機結(jié)合,可以為產(chǎn)生式系統(tǒng)的開發(fā)、調(diào)試和管理提供有益的幫助?;诳蚣艿谋硎緳C制可以用作產(chǎn)生式語言和推理機制設計的一個重要構(gòu)件。另外,框架可以直接用于表示規(guī)則,如果將每一個規(guī)則作為一個框架處理,一組用于解決特定問題的規(guī)則可組織成一類,且在這一類框架中表示這組規(guī)則的各種特性。2.12解答:略2.13解答:(1)題目描述可轉(zhuǎn)換為如下問題(N階漢諾塔問題)有編號為A、B、C的三個柱子和標識為1、2、…、N的尺寸依次從小到大的N個有中心孔的金片;初始狀態(tài)下N個金片按1、2、…、N順序堆放在A號柱子上,目標狀態(tài)下N個金片以同樣次序順序堆放在B號柱子上,金片的搬移須遵守以下規(guī)則:每次只能搬一個金片,且較大金片不能壓放在較小金片之上,可以借助于C針。(2)假設基本操作為move(x,A,C,B),表示將x個金片從A移到B上,中間可借助于C。當N=1時,則無需借助中間的C針,就可以直接實現(xiàn)將1個金片從A移到B上,這也是問題的最簡操作,可表示為move-one(1,A,B);當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,依次遞歸求解就可以得到相應的結(jié)果。(3)設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ī)模為。2.14解答:(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是誠實的,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))第三章問題求解方法3.1答:深度優(yōu)先搜索與廣度優(yōu)先搜索的區(qū)別在于:在對節(jié)點n進行擴展時,其后繼節(jié)點在OPEN表中的存放位置不同。廣度優(yōu)先搜索是將后繼節(jié)點放入OPEN表的末端,而深度優(yōu)先搜索則是將后繼節(jié)點放入OPEN表的前端。廣度優(yōu)先搜索是一種完備搜索,即只要問題有解就一定能夠求出,而深度優(yōu)先搜索是不完備搜索。 在不要求求解速度且目標節(jié)點的層次較深的情況下,廣度優(yōu)先搜索優(yōu)于深度優(yōu)先搜索;在要求求解速度且目標節(jié)點的層次較淺的情況下,深度優(yōu)先搜索優(yōu)于廣度優(yōu)先搜索。 廣度優(yōu)先的正例:積木問題;深度優(yōu)先的正例:郵遞員問題,反例:國際象棋。3.2答:衡量標準為:這組子狀態(tài)中有沒有目標狀態(tài),如果有,則選擇該節(jié)點并且搜索成功;若沒有,則按照某種控制策略從已生成的狀態(tài)中再選擇一個狀態(tài)作為當前狀態(tài)重復搜索過程。3.3答:(1)廣度優(yōu)先搜索:該程序必須找到解,并且最好是最優(yōu)解;(2)廣度優(yōu)先搜索:醫(yī)生要根據(jù)病人的各種病狀判斷病人的??;(3)深度優(yōu)先搜索:該程序要求一定要找到目標路徑;(4)深度優(yōu)先搜索:該程序要求找到最優(yōu)解;(5)廣度優(yōu)先搜索:不能確定它們是否等同,既不能確定它們是否有等同解。3.4答:對于四皇后問題,如果放一個皇后的耗散值為1的話,則任何一個解的耗散值都是4。因此如果h是對該耗散值的估計,是沒有意義的。對于像四皇后這樣的問題,啟發(fā)函數(shù)應該是對找到解的可能性的評價。利用一個位置放皇后后,消去的對角線的長度來進行評價。3.5答:定義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,而實際上只要一次擺渡就可以達到目標狀態(tài),其最優(yōu)路徑的耗散值為1。所以不滿足A*的條件。下面我們來證明h1=M+C-2B是滿足A*條件的。我們分兩種情況考慮。先考慮船在左岸的情況。如果不考慮限制條件,也就是說,船一次可以將三人從左岸運到右岸,然后再有一個人將船送回來。這樣,船一個來回可以運過河2人,而船仍然在左岸。而最后剩下的三個人,則可以一次將他們?nèi)繌淖蟀哆\到右岸。所以,在不考慮限制條件的情況下,也至少需要擺渡次。其中分子上的"-3"表示剩下三個留待最后一次運過去。除以"2"是因為一個來回可以運過去2人,需要個來回,而"來回"數(shù)不能是小數(shù),需要向上取整,這個用符號表示。而乘以"2"是因為一個來回相當于兩次擺渡,所以要乘以2。而最后的"+1",則表示將剩下的3個運過去,需要一次擺渡。

化簡有:再考慮船在右岸的情況。同樣不考慮限制條件。船在右岸,需要一個人將船運到左岸。因此對于狀態(tài)(M,C,0)來說,其所需要的最少擺渡數(shù),相當于船在左岸時狀態(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ù)。因此,當有限制條件時,最優(yōu)的擺渡次數(shù)只能大于等于該擺渡次數(shù)。所以該啟發(fā)函數(shù)h是滿足A*條件的。3.6答:在搜索期間改善h函數(shù),是一種動態(tài)改變h函數(shù)的方法。像改進的A*算法中,對NEXT中的節(jié)點按g值的大小選擇待擴展的節(jié)點,相當于令這些節(jié)點的h=0,就是動態(tài)修改h函數(shù)的一種方法。由定理2:若h(n)滿足單調(diào)限制,則由A*所擴展的節(jié)點序列,其f值是非遞減的,即f(ni)≤f(nj)),當h滿足單調(diào)條件時,A*所擴展的節(jié)點序列,其f是非遞減的。對于任何節(jié)點i,j,如果j是i的子節(jié)點,則有f(i)≤f(j)。利用該性質(zhì),我們可以提出另一種動態(tài)修改h函數(shù)的方法:f(j)=max(f(i),f(j))以f(j)作為節(jié)點j的f值。f值的改變,隱含了h值的改變。當h不滿足單調(diào)條件時,經(jīng)過這樣修正后的h具有一定的單調(diào)性質(zhì),可以減少重復節(jié)點的可能性。3.7答:像這種類型的問題,由于涉及到城市距離或旅行費用,所以利用代價樹廣度優(yōu)先搜索求解。為此,首先必須將旅行交通圖轉(zhuǎn)換為代價樹,轉(zhuǎn)換方法為:從初始節(jié)點A開始,把與它直接相鄰的節(jié)點作為他的后繼節(jié)點,對其他節(jié)點也作同樣的擴展,但若一個節(jié)點以作為某節(jié)點的前驅(qū)節(jié)點,則它就不能再作為該結(jié)點的后繼結(jié)點。另外,圖中節(jié)點除了初始節(jié)點A之外,其它的節(jié)點都有可能在代價樹中多次出現(xiàn),為了區(qū)分它們的多次出現(xiàn),分別用下標1,2…標出。但他們卻是圖中的同一個節(jié)點。設估價函數(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*條件。3.8答:可定義h為:h=B右邊的W的數(shù)目設j節(jié)點是i節(jié)點的子節(jié)點,則根據(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)。且容易驗證h(t)=0,所以該h是單調(diào)的。由于h滿足單調(diào)條件,所以也一定有h(n)≤h*(n),即滿足A*條件。3.9答:3.10答:(1)余一棋的弈法如下:兩棋手可以從5個錢幣堆中輪流拿走一個、兩個或三個錢幣,揀起最后一個錢幣者算輸。試通過博弈證明,后走的選手必勝,并給出一個簡單的特征標記來表示取勝策略。為了方便起見,用((AB)()())這樣的表表示一個狀態(tài)。這樣得到搜索圖如下:(2)八數(shù)碼問題空格:Up,Left,Down,Right3.11答:(1)與/或圖的解圖:那些可解結(jié)點的子圖,包含一結(jié)點到目的結(jié)點集的、連通的可解結(jié)點的子圖。在問題的完整的隱含圖中擴展生成出包含初始結(jié)點和目的結(jié)點集合的連通的明顯子圖。(2)算法AO*:必須對當前已生成出的與或圖中的所有結(jié)點實施其每解點是否為可解結(jié)點的標注過程,如果起始結(jié)點被標注為可解的,則搜索過程可成功地結(jié)束;如果起始結(jié)點還不能被標注為可解的,則應當繼續(xù)擴展生成結(jié)點(盡可能地記錄,所有生成的結(jié)點中,哪些結(jié)點被標注了可解的,以便減少下一次標注過程的工作量);同樣地,對不可解結(jié)點也同樣如此。利用結(jié)點的可解/不可解性質(zhì),能從搜索圖中刪去可解結(jié)點的任何不可解結(jié)點的子結(jié)點;同樣地,能刪去不可解結(jié)點的所有的子結(jié)點(搜索這些被刪除的結(jié)點是沒有意義的,而只會降低搜索的效率)。兩個主要過程的反復:自上而下的圖生長過程,并通過跟蹤有標記的連接符尋找一個候選局部解圖自下而上的估價函數(shù)值的修正、連接符的標記和SOLVED的標注過程(3)3.12答:此題要求按照課中例題的方式,給出算法,以下是每個循環(huán)結(jié)束時的搜索圖。上面這種做法比較簡單,也可以如下做:3.13答:略3.14答:博弈搜索通常被限制在一定的范圍,搜索的目標是確定一步好的走法(好棋),等對手回手后,再繼續(xù)搜索。因此,博弈搜索過程總是由當前狀態(tài)向目標狀態(tài)搜索,而不是由目標狀態(tài)向當前狀態(tài)搜索。這類博弈的實例有西洋跳棋等。3.15答: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)}3.16答:見上圖3.17答:略3.18答:α-β剪裁算法.

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

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

算法如下:

doublealphabeta(intdepth,doublealpha,doublebeta,Positionp);

{/*

alpha是MAX的當前值

beta是MIN的當前值,depth

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

double

t;

if(depth=0)

return

evaluate(p);/*

如果P是葉結(jié)點,算出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;

}

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

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

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

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

將目標公式的否定式?G轉(zhuǎn)化成子句的形式,并加入到子句集F中,得到子句集S。(4)應用歸結(jié)原理對子句集S中的子句進行歸結(jié),并把每次歸結(jié)得到的歸結(jié)式都并入S中。如此反復進行,若歸結(jié)得到一個空子句NIL,則停止歸結(jié),證明了G為真。4.4答:略4.5答:(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))4.6答:(1)(2){A/x,A/y,A/z,A/w,A/u}(3)4.7答:(1)(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(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)]

目標取反化子句集:

~{(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)4.8答:4.9答:答:我們用Skier(x)表示x是滑雪運動員,Alpinist(x)表示x是登山運動員,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)

目標:(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)

目標取反:

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

(4)

family1.prj6文件頭:/*****************************************************************************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("..\\fa.txt"),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)補充習題:1.編寫一Prolog程序使得你能和計算機“交談”(Conversationswithacomputer)。下圖顯示了對話時的情景,字體加粗的語句表示用戶從鍵盤輸入的內(nèi)容,其他則是計算機的回答。HELLOHIDOYOUWANTTOTALKNOIWANTTOSLEEPYOUAREASTUPIDCOMPUTERIAMANICECOMPUTER1.答:domains/*領域段,說明程序要用到的數(shù)據(jù)類型*/words=stringsentence=words*predicates/*謂詞段,說明程序要用到的謂詞名和參數(shù)*/nondetermtalknondetermhuman(sentence)nondetermanswer(sentence)nondetermtolist(words,sentence)nondetermprocess(words)nondetermchange(words,words)clauses/*子句段,說明程序要用到的事實和規(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/*目標段,說明程序要求解的目標*/talk.2.有一個農(nóng)夫帶著一只狼、一只山羊和一筐白菜過河,要從南岸過河到北岸。岸邊有一條小船,農(nóng)夫可以獨自劃著小船過河,或者每次帶其中的一樣東西過河。問題是如果他留下狼和羊在一起,那么狼就會把羊吃掉;如果留下羊和白菜,那么羊就會把白菜吃掉。農(nóng)夫如何才能安全地將全部東西運到河對岸?2.答:設計方案可以用farmer、wolf、goat和cabbage分別表示問題中的農(nóng)夫、狼、山羊和白菜等對象。狀態(tài)描述了各個成員的位置,可以用字母n和s分別表示北岸和南岸,例如,可以用location(s,n,n,s)表示農(nóng)夫、狼、山羊和白菜分別在南岸、北岸、北岸和南岸。動作描述了農(nóng)夫的擺渡操作,根據(jù)題意,一共只有四種動作,分別是農(nóng)夫獨自劃船、農(nóng)夫帶著狼劃船、農(nóng)夫帶著山羊劃船和農(nóng)夫帶著白菜劃船。問題求解的目標是一個特定的動作序列(即渡河程序),而每個動作都將當前狀態(tài)轉(zhuǎn)變成另一個新的狀態(tài),所以狀態(tài)的變化過程??梢苑磻鰟幼鲌?zhí)行的過程。因此,可以將求解動作序列的問題轉(zhuǎn)換成求解狀態(tài)變化過程的問題,狀態(tài)變化過程求出來后,只要用某種方法將狀態(tài)變化轉(zhuǎn)換成相應的動作序列輸出即可。我們用一個表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存儲的應該是初始狀態(tài);到最后,即農(nóng)夫擺渡結(jié)束時,States中所存儲的就是目標動作序列所對應的狀態(tài)變化過程。實施方案domains/*領域段,說明程序要用到的數(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/*子句段,說明程序要用到的事實和規(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īng)常變化。一個典型的平面路徑如圖所示,在這個圖中,點代表機器人的工作站,線表示點與點之間適于巡邏的通道。在機器人的內(nèi)部數(shù)據(jù)庫中,將通過一組事實表示圖的路徑,例如:joined_to(a,b);joined_to(b,c);joined_to(b,d);joined_to(d,c);joined_to(c,e)。機器人必須能夠判斷連接兩個點的路線,例如,它應該識別出這個序列代表從e到b的一條路線。請寫出一個程序,用來證明或者反證某一個給定序列是兩個給定點之間的路線。3.答:理解問題已知一個序列和一對點,要求證明(或反證)這個序列是這兩個點之間一條可能的路線??梢钥闯觯@是一個證明型問題:即證明給出的序列是給定的兩點之間的一條路線。那么什么是路線?結(jié)合圖2,我們來看幾個有用的例子。(1)bdc這個序列是a和c兩點之間的路線嗎?顯然不是,因為它的起始點不對。(2)dce這個序列是d和b兩點之間的路線嗎?當然不是:它的終止點不對。(3)abe是a和e之間的路線嗎?不是,因為在平面圖上,b和e兩個點之間不是直接相連的。可見,對于一個給定的點序列,要使它成為某對特定的點之間的路線,需要滿足以下三個條件:·序列應該從點對的第一點開始?!ば蛄袘撘渣c對的第二點結(jié)束?!ば蛄袘撌沁B通的(連通序列)——也就是說,序列中任意兩個連續(xù)的點在平面圖中應該是相連的。對于給定的一個序列和一對端點,如果這三個條件都滿足,那么可以確信這個序列是這兩個點之間的路線。這三個條件是證明該假設的充分條件,同時也是必要條件。設計方案在Prolog中可以用一個表來表示一個點序列,例如,序列可以表示為[e,c,d,b];一對端點也可以用一個表表示。因此,route_between([e,c,d,b],[e,b])可以表示egcgdgb是e、b兩點之間的路線。將是我們所關心的關系的一個實例。目標是什么?我們可以寫成route_between(X,[Y,Z]),這里序列X和一對端點[Y,Z]是給定的,我們關心的是目標能否取得成功。為了給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這三個謂詞的檢驗定義,我們應該能夠輸入詢問,如route_between([a,d,e,c,b],[a,b]),并得到一個是還是否的回答。執(zhí)行方案(1)begins_with該關系的一個實例就是begins_with([b,a,d],b)。顯然,這個關系要成立,端點與表頭必須是完全相同的。用規(guī)則表示就是begins_with([X|Y],X)??梢杂靡恍┰儐栠M行試驗,例如begins_with([b,a,d,],b)等。(2)ends_withends_with([b,a,d],d)就是該關系的一個實例。與begins_with相比,這個關系就不是那么容易定義了,因為表的最后一個元素看起來并不像第一個元素那樣特別。不過,你可以想出一個表,使得它與表[b,a,d]相關,又是從它的最后一個元素開始的嗎?將原表倒置一下,變成[d,a,b]如何?所以我們可以這樣描述ends_with:表X以點Y結(jié)束,如果X的逆序從點Y開始。表的倒置,即求一個表的逆序表是關于表的一個最常見的問題,這里我們不做具體討論,其完整程序如圖4所示。現(xiàn)在,我們就可以用reverse關系和剛才已經(jīng)定義好的begins_with關系,將上面的描述用Prolog表示成:ends_with(X,Y):-reverse(X,Z),begins_with(Z,Y).可以用一些合適的詢問來試驗一下。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給這個關系舉出幾個例子并不困難,例如,通過圖3我們可以看出,表[c,d,b,a]是一個連通序列,而[b,d,c,e,a]不是。用一般序列的表示方法,即[X|Y]來表示可以嗎?為了使得[X|Y]是一個連通序列,對于X有什么要求呢?顯然,X必須與序列中下一個出現(xiàn)的點在平面圖中是直接相連的;因此要把這個“下一個”點展開。所以我們應該用[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事實聲明a是連到b的,但是沒有事實對應于b連到a。所以需要使用關系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]這個模式是包含兩個或兩個以上成員的表,一個只有一個點的表當然是“連通的”,所以我們加上is_connected([X]),這個語句提供了一個“直接的答案”?,F(xiàn)在程序已經(jīng)完成了,接下來就是檢驗我們的計算機現(xiàn)在確實能夠解決機器人巡邏問題了,用一些詢問,如route_between([d,b,c,e],[d,e])試驗一下。機器人巡邏問題的完整程序如圖5所示,該程序在TurboProlog2.0環(huán)境下運行通過。domains/*領域段,說明程序要用到的數(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/*子句段,說明程序要用到的事實和規(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).lin

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論