人工智能經(jīng)典習(xí)題集及各章總結(jié)(期末測驗(yàn)必備)

1、人工智能經(jīng)典習(xí)題集及各章總結(jié)（期末測驗(yàn)必備）1/68個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途 /68 /68 /68作者:日期:人工智能各章小結(jié)及習(xí)題解答第一部分緒論習(xí)題解答：1什么是人工智能？發(fā)展過程中經(jīng)歷了哪些階段？解：人工智能是計(jì)算機(jī)科學(xué)的一個(gè)重要分支，也是一門正在發(fā)展中的綜合性前沿學(xué)科，它是由計(jì)算機(jī)科學(xué)、控制論、信息論、神經(jīng)生理學(xué)、哲學(xué)、語言學(xué)等多種學(xué)科相互滲透而發(fā)展起來的，目前正處于發(fā)展階段尚未形成完整體系。發(fā)展過程中經(jīng)歷的階段有：第一階段（40年代中50年代末）神經(jīng)元網(wǎng)絡(luò)時(shí)代第二階段（50年代中60年代中）通用方法時(shí)代第三階段（60年代中80年代初）知識(shí)工程時(shí)代第四階段

2、（80年代中90年代初）新的神經(jīng)元網(wǎng)絡(luò)時(shí)代第五階段（90年代初現(xiàn)在）海量信息處理與網(wǎng)絡(luò)時(shí)代2人工智能研究的基本內(nèi)容是什么？解：基本內(nèi)容是：搜索技術(shù)、知識(shí)表示、規(guī)劃方法、機(jī)器學(xué)習(xí)、認(rèn)知科學(xué)、自然語言理解與機(jī)器翻譯、專家系統(tǒng)與知識(shí)工程、定理證明、博弈、機(jī)器人、數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)、多Agent系統(tǒng)、復(fù)雜系統(tǒng)、足球機(jī)器人、人機(jī)交互技術(shù)等。3人工智能主要有哪幾大研究學(xué)派？解:（1）符號(hào)主義學(xué)派：由心理學(xué)途徑產(chǎn)生，符號(hào)主義認(rèn)為人工智能起源于數(shù)理邏輯，人類認(rèn)識(shí)（智能)的基本元素是符號(hào)，而智能行為則是符號(hào)運(yùn)算的結(jié)果。連接主義學(xué)派：由生理學(xué)途徑產(chǎn)生，連接主義又稱為仿生學(xué)派，認(rèn)為人工智能的基本元素是神經(jīng)元，智能產(chǎn)

3、生于大量神經(jīng)元的并行分布式聯(lián)結(jié)之中，而智能行為則是聯(lián)結(jié)計(jì)算的結(jié)果。行為主義學(xué)派：由生物演化途徑產(chǎn)生，行為主義認(rèn)為人工智能起源于控制論，提出智能取決于感知和行為，取決于對(duì)外界復(fù)雜環(huán)境的適應(yīng)，而不是表示和推理。4人工智能有哪些主要的研究領(lǐng)域？解:(1)問題求解邏輯推理與定理證明自然語言理解自動(dòng)程序設(shè)計(jì)專家系統(tǒng)機(jī)器學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)機(jī)器人學(xué)模式識(shí)別機(jī)器視覺智能控制智能檢索智能調(diào)度與指揮分布式人工智能與Agent15)計(jì)算智能與進(jìn)化計(jì)算個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途 /68 /68數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)人工生命系統(tǒng)與語言工具第2部分知識(shí)與知識(shí)表示本章小結(jié)：謂詞一產(chǎn)生式知識(shí)框架首先定義謂詞，

4、指|i出每個(gè)謂詞的確切11i!I產(chǎn)生式系統(tǒng)由3個(gè)；ii框架通常由指定”事物各個(gè)方面的丨語義網(wǎng)“i語義網(wǎng)絡(luò)由節(jié)點(diǎn)和|弧線或鏈線組成，I習(xí)題解答：1設(shè)有如下問題：(1)有五個(gè)相互可直達(dá)且距離已知的城市A、B、C、D、E，如圖所示；(2)某人從A地出發(fā)，去其它四個(gè)城市各參觀一次后回到A;(3)找一條最短的旅行路線個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途 #/68 /68請(qǐng)用產(chǎn)生式規(guī)則表示旅行過程。解：綜合數(shù)據(jù)庫(x)(X)中X可以是一個(gè)字母，也可以是一個(gè)字符串。初始狀態(tài)(A)目標(biāo)狀態(tài)(Ax1x2x3x4A)規(guī)則集：r1:IFL(S)=5THENGOTO(A)r2:IFL(S)5THENG

5、OTO(B)r3:IFL(S)5THENGOTO(C)r4:IFL(S)5THENGOTO(D)r5:IFL(S)C-D-E-B-A總距離為5+6+8+10+7=362神州大學(xué)和東方大學(xué)兩?；@球隊(duì)在東方大學(xué)進(jìn)行一場比賽，結(jié)局的比分是85:89，用語義網(wǎng)絡(luò)表示。是-種神州大學(xué)1籃球賽85：89客隊(duì)結(jié)局主隊(duì)東方大學(xué)第3部分推理本章小結(jié)：一一匸自然演-IIIIL經(jīng)典邏歸結(jié)演與/或形不確定與非習(xí)題解答：1張某被盜，公安局派出五個(gè)偵察員去調(diào)查。研究案情時(shí)，偵察員A說“趙與錢中至少有一人作案；偵察員B說“錢與孫中至少有一人作案；偵察員C說“孫與李中至少有一人作案；偵察員D說“趙與孫中至少有一人與此案無關(guān)；

6、偵察員E說“錢與李中至少有一人與此案無關(guān)。如果這五個(gè)偵察員的話都是可信的，試用歸結(jié)演繹推理求出誰是盜竊犯。解：第一步：將5位偵察員的話表示成謂詞公式，為此先定義謂詞。設(shè)謂詞P(x)表示是作案者，所以根據(jù)題意：A:P(zhao)vP(qian)B:P(qian)vP(sun)C:P(sun)vP(li)D:P(zhao)vP(sun)E:P(qian)vP(li)個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途 /68 /68以上每個(gè)偵察員的話都是一個(gè)子句。第二步：將待求解的問題表示成謂詞。設(shè)y是盜竊犯，則問題的謂詞公式為P(y)，將其否定并與ANSWER(y)做析?。篜(y)vANSWER

