研究生課程-人工智能原理-期末考試試題

1、AI 往年考試試題解析一、子句集及其化簡不包含任何文字的子句稱為空子句。 由于空子句不含有任何文字， 也就不能被任何解釋 所滿足，因此空子句是永假的。空子句一般被記為 NIL 。證明題會用到此結論化簡步驟：l消去連接詞“T反復使用如下等價公式： P t Q P V Q,即可消去謂詞公式中的連接詞“t。例如公式(x)( y)P(x,y) T ( y )(Q(x,y) T R(x,y)經(jīng)等價變化后為(x)( y)P(x,y) V ( y )( Q(x,y) V R(x,y)(2) 減少否認符號的轄域即把否認符號移到緊靠謂詞的位置上 反復使用雙重否認律 ( P) P狄摩根定律PV Q PA Q(P

2、A Q PV Q 量詞轉換律 ( x P xP , x P x P將每個否認符號“ 移到僅靠謂詞的位置,使每個否認符號最多只作用于一個謂詞 上。例如,上步所得公式經(jīng)本步變換后為(x)( y) P(x,y)V( y )( Q(x,y) A R(x,y)(3)對變元標準化在一個量詞的轄域內, 把謂詞公式中受該量詞約束的變元全部用另外一個沒有出現(xiàn) 過的任意變元代替,使不同量詞約束的變元有不同的名字。例如,上步所得公式經(jīng)本步變換后為(x)( y) P(x,y)V ( z )( Q(x,z)A R(x,z)( 4)化為前束范式 化為前束范式的方法是把所有量詞都移到公式的左邊,并且在移動時不能改變其相 對

3、順序。由于第 3步已對變元進行了標準化,每個量詞都有自己的變元,這就消除了任 何由變元引起沖突的可能,因此這種移動是可行的。例如,上步所得公式化為前束范式后為 :( x) ( y) ( z )( P(x,y)V( Q(x,z)A R(x,z) 5消去存在量詞 消去存在量詞時,需要區(qū)分以下兩種情況。 假設存在量詞不出現(xiàn)在全稱量詞的轄域內 即它的左邊沒有全稱量詞 ,只要用一 個新的個 體常量替換受該存在量詞約束的變元,就可消去該存在量詞。假設存在量詞位于一個或多個全稱量詞的轄域內,例如(Xi)( X2)(Xn)( y)P(Xi ,X2 ,X n ,y)那么需要用Skolem函數(shù)y=fx1,x2 ,

4、x n丨替換受該存在量詞約束的變元，然后再消 去該存在量詞。例如，在上步所得公式中存在量詞y)和z都位于X的轄域內，因此都需要用Skolem函數(shù)來替換。設替換 y和z的Skolem函數(shù)分別是fx和gx，那么替換后的 公式為 :( x) ( y) ( z )( P(x,fx )V( Q(x,gx )A R(x,gx ) 6化為 Skolem 標準形Skolem 標準形的一般形式為(Xi)( X2)(X2)M(Xi，X2,，Xn)其中，Mx 1,x 2,xn是Skolem標準形的母式，它由子句的合取所構成。把謂詞公式化為 Skolem 標準形需要使用以下等價關系P V Q A R= PV QA P

5、V R 例如，上步所得的公式化為 Skolem 標準形后為 X (P(X,f(X) V Q(X,g(X) A (P(X,f(X) V R(X,g(X)(7) 消去全稱量詞 由于母式中的全部變元均受全稱量詞的約束， 并且全稱量詞的次序已無關緊要， 因此可 以省掉全稱量詞。剩下的母式，仍假設其變元是被全稱量詞量化的。例如，上步所得公式消去全稱量詞后為(P(X,f(X) V Q(X,g(X) A (P(X,f(X) V R(X,g(X) 8消去合取詞 在母式中消去所有合取詞， 把母式用子句集的形式表示出來。 其中， 子句集中的每一個 元素都是一個子句。例如，上步所得公式的子句集中包含以下兩個子句P(

6、X,f(X) V Q(X,g(X) P(X,f(X) V R(X,g(X)(9)更換變元名稱 對子句集中的某些變元重新命名， 使任意兩個子句中不出現(xiàn)相同的變元名。 由于每一 個子句都對應著母式中的一個合取元， 并且所有變元都是由全稱量詞量化的， 因此任意兩個 相同子句的變元之間實際上不存在任何關系。這樣，更換變元名是不會影響公式的真值的例如，對上步所得公式，可把第二個子句集中的變元名X更換為y，得到如下子句P(X,f(X) V Q(X,g(X)P(y,f(y) V R(y,g(y)真題 1：將 (X)(y)( z)( P(X,y) A Q(X,z) V R(X,y,z) 化成子句集。 15 分

7、解析：根據(jù)步驟 5( X) ( y) ( z )(P(X,f(X)A Q(X,g(X) V R(X,f(X),g(X)根據(jù)步驟6、7子句集為：(P(X,f(X) V R(X,f(X),g(X) A (Q(X,g(X) V R(X,f(X),g(X)根據(jù)步驟8、 9 子句集為： P(x,f(x) V R(x,f(x),g(x)和 Q(y,g(y) V R(y,f(y),g(y)二、Herbrand 域H域定義：設S為論域D上的一個子句集，那么按下述方法構造的域Ha稱為海伯倫域，簡記為 H 域。l令H。是S中所有個體常量的集合，假設S中不包含個體常量，那么可任取一常量a D，并令 H 0 = a

8、;2令出訐H i V S中所有n元 函數(shù)f(x 1 ,x 2 ,x n )|x j是H i中的元素，其中，i=0,1,2, ;j=1,2, ,n。真題 2： S=P(f(x),a,g(y),b, 求該公式的 Herbrand 域。 15 分解析：此例中有兩個個體常量a、b和兩個函數(shù)f(x)、g(y)，依H域的定義有H 0 = a,bH1= a,bV f(a), f(b),g(a),(b) = a, b, f(a), f(b),g(a),g(b) H 2 = a, b, f(a), f(b),g(a),g(b) V f(f(a), f(f(b), f(g(a), f(g(b), g(f(a),

9、g(f(b), g(g(a), g(g(b)=a, b, f(a), f(b),g(a),g(b),f(f(a), f(f(b), f(g(a), f(g(b), g(f(a), g(f(b), g(g(a), g(g(b)H a= a, b, f(a), f(b),g(a),g(b),f(f(a), f(f(b), f(g(a), f(g(b), g(f(a), g(f(b), g(g(a),g(g(b),三、歸結原理 歸結原理根本思想是： 首先把欲證明問題的結論否認， 并參加子句集， 得到一個擴充的 子句集S然后設法檢驗子句集 S是否含有空子句，假設含有空子句，那么說明 S是不可 滿足的；

10、假設不含有空子句，那么繼續(xù)使用歸結法， 在子句集中選擇適宜的子句進行歸結，直 至導出空子句或不能繼續(xù)歸結為止。設C1和C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補，那么可從C1和C2中分別消去L1和L2，并將C1和C2中余下的局部按析取關系構成一個 新的子句C12。那么稱這一過程為歸結，稱C12為C1和C2的歸結式，稱C1和C2為C12的親本子句。例 1:設 C1= PV Q, C2= Q, C3=P，求 C1、C2、C3 的歸結式 C123。 解：假設先對 C1、 C2 歸結，可得到 C12= P然后再對 C12 和 C3 歸結，得到 C123=NIL 。 在命題

11、邏輯中， F,證明G為真的歸結反演過程如下： 否認目標公式G,得 G; 把G并入到公式集F中，得到 F,G; 把 F, G化為子句集S; 應用歸結原理對子句集S中的子句進行歸結，并把每次得到的歸結式并入S中。如此反復進行，假設出現(xiàn)空子句，那么停止歸結，此時就證明了G為真。謂詞邏輯的歸結原理：設 C1 和 C2 是兩個沒有公共變元的子句， L1 和 L2 分別是 C1 和C2中的文字。如果 L1和 L2存在最一般合一 b，那么稱C12=C1 b L1 b U C2 b -L2 b 為 C1 和 C2 的二元歸結式，而 L1 和 L2 為歸結式上的文字。 這里之所以使用集合符號和集合的運算，目的是

12、為了說明問題的方便。即先將子句Cib和Li b寫成集合的形式，并在集合表示下做減法和并集運算，然后再寫成子句集的形式。例 2 :設 C仁P aV R x，C2= P yV Q b，求 C12。解：取L1=Pa， L2= Py，那么L1和 L2的最一般合一是b=a/y根據(jù)定義，可得C12=C1b L1b UC2 L2b =P(a)， R(x)P(a)UP(a)， Q(b) P(a)=R(x) UQ(b) =R(x)， Q(b) = R(x) V Q(b)真題 3：用歸結原理證明 G 是否為 F1 和 F2 的邏輯結論。 15分F1： (x)(P(x)(Q(x) A R(x)F2: ( x)(P(

13、x) A S(x)G： ( x)(R(x) A S(x) 解析：假設結論 G 為假，即 G 為真，將 G 參加公式集，并化為子句集(具體化簡步驟參考第一局部內容，此題假定替換符號時使用a,替換 符號時用使用x、y，替換符號只是形式上的問題，采用其他符號替換亦可 。S= (x)(P(x)(Q(x)AR(x)， ( x)(P(x)AS(x)，( x)(R(x)AS(x)(1) P(x)V Q(x) 2 P(y)V R(y) 3 P(a) 4 S(a)(5) G: R(x) V S(x)，其中12是由F1化成的子句，3 4是由F2化 成的子句， 5為 G。(6) 對于4 5采用(如例2的方法)歸結原

14、理，設L1= S(x) ,L2=S(a)，那么L1與 L2的最一般合一是b= a/ xC12= R(x), S(x) S(x)打 U S(a) S(a) = R(x)7對2 6進行歸結并替換變元，C12= P(a)8NIL 3 7進行歸結。注意：考試答題過程中不必寫出取L1、L2及換元的過程，只需寫出歸結后的結果即可。 歸結過程中，并不一定所有的字句都應用到，只要歸結出NIL即可，比方此題目中的1字句就并沒有應用到。 如果實在不會，就隨便寫出一個子句的非語句，然后就說跟此語句結合產(chǎn)生NIL,所以結論成立，這就是所謂的自己編造條件。不建議使用四、產(chǎn)生式表示法、語義網(wǎng)絡表示法與框架表示法例：產(chǎn)生式

15、表示法與框架表示法的區(qū)別piTidu n v i nntTLnE5UkWOYLk窮li只表可;-單位規(guī)那么框架推理固建、切知識庫獨立可變，與知識庫成i體建立知國難通用性*應用簡單問題復雜問題用戶初學者擊家真題4:比擬語義網(wǎng)絡表示法與框架表示法的區(qū)別與聯(lián)系。解析：框架的表示結構與語義網(wǎng)絡節(jié)點的表示結構接近，只是由于前者引入了側面描述，使框架比節(jié)點具有更豐富的表示結構。所以有的研究者就把語義網(wǎng)絡和框架表示法統(tǒng)稱為槽 與填充值slot and filler表示法。框架系統(tǒng)就像語義網(wǎng)絡那樣，框架的某些槽的側面值可 以是其它框架，從而能建立起節(jié)點是框架的網(wǎng)絡。不過這兩種表示法在使用上還是存在語義差異的，

16、即框架表示法更強調表示事物的內部結構利用框架的豐富表示結構，而語義網(wǎng)絡更強調表示事物間的關系。真題5:a導彈是一種飛行的攻擊敵方目標的武器。b導彈分為戰(zhàn)略導彈和戰(zhàn)術導彈，戰(zhàn)略導彈有巡航式導彈和彈道式導彈兩種，而戰(zhàn)術導 彈都是巡航式的。c戰(zhàn)術導彈可以用路基發(fā)射、飛機發(fā)射和軍艦發(fā)射。請分別用產(chǎn)生式、框架結構表示出上述內容。解析：產(chǎn)生式r1 : if是武器and自動飛行and攻擊敵方目標then導彈。產(chǎn)生式r2 : if是戰(zhàn)略導彈or戰(zhàn)術導彈then導彈。產(chǎn)生式 心:if是巡航式導彈or彈道式導彈then戰(zhàn)略導彈。產(chǎn)生式r4 : if戰(zhàn)術導彈then巡航式。產(chǎn)生式r5 : if路基發(fā)射or飛機發(fā)射o

17、r軍艦發(fā)射then戰(zhàn)術導彈?？蚣苊?part-of: 屬性：巡航式 發(fā)射方式：路基發(fā)射、飛機 發(fā)射、軍艦發(fā)射。框架名： part-of: 屬性：巡航式、彈道式框架名： 屬性：攻擊敵方目標?？蚣苊?ISA :武器。注意：此題只要掌握思路，考試時候隨便寫出幾條即可，不用刻意去背答案。五、啟發(fā)式搜索與代價樹沒啥說的，直接畫出代價樹寫結論吧。真題5:以下圖是一個交通圖，設A城是出發(fā)地，E是目的地，邊上的數(shù)字代表兩城之間的交通費。試求從 A到E最小費用的旅行路線。畫出廣度搜索代價樹。15分六、A算法啟發(fā)式搜索算法用來估計節(jié)點重要性的函數(shù)稱為估價函數(shù)。估價函數(shù)fn被定義為從初始節(jié)點 SO出發(fā)，經(jīng)過節(jié)點

18、n到達目標節(jié)點SG的所有路徑中最小路徑代價的估計值。它的一般形式為f n=gn+ hn其中，gn是從初始節(jié)點 SO到節(jié)點n的實際代價；hn是從節(jié)點n到目標節(jié)點SO的 最優(yōu)路徑的估計代價。對gn的值，可以按指向父節(jié)點的指針，從節(jié)點n反向跟蹤到初始節(jié)點SO,得到一條從初始節(jié)點 SO到節(jié)點n的最小代價路徑，然后把這條路徑上所有有向 邊的代價相加，就得到 gn的值。對hn的值，那么需要根據(jù)問題自身的特性來確定， 它表達的是問題自身的啟發(fā)性信息，因此也稱hn為啟發(fā)函數(shù)。例：八數(shù)碼難題。估價函數(shù)為 :fn=dn+ Wn其中，dn表示節(jié)點 n在搜索樹中的深度； wn表示節(jié)點 n中“不在位的數(shù)碼 個數(shù)。請計算

19、初始狀態(tài) SO的估價函數(shù)值fSO。解：在本例的估價函數(shù)中，取 g n=dn，h n=Wn。它說明是用從 SO到n 的路徑上的單位代價表示實際代價， 用n中“不在位的數(shù)碼個數(shù)作為啟發(fā)信息。 一般來說， 某節(jié)點中的不在位的數(shù)碼個數(shù)越多，說明它離目標節(jié)點越遠。對初始節(jié)點SO,由于d SO= O,假設W SO= x，因此有f SO =O+x=x全局擇優(yōu)搜索：每當需要擴展節(jié)點時，總是從 Open表的所有節(jié)點中選擇一個估價函數(shù)值最小的節(jié)點進 行擴展，根據(jù)各節(jié)點的估價函數(shù)值，對Open表中的全部節(jié)點按從小到大的順序重新進行排序，直到求出結果。由于上述算法要對Open表中的全部節(jié)點按其估價函數(shù)值從小到大重新進

20、行排序，這樣在算法中先取出的節(jié)點就一定是Open表的所有節(jié)點中估價函數(shù)值最小的一個節(jié)點。注意：書中給出的搜索過程較為抽象，大家只要知道每次都選擇估價最小的點就可以了，具體細節(jié)會在下面的真題中給予說明。g(x)表示已走步數(shù)真題6:用全局擇優(yōu)搜索法解決八數(shù)碼難題。初始棋局和目標棋局如下:啟發(fā)函數(shù)，h(x)表示每一個將牌與目標位置的距離總和，畫出相應的狀態(tài)空間搜索樹，利用全局擇優(yōu)算法，狀態(tài)空間每次都選出 初始狀態(tài)SO:closed 表。open表中代價最小的解析：狀態(tài)空間搜索樹如以下圖所示。1475注意：關于答案中第二行中紅色數(shù)字4、4、5、5的解釋：對于答案第二行第一個圖，g(x)為啟發(fā)函數(shù)，即不

21、在位個數(shù)相對于SG來說位置不同的數(shù)碼個數(shù)，有2、8、1三個數(shù)，h(x)為當前樹深度，顯然為1,故第一個圖的估值函數(shù)為3+1=4。對于第二行左起第二個圖同第一個圖。對于第二行左起第三個圖，不在位的數(shù)字有1、2、& 4共4個數(shù)，故g(x)=4,又因為h(x)即深度為1，所以估值函數(shù)為 5;第四個圖同理，這樣便產(chǎn)生4、4、5、5等4個紅色數(shù)字。每次只需展開權值最小的圖，直到求出最優(yōu)解為止，如第三行4個圖的估價函數(shù)分別為5、6、4、6，應選擇第三個圖，因為它的權值最小。七、狀態(tài)空間描述大家可以回憶猴子爬箱子吃香蕉的那個問題，這類問題很容易解答真題7:桶、罐、和瓶分別能盛油 5千克、3.5千克、1、5千

22、克，現(xiàn)在5千克的桶裝滿 了油。要求只利用這三件容器把油分成2份，每份2.5千克。設計一個解決分油問題的產(chǎn)生式系統(tǒng)，給出問題狀態(tài)描述法、初始狀態(tài)、與目標狀態(tài)及產(chǎn)生式規(guī)那么至少給出4條規(guī)那么，但不必給出所有規(guī)那么。20分解析：用(x,y,z)表示桶、罐、瓶子里油的數(shù)量。那么初始狀態(tài)為：(5,0,0)，目標狀態(tài)為：(2.5,2.5,0)。規(guī)那么集：r1:(5,0,0)(1.5,3.5,0) r5:(3,0.5,1.5)(4.5,0.5,0) r9: (1,2.5,1.5)(,0)r2: (1.5,3.5,0)(1.5,2,1.5) r6:(4.5,0.5,0)(4.5,0,0.5)r3: (1.5,

23、2,1.5) (3,2,0)r7:(4.5,0,0.5)(1,3.5,0.5)r4: (3,2,0) (3,0.5,1.5)r8:(1,3.5,0.5)(1,2.5,1.5)真題 8：有 4個人過河只有一條船，最多可乘坐兩人，假設單個過各需要1,1,5,9 分鐘，假設兩個一起過，那么需要的時間以多的為準比方需要 5分和 9 分的兩人同時乘坐，那么需要 9 分，要求最少需要多少分鐘。(1)用產(chǎn)生式系統(tǒng)描述該問題，需求給出綜合數(shù)據(jù)庫狀態(tài)空間的定義，規(guī)那么集最少給 出 5 條規(guī)那么，但不必寫出所有規(guī)那么初始狀態(tài)和結束狀態(tài)。解析：設四個人分別為 A、B、C、D , H代表河，用“ H左邊的字母表示相應

24、的對象沒有 過河，“H右邊的字母表示相應的對象已經(jīng)過河了。初始狀態(tài)： A、 B、 C、 D、 H 目標狀態(tài)： H、 A、 B、 C、 D一次過河中的非法狀態(tài)即同時有3人或3人以上過河：A、H、B、C、D、 B、H、A、C、 D、C、 H、 A、 B、 D、D、 H、 A、 B、 C、H、 A、 B、 C、 D 問題的局部規(guī)那么集描述為：(隨便寫幾個合理的即可，有很多狀態(tài))r1：A、 B、 C、 D、 H C、 D、 H、 A、 Br2：C、 D、 H、 A、 B C、 D、 A、 H、 Br3：C、 D、 A、 H、 B A、 H、 C、 D、 Br4：A、 H、 C、 D、 B A、 B、

25、H、 C、 Dr5：A、 B、 H、 C、 D H、 A、 B、 C、 Dr6：A、 B、 C、 D、 H B、 D、 H、 A、 C(2)定義一個函數(shù) h 函數(shù)，并說明是否滿足 A* 條件注意：這是所有 9 道題目中唯一需要 A* 算法的構造的，因為含金量比擬低，故不在此介紹A* 算法，有想了解的同學請自行參閱課件。八、a - 3剪枝需要極大極小算法作為根底假設博弈的一方為 MAX，另一方為 MIN。在博弈過程的每一步，可供MAX和MIN選擇的行動方案都可能有多種。 從 MAX 方的觀點看， 可供自己選擇的那些行動方案之間是 “或的關系，而對那些可供 MIN 選擇的行動方案之間那么是“與的關系。在博弈樹中， 那些下一步該 MAX 走步的節(jié)點稱為 MAX 節(jié)點，而下一步該 MIN 走步的節(jié)點稱為 MIN 節(jié) 點。站在 MAX 方，所有能使 MAX 方獲勝的節(jié)點都是可解節(jié)點，所有能使 MIN 方獲勝的 節(jié)點都是不可解節(jié)點。需利用估價函數(shù) f(n) 對葉節(jié)點進行靜態(tài)評估，對 MAX 有利的節(jié)點其 估價函數(shù)取正值；那些對 MIN 有利的節(jié)點，其估價函數(shù)取負值；那些使雙方均等的節(jié)點， 其估價函數(shù)取接近于 0 的值。極大極小過程：為了計算非葉節(jié)點的值，必須從葉節(jié)點向上倒推。對于MAX 節(jié)點，由于 MAX 方總是選 擇估值最大的走步，因此， MAX 節(jié)點