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

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

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

3、) 行為主義學派：由生物演化途徑產(chǎn)生，行為主義認為人工智 能起源于操縱論，提出智能取決于感知和行為，取決于對外界復雜環(huán)境的 適應(yīng)，而不是表示和推理。4 .人工智能有哪些要緊的研究領(lǐng)域？ 解：(1)咨詢題求解(2) 邏輯推理與定理證明(3) 自然語言明白得(4) 自動程序設(shè)計(5) 專家系統(tǒng)(6) 機器學習(7) 神經(jīng)網(wǎng)絡(luò)(8) 機器人學(9) 模式識不(10) 機器視覺一_(丄1_)_智能操縱 dSd n n * n n d*- LSd n n n n du n n - LSd n n dSd n n du n n dsa 1i第一定義謂詞，指出每個謂詞的確切I I含義，然后再用連接詞把有關(guān)的

4、謂詞i I連接起來，形成一個謂詞公式表達一 I !個完整的意義。I_ d*B a a OKO a B*a nni-j t lui lab a a oko a B*a oea r lui baa a a oko a B*a u_u bad a a oko a ngjiiI產(chǎn)生式系統(tǒng)由3個差不多部分組成： 1規(guī)則庫、綜合數(shù)據(jù)庫、操縱系統(tǒng)。I I I I I h4 I I liBin I 4 I I I I I h4 I I liBin I 4 I F I I I I h4 I I I I F I I I I h4 i框架通常由指定事物各個方面的 I槽組成，每個槽擁有若干個側(cè)面， I而每個側(cè)面又可擁

5、有若干個值。(12 )智能檢索(13)智能調(diào)度與指揮(14 )分布式人工智能與謨示法JLE5) 運算智能與進化運算-(1i:知識表去1 (16) 數(shù)據(jù)挖掘與知識發(fā)覺表示法.7) 人工生命8) 系統(tǒng)與語言工具一、框架表示法!第2部分 知識與知識表麗義網(wǎng)絡(luò)表示法.本章小結(jié)：I語義網(wǎng)絡(luò)由節(jié)點和弧線或鏈線組成，I, I節(jié)點用于表示物體、概念和狀態(tài)，弧I I線用于表示節(jié)點間的關(guān)系。III I I I I I I I l-q-l II l-P-n I l-a-l I I -I I I “I II l-P-n I h-! I I -I I I h-! I im-l l I l I I I I I w*習題解