7、(y)第三步:求前提條件及P(y)vANSWER(y)的子句集，并將各子句列表如下：(1)P(zhao)vP(qian)(2)P(qian)vP(sun)(3)P(sun)vP(li)(4)P(zhao)vP(sun)(5)P(qian)vP(li)(6)P(y)vANSWER(y)第四步:應(yīng)用歸結(jié)原理進(jìn)行推理3(7)P(qian)vP(sun)(1)與(4)歸結(jié)(8)P(zhao)vP(li)(1)與(5)歸結(jié)(9)P(qian)vP(zhao)(2)與(4)歸結(jié)(10)P(sun)vP(li)(2)與(5)歸結(jié)(11)P(zhao)vP(li)(3)與(4)歸結(jié)(12)P(sun)vP(q

8、ian)(3)與(5)歸結(jié)(13)P(qian)(2)與(7)歸結(jié)(14)P(sun)(2)與(12)歸結(jié)(15)ANSWER(qian)(6)與(13)歸結(jié),Q=qian/y(16)ANSWER(sun)(6)與(14)歸結(jié)，o=sun/y所以，本題的盜竊犯是兩個(gè)人：錢和孫。2任何兄弟都有同一個(gè)父親，John和Peter是兄弟，且John的父親是David，問Peter的父親是誰？解：第一步：將已知條件用謂詞公式表示出來，并化成子句集。那么，要先定義謂詞。定義謂詞：設(shè)Father(x,y)表示x是y的父親。設(shè)Brother(x,y)表示x和y是兄弟。將已知事實(shí)用謂詞公式表示出來：F1:任何兄

9、弟都有同一個(gè)父親。VVV(x)(y)(z)(Brother(x,y)AFather(z,x)Father(z,y)F2:John和Peter是兄弟。Brother(John,Peter)F3:John的父親是David。Father(David,John)(3)將它們化成子句集，得S1=Brother(x,y)viFather(z,x)vFather(z,y),Brother(John,Peter),Father(David,John)第二步：把問題用謂詞公式表示出來，并將其否定與謂詞ANSWER做析取。設(shè)Peter的父親是u,則有：Father(u,Peter)將其否定與ANSWER做析取，

10、得G:，F(xiàn)ather(u,Peter)vANSWER(u)第三步：將上述公式G化為子句集S2，并將S1和S2合并到SoS2=Father(u,Peter)vANSWER(u)S=S1uS2將S中各子句列出如下：(1)Brother(x,y)viFather(z,x)vFather(z,y)(2)Brother(John,Peter)(3)Father(David,John)(4)Father(u,Peter)vANSWER(u)第四步：應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)。(5)Brother(John,y)vFather(David,y)(1)與(3)歸結(jié),q=David/z,John/x(6)Brothe

11、r(John,Peter)vANSWER(David)(4)與(5)歸結(jié),q=David/u,Peter/y(7)ANSWER(David)(2)與(6)歸結(jié)第五步:得到了歸結(jié)式ANSWER(David)，答案即在其中所以u(píng)=David,即Peter的父親是David。第4部分搜索策略本章小結(jié)個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途1狀I(lǐng)廠IIIIIII與盲目一廣度優(yōu)-深度優(yōu)-有界深度-代價(jià)樹的廣L代價(jià)樹的深局部擇L啟發(fā)4全局擇A*算廠廣度優(yōu)L深度及有界深有序I特殊情況提高搜索效率的方法博弈a_卩博弈極大極小分析法：計(jì)算出端節(jié)點(diǎn)的估值，再推算出父節(jié)點(diǎn)的得分。推算的方法是：對(duì)“或”節(jié)

12、點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最大的得分作為父節(jié)點(diǎn)的得分，這是為了使自己在可供選擇的方案中選一個(gè)對(duì)自己最有利的方案；對(duì)“與”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最小的得分作為父節(jié)點(diǎn)的得分，這是為了立足于最壞的情況。這樣計(jì)算出的父節(jié)點(diǎn)的得分稱為倒推值。a-p剪枝技術(shù)：對(duì)于一個(gè)“與”節(jié)點(diǎn)來說，它取當(dāng)前子節(jié)點(diǎn)中的最小倒推值作為它倒推值的上界，稱此值為p值。對(duì)于一個(gè)“或”節(jié)點(diǎn)來說，它取當(dāng)前子節(jié)點(diǎn)中的最大倒推值作為它倒推值的下界，稱此值為a值。12/68其一般規(guī)律為:(1)任何“或”節(jié)點(diǎn)x的a值如果不能降低其父節(jié)點(diǎn)的B值貝I對(duì)節(jié)點(diǎn)x以下的分枝可停止搜索，并使x的倒推值為a。這種剪枝成為B剪枝。(2)任何“與”節(jié)點(diǎn)x的B值如果不

13、能升高其父節(jié)點(diǎn)的a值，則對(duì)節(jié)點(diǎn)x以下的分枝可停止搜索，并使x的倒推值為po這種剪枝成為a剪枝。習(xí)題解答：1圖4-1是五城市間的交通路線圖，A城市是出發(fā)地，E城市是目的地，兩城市間的交通費(fèi)用(代價(jià))如圖中數(shù)字所示。求從A到E的最小費(fèi)用交通路線。解：先將交通圖轉(zhuǎn)換為代價(jià)樹，如圖4-2所示。若用g(x)表示從初始節(jié)點(diǎn)s0到節(jié)點(diǎn)x的代價(jià)，用c(x1,x2)表示從父節(jié)點(diǎn)x1到子節(jié)點(diǎn)x2的代價(jià)，則有：g(x2)=g(x1)+c(x1,x2)方法一：代價(jià)樹的廣度優(yōu)先搜索（擴(kuò)展節(jié)點(diǎn)n,將其子節(jié)點(diǎn)放入open表中，計(jì)算各子節(jié)點(diǎn)的代價(jià)，并按各節(jié)點(diǎn)的代價(jià)對(duì)open表中全部節(jié)點(diǎn)按從小到大的順序進(jìn)行排序（隊(duì)列）步驟如下

14、：14/68個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途 /68 /68所以，最優(yōu)路徑為A-C-D-E方法二：代價(jià)樹的深度優(yōu)先搜索（不一定是最優(yōu)解）（擴(kuò)展節(jié)點(diǎn)n,將其子節(jié)點(diǎn)按代價(jià)從小到大的順序放到open表的首部（棧）雖然D1的代價(jià)大于B1的代價(jià)，但按照代價(jià)樹E為目標(biāo)節(jié)點(diǎn)，E2-D1-C1-A所以路徑為A-C-D-E注：該題代價(jià)樹的深度優(yōu)先搜索與代價(jià)樹的廣度優(yōu)先搜索的結(jié)果相同，但這只是巧合。一般情況下，這兩種方法得到的結(jié)果不一定相同。另外，由于代價(jià)樹的深度優(yōu)先搜索有可能進(jìn)入無窮分支的路徑，因此它是不完備的。2如下圖4-5所示，分別用代價(jià)樹的廣度優(yōu)先搜索策略和代價(jià)樹的深度優(yōu)先搜索策略，求

15、A到E的最短費(fèi)用路徑。個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途圖 #/68圖 /68解：先將其化成代價(jià)樹，如圖4-6:(1)代價(jià)樹的廣度優(yōu)先搜索，步驟如下：個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途 /6811115圖E為目標(biāo)節(jié)點(diǎn)，路徑為A-C-E，代價(jià)為15。(2)代價(jià)樹的深度優(yōu)先搜索，步驟如下：雖然C1代價(jià)低于D1，但按照代價(jià)樹的深度優(yōu)先搜索策略，對(duì)D1進(jìn)行擴(kuò)展，放入closed表中，因?yàn)锽1擴(kuò)展的節(jié)點(diǎn)為D1，而C1是A節(jié)點(diǎn)擴(kuò)展得到的。E出棧，為目標(biāo)節(jié)點(diǎn)，結(jié)束。故解路徑為A-B-D-E,代價(jià)為17,不是最優(yōu)解。注：深度優(yōu)先搜索是不完備的，即使問題有解，也不一定能求得解

