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

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

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

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

4、短的旅行路線請(qǐng)用產(chǎn)生式規(guī)則表示旅行過(guò)程。解：綜合數(shù)據(jù)庫(kù)（x）(x)中x可以是一個(gè)字母，也可以是一個(gè)字符串。初始狀態(tài)（A）目標(biāo)狀態(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 神州大學(xué)和東方大學(xué)兩?；@球隊(duì)在東方大學(xué)進(jìn)行一場(chǎng)比賽，結(jié)局的比分是85：89，用語(yǔ)義網(wǎng)絡(luò)表示。第3部分 推理本章小結(jié)：自然演繹推理習(xí)題解答：1 張某被

5、盜，公安局派出五個(gè)偵察員去調(diào)查。研究案情時(shí)，偵察員A說(shuō)“趙與錢(qián)中至少有一人作案”；偵察員B說(shuō)“錢(qián)與孫中至少有一人作案”；偵察員C說(shuō)“孫與李中至少有一人作案”；偵察員D說(shuō)“趙與孫中至少有一人與此案無(wú)關(guān)”；偵察員E說(shuō)“錢(qián)與李中至少有一人與此案無(wú)關(guān)”。如果這五個(gè)偵察員的話都是可信的，試用歸結(jié)演繹推理求出誰(shuí)是盜竊犯。解：第一步：將5位偵察員的話表示成謂詞公式，為此先定義謂詞。設(shè)謂詞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)以上每個(gè)偵察員的話

6、都是一個(gè)子句。第二步：將待求解的問(wèn)題表示成謂詞。設(shè)y是盜竊犯，則問(wèn)題的謂詞公式為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)第四步：應(yīng)用歸結(jié)原理進(jìn)行推理。（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所以，本題的盜竊犯是兩個(gè)人：錢(qián)和孫。 2 任何兄弟都有同一個(gè)父親，John和Peter是兄弟，且John的父親是David，問(wèn)Peter的父親是誰(shuí)？解：第一步

8、：將已知條件用謂詞公式表示出來(lái)，并化成子句集。那么，要先定義謂詞。（1） 定義謂詞：設(shè)Father(x,y)表示x是y的父親。設(shè)Brother(x,y)表示x和y是兄弟。（2） 將已知事實(shí)用謂詞公式表示出來(lái)：F1: 任何兄弟都有同一個(gè)父親。( 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)第二步：把問(wèn)題用謂詞公式表示出來(lái)，并將其否定與謂詞ANSWER做析取。設(shè)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)第四步：應(yīng)用歸結(jié)原理進(jìn)行歸結(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(píng)=David,即Peter的父親是David。第4部分 搜索策略本章小結(jié)：博弈問(wèn)題：極大極小分析法：計(jì)算出端節(jié)點(diǎn)的估值，再推

11、算出父節(jié)點(diǎn)的得分。推算的方法是：對(duì)“或”節(jié)點(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)的得分稱(chēng)為倒推值。-剪枝技術(shù)：對(duì)于一個(gè)“與”節(jié)點(diǎn)來(lái)說(shuō)，它取當(dāng)前子節(jié)點(diǎn)中的最小倒推值作為它倒推值的上界，稱(chēng)此值為值。對(duì)于一個(gè)“或”節(jié)點(diǎn)來(lái)說(shuō)，它取當(dāng)前子節(jié)點(diǎn)中的最大倒推值作為它倒推值的下界，稱(chēng)此值為值。其一般規(guī)律為:（1）任何“或”節(jié)點(diǎn)x的值如果不能降低其父節(jié)點(diǎn)的值，則對(duì)節(jié)點(diǎn)x以下的分枝可停止搜索，并使x的倒推值為。這種剪枝成為剪枝。（2）任何“與”節(jié)

12、點(diǎn)x的值如果不能升高其父節(jié)點(diǎn)的值，則對(duì)節(jié)點(diǎn)x以下的分枝可停止搜索，并使x的倒推值為。這種剪枝成為剪枝。習(xí)題解答:1 圖4-1是五城市間的交通路線圖，A城市是出發(fā)地，E城市是目的地，兩城市間的交通費(fèi)用（代價(jià)）如圖中數(shù)字所示。求從A到E的最小費(fèi)用交通路線。圖4-1解：先將交通圖轉(zhuǎn)換為代價(jià)樹(shù)，如圖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à)樹(shù)的廣度優(yōu)先搜索（擴(kuò)展節(jié)點(diǎn)，將其子節(jié)點(diǎn)放入open表中，計(jì)算各子節(jié)點(diǎn)的代價(jià)，并按各節(jié)點(diǎn)的代價(jià)對(duì)open表中全部節(jié)點(diǎn)按從小到大的順序進(jìn)行排序

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

14、入無(wú)窮分支的路徑，因此它是不完備的。如下圖-5所示，分別用代價(jià)樹(shù)的廣度優(yōu)先搜索策略和代價(jià)樹(shù)的深度優(yōu)先搜索策略，求A到E的最短費(fèi)用路徑。圖解：先將其化成代價(jià)樹(shù),如圖4-6：D1651C1D2E1C2E2B2E3E466577788圖4-6(1)代價(jià)樹(shù)的廣度優(yōu)先搜索,步驟如下：AB1C167圖4-7-1E為目標(biāo)節(jié)點(diǎn)，路徑為A-C-E，代價(jià)為15。（2）代價(jià)樹(shù)的深度優(yōu)先搜索,步驟如下：B1C167D1A511圖4-8-2圖4-8-1雖然C1代價(jià)低于D1，但按照代價(jià)樹(shù)的深度優(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é)束。

15、故解路徑為A-B-D-E,代價(jià)為17，不是最優(yōu)解。注：深度優(yōu)先搜索是不完備的，即使問(wèn)題有解，也不一定能求得解。得到的解也不一定是最優(yōu)解（因?yàn)槭蔷植績(jī)?yōu)先搜索）。3 下圖是五城市間的交通費(fèi)用圖，若從西安出發(fā)，要求把每個(gè)城市都訪問(wèn)一遍，最后到達(dá)廣州，請(qǐng)找一條最優(yōu)路線。邊上的數(shù)字是兩城市間的交通費(fèi)用。解：先畫(huà)出代價(jià)樹(shù)： 故由此得出最優(yōu)路線為A-B1-D2-C4-E12即A-B-D-C-E，交通費(fèi)用為375。4 設(shè)有如圖所示的一棵與/或樹(shù)，請(qǐng)分別用與/或樹(shù)的廣度優(yōu)先搜索及與/或樹(shù)的深度優(yōu)先搜索求出解樹(shù)。解：（1）與/或樹(shù)的廣度優(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)