人工智能例題大綱

1、1. 用謂詞邏輯知識表示方法表示如下知識：(1) 有人喜歡梅花，有人喜歡菊花，有人既喜歡梅花又喜歡菊花。(2) 不是每個計算機系的學(xué)生都喜歡在計算機上編程序。解： (1)定義謂詞P(x)： x 是人L(x,y)： x 喜歡 y其中， y 的個體域是 梅花，菊花 。將知識用謂詞表示為：(x)(P(x) L(x,梅花 ) L(x, 菊花 ) L(x, 梅花 ) L(x, 菊花 )解： (2)定義謂詞S(x)： x 是計算機系學(xué)生L(x, pragramming) ： x 喜歡編程序U(x,computer) ： x 使用計算機將知識用謂詞表示為：(x) (S(x) L(x, pragramming

2、)U(x,computer)2. 請用語義網(wǎng)絡(luò)表示如下知識：高老師從3 月到 7 月給計算機系的學(xué)生講“計算機網(wǎng)絡(luò)”課。解：3. 判斷以下子句集是否為不可滿足P(x) Q(x ) R(x), P(y) R(y), Q(a), R(b)解：采用歸結(jié)反演，存在如下歸結(jié)樹，故該子句集為不可滿足。4、證明 G 是 F 的邏輯結(jié)論F: (x)(y)(P(f(x) (Q(f(y)G: P(f(a) P(y) Q(y)證：先轉(zhuǎn)化成子句集對 F，進行存在固化，有P(f(v) (Q(f(w)得以下兩個子句P(f(v)， Q(f(w)對 G，有 P(f(a) P(y) Q(y)先進行內(nèi)部合一，設(shè)合一f(a)/y

3、，則有因子 P(f(a) Q(f(a)再對上述子句集進行歸結(jié)演繹推理。其歸結(jié)樹如下圖所示，即存在一個到空子句的歸結(jié)過程。因此 G 為真。5 設(shè)有如下結(jié)構(gòu)的移動將牌游戲：其中， B 表示黑色將牌，W 表是白色將牌，E 表示空格。游戲的規(guī)定走法是：(1) 任意一個將牌可移入相鄰的空格，規(guī)定其代價為1；(2) 任何一個將牌可相隔1 個其它的將牌跳入空格，其代價為跳過將牌的數(shù)目加1。游戲要達到的目標(biāo)什是把所有W 都移到 B 的左邊。對這個問題，請定義一個啟發(fā)函數(shù) h(n) ，并給出用這個啟發(fā)函數(shù)產(chǎn)生的搜索樹。你能否判別這個啟發(fā)函數(shù)是否滿足下界要求在求出的搜索樹中，對所有節(jié)點是否滿足單調(diào)限制解：設(shè) h(

4、x)=每個 W 左邊的 B 的個數(shù)， f(x)=d(x)+3*h(x) ，其搜索樹如下：6 設(shè)有如下一組推理規(guī)則:r:IFETHENE112r:IFEANDETHEN E2234r3:IFE4THENHr4:IFE5THENH且已知 CF(E1)=,CF(E3)=,CF(E5)=。求 CF(H)=解： (1) 先由 r1 求 CF(E2)CF(E2 )=× max0,CF(E1)= × max0,=(2) 再由 r2 求 CF(E4 )CF(E4 )=× max0, minCF(E2), CF(E3 )= × max0, min, =(3) 再由 r3

5、求 CF1(H)CF1(H)=× max0,CF(E4)= × max0, =(4) 再由 r4 求 CF2(H)CF2(H)=× max0,CF(E5)= × max0, =(5) 最后對 CF1(H )和 CF2(H)進行合成，求出 CF(H) CF(H)= CF1(H)+CF2(H)- CF1(H) × CF2(H)=7 設(shè)訓(xùn)練例子集如下表所示：請用 ID3 算法完成其學(xué)習(xí)過程。解：設(shè)根節(jié)點為 S，盡管它包含了所有的訓(xùn)練例子，但卻沒有包含任何分類信息，因此具有最大的信息熵。即：H(S)= - (P(+)log 2P(+) - P(-)lo

6、g2 P(-)式中P(+)=3/6， P(-)=3/6即有H(S)= - (3/6)*log (3/6) - (3/6)*log (3/6)= *(-1) - *(-1) = 1按照 ID3 算法，需要選擇一個能使 S 的期望熵為最小的一個屬性對根節(jié)點進行擴展，因此我們需要先計算 S 關(guān)于每個屬性的條件熵：H(S|x)= ( |S | / |S|)* H(S)+(|S|/|S|)*H(S)iTTFF其中， T 和 F 為屬性 xi 的屬性值， ST 和 SF 分別為 xi=T 或 xi=F 時的例子集， |S| 、 |ST| 和 |SF|分別為例子集S、 STF和 S 的大小。下面先計算S 關(guān)

7、于屬性x1 的條件熵：在本題中，當(dāng)x1=T 時，有：ST=1， 2， 3當(dāng) x1=F 時，有：SF=4， 5， 6其中， ST 和 SF 中的數(shù)字均為例子集S 中例子的序號，且有|S|=6 ， | S T |=| S F |=3 。由 ST 可知：P(+)=2/3，P(-)=1/3則有：H(ST)= - (P(+)log2 P(+) - P(-)log2 P(- )= - (2/3)log2(2/3)- (1/3)log2(1/3) =再由 SF 可知：PSF(+)=1/3，PSF(-)=2/3則有：H(SF)= - (PSF(+)log2 PST(+) - PSF(-)log2 PSF(-

8、)= - (2/3)log2(2/3)- (1/3)log2(1/3) =將 H(ST)和 H (SF)代入條件熵公式，有：H(S|x 1)=(|ST|/|S|)H(S T)+ (|SF|/|S|)H(S F)=(3/6) + (3/6)=下面再計算S 關(guān)于屬性x2 的條件熵：在本題中，當(dāng)x2=T 時，有：ST=1， 2， 5， 6當(dāng) x2=F 時，有：SF=3， 4其中， ST 和 SF 中的數(shù)字均為例子集S 中的各個例子的序號，且有|S|=6 ， | ST |=4 ，| S F |=2 。由 ST 可知：PST (+) = 2/4PST (-) = 2/4則有：H(ST)= - (P ST

9、 (+)log2 P ST (+) - P ST (-)log2 P ST (- )= - (2/4)log2(2/4) - (2/4)log2(2/4) =1再由 SF 可知：PSF (+)=1/2PSF (-)=1/2則有：H(SF)= - (P(+)log2 P(+) - P(-)log2 P(- )= - (1/2)log2(1/2)- (1/2)log2(1/2) =1將 H(ST)和 H (SF)代入條件熵公式，有：H(S|x2)=(|S |/|S|)H(S)+ (|S |/|S|)H(S)TTFF=(4/6) 1 + (2/6) 1=1可見，應(yīng)該選擇屬性x1 對根節(jié)點進行擴展。用

10、x1 對 S 擴展后所得到的部分決策樹如下圖所示。8 八數(shù)碼難題f(n)=d(n)+P(n)d(n) 深度P(n)與目標(biāo)距離顯然滿足P(n) h*(n)即 f*=g*+h*9 修道士和野人問題解：用 m 表示左岸的修道士人數(shù)， c 表示左岸的野人數(shù)， b 表示左岸的船數(shù)，用三元組 (m, c, b)表示問題的狀態(tài)。對 A* 算法，首先需要確定估價函數(shù)。設(shè)g(n)=d(n)， h(n)=m+c-2b ，則有f(n)=g(n)+h(n)=d(n)+m+c-2b其中， d(n)為節(jié)點的深度。通過分析可知h(n) h*(n)，滿足 A*算法的限制條件。M-C 問題的搜索過程如下圖所示。10 設(shè)有如下一

11、組知識：r1： IFE1THENHr2： IFE2THENHr3： IFE3THENHr4： IFE4AND( E5ORE6)THEN已知： CF(E2)=，CF(E3)=， CF(E4)=，CF(E5)=,求： CF(H)=解：由 r4 得到：E1CF(E6)=CF(E1)= × max0, CF(E4 AND(E5ORE6)= × max0, minCF(E4),CF(E5ORE6)=× max0, minCF(E4),maxCF(E5),CF(E6)=× max0, minCF(E4),max,=× max0, min, =×

12、max0, =由 r1 得到： CF1(H)=CF(H, E1) × max0, CF(E1) =× max0, =由 r2 得到： CF2(H)=CF(H, E2) × max0, CF(E2 ) =× max0, =由 r3 得到： CF3(H)=CF(H, E3) × max0, CF(E3 ) =× max0, =根據(jù)結(jié)論不精確性的合成算法，CF1(H)和 CF2(H)同號，有：1,2(H)1()2()1()2()CFCF HCF HCF HCF H0. 360. 480. 360. 480. 840. 170. 67CF12

13、(H)和 CF3(H)異號，有：CF1,2 ,3( H)CF1, 2( H)CF3( H)1min CF1,2( H) , CF3( H)0. 670. 30. 371min 0. 67,0. 30. 70. 53即綜合可信度為CF(H)=11 設(shè)有如下知識：r1： IF E1（） AND E2（）THEN E5（）r2： IF E3（） AND E4（） ANDE5（） THENH（）已知：CF（ E1） =，CF（ E2） =， CF（ E3） =， CF（ E4）=求：CF（H） =解：CF(E1 AND E2)=*+*=CF(E5)=*=CF(E3 AND E4 ANDE5)=*+*+

14、*=CF(H)=*=12 設(shè)有如下規(guī)則：r:IFEANDE THENA=a , a CF=, 11212r2:IFE3THEN H=h1, h2CF=, r3:IFATHENH=h 1, h2CF=, 已知用戶對初始證據(jù)給出的確定性為：CER(E1)=CER(E2)=CER(E3)=并假 定中的元素個數(shù) =10求： CER(H)=解：由給定知識形成的推理網(wǎng)絡(luò)如下圖所示：(1) 求 CER(A) 由 r1:CER(E1ANDE2 )=minCER(E1),CER(E2)=min, =m(a 1, a2)=× ,×=,Bel(A)=m(a 1)+m(a 2)=+=Pl(A)=1

15、-Bel( A)=1-0=1f(A)=Bel(A)+|A|/|Pl(A)-Bel(A)=+2/10*=故CER(A)=MD(A/E') × f(A)=(2) 求 CER(H)由 r2 得m1(h 1, h 2)=CER(E3) × , CER(E3)×= ×,×=, m1( )=1-m 1(h 1)+m 1(h 2)=1-+=由 r3 得m2(h 1, h 2)=CER(A)× , CER(A)×= ×,×=, m2( )=1-m 2(h 1)+m 2(h 2)=1-+=求正交和 m=m 1 m2

16、K=m1( ) ×m2()+m (h ) ×m(h )+m1(h)×m( )+m( ) ×m(h)112112121+m 1(h 2)×m2(h 2)+m 1(h2 )×m2( )+m1( ) ×m2(h 2)=×+× +× +×+× +× +×=+=m( h1 )1?1(1)2(1 )1(1)2()1( )2(1)Km h? m hm h? mm? m h10.360. 060. 360. 650. 460. 060. 881. 32同理可得：()1 (

17、h2)(h2)(h2)( )( )(h2)m h2Km1m2m1m2m1m210. 290. 180. 650. 460. 290. 340.180. 88故有： m()=1-m(h 1)+m(h 2)=1-+ =再根據(jù) m 可得Bel(H)=m(h 1 )+m(h 2 ) = + =Pl(H)=m( )+Bel(H)=+=1f ( H)Bel( H)H? ()()0. 662(1 0. 66) 0. 73Pl HBel H10CER(H)=MD(H/E')× f(H)=13 用 ID3 算法完成下述學(xué)生選課的例子假設(shè)將決策y 分為以下3 類：y1：必修 AIy2：選修 AI

18、y3：不修 AI做出這些決策的依據(jù)有以下3 個屬性：x1：學(xué)歷層次x2：專業(yè)類別x1=1x2=1研究生，電信類，x1=2 x2=2本科機電類x3：學(xué)習(xí)基礎(chǔ)x3=1 修過 AI， x3=2 未修 AI表給出了一個關(guān)于選課決策的訓(xùn)練例子集S。該訓(xùn)練例子集S 的大小為8。 ID3 算法就是依據(jù)這些訓(xùn)練例子，以S為根節(jié)點，按照信息熵下降最大的原則來構(gòu)造決策樹的。解： 首先對根節(jié)點，其信息熵為：3()() log()H SiP y i2 P y i1其中，為可選的決策方案數(shù)，且有P(y1)=1/8， P(y2)=2/8， P(y3)=5/8即有：H(S)= -(1/8)log 2(1/8)- (2/8)

19、log 2(2/8)- (5/8)log 2(5/8) =按照 ID3 算法，需要選擇一個能使 S 的期望熵為最小的一個屬性對根節(jié)點進行擴展，因此我們需要先計算 S 關(guān)于每個屬性的條件熵：H (S / x)| St |H (S )it | S |t其中， t 為屬性 xi 的屬性值， St 為 xi=t 時的例子集， |S| 和 |S t | 分別是例子集S 和 St 的大小。下面先計算 S 關(guān)于屬性 x1 的條件熵：在表 6-1 中， x的屬性值可以為1 或 2。當(dāng) x =1 時， t=1 時，有：11S1=1， 2， 3， 4當(dāng) x1=2 時， t=2 時，有：S2=5， 6， 7， 8其

20、中， S1 和 S2 中的數(shù)字均為例子集S 中的各個例子的序號，且有|S|=8 ， |S 1 |=|S 2|=4 。由 S1 可知：Ps1(y1)=1/4,Ps1(y2)=1/4,Ps1(y3)=2/4則有：H(S1)= - Ps1(y1)log2 Ps1(y1) - Ps1(y2)log 2 Ps1 (y2 )- Ps1(y3 )log 2 Ps1(y3 )= -(1/4)log 2(1/4)- (1/4)log 2(1/4)- (2/4)log 2(2/4) =再由 S2 可知：Ps2 (y1)=0/4,Ps2(y2)=1/4,Ps2 (y3)=3/4則有：H(S2)=Ps2(y2)log

21、2 Ps2(y2 )- Ps2(y3 )log2 Ps2(y3 )=- (1/4)log2 (1/4)- (3/4)log 2(3/4) =將 H(S1)和 H(S2)代入條件熵公式，有：H(S/x1)=(|S 1|/|S|)H(S1 )+ (|S 2|/|S|)H(S2)=(4/8) +(4/8)=同樣道理，可以求得：H(S/x2)=H(S/x3)=可見，應(yīng)該選擇屬性x3 對根節(jié)點進行擴展。用x3 對S 擴展后所得到的得到部分決策樹如圖所示。Sx3=1x3=2x3=1, y3x3=2,x1, x2圖 部分決策樹在該樹中，節(jié)點“ x3=1, y3 ”為決策方案 y3。由于 y3 已是具體的決策

22、方案，故該節(jié)點的信息熵為 0，已經(jīng)為葉節(jié)點。節(jié)點 “x3=2, x1, x2”的含義是需要進一步考慮學(xué)歷和專業(yè)這兩個屬性，它是一個中間節(jié)點，還需要繼續(xù)擴展。至于其擴展方法與上面的過程類似。通過計算可知，該節(jié)點對屬性x1 和 x2，其條件熵均為1。由于它對屬性條件熵相同，因此可以先選擇x1，也可以先選擇x2。依此進行下去，若先選擇x1 可得到如圖所示的最終的決策樹；若先選擇x1 和 x2 的x2 可得到如圖所示的最終的決策樹。14 （歸結(jié)反演）已知：“張和李是同班同學(xué)，如果 x 和 y 是同班同學(xué)，則 x 的教室也是 y 的教室，現(xiàn)在張在 302 教室上課。”問： “現(xiàn)在李在哪個教室上課”解：首

23、先定義謂詞：C(x, y)x 和 y 是同班同學(xué)；At(x, u)x 在 u 教室上課。把已知前提用謂詞公式表示如下：C(zhang, li)(x) (y) (u) (C(x, y) At(x, u) At(y,u)At(zhang, 302)把目標(biāo)的否定用謂詞公式表示如下： (v)At(li, v)把上述公式化為子句集：C(zhang, li) C(x, y) At(x, u) At(y, u)At(zhang, 302)把目標(biāo)的否定化成子句式，并用重言式 At(li,v) At(li,v)代替之。把此重言式加入前提子句集中，得到一個新的子句集，對這個新的子句集，應(yīng)用歸結(jié)原理求出其證明樹。其

24、求解過程如下圖所示。該證明樹的根子句就是所求的答案，即“李明在302 教室”。公式：A估價函數(shù)用來估計節(jié)點重要性，定義為從初始節(jié)點S0 出發(fā)，約束經(jīng)過節(jié)點n 到達目標(biāo)節(jié)點Sg 的所有路徑中最小路徑代價的估計值。一般形式：f(n)=g(n)+h(n)其中， g(n)是從初始節(jié)點S0 到節(jié)點 n 的實際代價； h(n)是從節(jié)點 n 到目標(biāo)節(jié)點 Sg 的最優(yōu)路徑的估計代價。BA* 算法是對 A 算法的估價函數(shù)f(n)=g(n)+h(n) 加上某些限制后得到的一種啟發(fā)式搜索算法假設(shè) f*(n) 是從初始節(jié)點 S 出發(fā)，約束經(jīng)過節(jié)點n 到達目標(biāo)節(jié)點S 的最小代價，0g估價函數(shù) f(n)是對 f*(n)

25、的估計值。記f*(n)=g*(n)+h*(n)其中， g*(n) 是從 S0 出發(fā)到達 n 的最小代價 ,h*(n) 是 n到 Sg 的最小代價如果對 A 算法（全局擇優(yōu)）中的g(n)和 h(n)分別提出如下限制：第一， g(n)是對最小代價 g*(n) 的估計，且 g(n)>0；第二， h(n) 是最小代價 h*(n) 的下界，即對任意節(jié)點n 均有 h(n) h*(n)。則稱滿足上述兩條限制的A 算法為 A* 算法。C 不確定性知識的表示形式：在 C-F模型中，知識是用產(chǎn)生式規(guī)則表示的，其一般形式為：IFETHENH(CF(H, E)其中， E 是知識的前提條件；H 是知識的結(jié)論；CF

26、(H, E)是知識的可信度。D 組合證據(jù)合?。?E=E1 AND E2 AND時En，若已知CF(E1)， CF(E2)， ，則CF(E)=minCF(E1), CF(E2),CF(En)析?。?E=E1 OR E2OREn時，若已知CF(E1)， CF(E2)， ，則CF(E)=maxCF(E1), CF(E2),CF(En)E 不確定性的更新公式CF(H)=CF(H, E)× max0, CF(E)若 CF(E)<0，則CF(H)=0即該模型沒考慮E 為假對 H 的影響。若 CF(E)=1，則 CF(H)=CF(H,E)F 設(shè)有知識： IFETHENH(CF(H, E)11

27、IFE2THENH(CF(H, E2)則結(jié)論 H 的綜合可信度可分以下兩步計算：(1) 分別對每條知識求出其CF(H)。即CF1(H)=CF(H, E1)× max0, CF(E1)CF2(H)=CF(H, E2)× max0, CF(E2)(2) 用如下公式求 E1 與 E2 對 H 的綜合可信度CF( H)CF( H)CF( H)CF( H)若 CF( H)011212且 CF2( H)0CF( H)CF( H)CF( H)CF( H)若 CF( H)0CF( H)11212且 CF2( H)0CF( H) CF( H)若 CF1( H )與121 min CF( H

28、) , CF( H )CF2( H )異號12G 帶加權(quán)因子的可信度推理在這種不確定性推理中， 證據(jù)的不確定性仍然用可信度因子表示， 組合證據(jù)的可信度可通過計算得到。對于前提條件E=E1(1) AND E2(2) ANDAND En( n)所對應(yīng)的組合證據(jù)，其可信度由下式計算：CF(E)= CF(E1)*1 +CF(E2)*2+CF(En)*n如果不滿足歸一條件，則可信度由下式計算：CF(E)= (CF(E1)*1 +CF(E2)*2+CF(En)*n)/( 1+ 2+n)H 證據(jù)理論設(shè)函數(shù) m： 2 0， 1，且滿足m()0m( A)1A則稱 m 是 2上的概率分配函數(shù)，m(A) 稱為 A

29、的基本概率數(shù)。I 概率分配函數(shù)的合成設(shè) m1和 m2是 2上的基本概率分配函數(shù)，它們的正交和m m1m2定義為m( si )K 1 m1( si )m2( s i )m1( si )m2( )m1()m2( si )其中Km(m(n m( sm( sm( sm() m( )m( s)121 i2 i1 i212ii 1J 信任函數(shù)（下限函數(shù)）對任何命題 A ,其信任函數(shù)為Bel( A)m( si )siAn( )()()( )1Belm Bm simBi1K 似然函數(shù)（上限函數(shù)）對任何命題 A ,其似然函數(shù)為nPl( A)1Bel(A)1m( si )1 m( si )m( si ) siAi1si A1 1m( )Bel( A)m()Bel( A)Pl( )1Bel()1Bel()1似然函數(shù)也稱為上限函數(shù)， 表示對 A 的非假信任度。 可以看出，對任何命題 A 、 A 都有Pl(A)-Bel(A) = Pl(B)- Bel(B) = m()L 類概率函數(shù)設(shè) 為有限域，對任何命題A ，命題 A 的類概率函數(shù)為APl( A) Bel( A)f ( A) Bel( A)M 證據(jù)的匹配度表示設(shè) A 是規(guī)則條件部分的命題， E'是外部輸入的證據(jù)和已證實的命題， 在證據(jù) E'的條件下，命題 A 與證據(jù) E