16、。得到的解也不一定是最優(yōu)解(因?yàn)槭蔷植績?yōu)先搜索)3下圖是五城市間的交通費(fèi)用圖，若從西安出發(fā)，要求把每個(gè)城市都訪問一遍，最后到達(dá)廣州，請(qǐng)找一條21/68最優(yōu)路線。邊上的數(shù)字是兩城市間的交通費(fèi)用。解：先畫出代價(jià)樹：130DA150BBDB907075DEE16075909512075160170907075130E11EBE1E1E1按代價(jià)樹的廣度優(yōu)先搜索即可得出最優(yōu)路線，步驟如下:圖23/68個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途80 /68 /68A150CEBEE195190CCDEEDEBEEBE420340285425295365355300380

17、340225340DB952515524026522185375故由此得出最優(yōu)路線為A-B1-D2-C4-E12即A-B-D-C-E，交通費(fèi)用為375。4設(shè)有如圖所示的一棵與/或樹，請(qǐng)分別用與/或樹的廣度優(yōu)先搜索及與/或樹的深度優(yōu)先搜索求出解樹。解:(1)與/或樹的廣度優(yōu)先搜索先擴(kuò)展節(jié)點(diǎn)A,得到節(jié)點(diǎn)B和C,再擴(kuò)展節(jié)點(diǎn)B,得節(jié)點(diǎn)t1、t2，因?yàn)閠1、t2為可解節(jié)點(diǎn)，故節(jié)點(diǎn)B可解，從而可節(jié)點(diǎn)A可解。所以求得解樹為：(2)與/或樹的深度優(yōu)先搜索先擴(kuò)展節(jié)點(diǎn)A,得到節(jié)點(diǎn)B和C,再擴(kuò)展節(jié)點(diǎn)C,得節(jié)點(diǎn)D和t5,t5為可解節(jié)點(diǎn)，再擴(kuò)展節(jié)D，得節(jié)點(diǎn)t3、t4，因?yàn)閠3、t4為可解節(jié)點(diǎn)，故節(jié)點(diǎn)D可解，因?yàn)楣?jié)點(diǎn)D和

18、t5可解，故節(jié)點(diǎn)C可解，從而可節(jié)點(diǎn)A可解。所以求得解樹為：個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途 #/68 /68 /685設(shè)有如圖所示的與/或樹，請(qǐng)分別按和代價(jià)法及最大代價(jià)法求解樹代價(jià)。按和代價(jià)法：h(B)=7,h(C)=3,h(A)=7+3+5+6=21按最大代價(jià)法：h(B)=5,h(C)=2,h(A)=5+5=101、談?wù)勀銓?duì)于人工智能的認(rèn)識(shí)。人工智能就是人造智能，目前指用計(jì)算機(jī)模擬或?qū)崿F(xiàn)的智能，因此人工智能又稱機(jī)器智能。人工智能在我看來，應(yīng)該是像人一樣思考的系統(tǒng)、像人一樣行動(dòng)的系統(tǒng)、理性地思考的系統(tǒng)、理性地行動(dòng)的系統(tǒng)，是像人一樣具有感知的系統(tǒng)，是

19、可以獨(dú)立思考、獨(dú)立判斷的系統(tǒng)2、人工智能有哪些研究途徑和方法？它們的關(guān)系如何？心理模擬，符號(hào)推演;生理模擬，神經(jīng)計(jì)算;行為模擬，控制進(jìn)化;群體模擬，仿生計(jì)算;博采廣鑒，自然計(jì)算;原理分析，數(shù)學(xué)建模；它們各有所長，也都有一定的局限性，因此這些研究途徑和方法并不能互相取代，而是并存和互補(bǔ)的關(guān)系。3、人工智能有哪些研究內(nèi)容？搜索與求解、學(xué)習(xí)與發(fā)現(xiàn)、知識(shí)與推理、發(fā)明與創(chuàng)造、感知與交流、記憶與聯(lián)想、系統(tǒng)與建造、應(yīng)用與工程等八個(gè)方面。4、人工智能有哪些分支領(lǐng)域和研究方向？從模擬的智能層次和所用的方法看，可分為符號(hào)智能和計(jì)算智能兩大領(lǐng)域；從模擬的腦智能或腦功能看，可分為機(jī)器學(xué)習(xí)、機(jī)器感知、機(jī)器聯(lián)想、機(jī)器推理

20、、機(jī)器行為等分支領(lǐng)域；從應(yīng)用角度看，可分為難題求解、自動(dòng)規(guī)劃、調(diào)度與配置、機(jī)器定理證明、自動(dòng)程序設(shè)計(jì)、機(jī)器翻譯、智能控制、智能管理、智能決策、智能通信、智能仿真、智能CAD、智能制造、智能CAI、智能人機(jī)接口、模式識(shí)別、數(shù)據(jù)挖掘與數(shù)據(jù)庫中的知識(shí)發(fā)現(xiàn)、計(jì)算機(jī)輔助創(chuàng)新、計(jì)算機(jī)文藝創(chuàng)作、機(jī)器博弈、智能機(jī)器人；從系統(tǒng)角度看，可分為智能計(jì)算機(jī)系統(tǒng)和智能應(yīng)用系統(tǒng)；從基礎(chǔ)理論看，可分為數(shù)理邏輯和多種非標(biāo)準(zhǔn)邏輯、圖論、人工神經(jīng)網(wǎng)絡(luò)、模糊集、粗糙集、概率統(tǒng)計(jì)和貝葉斯網(wǎng)絡(luò)、統(tǒng)計(jì)學(xué)習(xí)理論與支持向量機(jī)、形式語言與自動(dòng)機(jī)等領(lǐng)域；5、人工智能有哪些應(yīng)用領(lǐng)域或課題？試舉例說明難題求解、自動(dòng)規(guī)劃、調(diào)度與配置、機(jī)器定理證明、自

21、動(dòng)程序設(shè)計(jì)、機(jī)器翻譯、智能控制、智能管理、智能決策、智能通信、智能仿真、智能CAD、智能制造、智能CAI、智能人機(jī)接口、模式識(shí)別、數(shù)據(jù)挖掘與數(shù)據(jù)庫中的知識(shí)發(fā)現(xiàn)、計(jì)算機(jī)輔助創(chuàng)新、計(jì)算機(jī)文藝創(chuàng)作、機(jī)器博弈、智能機(jī)器人。就機(jī)器博弈方面，在1997年IBM的“深藍(lán)”計(jì)算機(jī)以2勝3平1負(fù)的戰(zhàn)績擊敗了蟬聯(lián)12年之久的直接國際象棋冠軍加里卡斯帕羅夫，比如先如今中的五子棋對(duì)弈，能實(shí)現(xiàn)人與電腦之間的下棋，電腦自動(dòng)搜索棋步，還可根據(jù)人們所選的電腦難度來決定電腦的難易程度。6、簡述人工智能的發(fā)展?fàn)顩r人工智能的現(xiàn)狀和發(fā)展呈現(xiàn)如下特點(diǎn)：多種途徑齊頭并進(jìn)，多種方法寫作互補(bǔ)；新思想、新技術(shù)不斷涌現(xiàn)，新領(lǐng)域、新方向不斷開括;

