人工智能習題集及各章小結(jié)[17頁]

1、人工智能各章小結(jié)及習題解答第一部分 緒論習題解答：1什么是人工智能？發(fā)展過程中經(jīng)歷了哪些階段？解：人工智能是計算機科學的一個重要分支，也是一門正在發(fā)展中的綜合性前沿學科，它是由計算機科學、控制論、信息論、神經(jīng)生理學、哲學、語言學等多種學科相互滲透而發(fā)展起來的，目前正處于發(fā)展階段尚未形成完整體系。 發(fā)展過程中經(jīng)歷的階段有： 第一階段（40年代中50年代末） 神經(jīng)元網(wǎng)絡時代第二階段（50年代中60年代中） 通用方法時代第三階段（60年代中80年代初） 知識工程時代第四階段（80年代中90年代初） 新的神經(jīng)元網(wǎng)絡時代第五階段（90年代初現(xiàn)在） 海量信息處理與網(wǎng)絡時代2人工智能研究的基本內(nèi)容是什么？解

2、：基本內(nèi)容是：搜索技術、知識表示、規(guī)劃方法、機器學習、認知科學、自然語言理解與機器翻譯、專家系統(tǒng)與知識工程、定理證明、博弈、機器人、數(shù)據(jù)挖掘與知識發(fā)現(xiàn)、多Agent系統(tǒng)、復雜系統(tǒng)、足球機器人、人機交互技術等。3人工智能主要有哪幾大研究學派？解：（）符號主義學派：由心理學途徑產(chǎn)生，符號主義認為人工智能起源于數(shù)理邏輯，人類認識（智能）的基本元素是符號，而智能行為則是符號運算的結(jié)果。（）連接主義學派：由生理學途徑產(chǎn)生，連接主義又稱為仿生學派，認為人工智能的基本元素是神經(jīng)元，智能產(chǎn)生于大量神經(jīng)元的并行分布式聯(lián)結(jié)之中，而智能行為則是聯(lián)結(jié)計算的結(jié)果。 （）行為主義學派：由生物演化途徑產(chǎn)生，行為主義認為人工

3、智能起源于控制論，提出智能取決于感知和行為，取決于對外界復雜環(huán)境的適應，而不是表示和推理。人工智能有哪些主要的研究領域？解：（）問題求解（）邏輯推理與定理證明（）自然語言理解（）自動程序設計（）專家系統(tǒng)（）機器學習（）神經(jīng)網(wǎng)絡（）機器人學（）模式識別（）機器視覺（）智能控制（）智能檢索（）智能調(diào)度與指揮（）分布式人工智能與（）計算智能與進化計算（）數(shù)據(jù)挖掘與知識發(fā)現(xiàn)（）人工生命（）系統(tǒng)與語言工具第2部分 知識與知識表示本章小結(jié)： 習題解答：1 設有如下問題：（1）有五個相互可直達且距離已知的城市A、B、C、D、E，如圖所示；（2）某人從A地出發(fā)，去其它四個城市各參觀一次后回到A;（3）找一條最

4、短的旅行路線請用產(chǎn)生式規(guī)則表示旅行過程。解：綜合數(shù)據(jù)庫（x）(x)中x可以是一個字母，也可以是一個字符串。初始狀態(tài)（A）目標狀態(tài)（Ax1x2x3x4A） 規(guī)則集： r1: IF L(S)=5 THEN GOTO(A) r2: IF L(S)5 THEN GOTO(B) r3: IF L(S)5 THEN GOTO(C) r4: IF L(S)5 THEN GOTO(D) r5: IF L(S)C-D-E-B-A總距離為5+6+8+10+7=362 神州大學和東方大學兩校籃球隊在東方大學進行一場比賽，結(jié)局的比分是85：89，用語義網(wǎng)絡表示。第3部分 推理本章小結(jié)：自然演繹推理習題解答：1 張某被

