人工智能期末試題

1、2.證明G是否為,，的邏輯結(jié)論。：G：2.先把G否定，并放入F中，得到的F1,F2, ¬G為，¬（）再把F1,F2, ¬G化為子句集，得到其中是由F1化為的兩個子句，是由F2化為的兩個子句，是由G化為的子句。由子句集可以看出只有唯一的一個Q因此可以得出G不是F的邏輯結(jié)構(gòu)。3.假設張被盜，公安局派出5人去調(diào)查。案情分析時，偵查員A說：“趙與錢中至少有一人作案”；偵查員B說：“錢與孫中至少有一人作案”；偵查員C說：“孫與李中至少有一人作案”；偵查員D說：“趙與孫中至少有一人與此案無關”；偵查員E說：“錢與李中至少有一人與此案無關”。如果這5個偵查員的話都是可信的，試用

2、歸結(jié)演繹推理求出誰是盜竊犯。3.解：(1) 先定義謂詞和常量設C(x)表示x 作案，Z 表示趙，Q 表示錢，S 表示孫，L 表示李(2) 將已知事實用謂詞公式表示出來趙與錢中至少有一個人作案：C(Z)C(Q)錢與孫中至少有一個人作案：C(Q)C(S)孫與李中至少有一個人作案：C(S)C(L)趙與孫中至少有一個人與此案無關：¬ (C (Z)C(S)，即¬C (Z) ¬C(S)錢與李中至少有一個人與此案無關：¬ (C (Q)C(L)，即¬C (Q) ¬C(L)(3) 將所要求的問題用謂詞公式表示出來，并與其否定取析取。設作案者為u，則要求

3、的結(jié)論是C(u)。將其與其否取析取，得：¬ C(u) C(u)(4) 對上述擴充的子句集，按歸結(jié)原理進行歸結(jié)，其修改的證明樹如下：C(Q)C(S)¬C (Z)¬C(S)C(Z)C(Q)C(Q)¬C(S)C(Q)¬C(u)C(u)C(Q)Q/u因此，錢是盜竊犯。實際上，本案的盜竊犯不止一人。根據(jù)歸結(jié)原理還可以得出：C(S)C(L)¬C (Q) ¬C(L)C(S)¬C(Q)C(Q)C(S)C(S)¬C(u)C(u)C(S)S/u因此，孫也是盜竊犯。4.設有如圖所示的與/或樹，請分別用和代價法、最大代價法求解樹

4、的代價。Dt4t3t2t132226157ECBA4. 解：若按和代價法，則該解樹的代價為：h(A)=2+3+2+5+2+1+6=21若按最大代價法，則該解樹的代價為：h(A)=maxh(B)+5, h(C)+6 = max(h(E)+2)+5, h(C)+6= max(max(2, 3)+2)+5, max(2, 1)+6=max(5+5), (2+6)=105.設有如下一組推理規(guī)則：IF THEN （0.6）：IF AND THEN (0.7)：IF THEN H （0.8）：IF THEN H (0.9)且已知CF()=0.5，CF()=0.6,CF()=0.7,求CF(H)。5. 解：

5、(1) 先由r1 求CF(E2)CF(E2)=0.6 × max0,CF(E1)=0.6 × max0,0.5=0.3(2) 再由r2 求CF(E4)CF(E4)=0.7 × max0, minCF(E2 ), CF(E3 )=0.7 × max0, min0.3, 0.6=0.21(3) 再由r3 求CF1(H)CF1(H)= 0.8 × max0,CF(E4)=0.8 × max0, 0.21)=0.168(4) 再由r4 求CF2(H)CF2(H)= 0.9 ×max0,CF(E5)=0.9 ×max0, 0

6、.7)=0.63(5) 最后對CF1(H )和CF2(H)進行合成，求出CF(H)CF(H)= CF1(H)+CF2(H)+ CF1(H) × CF2(H)=0.6926.設 U=V=W=1，2，3，4且有如下規(guī)則：IF x is F THEN y is G：IF y is G THEN z is H：IF x is F THEN z is H其中，F(xiàn),G,H的模糊集分別為F=1/1+0.8/2+0.5/3+0.4/4G=0.1/2+0.2/3+0.4/4H=0.2/2+0.5/3+0.8/4請用模糊關系驗證滿足模糊三段論。6.先求FG上的關系，=再求GH上的關系,=最后求FGH的關