22、理論研究更加深入，應(yīng)用研究更加廣泛;研究隊(duì)伍日益壯大,社會(huì)影響越來越大;以上特點(diǎn)展現(xiàn)了人工智能學(xué)科的繁榮景象和光明前景。它表明，雖然在通向其最終目標(biāo)的道路上，還有不少困難、問題和挑戰(zhàn)，但前進(jìn)和發(fā)展畢竟是大勢所趨。7、試編寫一個(gè)描述親屬關(guān)系的PROLOG程序，然后再給出一些事實(shí)數(shù)據(jù)，建立一個(gè)小型演繹數(shù)據(jù)庫。domainsname=symbol.sex=symbol.age=integer.predicates個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途 /68 /68(0, /68、person(name,sex,age)mother(name,name)fat

23、her(name,name)brother(name,name)sister(name,name)grandfather(name,name)grandmother(name,name)goalbrother(Namel,Name2),write(Namel,is,Name2,sbrother!n),sister(Name3,Name4),write(Name3,is,Name4,ssister!n),grandfather(Name5,Name6),write(Name5,is,Name6,sgrandfather!n),grandmother(Name7,Name8),write(Name

24、7,is,Name8,sgrandmother!n).clausesperson(alan,m,21).mother(alice,alan).mother(marry,jane).person(john,m,22).mother(alice,john).father(alan,tom).person(marry,w,23).person(ann,w,24).mother(alice,marry).mother(alice,ann).father(tom,ben).brother(Name1,Name2):-person(Name1,m,Age1),person(Name2,m,Age2),mo

25、ther(Z,Name1),mother(Z,Name2),Age1Age2.sister(Name3,Name4):-person(Name3,w,Age3),person(Name4,w,Age4),mother(Z,Name3),mother(Z,Name4),Age3Age4.grandfather(Name1,Name2):-father(Name1,Y),father(Y,Name2).grandmother(Name7,Name8):-mother(Name7,X),mother(X,Name8).何為狀態(tài)圖和與或圖？圖搜索與問題求解有什么關(guān)系？狀態(tài)圖是描述尋找目標(biāo)或路徑問題的有

26、向圖，即描述一個(gè)實(shí)體基于事件反應(yīng)的動(dòng)態(tài)行為,顯示了該實(shí)體如何根據(jù)當(dāng)前所處的狀態(tài)對(duì)不同的時(shí)間做出反應(yīng)的。與或圖是一種系統(tǒng)地將問題分解為互相獨(dú)立的小問題，然后分而解決的方法。與或圖中有兩種代表性的節(jié)點(diǎn)：“與節(jié)點(diǎn)”和“或節(jié)點(diǎn)”，“與節(jié)點(diǎn)”指所有的后續(xù)節(jié)點(diǎn)都有解時(shí)它才有解；“或節(jié)點(diǎn)”指各個(gè)后續(xù)節(jié)點(diǎn)均完全獨(dú)立，只要其中有一個(gè)有解它就有解。關(guān)系：問題求解就是在一個(gè)圖中尋找一個(gè)從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑問題，圖搜索模擬的實(shí)際是人腦分析問題，解決問題的過程，它基于領(lǐng)域知識(shí)的問題求解過程。綜述圖搜索的方式和策略。答：圖搜索方式可分為樹式搜索和線式搜索。圖搜索策略可分為盲目搜索和啟發(fā)式搜索。10什么是問題的解？什

27、么是最優(yōu)解？答：能夠解決問題的方法或具體做法。其中最好的解決方法即代價(jià)最小的解稱為最優(yōu)解。11.什么是與或樹？什么是可解節(jié)點(diǎn)？什么是解樹？答：一棵樹中的弧線表示所連樹枝為“與”關(guān)系不帶弧線的樹枝為或關(guān)系。這棵樹中既有與關(guān)系又有或關(guān)系，因此被稱為與或樹。滿足下列條件的節(jié)點(diǎn)為可解節(jié)點(diǎn)。終止節(jié)點(diǎn)是可解節(jié)點(diǎn)；一個(gè)與節(jié)點(diǎn)可解，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全都可解；一個(gè)或節(jié)點(diǎn)可解，只要其子節(jié)點(diǎn)至少有一個(gè)可解。解樹實(shí)際上是由可解節(jié)點(diǎn)形成的一棵子樹,這棵子樹的根為初始節(jié)點(diǎn),葉為終止節(jié)點(diǎn)，且這棵子樹一定是與樹。12設(shè)有三只琴鍵開關(guān)一字排開，初始狀態(tài)為“關(guān)、開、關(guān)”，問連按三次后是否會(huì)出現(xiàn)“開、開、開”或“關(guān)、關(guān)、關(guān)”的狀態(tài)

28、？要求每次必須按下一個(gè)開關(guān)，而且只能按一個(gè)開關(guān)。請(qǐng)畫出狀態(tài)空間圖。解：用(K1,K2,K3)表示三個(gè)開關(guān)的狀態(tài)，取值為0時(shí)表示閉合，為1時(shí)表示打開。則初始狀態(tài)為(0,1,0)。根據(jù)題設(shè)要求，一個(gè)狀態(tài)I的下一個(gè)狀態(tài)和I只能有一位取值不同(此即狀態(tài)轉(zhuǎn)換規(guī)則)，據(jù)此可以畫出狀態(tài)空間圖。從此狀態(tài)圖不難看出：經(jīng)過連續(xù)三步有狀態(tài)(0,1,0)只能到達(dá)狀態(tài)(0,0,0)而不能到達(dá)狀態(tài)(1,1,1),即會(huì)出現(xiàn)狀態(tài)“關(guān)，關(guān)，關(guān)”但不會(huì)出現(xiàn)“開，開，開”13.有一農(nóng)夫帶一只狼、一只羊和一筐菜欲從河的左岸乘船到右岸,但受下列條件限制：船太小，農(nóng)夫每次只能帶一樣?xùn)|西過河。(2)如果沒有農(nóng)夫看管，則狼要吃羊，羊要吃菜。