5、盜，公安局派出五個偵察員去調(diào)查。研究案情時，偵察員A說“趙與錢中至少有一人作案”；偵察員B說“錢與孫中至少有一人作案”；偵察員C說“孫與李中至少有一人作案”；偵察員D說“趙與孫中至少有一人與此案無關”；偵察員E說“錢與李中至少有一人與此案無關”。如果這五個偵察員的話都是可信的，試用歸結(jié)演繹推理求出誰是盜竊犯。解：第一步：將5位偵察員的話表示成謂詞公式，為此先定義謂詞。設謂詞P(x)表示是作案者，所以根據(jù)題意：A: P(zhao) P(qian) B: P(qian) P(sun)C: P(sun) P(li) D: P(zhao) P(sun)E: P(qian) P(li)以上每個偵察員的話

6、都是一個子句。第二步：將待求解的問題表示成謂詞。設y是盜竊犯，則問題的謂詞公式為P(y)，將其否定并與ANSWER(y)做析?。篜(y) ANSWER(y)第三步：求前提條件及P(y) ANSWER(y)的子句集，并將各子句列表如下：（1） P(zhao) P(qian)（2） P(qian) P(sun)（3） P(sun) P(li)（4） P(zhao) P(sun)（5） P(qian) P(li)（6） P(y) ANSWER(y)第四步：應用歸結(jié)原理進行推理。（7） P(qian) P(sun) (1)與(4)歸結(jié)（8） P(zhao) P(li) (1)與(5)歸結(jié)（9） P(q

7、ian) P(zhao) (2)與(4)歸結(jié)（10） P(sun) P(li) (2)與(5)歸結(jié)（11） P(zhao) P(li) (3)與(4)歸結(jié)（12） P(sun) P(qian) (3)與(5)歸結(jié)（13） P(qian) (2)與(7)歸結(jié)（14） P(sun) (2)與(12)歸結(jié)（15） ANSWER(qian) (6)與(13)歸結(jié)，=qian/y（16） ANSWER(sun) (6)與(14)歸結(jié), =sun/y所以，本題的盜竊犯是兩個人：錢和孫。 2 任何兄弟都有同一個父親，John和Peter是兄弟，且John的父親是David，問Peter的父親是誰？解：第一步