6、答：1設(shè)有如下咨詢題:（1）有五個相互可直達且距離已知的都市A、B、C、D、E,如圖所示；（2）（3）請用產(chǎn)生式規(guī)則表示旅行過程。解：綜合數(shù)據(jù)庫（x）起始（x）中x能夠是一個字 初始狀態(tài)aB k ； 目標狀態(tài)（Ax1x2x63 規(guī)則集：（a CBf （ a CD）r1： IF L（S）=5某人從A地動身，去其它四個都市各參觀一次后回到A；找一條最短的旅行路線(AD )AC JK(ace)THEN GOTO(A) tHeCDe ) GOTO(B) THEN 10 GOTO(C) THeN GOTO(D) (ACTHEN2 IFa cdB(S)5r3:r4:IFIFIFL(S)5L(S)5L(S)

7、C-D-E-B-AI 總距離為 5+6+8+10+7=36 客隊結(jié)w2神州大學和東方大學兩校籃球隊在東方大學 比分是85： 89,用語義85： 89進行一場競賽，結(jié)局的第3部分推理本章小結(jié):習題解答:不確定與非單調(diào)推理與/或形演繹推理1張某被盜，公安局派出五個偵察員去調(diào)查。研究案情時，偵察員A講“趙與鈔票中至少有一人作案”；偵察員B講“鈔票與孫中至少有一人作 案”；偵察員C講“孫與李中至少有一人作案”；偵察員D講“趙與孫中至 少有一人與此案無關(guān)”；偵察員E講“鈔票與李中至少有一人與此案無關(guān)” 如果這五個偵察員的話差不多上可信的，試用歸結(jié)演繹推理求出誰是盜竊 犯。解：第一步：將5位偵察員的話表示

8、成謂詞公式，為此先定義謂詞。 設(shè)謂詞P(x)表示是作案者，因此按照題意：P(zhao) V P(qian)P(sun) V P(li)A:C:B: P(qian) V P(sun)D:P(zhao) VP(sun)E:P(qian) V P(li)以上每個偵察員的話差不多上一個子句。第二步：將待求解的咨詢題表示成謂詞。設(shè)y是盜竊犯，則咨詢題的謂詞公式為P(y),將其否定并與ANSWER(y)做析取:P(y) V ANSWER(y)第三步：列表如下：求前提條件及P(y) V ANSWER(y)的子句集，并將各子句P (zhao)P(qia n)V P(qian)V P(sun)P(sun) V

9、P(li)P(zhao) VP(sun)P(qian) V P(li)P(y) V ANSWER(y)第四步：應(yīng)用歸結(jié)原理進行推理。P(qian) V P(sun) P(zhao) VP(li)P(qian) V P(zhao) P(su n) VP(li) P(zhao) V P(li) P(su n) VP (qia n) P(qian)P(sun) ANSWER(qian) ANSWER(sun)(1) 與(4)歸結(jié)(1) 與(5)歸結(jié)(2) 與(4)歸結(jié)(2) 與(5)歸結(jié)(3) 與(4)歸結(jié)(3) 與(5)歸結(jié)(2)與(7)歸結(jié)(2)與(12)歸結(jié)(6)與(13)歸結(jié)=qia n/y

10、(6)與(14)歸結(jié)，(T =sun/yJohn和Peter是兄弟，且John的父親是2 任何兄弟都有同一個父親，David，咨詢Peter的父親是誰？ 解：第一步：將已知條件用謂詞公式表示出來，并化成子句集。那么，要先定義謂詞。 定義謂詞：設(shè)Father(x,y)表示x是y的父親。 設(shè)Brother(x,y)表示x和y是兄弟。將已知事有用謂詞公式表示出來：F1: 任何兄弟都有同一個父親。(x)(y)( z)( Brother(x,y) A Father(z,x尸 Father(z,y)F2: John 和 Peter是兄弟。Brother(John, Peter)F3: John 的父親是

11、David。Father(David, John) 將它們化成子句集，得S1=Brother(x,y) Father(z,x)V Father(z,y), Brother(John, Peter), F ather(David, John)i第四步：應(yīng)用歸結(jié)原理進行歸結(jié)。V盲目搜索r(DaVd，有界深度優(yōu)先搜索i (5)BrotherQohn,y)I (1)與(嚴歸結(jié)空略-therQohn, Peter) V ANSWER(David)(6)Bro David/z,n/X價樹的廣度優(yōu)先搜索 代價樹的深度優(yōu)先搜索L啟發(fā)式搜索L局部擇優(yōu)搜索i_全局擇優(yōu)搜索5)歸結(jié)=呵第二步：把咨詢題用謂詞公式表示

12、出來，并將其否定與謂詞ANSWER做析取。設(shè) Peter的父親是 u,則有：Father(u, Peter)將其否定與ANSWER做析取，得G:Father(u, Peter) V ANSWER(u)第三步：將上述公式G化為子句集S2,并將S1和S2合并到S。S2=Father(u, Peter) V ANSWER(u)S=S1U S2將S中各子句列出如下:(1 )Brother(x,y) VFather(z,x)V Father(z,y) (2) Brother(John, Peter)廠(3)Father(DavidJohn)Father(u, Peter) V ANSWER(u)廣度優(yōu)先

13、搜索i_深度優(yōu)先搜索博弈咨詢vid/U搜索策略r/y:(7) ANS!第五步：得id,即Peter的父親-A*算法)與(6)歸結(jié)VER(David)到了歸結(jié)式 ANSWER(pav)廣度優(yōu)先搜索在其中，因此u=Dav :盲目搜(Dav總是與)或樹d。搜索策略1_深度及有界深度優(yōu)先搜索專門情形提升搜索效率的方法“ a-S剪枝技術(shù)r 0 IvaaTV”Tca.口Ivaa、T”TvaL/VkJj iI、博弈咨詢I有序搜索:第4部分搜索策略I!本章小結(jié)：極大極小分析法：運算出端節(jié)點的估值，再推算出父節(jié)點的得分。推算的方法是：對“或”節(jié)點，選其子節(jié)點中一個最大的得分作為父 節(jié)點的得分，這是為了使自己在可

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

15、，并使x的倒推值為P。這種剪枝成為枝。習地，用交通路線。圖4-1市間44曰E4都市間的交通路線圖 用(代，A都市是動身地，E都市是目的 價)如圖中數(shù)字所示。求從A到E的最小費解：先將交通圖轉(zhuǎn)換為代價樹，如圖4-2所示。若用g(x)表示從初始節(jié)點s0到節(jié)點x的代價，用c(x1,x2)表示從父節(jié) 點x1到子節(jié)點x2的代價，則有：g(x2)=g(x1)+c(x1,x2)圖4-1圖4-2E1方法一：代價樹的廣度優(yōu)先搜索 （擴展節(jié) 按各節(jié)點的代價對步驟如下：open表中，運算各子節(jié)點的代價，并）將其子節(jié)點放入en表中全部節(jié)點按從小到大的順序進行排序（隊列）圖 4-3-1-49因此,最優(yōu)路徑為A-C-D-

16、EC13A圖 4-3-4 A方法二：代價樹的深度優(yōu)先搜索（不一定是最優(yōu)解）展節(jié)點為，將其子節(jié)點按代價從小到大的順序放到open表的首部（棧% B14B2A9C13圖 4-4-2圖 4-4-34如下：圖 4-4-1E為目標節(jié)點E2-D1-C1-A管 D1的代價大于B1的代價，但按照代價、八、樹的深度優(yōu)先搜索策略，要對 D1進行擴展,因此路徑為A- C - D- E 放入closed表中（若按代價樹的廣度優(yōu)先搜索，要對B1、D1排序，先擴展B1）注：該題代價樹的深度優(yōu)先搜索與代價樹的廣度優(yōu)先搜索的結(jié)果相同, 但這只是巧合。一樣情形下，這兩種方法得到的結(jié)果不一定相同。另外，6A由于代價樹的深度優(yōu)先搜

17、索有可能進 的。7C1C2求A到E的最短費用84 57 疋2 如下圖4 -5 深度優(yōu)先搜索策略D2D52窮分支的路徑，因此它是不完備優(yōu)先搜索策略和代價樹的(1)代價樹的廣度優(yōu)先搜索，步驟如下:76 711圖 4-7-35 E為目標節(jié)點，路徑為A-C-E，代價為15。（2）代價樹的深度優(yōu)先搜索，步驟如下:八75(DD1111圖 4-8-1圖 4-8-2盡管C1代價低于D1，但按照代價樹的深度優(yōu)先搜索策略， 對D1進行 擴展，放入closed表中，因為B1擴展的節(jié)點為D1,而C1是A節(jié)點擴展 得到的。E出棧，為目標節(jié)點，終止。故解路徑為 A-B-D-E，代價為17, 不是最優(yōu)解。注：深度優(yōu)先搜索是

18、不完備的，即使咨詢題有解，也不一定能求得解。 得到的解也不一定是最優(yōu)解（因為是局部優(yōu)先搜索）。75 -E10 1.E12)(已Sg70 a(C3 11，( E4 j* 丿 /A17西安sof C2130、/901301 7汛/160!170上海D75、16075 y解：先畫出代價樹:250D3 j ( E3 I. if B3 j門70 門130E16-圖 4-10A D1 1 、120索即可得出最優(yōu)路線,圖 4-11-1120、J步驟如下:E1150 丿1 )150jh155240圖 4-11-2圖 4-11-37 D1 1八120kJ/B3匕 、)嚴4 J 汽 C3 ) / E4 )1950 25019