人工智能化習題集和各小結(jié)

人工智能各章小結(jié)及習題解答第一部分緒論習題解答：1.什么是人工智能？發(fā)展過程中經(jīng)歷了哪些階段?解：人工智能是計算機科學的一個重要分支，由計算機科學、控制論、信息論、神經(jīng)生理學、來的，目前正處于發(fā)展階段尚未形成完整體系。發(fā)展過程中經(jīng)歷的階段有：第一階段(40年代中?50年代末)第二階段(50年代中?60年代中)第三階段(60年代中?80年代初)第四階段(80年代中?90年代初)第五階段(90年代初?現(xiàn)在)也是一門正在發(fā)展中的綜合性前沿學科，它是哲學、語言學等多種學科相互滲透而發(fā)展起神經(jīng)元網(wǎng)絡(luò)時代通用方法時代知識工程時代新的神經(jīng)元網(wǎng)絡(luò)時代海量信息處理與網(wǎng)絡(luò)時代.人工智能研究的基本內(nèi)容是什么？解：基本內(nèi)容是：搜索技術(shù)、知識表示、規(guī)劃方法、機器學習、認知科學、自然語言理解與機器翻譯、專家系統(tǒng)與知識工程、定理證明、博弈、機器人、數(shù)據(jù)挖掘與知識發(fā)現(xiàn)、多Agent系統(tǒng)、復雜系統(tǒng)、足球機器人、人機交互技術(shù)等。.人工智能主要有哪幾大研究學派？解：(1)符號主義學派：由心理學途徑產(chǎn)生，符號主義認為人工智能起源于數(shù)理邏輯，人類認識(智能)的基本元素是符號，而智能行為則是符號運算的結(jié)果。(2)連接主義學派：由生理學途徑產(chǎn)生，連接主義又稱為仿生學派，認為人工智能的基本元素是神經(jīng)元，智能產(chǎn)生于大量神經(jīng)元的并行分布式聯(lián)結(jié)之中，而智能行為則是聯(lián)結(jié)計算的結(jié)果。(3)行為主義學派：由生物演化途徑產(chǎn)生，行為主義認為人工智能起源于控制論，提出智能取決于感知和行為，取決于對外界復雜環(huán)境的適應，而不是表示和推理。4.人工智能有哪些主要的研究領(lǐng)域?解：(1)問題求解(2)邏輯推理與定理證明(3)自然語言理解(4)自動程序設(shè)計(5)專家系統(tǒng)(6)機器學習(7)神經(jīng)網(wǎng)絡(luò)(8)機器人學(9)模式識別(10)機器視覺(11)智能控制