29、請(qǐng)?jiān)O(shè)計(jì)一個(gè)過河方案，使得農(nóng)夫、狼、羊、菜都能不受損失地過河。畫出相應(yīng)的狀態(tài)空間圖。提示：(1)用四元組(農(nóng)夫、狼、羊、菜)表示狀態(tài),其中每個(gè)元素都可為0或1,用0表示在左岸，用1表示在右岸。(2)把每次過河的一種安排作為一個(gè)算符，每次過河都必須有農(nóng)夫，因?yàn)橹挥兴梢詣澊?。解：初始S=(0,0,0,0),目標(biāo)G=(1,1,1,1)定義操作符L(i)表示農(nóng)夫帶東西到右岸：i=0農(nóng)夫自己到右岸；i=1農(nóng)夫帶狼到右岸；i=2農(nóng)夫帶羊到右岸；i=3農(nóng)夫帶菜到右岸；約束狀態(tài)如下：(1,0,0,X)狼、羊在左岸；(1,X,0,0)羊、菜在左岸；(0,1,1,X)狼、羊在右岸；(0,X,1,1)羊、菜在右岸；

30、(0,0,0,D)+J(bb映2農(nóng)夫回來0,1,映3帶菜過河(b0,1,14一帶羊回來00,0,1錄簣狼過河(1,1,山1*匡農(nóng)夫回來(0,1,0,17一帶羊過河(1,1,1,1*(b1,b1*個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途 /68 /68請(qǐng)闡述狀態(tài)空間的一般搜索過程。OPEN表與CLOSED表的作用是什么？答：先把問題的初始狀態(tài)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)對(duì)其進(jìn)行擴(kuò)展，生成一組子節(jié)點(diǎn)，然后檢查問題的目標(biāo)狀態(tài)是否出現(xiàn)在這些子節(jié)點(diǎn)中。若出現(xiàn)，則搜索成功，找到了問題的解；若沒出現(xiàn)，則再按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)。重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中

31、或者沒有可供操作的節(jié)點(diǎn)為止。所謂對(duì)一個(gè)節(jié)點(diǎn)進(jìn)行“擴(kuò)展”是指對(duì)該節(jié)點(diǎn)用某個(gè)可用操作進(jìn)行作用，生成該節(jié)點(diǎn)的一組子節(jié)點(diǎn)。OPEN表用于存放剛生成的節(jié)點(diǎn)，對(duì)于不同的搜索策略，節(jié)點(diǎn)在OPEN表中的排序是不同的。CLOSED表用于存放將要擴(kuò)展或者已擴(kuò)展的節(jié)點(diǎn)。廣度優(yōu)先搜索與深度優(yōu)先搜索各有什么特點(diǎn)？廣度優(yōu)先搜索就是始終先在同一級(jí)節(jié)點(diǎn)中考查，只有當(dāng)同一級(jí)節(jié)點(diǎn)考查完之后，才考查下一級(jí)節(jié)點(diǎn)?；蛘哒f，是以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，向下逐級(jí)擴(kuò)展搜索樹。所以,廣度優(yōu)先策略的搜索樹是自頂向下一層一層逐漸生成的。深度優(yōu)先搜索就是在搜索樹的每一層始終先只擴(kuò)展一個(gè)子節(jié)點(diǎn)，不斷地向縱深前進(jìn)，直到不能再前進(jìn)（到達(dá)葉子節(jié)點(diǎn)或受到深度限制）

32、時(shí)，才從當(dāng)前節(jié)點(diǎn)返回到上一級(jí)節(jié)點(diǎn)，沿另一方向又繼續(xù)前進(jìn)。這種方法的搜索樹是從樹根開始一枝一枝逐漸形成的。深度優(yōu)先搜索亦稱為縱向搜索。由于一個(gè)有解的問題樹可能含有無窮分枝，深度優(yōu)先搜索如果誤入無窮分枝（即深度無限），則不可能找到目標(biāo)節(jié)點(diǎn)。所以，深度優(yōu)先搜索策略是不完備的。另外，應(yīng)用此策略得到的解不一定是最佳解（最短路徑）。廣度優(yōu)先搜索與深度優(yōu)先搜索都屬于盲目搜索。16是五大城市間的交通示意圖，邊上的數(shù)字是兩城市間的距離。用圖搜索技術(shù)編寫程序，求解以下問乂/2216昆明廣州題：解：domainsp=stringd=integerpp=p*predicatesroad(p,p,d)path(p,p,

33、pp,d)member(p,pp)clausespath(X,Y,L,D):-road(X,YD),L=XIY.path(X,Y,L,D):-road(X,Z,Dl),%從當(dāng)前點(diǎn)向前走到下一點(diǎn)Znot(member(Z,L),path(Z,Y,ZIL,D2),D=D1+D2.%再找Z到出口Y的路徑member(X,Xl_).member(X,_|T)ifmember(X,T).road(A,B,D):-road(B,A,D).%因?yàn)闆]向圖/*父通圖*/road(“西安”，”北京”,1165).road(“西安”，“廣州”,2129).road(“昆明，”北京”,3179).road(“昆明”，

34、“廣州”,2216).road(“上?！?，”北京”,1462).road(“西安”，”上?！?1511).road(“西安”，”昆明”,1942).road(“昆明”，”上?！?2677).road(“北京”，”廣州”,2510).road(“廣州”，“上?！?1511).path(“西安”，”北京”,L,D),write(L,D).path(“西安”，”北京”,L,D),member(“上海,L),write(L,D).path(“西安”，”北京”,L,D),member(“上?！?L),not(member(“昆明,L),write(L,D).何謂估價(jià)函數(shù)？在估價(jià)函數(shù)中,g(x)和h(x)

35、各起什么作用？答：估價(jià)函數(shù)用來估計(jì)節(jié)點(diǎn)重要性的函數(shù)。估價(jià)函數(shù)f(x)被定義為從初始節(jié)點(diǎn)SO出發(fā)，約束經(jīng)過節(jié)點(diǎn)x到達(dá)目標(biāo)節(jié)點(diǎn)Sg的所有路徑中最小路徑代價(jià)的估計(jì)值。它的一般形式為：f(x)=g(x)+h(x)其中，g(x)是從初始節(jié)點(diǎn)SO到節(jié)點(diǎn)x的實(shí)際代價(jià)；h(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估計(jì)代價(jià)。局部擇優(yōu)搜索與全局擇優(yōu)搜索的相同處與區(qū)別各是什么？局部擇優(yōu)搜索與全局擇優(yōu)搜索的區(qū)別是，擴(kuò)展節(jié)點(diǎn)N后僅對(duì)N的子節(jié)點(diǎn)按啟發(fā)函數(shù)值大小以升序排序，再將它們依次放入OPEN表的首部。故算法從略。傳教士和野人問題。有三個(gè)傳教士和三個(gè)野人一起來到河邊準(zhǔn)備渡河，河邊有一條空船,且傳教士和野人都會(huì)劃船，但每

36、次最多可供兩人乘渡。河的任何一岸以及船上一旦出現(xiàn)野人人數(shù)超過傳教士人數(shù)，野人就會(huì)把傳教士吃掉。為安全地渡河，傳教士應(yīng)如何規(guī)劃渡河方案？試給出該問題的狀態(tài)圖表示，并用PROLOG語言編程求解之。若傳教士和野人的數(shù)目均為五人，渡船至多可乘三人，請(qǐng)定義一個(gè)啟發(fā)函數(shù)，并給出相應(yīng)的搜索樹。解：首先選取描述問題狀態(tài)的方法。在這個(gè)問題中，需要考慮兩岸的修道士人數(shù)和野人數(shù)，還需要考慮船在左岸還是在右岸。從而可用一個(gè)三兀組來表示狀態(tài)：S=(m,c,b)其中，m表示左岸的修道士人數(shù)，c表示左岸的野人數(shù)，b表示左岸的船數(shù)。右岸的狀態(tài)可由下式確定：右岸修道士數(shù)：m=3-m；右岸野人數(shù)：c=3-c；右岸船數(shù)：b=1-b

37、在這種表示方式下,m和c都可取0、中之一,b可取0和1中之一。因此，共有4x4x2=32種狀態(tài)。這32種狀態(tài)并非全有意義，除去不合法狀態(tài)和修道士被野人吃掉的狀態(tài)，有意義的狀態(tài)只有16種：So=(3,3,1)S=(3,2,1)S2=(3,1,1)S3=(2,2,1)S4=(l,1,1)S5=(0,3,1)S6=(0,2,1)S7=(0,1,1)S8=(3,2,0)S9=(3,1,0)S10=(3,0,0)SB2,2,0)SC，1,0)j2,0)j1,0)S15=(0,0,0)有了這些狀態(tài)，還需要考慮可進(jìn)行的操作。操作是指用船把修道士或野人從河的左岸運(yùn)到右岸，或從河的右岸運(yùn)到左岸。每個(gè)操作都應(yīng)當(dāng)滿

38、足如下條件：一是船至少有一個(gè)人(m或c)操作，離開岸邊的m和c的減少數(shù)目應(yīng)該等于到達(dá)岸邊的m和c的增加數(shù)目；二是每次操作船上人數(shù)不得超過2個(gè)；三是操作應(yīng)保證不產(chǎn)生非法狀態(tài)。因此，操作應(yīng)由條件部分和動(dòng)作部分：條件：只有當(dāng)其條件具備時(shí)才能使用動(dòng)作:刻劃了應(yīng)用此操作所產(chǎn)生的結(jié)果。操作的表示：用符號(hào)P表示從左岸到右岸的運(yùn)人操ij作用符號(hào)Q表示從右岸到左岸的操作其中：i表示船上的修道士人數(shù)j表示船上的ij野人數(shù)操作集本問題有10種操作可供選擇：Q02，Q20F=P01，P10，P11，P02,P20，Qoi，Q10，Q11，下面以P01和Q01為例來說明這些操作的條件和動(dòng)作。操作符號(hào)條件動(dòng)作Pb=1,m

39、=0或3,c三1b=0,c=cT01D(x)X是不沾和ilT：I/XA)X喜歡yF,：WxgD(y)TLXME：Vx-iUxTa)G:OLi)b=0,m=0或3,20.設(shè)（1）凡卜龐清沽的東西就仃人:橄人們都不也歡蒼蠅蒼婭圧不晴潔何cW2b=1,c=c+l事清潔的東西就有人喜歡（2）人們都不喜歡蒼蠅用歸結(jié)原理證明蒼蠅是不清潔的八皇后問題:答案:用八元組（X0,Xl,X2,X3,X4,X5,X6,X7）表示第18行的棋子，值（x0,xl,x2,x3,x4,x5,x6,x7）表示其在列上的位置。狀態(tài)可表示為八元組的一組值。DOMAINS1list=inteqerQwwvwwPREDICATES-1