7、系R，R=2.(龍云獻） 簡述用A*算法求解問題時為什么會出現(xiàn)重復擴展節(jié)點問題，解決的方法有哪些？答：當問題有解時，A*算法總是找到問題的最優(yōu)解結(jié)束。如果h函數(shù)定義的不合理，則當擴展一個節(jié)點時，不一定就找到了從初始節(jié)點到該節(jié)點的最優(yōu)路徑，對于這樣的節(jié)點，就有可能被多次擴展。特別是如果這樣的節(jié)點處于問題的最優(yōu)解路徑上時，則一定會被多次擴展。解決的方法一是對h函數(shù)的定義給出限制，使得h滿足單調(diào)性。對于滿足單調(diào)性條件的h，則一定不會出現(xiàn)重復擴展節(jié)點問題。二是對A*算法加以改進，使用修正的A*算法進行搜索，則可以減少重復擴展節(jié)點問題。3. （劉林洋）簡述回溯策略與深度優(yōu)先策略的不同點。答：回溯搜索策略

8、與深度有限搜索策略最大的不同是深度有限搜索策略屬于圖搜索，而回溯搜索則不是圖搜索。在回溯搜索中，只保留了從初始節(jié)點到當前節(jié)點的搜索路徑。而深度優(yōu)先搜索，則保留了所有的已經(jīng)搜索過的路徑。4. (張松)設有如下兩個模糊關系：請寫出R1與R2的合成R1R2。解：R(1,1)=(0.30.2)(0.70.6)(0.20.9)= 0.20.60.2=0.6R(1,2)=(0.30.8)(0.70.4)(0.20.1)= 0.30.40.1=0.4R(2,1)=(10.2)(00.6)(0.40.9)= 0.200.4=0.4R(2,2)=(10.8)(00.4)(0.40.1)= 0.800.1=0.8

9、R(3,1)=(00.2)(0.50.6)(10.9)= 0.20.60.9=0.9R(3,2)=(00.8)(0.50.4)(10.1)= 00.40.1=0.4因此有5.（張松）設U=V=1，2，3，4且有如下推理規(guī)則： IF x is 少 THEN y is 多其中，“少”與“多”分別是U與V上的模糊集，設 少=0.9/1+0.7/2+0.4/3 多=0.3/2+0.7/3+0.9/4已知事實為 x is 較少“較少”的模糊集為 較少=0.8/1+0.5/2+0.2/3請用模糊關系Rm求出模糊結(jié)論。 解：先用模糊關系Rm求出規(guī)則 IF x is 少 THEN y is 多所包含的模糊關系

10、Rm Rm (1,1)=(0.90)(1-0.9)=0.1 Rm (1,2)=(0.90.3)(1-0.9)=0.3 Rm (1,3)=(0.90.7)(1-0.9)=0.7 Rm (1,4)=(0.90.9)(1-0.9)=0.7 Rm (2,1)=(0.70)(1-0.7)=0.3 Rm (2,2)=(0.70.3)(1-0.7)=0.3 Rm (2,3)=(0.70.7)(1-0.7)=0.7 Rm (2,4)=(0.70.9)(1-0.7)=0.7 Rm (3,1)=(0.40)(1-0.4)=0.6 Rm (3,2)=(0.40.3)(1-0.4)=0.6 Rm (3,3)=(0.4

11、0.7)(1-0.4)=0.6 Rm (3,4)=(0.40.9)(1-0.4)=0.6 Rm (4,1)=(00)(1-0)=1 Rm (4,2)=(00.3)(1-0)=1 Rm (4,3)=(00.7)(1-0)=1 Rm (3,4)=(00.9)(1-0)=1即：因此有即，模糊結(jié)論為 Y=0.3, 0.3, 0.7, 0.86.(張松)設已知：(1) 如果x是y的父親，y是z的父親，則x是z的祖父；(2) 每個人都有一個父親。使用歸結(jié)演繹推理證明：對于某人u，一定存在一個人v，v是u的祖父。 解：先定義謂詞 F(x,y)：x是y的父親 GF(x,z)：x是z的祖父 P(x)：x是一個人

12、 再用謂詞把問題描述出來： 已知F1：(x) (y) (z)( F(x,y)F(y,z)GF(x,z) F2：(y)(P(x)F(x,y) 求證結(jié)論G：(u) (v)( P(u)GF(v,u) 然后再將F1，F(xiàn)2和¬G化成子句集： ¬F(x,y)¬F(y,z)GF(x,z) ¬P(r)F(s,r) P(u) ¬GF(v,u) 對上述擴充的子句集，其歸結(jié)推理過程如下：¬F(x,y)¬F(y,z)GF(x,z)¬GF(v,u)¬F(x,y)¬F(y,z)¬P(r)F(s,r)¬F

13、(y,z)¬P(y)¬P(r)F(s,r)¬P(y)¬P(z)¬P(y)P(u)NIL x/v,z/ux/s,y/ry/s,z/r y/z y/u 由于導出了空子句，故結(jié)論得證。1.假設有以下一段天氣預報：“貴陽地區(qū)今天白天晴，東北風1級，最高氣溫25º，最低氣溫16º，降水概率10%，濕度64%?！闭堄每蚣鼙硎具@一知識。（陳麗麗）解：Frame<天氣預報> 地域：貴陽 時段：今天白天 天氣：晴 風向：東北 風力：1級 氣溫：最高：25度 最低：16度 降水概率：10% 濕度：64%2.把下列謂詞公式化成子句集：

14、（陳麗麗）(1) (x)(y)(P(x, y)Q(x, y)(2) (x)(y)(P(x, y)(Q(x, y)R(x, y) 解：(1) 由于(x)(y)(P(x, y)Q(x, y)已經(jīng)是Skolem標準型，且P(x, y)Q(x, y)已經(jīng)是合取范式，所以可直接消去全稱量詞、合取詞，得 P(x, y), Q(x, y) 再進行變元換名得子句集： S= P(x, y), Q(u, v) (2) 對謂詞公式(x)(y)(P(x, y)(Q(x, y)R(x, y)，先消去連接詞“”得：(x)(y)(P(x, y)(¬Q(x, y)R(x, y)此公式已為前束范式。再消去存在量詞，即

15、用Skolem函數(shù)f(x)替換y得：(x)(P(x, f(x)¬Q(x, f(x)R(x, f(x)此公式已為Skolem標準型。 最后消去全稱量詞得子句集： S=P(x, f(x)¬Q(x, f(x)R(x, f(x) (1) 有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花 。解：定義謂詞P(x)：x是人L(x,y)：x喜歡y其中，y的個體域是梅花，菊花。將知識用謂詞表示為：(x )(P(x)L(x, 梅花)L(x, 菊花)L(x, 梅花)L(x, 菊花) (2) 新型計算機速度又快，存儲容量又大。解：定義謂詞NC(x)：x是新型計算機F(x)：x速度快B(x

16、)：x容量大將知識用謂詞表示為：(x) (NC(x)F(x)B(x)(3) 凡是喜歡編程序的人都喜歡計算機。解：定義謂詞P(x)：x是人L(x, y)：x喜歡y將知識用謂詞表示為：(x) (P(x)L(x,pragramming)L(x, computer)、設有如下一組推理規(guī)則:r1: IF E1 THEN E2 (0.6)r2: IF E2 AND E3 THEN E4 (0.7)r3: IF E4 THEN H (0.8)r4: IF E5 THEN H (0.9)且已知CF(E1)=0.5, CF(E3)=0.6, CF(E5)=0.7。求CF(H)=?解：(1) 先由r1 求CF(E

17、2)CF(E2)=0.6 × max0,CF(E1)=0.6 × max0,0.5=0.3(2) 再由r2 求CF(E4)CF(E4)=0.7 × max0, minCF(E2 ), CF(E3 )=0.7 × max0, min0.3, 0.6=0.21(3) 再由r3 求CF1(H)CF1(H)= 0.8 × max0,CF(E4)=0.8 × max0, 0.21)=0.168(4) 再由r4 求CF2(H)CF2(H)= 0.9 ×max0,CF(E5)=0.9 ×max0, 0.7)=0.63(5) 最后

18、對CF1(H )和CF2(H)進行合成，求出CF(H)CF(H)= CF1(H)+CF2(H)+ CF1(H) × CF2(H)=0.692一、（夏道麗）請把下面命題用一個語義網(wǎng)絡表示出來：（1） 所有動物都具有喜吃食、能運動的屬性；（2） 鳥（bird）、魚（fish）分別都是動物的一種，因此，它們也各自繼承了動物的這些屬性；（3） 此外，金魚是魚的一種，故金魚就又繼承了fish類動物所具有的會游泳、繁殖、可喂養(yǎng)等屬性，并又有可觀賞等特點；同理，孔雀繼承了鳥具有的能下蛋、有翅膀的屬性，還具有展翼喜歡表現(xiàn)的習性等。吃食運動解：CANCAN下蛋翅膀繁殖喂養(yǎng)游泳動物CANAKOCANMA

19、YCANHAVE展翼觀賞魚鳥CANAKOAKOCAN 金魚孔雀二、（夏道麗）假設有以下一段新聞：“今天，一次強度為里氏8.5級的強烈地震襲擊下斯洛文尼亞地氏，造成25人死亡和5億美元的財產(chǎn)損失。下斯洛文尼亞地區(qū)主席說：多年來，靠近薩迪壕金斯斷層的重災區(qū)一直是一個危險地區(qū)。這是本地區(qū)發(fā)生的第3號地震。”請用框架表示這一知識。解：Frame<地震3>時間：今天地點：下斯洛文尼亞地區(qū)傷亡人數(shù)：25人財產(chǎn)損失：500，000，000美元震級：8.5斷層：薩迪壕金斯五、（趙娉婷）4.5 有一農(nóng)夫帶一條狼，一只羊和一框青菜與從河的左岸乘船倒右岸，但受到下列條件的限制：(1) 船太小，農(nóng)夫每次只

20、能帶一樣東西過河；(2) 如果沒有農(nóng)夫看管，則狼要吃羊，羊要吃菜。請設計一個過河方案，使得農(nóng)夫、浪、羊都能不受損失的過河，畫出相應的狀態(tài)空間圖。題示：(1) 用四元組（農(nóng)夫，狼，羊，菜）表示狀態(tài)，其中每個元素都為0或1，用0表示在左岸，用1表示在右岸。(2) 把每次過河的一種安排作為一種操作，每次過河都必須有農(nóng)夫，因為只有他可以劃船。解：第一步，定義問題的描述形式用四元組S=（f，w，s，v）表示問題狀態(tài)，其中，f，w，s和v分別表示農(nóng)夫，狼，羊和青菜是否在左岸，它們都可以取1或0，取1表示在左岸，取0表示在右岸。第二步，用所定義的問題狀態(tài)表示方式，把所有可能的問題狀態(tài)表示出來，包括問題的初始

21、狀態(tài)和目標狀態(tài)。由于狀態(tài)變量有4個，每個狀態(tài)變量都有2種取值，因此有以下16種可能的狀態(tài)：S0=(1,1,1,1)，S1=(1,1,1,0)，S2=(1,1,0,1)，S3=(1,1,0,0)S4=(1,0,1,1)，S5=(1,0,1,0)，S6=(1,0,0,1)，S7=(1,0,0,0) S8=(0,1,1,1)，S9=(0,1,1,0)，S10=(0,1,0,1)，S11=(0,1,0,0)S12=(0,0,1,1)，S13=(0,0,1,0)，S14=(0,0,0,1)，S15=(0,0,0,0)其中，狀態(tài)S3，S6，S7，S8，S9，S12是不合法狀態(tài)，S0和S15分別是初始狀態(tài)和

22、目標狀態(tài)。第三步，定義操作，即用于狀態(tài)變換的算符組F由于每次過河船上都必須有農(nóng)夫，且除農(nóng)夫外船上只能載狼，羊和菜中的一種，故算符定義如下：L(i)表示農(nóng)夫從左岸將第i樣東西送到右岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除農(nóng)夫外不載任何東西）。由于農(nóng)夫必須在船上，故對農(nóng)夫的表示省略。R (i)表示農(nóng)夫從右岸將第i樣東西帶到左岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除農(nóng)夫外不載任何東西）。同樣，對農(nóng)夫的表示省略。這樣，所定義的算符組F可以有以下8種算符：L (0)，L (1)，L (2)，L (3) R(0)，R(1)，R (2)，R (3)第四步，根據(jù)上述定義的狀態(tài)和操作進行求解。該問題求解過程的狀態(tài)空間圖如下：(1,1,l,1)L(2)(0,1,0,1)R(0)(1,1,0,1)L(3)L(1)(0,1,0,0)(0,0,0,1)R(2)R(2)(1,1,1,0)(1,0,1,1)L(2)L(3)(0,0,1,0)R(0)(1,0,1,0)L(2)(0,0,0,0)六、（趙娉婷）1 我們有n(n64)根小木棍，每根長度均不大于50?，F(xiàn)在需要將它們拼接成長度相同的若干長木棍，并使得這些長木棍最短。問如何拼接？剪枝一（改變搜索順序）對木