(12)智能檢索(13)智能調(diào)度與指揮(14)分布式人工智能與Agent(15)計算智能與進化計算(16)數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(17)人工生命(18)系統(tǒng)與語言工具第2部分知識與知識表示知識表不首先定義謂詞，指出每個謂詞的確切含義，然后再用連接詞把有關(guān)的謂詞知識表不首先定義謂詞，指出每個謂詞的確切含義，然后再用連接詞把有關(guān)的謂詞連接起來，出成一個謂詞公式表達一謂詛表73去個完整的意義。mmm■i-e4-immin?!■i-emit-en-i1^94■nti1mq1t-en-irmn4產(chǎn)生式系統(tǒng)由3個基本部分組成：規(guī)產(chǎn)生式表小法則庫、綜合數(shù)據(jù)庫、控制系統(tǒng)?？蚣芡ǔＳ芍付ㄊ挛锔鱾€方面的框木表小法——,1槽組成，每個槽擁有若寸個側(cè)面，而每個側(cè)面乂可擁有若寸個值。語義網(wǎng)絡(luò)表示法—語義網(wǎng)絡(luò)由節(jié)點和弧線或鏈線組成，下點用于表小物體、概危、和狀態(tài)，弧或用丁表小|」只問日勺關(guān)亦。1■串1l-Bm111■第4411■串11■甚河41IFST11■串S41+FW41HmTmST1IFS411■串11甚河41hB411■?■1習題解答：1設(shè)有如下問題：(1)有五個相互可直達且距離已知的城市A、RC、D、E,如圖所示;(2)某人從A地出發(fā)，去其它四個城市各參觀一次后回到A;(3)找一條最短的旅行路線請用產(chǎn)生式規(guī)則表示旅行過程。解：①綜合數(shù)據(jù)庫(x)(x)中x可以是一個字母，也可以是一個字符串。②初始狀態(tài)(A③目標狀態(tài)(Ax1x2x3x4A)④規(guī)則集：r1:IFL(S)=5THENGOTO(A)

r2:IFL(S)<5THENGOTO(B)r3:IFL(S)<5THENGOTO(C)r4:IFL(S)<5THENGOTO(D)r5:IFL(S)<5THENGOTO(E)其中L(S)為走過的城市數(shù)，GOTO(x)為走向城市x⑤路線如下圖所示：(ACDEBA)(ACDEBA)目標最短旅行路線為：A->C->D->E->B->A目標最短旅行路線為：A->C->D->E->B->A總距離為5+6+8+10+7=362神州大學和東方大學兩?；@球隊在東方大學進行一場比賽，結(jié)局的比分是義網(wǎng)絡(luò)表示。85:89,用語比賽是一種*85：89第3部分推理本章小結(jié):自然演繹推理推理經(jīng)典邏輯推理比賽是一種*85：89第3部分推理本章小結(jié):自然演繹推理推理經(jīng)典邏輯推理歸結(jié)演繹推理不確定與非單調(diào)推理習題解答：1張某被盜，公安局派出五個偵察員去調(diào)查。研究案情時，偵察員A說“趙與錢中至少有一人作案”；偵察員B說“錢與孫中至少有一人作案”；偵察員C說“孫與李中至少有一人作案”偵察員D說“趙與孫中至少有一人與此案無關(guān)”；偵察員E說“錢與李中至少有一人與此案無關(guān)”。如果這五個偵察員的話都是可信的，試用歸結(jié)演繹推理求出誰是盜竊犯。解：第一步：將5位偵察員的話表示成謂詞公式，為此先定義謂詞。設(shè)謂詞P(x)表示是作案者，所以根據(jù)題意：A:P(zhao)VP(qian)B:P(qian)VP(sun)

C:P(sun)VP(li)C:P(sun)VP(li)D:「P(zhao)V「P(sun)E:「P(qian)V「P(li)以上每個偵察員的話都是一個子句。第二步：將待求解的問題表示成謂詞。設(shè)y是盜竊犯，則問題的謂詞公式為P(y),將其否定并與ANSWER(那析取：ANSWER(y)的子句集，并將各子句列表如下:「P(y)VANSWER(y)的子句集，并將各子句列表如下:第三步：求前提條件及「P(y)V⑺P(qian)V「P(sun)(1)與⑺P(qian)V「P(sun)(1)與(4)歸結(jié)(8)P(zhao)V「P(li)(1)與(5)歸結(jié)(9)P(qian)V「P(zhao)(2)與(4)歸結(jié)(10)P(sun)V「P(li)(2)與(5)歸結(jié)(11)「P(zhao)VP(li)(3)與(4)歸結(jié)(12)P(sun)V「P(qian)(3)與(5)歸結(jié)(13)P(qian)(2)與⑺歸結(jié)(14)P(sun)(2)與(12)歸結(jié)(15)ANSWER(qian)(6)與(13)歸結(jié),(16)ANSWER(sun)(6)與(14)歸結(jié),(T(T所以，本題的盜竊犯是兩個人:錢和孫。={qian/y}={sun/y}P(zhao)VP(qian)P(qian)VP(sun)(3)P(sun)VP(li)(4)「P(zhao)V「P(sun)(5)「P(qian)V「P(li)(6)「P(y)VANSWER(y)第四步：應用歸結(jié)原理進行推理。2任何兄弟都有同一個父親，John和Peter是兄弟，且John的父親是David,問Peter的父親是誰？解：第一步：將已知條件用謂詞公式表示出來，并化成子句集。那么，要先定義謂詞。定義謂詞：設(shè)Father(x,y)表示x是y的父親。設(shè)Brother(x,y)表示x和y是兄弟。將已知事實用謂詞公式表示出來：F1:任何兄弟都有同一個父親。(幻(y)笛)(Brother(x,y)AFather(z,x)-Father(z,y))F2:John和Peter是兄弟。Brother(John,Peter)F3:John的父親是David。Father(David,John)將它們化成子句集，得S1={「Brother(x,y)V「Father(z,x)VFather(z,y),Brother(John,Peter),Father(David,John)}第二步：把問題用謂詞公式表示出來，并將其否定與謂詞ANSWER析取。設(shè)Peter的父親是u,貝U有：Father(u,Peter)將其否定與ANSWER析取，得G:「Father(u,Peter)VANSWER(u)第三步：將上述公式G化為子句集S2,并將S1和S2合并到SoS2={「Father(u,Peter)VANSWER(u)}S=S1US2將S中各子句列出如下：(1)「Brother(x,y)V「Father(z,x)VFather(z,y)Brother(John,Peter)Father(David,John)(4)「Father(u,Peter)VANSWER(u)第四步：應用歸結(jié)原理進行歸結(jié)。⑸「Brother(John,y)VFather(David,y)(1)與(3)歸結(jié)，0-={David/z,John/x}(6)「Brother(John,Peter)VANSWER(David)(4)與(5)歸結(jié),o-={David/u,Peter/y}(7)ANSWER(David)(2)與(6)歸結(jié)第五步：得到了歸結(jié)式ANSWER(David)答案即在其中，所以u=David,即Peter的父親是David。第4部分搜索策略本章小結(jié):

狀態(tài)空間搜索策略一盲目搜索_啟發(fā)式搜索—1廣度優(yōu)先搜索:1深度優(yōu)先搜索:1有界深度優(yōu)先搜索'i代價樹的廣度優(yōu)先搜索：1代價樹的深度優(yōu)先搜索;_局部擇優(yōu)搜索；1全局擇優(yōu)搜索■與/或樹-搜索策略一盲目搜索_「i—A*算法：廣度優(yōu)先搜索!1i1深度及有界深度優(yōu)先搜索i1|1|_啟序搜索；i:特殊情況;3111j提高搜索效率的方法」;-博弈問題防：i搜索策略博弈問題：極大極小分析法：計算出端節(jié)點的估值，再推算出父節(jié)點的得分。推算的方法是：對“或”節(jié)點，選其子節(jié)點中一個最大的得分作為父節(jié)點的得分，這是為了使自己在可供選擇的方案中選一個對自己最有利的方案；對“與”節(jié)點，選其子節(jié)點中一個最小的得分作為父節(jié)點的得分，這是為了立足于最壞的情況。這樣計算出的父節(jié)點的得分稱為倒推值。a-3剪枝技術(shù)：對于一個“與”節(jié)點來說，它取當前子節(jié)點中的最小倒推值作為它倒推值的上界，稱此值為3值。對于一個“或”節(jié)點來說，它取當前子節(jié)點中的最大倒推值作為它倒推值的下界，稱此值為a值。其一般規(guī)律為：（1）任何“或”節(jié)點X的a值如果不能降低其父節(jié)點的3值，則對節(jié)點X以下的分枝可停止搜索，并使X的倒推值為a。這種剪枝成為3剪枝。（2）任何“與”節(jié)點X的3值如果不能升高其父節(jié)點的a值，則對節(jié)點X以下的分枝可停止搜索，并使X的倒推值為3o這種剪枝成為a剪枝。習題解答：1圖4-1是五城市間的交通路線圖，A城市是出發(fā)地，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-2方法一：代價樹的廣度優(yōu)先搜索(擴展節(jié)點n,將其子節(jié)點放入open表中，計算各子節(jié)點的代價，并按各節(jié)點的代價對open表中全部節(jié)點按從小到大的順序進行排序(隊列))步驟如下：圖4-3-3圖4-3-4圖4-3-5所以，最優(yōu)路徑為A->C->D->E方法二：代價樹的深度優(yōu)先搜索（不一定是最優(yōu)解）open表的首部（棧））（擴展節(jié)點n,open表的首部（棧））雖然D1的代價大于B1的代價，但按照代價樹的深度優(yōu)先搜索策略，要對D1進行擴展,放入closed表中（若按代價樹的廣度優(yōu)先搜索，要對B1、D1排序，先擴展B1）E為目標節(jié)點，E2->D1->C1->A所以路徑為A->C->D->E注：該題代價樹的深度優(yōu)先搜索與代價樹的廣度優(yōu)先搜索的結(jié)果相同，但這只是巧合。一般情況下，這兩種方法得到的結(jié)果不一定相同。另外，由于代價樹的深度優(yōu)先搜索有可能進入無窮分支的路徑，因此它是不完備的。2如下圖4-5所示，分別用代價樹的廣度優(yōu)先搜索策略和代價樹的深度優(yōu)先搜索策略，求A到E的最短費用路徑。(解：先將其化成代價樹，8(1)代價樹的廣度優(yōu)先搜索6圖4-7-1圖4—5如圖4-6:◎產(chǎn)飛②&②圖4-6,步驟如下：15圖4-7-265圖4-7-3E為目標節(jié)點，路徑為A->C->E,代價為15。(2)代價樹的深度優(yōu)先搜索，步驟如下:圖4-8-1圖4-8-2圖4-8-1圖4-8-2雖然C1代價低于D1,但按照代價樹的深度優(yōu)先搜索策略，對D1進行擴展，放入closed表中，因為B1擴展的節(jié)點為D1,而C1是A節(jié)點擴展得到的。E出棧，為目標節(jié)點，結(jié)束。故解路徑為A->B->D->E,代價為17,不是最優(yōu)解。注：深度優(yōu)先搜索是不完備的，即使問題有解，也不一定能求得解。得到的解也不一定是最優(yōu)解(因為是局部優(yōu)先搜索)。3下圖是五城市間的交通費用圖，若從西安出發(fā)，要求把每個城市都訪問一遍，最后到達廣州，請找一條最優(yōu)路線。邊上的數(shù)字是兩城市間的交通費用。S0A西安上海S0A西安上海D解：先畫出代價樹:130A95120C1D1E117090707575130130E2B2D3B370C4E5E6D5E7B4E8E9B5E1016075170C2D29013070150130A95120C1D1E117090707575130130E2B2D3B370C4E5E6D5E7B4E8E9B5E1016075170C2D29013070150圖4-10按代價樹的廣度優(yōu)先搜索即可得出最優(yōu)路線，步驟如下:圖4-11-2250155240265225185圖4-11-3圖4-11-4A80E1C1D1150C2C3D2B2D3E3B3E215525(2619C4C5D4E5E6D5E7B4E8E9B5E10250355420340E419095380340285225340425300295365120225185240375圖4-11-5故由此得出最優(yōu)路線為A->B1->D2->C4->E12即A->B->D->C->E,交通費用為375。4設(shè)有如圖所示的一棵與/或樹，請分別用與/或樹的廣度優(yōu)先搜索及與/或樹的深度優(yōu)先搜索求出解樹。t3t4t3t4解：(1)與/或樹的廣度優(yōu)先搜索先擴展節(jié)點A,先擴展