8、：將已知條件用謂詞公式表示出來，并化成子句集。那么，要先定義謂詞。（1） 定義謂詞：設Father(x,y)表示x是y的父親。設Brother(x,y)表示x和y是兄弟。（2） 將已知事實用謂詞公式表示出來：F1: 任何兄弟都有同一個父親。( x)( y)( z)( Brother(x,y)Father(z,x)Father(z,y)F2: John和Peter是兄弟。Brother(John, Peter)F3: John的父親是David。Father(David, John)（3） 將它們化成子句集，得S1=Brother(x,y)Father(z,x)Father(z,y), Brot

9、her(John, Peter), Father(David, John)第二步：把問題用謂詞公式表示出來，并將其否定與謂詞ANSWER做析取。設Peter的父親是u，則有：Father(u, Peter)將其否定與ANSWER做析取，得G: Father(u, Peter) ANSWER(u)第三步：將上述公式G化為子句集S2，并將S1和S2合并到S。S2=Father(u, Peter) ANSWER(u)S=S1S2將S中各子句列出如下：（1）Brother(x,y)Father(z,x)Father(z,y)（2）Brother(John, Peter)（3）Father(David,

10、 John)（4）Father(u, Peter) ANSWER(u)第四步：應用歸結(jié)原理進行歸結(jié)。（5）Brother(John,y) Father(David,y) （1）與（3）歸結(jié)，= David/z, John/x（6）Brother(John, Peter) ANSWER(David) （4）與（5）歸結(jié)，= David/u, Peter/y（7）ANSWER(David) （2）與（6）歸結(jié)第五步：得到了歸結(jié)式ANSWER(David)，答案即在其中，所以u=David,即Peter的父親是David。第4部分 搜索策略本章小結(jié)：博弈問題：極大極小分析法：計算出端節(jié)點的估值，再推

11、算出父節(jié)點的得分。推算的方法是：對“或”節(jié)點，選其子節(jié)點中一個最大的得分作為父節(jié)點的得分，這是為了使自己在可供選擇的方案中選一個對自己最有利的方案；對“與”節(jié)點，選其子節(jié)點中一個最小的得分作為父節(jié)點的得分，這是為了立足于最壞的情況。這樣計算出的父節(jié)點的得分稱為倒推值。-剪枝技術：對于一個“與”節(jié)點來說，它取當前子節(jié)點中的最小倒推值作為它倒推值的上界，稱此值為值。對于一個“或”節(jié)點來說，它取當前子節(jié)點中的最大倒推值作為它倒推值的下界，稱此值為值。其一般規(guī)律為:（1）任何“或”節(jié)點x的值如果不能降低其父節(jié)點的值，則對節(jié)點x以下的分枝可停止搜索，并使x的倒推值為。這種剪枝成為剪枝。（2）任何“與”節(jié)

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

13、（隊列）步驟如下：圖4-3-1 圖4-3-2圖4-3-3圖4-3-4圖4-3-5所以，最優(yōu)路徑為A-C-D-E方法二：代價樹的深度優(yōu)先搜索（不一定是最優(yōu)解）（擴展節(jié)點，將其子節(jié)點按代價從小到大的順序放到open表的首部（棧）步驟如下：雖然D1的代價大于B1的代價，但按照代價樹的深度優(yōu)先搜索策略，要對D1進行擴展，放入closed表中（若按代價樹的廣度優(yōu)先搜索，要對B1、D1排序，先擴展B1）E為目標節(jié)點，E2-D1-C1-A所以路徑為A-注：該題代價樹的深度優(yōu)先搜索與代價樹的廣度優(yōu)先搜索的結(jié)果相同，但這只是巧合。一般情況下，這兩種方法得到的結(jié)果不一定相同。另外，由于代價樹的深度優(yōu)先搜索有可能進

14、入無窮分支的路徑，因此它是不完備的。如下圖-5所示，分別用代價樹的廣度優(yōu)先搜索策略和代價樹的深度優(yōu)先搜索策略，求A到E的最短費用路徑。圖解：先將其化成代價樹,如圖4-6：D1651C1D2E1C2E2B2E3E466577788圖4-6(1)代價樹的廣度優(yōu)先搜索,步驟如下：AB1C167圖4-7-1E為目標節(jié)點，路徑為A-C-E，代價為15。（2）代價樹的深度優(yōu)先搜索,步驟如下：B1C167D1A511圖4-8-2圖4-8-1雖然C1代價低于D1，但按照代價樹的深度優(yōu)先搜索策略，對D1進行擴展，放入closed表中，因為B1擴展的節(jié)點為D1，而C1是A節(jié)點擴展得到的。E出棧，為目標節(jié)點，結(jié)束。

15、故解路徑為A-B-D-E,代價為17，不是最優(yōu)解。注：深度優(yōu)先搜索是不完備的，即使問題有解，也不一定能求得解。得到的解也不一定是最優(yōu)解（因為是局部優(yōu)先搜索）。3 下圖是五城市間的交通費用圖，若從西安出發(fā)，要求把每個城市都訪問一遍，最后到達廣州，請找一條最優(yōu)路線。邊上的數(shù)字是兩城市間的交通費用。解：先畫出代價樹： 故由此得出最優(yōu)路線為A-B1-D2-C4-E12即A-B-D-C-E，交通費用為375。4 設有如圖所示的一棵與/或樹，請分別用與/或樹的廣度優(yōu)先搜索及與/或樹的深度優(yōu)先搜索求出解樹。解：（1）與/或樹的廣度優(yōu)先搜索先擴展節(jié)點A,得到節(jié)點B和C，再擴展節(jié)點B,得節(jié)點t1、t2，因為t1、t2為可解節(jié)點，故節(jié)點B可解，從而可節(jié)點