40、queens(inteqe巧list)卩vWv*w*wv*w*v*w*A?v*Xivv*w*vVWWWv*v”range(integer/integer,lis1safe(list)PWaRaIaRaRaWaRaIaWattack(eger.lispermutation(list,list)adelete(inteqer#list,list)WvWv*w*wv*w*v*w*A?vVvWv*wwv*v*w*v*wWWWvV?v*wwv*wwv*w*v”GOAI1queens(8,X),write(X).nlrfailCLAUSES-1queens(N,Qs):range(1

41、zN,Ns),permutation(gNs)rsafe(Qs)3range(MZNZM|Ns):-MNzMl=M+lrrange(MlzNzNs)“range(N,NfN).4safeEQlQs):-safe(Qs)fnot(attack(QrlrQs)safe()dattack(X,N,Y|):-X=Y+N.+attack(X,N,Y|):-X=Y-Ndattacjyx,N,_|Ys):-Nl=N+lfattack(X,Ys)4permutationL(1.)心permutation.(A|X,Y):delete(A,Y.Yl),permutation.(X,Yl).4*XvXAvVvVv

42、VName：Unit(Last-name,First-name)Sex：Area(male,female)Default：maleAge：Unit(Years)Telephone：HomeUnit(Number)MobileUnit(Number)教師框架FrameAKOvTeachers-StudentsMajor：Unit(Major-Name)Lectures：Unit(Course-Name)Field：Unit(Field-Name)Project:Area(National，Provincial，Other)Default：ProvincialPaper：Area(SCI，EI,C

43、ore，General)Default：Core學(xué)生框架FrameAKOvTeachers-StudentsMajor：Unit(Major-Name)Classes：Unit(Classes-Name)Degree：Area(doctor，mastor,bachelor)Default：bachelor第3章確定性推理部分參考答案38判斷下列公式是否為可合一，若可合一，則求出其最一般合一。P(a,b),P(x,y)P(f(x),b),P(y,z)P(f(x),y),P(y,f(b)P(f(y),y,x),P(x,f(a),f(b)P(x,y),P(y,x)解：“可合一，其最一般和一為：O=a

44、/x,b/y?？珊弦?，其最一般和一為：O=y/f(x),b/z。可合一，其最一般和一為：O=f(b)/y,b/x。不可合一。(5)可合一，其最一般和一為：O=y/x。3.11把下列謂詞公式化成子句集：(Vx)(Vy)(P(x,y)AQ(x,y)(Vx)(Vy)(P(x,y)-Q(x,y)(Vx)(3y)(P(x,y)V(Q(x,y)-R(x,y)(Vx)(Vy)(3z)(P(x,y)-Q(x,y)VR(x,z)解：(1)由于(Vx)(Vy)(P(x,y)AQ(x,y)已經(jīng)是Skolem標(biāo)準(zhǔn)型，且P(x,y)AQ(x,y)已經(jīng)是合取范式，所以可直接消去全稱量詞、合取詞，得P(x,y),Q(x,y

45、)再進(jìn)行變?cè)獡Q名得子句集：S=P(x,y),Q(u,v)對(duì)謂詞公式(Vx)(Vy)(P(x,y)-Q(x,y)，先消去連接詞“一”得：(Vx)(Vy)(-P(x,y)VQ(x,y)此公式已為Skolem標(biāo)準(zhǔn)型。再消去全稱量詞得子句集：S=-P(x,y)VQ(x,y)對(duì)謂詞公式(Vx)(3y)(P(x,y)V(Q(x,y)-R(x,y)，先消去連接詞“一”得：(Vx)(3y)(P(x,y)V(-Q(x,y)VR(x,y)此公式已為前束范式。再消去存在量詞，即用Skolem函數(shù)f(x)替換y得：(Vx)(P(x,f(x)V-Q(x,f(x)VR(x,f(x)此公式已為Skolem標(biāo)準(zhǔn)型。最后消去全

46、稱量詞得子句集：S=P(x,f(x)V-Q(x,f(x)VR(x,f(x)對(duì)謂詞(Vx)(Vy)(3z)(P(x,y)-Q(x,y)VR(x,z)，先消去連接詞“一”得：(Vx)(Vy)(3z)(-P(x,y)VQ(x,y)VR(x,z)再消去存在量詞，即用Skolem函數(shù)f(x)替換y得：(Vx)(Vy)(-P(x,y)VQ(x,y)VR(x,f(x,y)此公式已為Skolem標(biāo)準(zhǔn)型。最后消去全稱量詞得子句集：S=-P(x,y)VQ(x,y)VR(x,f(x,y)3-13判斷下列子句集中哪些是不可滿足的：-PVQ,-Q,P,-PPVQ,-PVQ,PV-Q,-PV-QP(y)VQ(y),-P(

47、f(x)VR(a)-P(x)VQ(x),-P(y)VR(y),P(a),S(a),-S(z)V-R(z)-P(x)VQ(f(x),a)，-P(h(y)VQ(f(h(y),a)V-P(z)個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途 /68 #/68P(x)VQ(x)VR(x)，-P(y)VR(y),-Q(a),-R(b)解：(1)不可滿足，其歸結(jié)過程為：不可滿足，其歸結(jié)過程為:不是不可滿足的，原因是不能由它導(dǎo)出空子句。不可滿足，其歸結(jié)過程略不是不可滿足的，原因是不能由它導(dǎo)出空子句。不可滿足，其歸結(jié)過程略3.14對(duì)下列各題分別證明G是否為耳,F2，,F的邏輯結(jié)論:12nF:(3x)(3y

48、)(P(x,y)G:(Vy)(3x)(P(x,y)F:(Vx)(P(x)A(Q(a)VQ(b)G:(3x)(P(x)AQ(x)F:(3x)(3y)(P(f(x)A(Q(f(y)G:P(f(a)AP(y)AQ(y)F1:(Vx)(P(x)f(Vy)(Q(yLL(x.y)F2:(3x)(P(x)A(Vy)(R(y)fL(x.y)G:(Vx)(R(x)fQ(x)F1:(Vx)(P(x)-(Q(x)AR(x)F2:(3x)(P(x)AS(x)G:(3x)(S(x)AR(x)解：(1)先將F和-G化成子句集：S=P(a,b),-P(x,b)再對(duì)S進(jìn)行歸結(jié)：個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)

49、用途所以，G是F的邏輯結(jié)論(2)先將F和-G化成子句集由F得：S=P(x),(Q(a)VQ(b)由于-G為：-(3x)(P(x)AQ(x),即(Vx)(-P(x)V-Q(x),可得：S2=-P(x)V-Q(x)因此，擴(kuò)充的子句集為：S=P(x),(Q(a)VQ(b),-P(x)V-Q(x)再對(duì)S進(jìn)行歸結(jié)：所以，G是F的邏輯結(jié)論同理可求得(3)、(4)和(5),其求解過程略。3.15設(shè)已知：如果x是y的父親，y是z的父親，則x是z的祖父；每個(gè)人都有一個(gè)父親。使用歸結(jié)演繹推理證明：對(duì)于某人u,一定存在一個(gè)人v,v是u的祖父。解：先定義謂詞F(x,y)：x是y的父親GF(x,z)：x是z的祖父P(x

50、)：x是一個(gè)人再用謂詞把問題描述出來：已知F1：(Vx)(vy)(Vz)(F(x,y)AF(y,z)fGF(x,z)F2：(vy)(P(x)-F(x,y)求證結(jié)論G：(3u)(3v)(P(u)fGF(v,u)然后再將F1,F2和-G化成子句集：-F(x,y)V-F(y,z)VGF(x,z)-P(r)VF(s,r)P(u)-GF(v,u)對(duì)上述擴(kuò)充的子句集，其歸結(jié)推理過程如下：-F(x,y)V-門I-GFx/v,z/ux-F(x,y)40/(682個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途 /68 /68x/s,y/ry/s,z/ry/zy/u由于導(dǎo)出了空子句，故結(jié)論得證。3.16假設(shè)

51、張被盜，公安局派出5個(gè)人去調(diào)查。案情分析時(shí)，貞察員A說：“趙與錢中至少有一個(gè)人作案”貞察員B說：“錢與孫中至少有一個(gè)人作案”貞察員C說：“孫與李中至少有一個(gè)人作案”貞察員D說：“趙與孫中至少有一個(gè)人與此案無關(guān)”貞察員E說：“錢與李中至少有一個(gè)人與此案無關(guān)”如果這5個(gè)偵察員的話都是可信的，使用歸結(jié)演繹推理求出誰是盜竊犯。解：(1)先定義謂詞和常量設(shè)C(x)表示x作案，Z表示趙，Q表示錢，S表示孫，L表示李將已知事實(shí)用謂詞公式表示出來趙與錢中至少有一個(gè)人作案：C(Z)VC(Q)錢與孫中至少有一個(gè)人作案：C(Q)VC(S)孫與李中至少有一個(gè)人作案：C(S)VC(L)趙與孫中至少有一個(gè)人與此案無關(guān)：-

52、(C(Z)AC(S)，即-C(Z)V-C(S)錢與李中至少有一個(gè)人與此案無關(guān)：-(C(Q)AC(L)，即-C(Q)V-C(L)將所要求的問題用謂詞公式表示出來，并與其否定取析取。設(shè)作案者為u,則要求的結(jié)論是C(u)。將其與其否)取析取，得：-C(u)VC(u)對(duì)上述擴(kuò)充的子句集，按歸結(jié)原理進(jìn)行歸結(jié)，其修改的證明樹如下：因此，錢是盜竊犯。實(shí)際上，本案的盜竊犯不止一人。根據(jù)歸結(jié)原理還可以得出:因此，孫也是盜竊犯。3.18設(shè)有子句集：P(x)VQ(a,b),P(a)VQ(a,b),Q(a,f(a),P(x)VQ(x,b)分別用各種歸結(jié)策略求出其歸結(jié)式。解：支持集策略不可用，原因是沒有指明哪個(gè)子句是由

53、目標(biāo)公式的否定化簡來的。刪除策略不可用，原因是子句集中沒有沒有重言式和具有包孕關(guān)系的子句。單文字子句策略的歸結(jié)過程如下：用線性輸入策略(同時(shí)滿足祖先過濾策略)的歸結(jié)過程如下:INI3.19設(shè)已知：能閱讀的人是識(shí)字的；海豚不識(shí)字；有些海豚是很聰明的。請(qǐng)用歸結(jié)演繹推理證明：有些很聰明的人并不識(shí)字。解：第一步，先定義謂詞，設(shè)R(x)表示x是能閱讀的；K(y)表示y是識(shí)字的；W(z)表示z是很聰明的；第二步，將已知事實(shí)和目標(biāo)用謂詞公式表示出來能閱讀的人是識(shí)字的：(Vx)(R(x)-K(x)海豚不識(shí)字：(Vy)(-K(y)有些海豚是很聰明的：(3z)W(z)有些很聰明的人并不識(shí)字：(3x)(W(z)A-

54、K(x)第三步，將上述已知事實(shí)和目標(biāo)的否定化成子句集：-R(x)VK(x)-K(y)W(z)-W(z)VK(x)第四步，用歸結(jié)演繹推理進(jìn)行證明320對(duì)子句集：PVQ,QVR,RVW,RVP,WVQ,QVR用線性輸入策略是否可證明該子句集的不可滿足性？解：用線性輸入策略不能證明子句集PVQ,QVR,RVW,RVP,WVQ,QVR的不可滿足性。原因是按線性輸入策略，不存在從該子句集到空子句地歸結(jié)過程。321對(duì)線性輸入策略和單文字子句策略分別給出一個(gè)反例，以說明它們是不完備的。322分別說明正向、逆向、雙向與/或形演繹推理的基本思想。323設(shè)已知事實(shí)為(PVQ)AR)V(SA(TVU)F規(guī)則為S(X

55、AY)VZ試用正向演繹推理推出所有可能的子目標(biāo)。解：先給出已知事實(shí)的與/或樹，再利用F規(guī)則進(jìn)行推理，其規(guī)則演繹系統(tǒng)如下圖所示。由該圖可以直接寫出所有可能的目標(biāo)子句如下：PVQVTVUPVQVXVZPVQVYVZRVTVURVXVZRVYVZ所有子有JPrQJ!R_Da叵,A瓦rTI1J1F規(guī))(YXS17PQIrTIJ已(p1RT(SA(PVQ)AR)3.24設(shè)有如下一段知識(shí)：“張、王和李都屬于高山協(xié)會(huì)。該協(xié)會(huì)的每個(gè)成員不是滑雪運(yùn)動(dòng)員，就是登山運(yùn)動(dòng)員,其中不喜歡雨的運(yùn)動(dòng)員是登山運(yùn)動(dòng)員，不喜歡雪的運(yùn)動(dòng)員不是滑雪運(yùn)動(dòng)員。王不喜歡張所喜歡的一切東西，而喜歡張所不喜歡的一切東西。張喜歡雨和雪?！痹囉弥^

56、詞公式集合表示這段知識(shí)，這些謂詞公式要適合一個(gè)逆向的基于規(guī)則的演繹系統(tǒng)。試說明這樣一個(gè)系統(tǒng)怎樣才能回答問題：“高山俱樂部中有沒有一個(gè)成員，他是一個(gè)登山運(yùn)動(dòng)員，但不是一個(gè)滑雪運(yùn)動(dòng)員？”解：(1)先定義謂詞A(x)表示x是高山協(xié)會(huì)會(huì)員S(x)表示x是滑雪運(yùn)動(dòng)員個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途C(x)表示x是登山運(yùn)動(dòng)員L(x,y)表示x喜歡y將問題用謂詞表示出來“張、王和李都屬于高山協(xié)會(huì)A(Zhang)AA(Wang)人A(Li)高山協(xié)會(huì)的每個(gè)成員不是滑雪運(yùn)動(dòng)員，就是登山運(yùn)動(dòng)員(Vx)(A(x)A-S(x)fC(x)高山協(xié)會(huì)中不喜歡雨的運(yùn)動(dòng)員是登山運(yùn)動(dòng)員(Vx)(-L(x,Rai

57、n)fC(x)高山協(xié)會(huì)中不喜歡雪的運(yùn)動(dòng)員不是滑雪運(yùn)動(dòng)員(Vx)(-L(x,Snow)f-S(x)王不喜歡張所喜歡的一切東西(Vy)(L(Zhang,y)f-L(Wang,y)王喜歡張所不喜歡的一切東西(Vy)(-L(Zhang,y)fL(Wang,y)張喜歡雨和雪L(Zhang,Rain)AL(Zhang,Snow)將問題要求的答案用謂詞表示出來高山俱樂部中有沒有一個(gè)成員，他是一個(gè)登山運(yùn)動(dòng)員，但不是一個(gè)滑雪運(yùn)動(dòng)員？(3x)(A(x)fC(x)A-S(x)為了進(jìn)行推理，把問題劃分為已知事實(shí)和規(guī)則兩大部分。假設(shè)，劃分如下：已知事實(shí)：A(Zhang)AA(Wang)AA(Li)L(Zhang,Rai

58、n)AL(Zhang,Snow)規(guī)則：(Vx)(A(x)A-S(x)fC(x)(Vx)(-L(x,Rain)fC(x)(Vx)(-L(x,Snow)f-S(x)(Vy)(L(Zhang,y)f-L(Wang,y)(Vy)(-L(Zhang,y)fL(Wang,y)把已知事實(shí)、規(guī)則和目標(biāo)化成推理所需要的形式事實(shí)已經(jīng)是文字的合取形式：L：A(Zhang)AA(Wang)AA(Li)f2：L(Zhang,Rain)AL(Zhang,Snow)將規(guī)則轉(zhuǎn)化為后件為單文字的形式：r1:A(x)A-S(x)C(x)r2：-L(x,Rain)fC(x)r3：-L(x,Snow)-S(x)r4:L(Zhang,

59、y)f-L(Wang,y)r5：-L(Zhang,y)L(Wang,y)將目標(biāo)公式轉(zhuǎn)換為與/或形式-A(x)V(C(x)A-S(x)進(jìn)行逆向推理逆向推理的關(guān)鍵是要能夠推出L(Zhang,Rain)AL(Zhang,Snow)，其逆向演繹過程如下50/68個(gè)人收集整理，勿做商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途 /68 /68圖所示。-A(x)VC(x)Wang/x-L(x,rRa-L(WarL(Zha-L(x,-L(WaL(ZhaIL(ZhanL(Zhan搜索策略部分參考答案45有一農(nóng)夫帶一條狼，一只羊和一框青菜與從河的左岸乘船倒右岸，但受到下列條件的限制：船太小，農(nóng)夫每次只能帶一樣?xùn)|西過河；如果

60、沒有農(nóng)夫看管，則狼要吃羊，羊要吃菜。請(qǐng)?jiān)O(shè)計(jì)一個(gè)過河方案，使得農(nóng)夫、浪、羊都能不受損失的過河，畫出相應(yīng)的狀態(tài)空間圖。題示：(1)用四元組(農(nóng)夫，狼，羊，菜)表示狀態(tài)，其中每個(gè)元素都為0或1,用0表示在左岸，用1表示在右岸。(2)把每次過河的一種安排作為一種操作，每次過河都必須有農(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)表示出來，包括問題的初始狀態(tài)和目標(biāo)狀態(tài)。由于狀態(tài)變量有4個(gè)