人工智能課程習(xí)題與部分解答

《人工智能》課程習(xí)題與局部解答第1章緒論1.1什么是人工智能?它的研究目標(biāo)是什么?1.2什么是圖靈測試?簡述圖靈測試的根本過程及其重要特征.1.3在人工智能的開展過程中，有哪些思想和思潮起了重要作用？1.5在人工智能的開展過程中，有哪些思想和思潮起了重要作用？1.7人工智能的主要研究和應(yīng)用領(lǐng)域是什么？其中，哪些是新的研究熱點(diǎn)？第2章知識表示方法2.1什么是知識？分類情況如何？2.2什么是知識表示？不同的知識表示方法各有什么優(yōu)缺點(diǎn)?2.4人工智能對知識表示有什么要求?2.5用謂詞公式表示以下規(guī)那么性知識：自然數(shù)都是大于零的整數(shù)。任何人都會(huì)死的。[解]定義謂詞如下:N(x):“x是自然數(shù)”,I(x):“x是整數(shù)”,L(x):“x大于0”,D(x):“x會(huì)死的”,M(x):“x是人”2.6用謂詞公式表示以下事實(shí)性知識：小明是計(jì)算機(jī)系的學(xué)生，但他不喜歡編程。李曉新比他父親長得高。2.8產(chǎn)生式系統(tǒng)由哪幾個(gè)局部組成?它們各自的作用是什么?2.9可以從哪些角度對產(chǎn)生式系統(tǒng)進(jìn)行分類?闡述各類產(chǎn)生式系統(tǒng)的特點(diǎn)。2.10簡述產(chǎn)生式系統(tǒng)的優(yōu)缺點(diǎn)。2.11簡述框架表示的根本構(gòu)成，并給出框架的一般結(jié)構(gòu)2.12框架表示法有什么特點(diǎn)？2.13試構(gòu)造一個(gè)描述你的臥室的框架系統(tǒng)。2.14試描述一個(gè)具體的大學(xué)教師的框架系統(tǒng)。[解]一個(gè)具體大學(xué)教師的框架系統(tǒng)為：框架名：<教師-1>類屬：<大學(xué)教師>姓名：張宇性別：男年齡：32職業(yè)：<教師>職稱：副教授部門：計(jì)算機(jī)系研究方向：計(jì)算機(jī)軟件與理論工作：參加時(shí)間：2000年7月工齡：當(dāng)前年份-2000工資：<工資單>2.16把以下命題用一個(gè)語義網(wǎng)絡(luò)表示出來(1)樹和草都是植物；(2)樹和草都是有根有葉的；(3)水草是草，且生長在水中；(4)果樹是樹，且會(huì)結(jié)果；(5)蘋果樹是果樹的一種，它結(jié)蘋果。[解]植物植物AKOAKOAKOAKOHAVEHAVEHAVEHAVE有根有葉草樹有根有葉草樹AKOAKOAKOAKO水草果樹水草果樹AKOLocateatAKOLocateat蘋果樹水蘋果樹水HAVEHAVE蘋果蘋果2.17在基于語義網(wǎng)絡(luò)的推理系統(tǒng)中，一般有幾種推理方法，簡述它們的推理過程。2.18簡述語義網(wǎng)絡(luò)中常用的語義聯(lián)系。2.19用一個(gè)語義網(wǎng)絡(luò)表示：“我的汽車是棕黃色的”“李華的汽車是綠色的”[解]參考課件。2.10用語義網(wǎng)絡(luò)和框架方法表示以下知識：JohngivesabooktoMary[解]參考課件。第3章搜索推理技術(shù)3.1在人工智能中，搜索問題一般包括哪兩個(gè)重要問題?3.2簡述搜索策略的評價(jià)標(biāo)準(zhǔn)。3.3比擬盲目搜索中各種方法的優(yōu)缺點(diǎn)。試用寬度優(yōu)先搜索策略，畫出搜索樹、找出最優(yōu)搜索路線。[解]〔1〕搜索樹參考課件。〔2〕最優(yōu)搜索路線：S0→S1→S5→S10.3.5對于八數(shù)碼問題，設(shè)初始狀態(tài)和目標(biāo)狀態(tài)如圖3.2所示：S1=283Sg=1231648475765圖3.2八數(shù)碼問題試給出深度優(yōu)先〔深度限制為5〕和寬度優(yōu)先狀態(tài)圖。[解](1)深度優(yōu)先〔深度限制為5〕狀態(tài)圖為(2)寬度優(yōu)先狀態(tài)圖為3.6什么是啟發(fā)式搜索?其中什么是評估函數(shù)?其主要作用是什么?3.7最好優(yōu)先的根本思想是什么?有什么優(yōu)缺點(diǎn)?3.8對于八數(shù)碼問題，設(shè)初始狀態(tài)和目標(biāo)狀態(tài)如圖3.2所示。設(shè)d(x)表示節(jié)點(diǎn)x在搜索樹中的深度，評估函數(shù)為f(x)=d(x)+w(x)，其中w(x)為啟發(fā)式函數(shù)。試按以下要求給出八數(shù)碼問題的搜索圖，并說明滿是一種A*算法，找出對應(yīng)的最優(yōu)搜索路徑?！?〕w(x)=h(x)表示節(jié)點(diǎn)x中不在目標(biāo)狀態(tài)中相應(yīng)位置的數(shù)碼個(gè)數(shù)；〔2〕w(x)=p(x)表示節(jié)點(diǎn)x的每一數(shù)碼與其目標(biāo)位置之間的距離總和?！?〕w(x)=0，情況又如何？[解](1)8數(shù)碼的搜索過程如下圖：在上面確定h(x)時(shí)，盡管并不知道h*(x)具體為多少，但當(dāng)采用單位代價(jià)時(shí)，通過對不在目標(biāo)狀態(tài)中相應(yīng)位置的數(shù)碼個(gè)數(shù)的估計(jì)，可以得出至少需要移動(dòng)h(x)步才能夠到達(dá)目標(biāo)，顯然h(x)≤h*(x)。因此它滿足A*算法的要求。最優(yōu)搜索路徑:如圖粗線所示。(2)此時(shí)8數(shù)碼搜索圖可表示為：這時(shí)，顯然有h(x)≤p(x)≤h*(n)，相應(yīng)的搜索過程也是A*算法。然而，p(x)比h(n)有更強(qiáng)的啟發(fā)式信息，由w(x)=p(x)構(gòu)造的啟發(fā)式搜索樹，比w(x)=h(x)構(gòu)造的啟發(fā)式搜索樹節(jié)點(diǎn)數(shù)要少?！?〕假設(shè)w(x)=0，該問題就變?yōu)閷挾葍?yōu)先搜索問題。3.9如圖3.3所示，是5個(gè)城市之間的交通路線圖，A城市是出發(fā)地，E城市是目的地，兩城市之間的交通費(fèi)用〔代價(jià)〕如圖中的數(shù)字，求從A到E的最小費(fèi)用交通路線。335ACDEB3424圖3.3旅行交通圖此題是考察代價(jià)樹搜索的根本概念，了解這種搜索方法與深度優(yōu)先和寬度優(yōu)先的不同。首先將旅行交通圖轉(zhuǎn)換為代價(jià)樹如圖3.4所示。圖3.4交通圖的代價(jià)樹(1)如果一個(gè)節(jié)點(diǎn)已經(jīng)成為某各節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，那么它就不能再作為該節(jié)點(diǎn)的后繼節(jié)點(diǎn)。例如節(jié)點(diǎn)B相鄰的節(jié)點(diǎn)有A和D，但由于在代價(jià)樹中，A已經(jīng)作為B的前驅(qū)節(jié)點(diǎn)出現(xiàn)，那么它就不再作為B的后繼節(jié)點(diǎn)。(2)除了初始節(jié)點(diǎn)A外，其它節(jié)點(diǎn)都有可能在代價(jià)樹中屢次出現(xiàn)，為了區(qū)分它們的屢次出現(xiàn)，分別用下標(biāo)1、2、3…標(biāo)出，但它們都是圖中同一節(jié)點(diǎn)。例如C1和C2都代表圖中節(jié)點(diǎn)C。對上面所示的代價(jià)樹做寬度優(yōu)先搜索，可得到最優(yōu)解為：A→C1→D1→E2代價(jià)為8。由此可見，從A城市到E城市的最小費(fèi)用路線為：A→C→D→E如果采用代價(jià)樹的深度優(yōu)先搜索，也會(huì)得到同樣的結(jié)果：A→C→D→E但注意：這只是一種巧合，一般情況下，這兩種方法得到的結(jié)果不一定相同。再者，代價(jià)樹的深度優(yōu)先搜索可能進(jìn)入無窮分支路徑，因此也是不完備的。3.10對于圖3.4所示的狀態(tài)空間圖，假設(shè)U是目標(biāo)狀態(tài)，試給出寬度優(yōu)先搜索與深度優(yōu)搜索的OPEN表和CLOSED表的變化情況。圖3.5狀態(tài)空間圖[解]寬度優(yōu)先搜索的OPEN表和CLOSED表的變化情況：1.OPEN=[A];CLOSED=[]2.OPEN=[B,C,D];CLOSED=[A]3.OPEN=[C,D,E,F];CLOSED=[B,A]4.OPEN=[D,E,F,G,H];CLOSED=[C,B,A]5.OPEN=[E,F,G,H,I,J];CLOSED=[D,C,B,A]6.OPEN=[F,G,H,I,J,K,L];CLOSED=[E,D,C,B,A]7.OPEN=[G,H,I,J,K,L,M]〔由于L已在OPEN中〕;CLOSED=[F,E,D,C,B,A]8.OPEN=[H,I,J,K,L,M,N];CLOSED=[G,F,E,D,C,B,A]9.以此類推，直到找到了U或OPEN=[]。深度優(yōu)先搜索的OPEN表和CLOSED表的變化情況：1.OPEN=[A];CLOSED=[]2.OPEN=[B,C,D];CLOSED=[A]3.OPEN=[E,F,C,D];CLOSED=[B,A]4.OPEN=[K,L,F,C,D];CLOSED=[E,B,A]5.OPEN=[S,L,F,C,D];CLOSED=[K,E,B,A]6.OPEN=[L,F,C,D];CLOSED=[S,K,E,B,A]7.OPEN=[T,F,C,D];CLOSED=[L,S,K,E,B,A]8.OPEN=[F,C,D];CLOSED=[T,L,S,K,E,B,A]9.OPEN=[M,C,D]〔由于L已經(jīng)在CLOSED中;CLOSED=[F,T,L,S,K,E,B,A]10.OPEN=[C,D];CLOSED=[M,F,T,L,S,K,E,B,A]11.OPEN=[G,H,D];CLOSED=[C,M,F,T,L,S,K,E,B,A]12.以此類推，直到找到了U或OPEN=[]。第4章自動(dòng)推理4.1什么是推理的控制策略？有哪幾種主要的推理驅(qū)動(dòng)模式？4.2自然演繹推理的根本概念與根本的推理規(guī)那么。4.3什么是合取范式?什么是析取范式?什么是Skolem標(biāo)準(zhǔn)化?如何將一個(gè)公式化為這些形式?4.4將以下公式化為Skolem標(biāo)準(zhǔn)型:[解]在公式中，的前面沒有全稱量詞，的前面有全稱量詞和,在的前面有全稱量詞,和。所以，在中，用常數(shù)a代替x,用二元函數(shù)f(y,z)代替u,用三元函數(shù)g(y,z,v)代替w,去掉前綴中的所有存在量詞之后得出Skolem標(biāo)準(zhǔn)型：4.5化為子句形有哪些步驟?[解](1)利用等價(jià)謂詞關(guān)系消去謂詞公式中的蘊(yùn)涵符“→”和雙條件符“←→”。(2)利用等價(jià)關(guān)系把否認(rèn)符號“┐”移到緊靠謂詞的位置上。(3)重新命名變元名，使不同量詞約束的變元有不同的名字。(4)消去存在量詞。(5)將公式化為前束形。(6)把公式化為Skolem標(biāo)準(zhǔn)形。(7)消去全稱量詞。(8)消去合取詞。(9)對變元更名，使不同子句中的變元不同名。4.6將以下謂詞公式化為子句集:(1)(x)[~P(x)~Q(x)]→(y)[S(x,y)Q(x)](x)[P(x)B(x)](2)[解](1)轉(zhuǎn)換過程遵照以下9個(gè)步驟依此為:A.消去蘊(yùn)涵符符號：B.減少否認(rèn)符號的轄域：C.變量標(biāo)準(zhǔn)化：D.消去存在量詞：E.化為前束型：F.把母式化為合取范式：G.消去全稱量詞：H.消去合取詞：I.子句變量標(biāo)準(zhǔn)化后,最終的子句集為：(2)參見課本P122A.消去蘊(yùn)涵符符號：B.減少否認(rèn)符號的轄域:C.變量標(biāo)準(zhǔn)化:D.消去存在量詞:E.化為前束型:F.把母式化為合取范式:G.消去全稱量詞:H.消去合取詞:I.更改變量名:4.7把下面的表達(dá)式轉(zhuǎn)化成子句形式〔1〕〔2〕〔3〕[解](1)那么子句集為(2)那么子句集為(3)那么子句集為4.10求證G是F1和F2的邏輯結(jié)論。[證明]首先將和化為子句集：F1：所以F2：所以所以下面進(jìn)行歸結(jié)：①②③④R(b)⑤Q(b)⑥L(a,b)③和④⑦①和②⑧⑤和⑦⑨Nil⑥和⑧所以，G是F1,F2的邏輯結(jié)論。4.12利用歸結(jié)原理證明：“有些患者喜歡任一醫(yī)生。沒有任一患者喜歡任一庸醫(yī)。所以沒有庸醫(yī)的醫(yī)生”。[解]定義謂詞為:P(x):“x是患者”,D(x):“x是醫(yī)生”,Q(x):“x是庸醫(yī)”,L(x,y):“x喜歡y”,那么前提與結(jié)論可以符號化為:A1:A2:G:目前是證明G是A1和A2的邏輯結(jié)論,即證明是不可滿足的.首先,求出子句集合:A1:A2::因此的子句集合S為:歸結(jié)證明S是不可滿足的:S(2)(4)(1)(3)(5)(7)(9)Nil(6)(8)4.14：能閱讀的都是有文化的；海豚是沒有文化的；某些海豚是有智能的；用歸結(jié)反演法證明：某些有智能的并不能閱讀。[證明]首先定義謂詞:R(x):x能閱讀,L(x):x有文化D(x):x是海豚,I(x):x有智能將前提形式化地表示為:A1:A2:A3:將結(jié)論形式化地表示為:G:即要證明為真.即證明是不可滿足的.把它化為子句集為:現(xiàn)在用歸結(jié)證明S是不可滿足的:S(4)(5)(1)(6)(2)(7)(9)Nil(3)(8)4.15某人被盜，公安局派出所派出5個(gè)偵察員去調(diào)查。研究案情時(shí):偵察員A說：“趙與錢中至少有一人作案”；偵察員B說：“錢與孫中至少有一人作案”；偵察員C說：“孫與李中至少有一人作案”；偵察員D說：“趙與孫中至少有一人與此案無關(guān)”；偵察員E說：“錢與李中至少有一人與此案無關(guān)”。如果這5個(gè)偵察員的話都是可信的，試問誰是盜竊犯呢？[解]第一步:設(shè)謂詞P(x)表示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è)偵查員的話都是一個(gè)子句。第二步：將待求解的問題表示成謂詞。設(shè)y是盜竊犯，那么問題的謂詞公式為P(y),將其否認(rèn)并與ANS(y)做析取得:~P(y)∨ANS(y)第三步:求前提條件及~P(y)∨ANS(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)∨ANS(y)第四步：應(yīng)用歸結(jié)原理進(jìn)行推理。(7)P(qian)∨~P(sun)(1)與(4)歸結(jié)(8)P(zhao)∨~P(li)(1)與(5)歸結(jié)(9)P(qian)∨~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)ANS(qian)(6)與(13)歸結(jié)(16)ANS(sun)(6)與(14)歸結(jié)所以，此題的盜竊犯是兩個(gè)人:錢和孫。4.16：張和李是同班同學(xué)，如果x和y是同班同學(xué)，那么x的教室也是y的教室?，F(xiàn)在張?jiān)贘1-3上課，問李在哪里上課？[解]首先定義謂詞：C(x,y):x和y是同學(xué)At(x,u):x在u教室上課那么前提可表示為C(Zhang,Li)At(Zhang,J1-3)將目標(biāo)表示成謂詞:典At(Li,v)，采用重言式，得到子句集合S為：歸結(jié)過程如下：(5)(2)(4)歸結(jié){Li|y,v|u}(6)(1)(5)歸結(jié){Zhang|x}(7)(3)(6)歸結(jié){J1-3|v}最后就是所得到的答案：李在J1-3上課。第5章不確定性推理5.1什么是不確定性推理?不確定性推理的根本問題是什么?5.2在主觀Bayes方法中，如何引入規(guī)那么的強(qiáng)度的似然率來計(jì)算條件概率?這種方法優(yōu)點(diǎn)是什么？主觀Bayes方法有什么問題？試說明LS和LN的意義。5.3設(shè)有規(guī)那么：R1:IFE1THEN(20,1)HR2:IFE2THEN(300,1)H證據(jù)E1和E2必然發(fā)生，并且P(H)=0.03，求H的后驗(yàn)概率。[解]因?yàn)镻(H)=0.03,那么O(H)=0.03/(1-0.03)=0.030927根據(jù)R1有O(H|E1)=LS1×O(H)=20×0.030927=0.6185根據(jù)R2有O(H|E2)=LS2×O(H)=300×0.030927=9.2781那么所以H的后驗(yàn)概率為5.4設(shè)有規(guī)那么：R1:IFE1THEN(65,0.01)HR2:IFE2THEN(300,0.0001)H:P(E1|S1)=0.5,P(E2|S2)=0.02,P(H)=0.01,P(E1)=0.1,P(E2)=0.03求:P(H|S1S2)[解]根據(jù)R1，因?yàn)镻(E1|S1)=0.5>P(E1)=0.1，那么有根據(jù)R2，因?yàn)镻(E2|S2)=0.02<P(E2)=0.03，那么有根據(jù)上面的計(jì)算，因?yàn)椋耗敲从?.5何謂可信度？簡述可信度模型及其各局部含義。5.6設(shè)有如下規(guī)那么：R1:IFE1THENH(0.9)R2:IFE2THENH(0.6)R3:IFE3THENH(-0.5)R4:IFE4AND(E5ORE6)THENE1(0.8)CF(E2)=0.8,CF(E3)=0.6,CF(E4)=0.5,CF(E5)=0.6,CF(E6)=0.8,求CF(H)=?[解]由R4得到:CF(E1)=0.8×max{0,CF(E4AND(E5ORE6))=0.8×max{0,min{CF(E4),CF(E5ORE6)}}=0.8×max{0,min{CF(E4),max{CF(E5),CF(E6)}}=0.8×max{0,min{0.5,0.8}}=0.8×max{0,0.5}=0.4由R1得到:CF1(H)=CF(H,E1)×max{0,CF(E1)}=0.9×max{0,0.4}=0.36由R2得到:CF2(H)=CF(H,E2)×max{0,CF(E2)}=0.6×max{0,0.8}=0.48由R3得到:CF3(H)=CF(H,E3)×max{0,CF(E3)}=-0.5×max{0,0.6}=-0.3根據(jù)結(jié)論不確定性的合成算法得到:CF1,2(H)=CF1(H)+CF2(H)-CF1(H)×CF2×0.48=0.67CF1,2,3(H)=CF1,2(H)+CF3(H)=0.67+(-0.3)=0.47或者5.7設(shè)有如下規(guī)那么：R1:IFE1THENH(0.8)R2:IFE2THENH(0.6)R3:IFE3THENH(-0.5)R4:IFE4AND(E5ORE6)THENE1(0.7)R5:IFE7ANDE8THENE3(0.9)在系統(tǒng)運(yùn)行中已從用戶處得CF(E2)=0.8,CF(E4)=0.5,CF(E5)=0.6,CF(E6)=0.7,CF(E7)=0.6,CF(E8)=0.9,求H的綜合可信度CF(H)。[解](1)求證據(jù)E4,E5,E6邏輯組合的可信度(2)根據(jù)規(guī)那么R4,求CF(E1)(3)求證據(jù)E7,E8邏輯組合的可信度(4)根據(jù)規(guī)那么R5,求CF(E3)(5)根據(jù)規(guī)那么R1,求CF1(H)(6)根據(jù)規(guī)那么R2,求CF2(H)(7)根據(jù)規(guī)那么R3,求CF3(H)(8)組合由獨(dú)立證據(jù)導(dǎo)出的假設(shè)H的可信度CF1(H),CF2(H)和CF3(H),得到H的綜合可信度:或者5.8設(shè)有如下規(guī)那么：R1:A1→B1CF(B1,A1)=0.8R2:A2→B1CF(B1,A2)=0.5R3:B1∧A3→B2CF(B2,B1∧A3)=0.8初始證據(jù)A1,A2,A3的CF值均設(shè)為1，而初始未知證據(jù)B1,B2的CF值均為0，即對B1,B2一無所知。求CF(B1),CF(B2)的更新值。[解](1)對知識R1,R2，分別計(jì)算CF(B1)。CF1(B1)=CF(B1,A1)×max{0,CF(A1)}=0.8×1=0.8CF2(B1)=CF(B1,A2)×max{0,CF(A2)}=0.5×1=0.5(2)計(jì)算B1的綜合可信度。CF1,2(B1)=CF1(B1)+CF2(B1)-CF1(B1)×CF2(B1)×0.5=0.9(3)計(jì)算B2的可信度CF(B2)。這時(shí)，B1作為B2的證據(jù)，其可信度已有前面計(jì)算出來，而A3的可信度為初始指定的1。由規(guī)那么R3得到CF(B2)=CF(B2,B1∧A3)×max{0,CF(B1∧A3)}=CF(B2,