《人工智能及其應(yīng)用》(蔡自興)課后習題答案第3章

1、第三章 搜索推理技術(shù)3-1 什么是圖搜索過程?其中，重排OPEN表意味著什么，重排的原則是什么?圖搜索的一般過程如下：(1) 建立一個搜索圖G(初始只含有起始節(jié)點S)，把S放到未擴展節(jié)點表中（OPEN表）中。(2) 建立一個已擴展節(jié)點表（CLOSED表），其初始為空表。(3) LOOP：若OPEN表是空表，則失敗退出。(4) 選擇OPEN表上的第一個節(jié)點，把它從OPEN表移出并放進CLOSED表中。稱此節(jié)點為節(jié)點n，它是CLOSED表中節(jié)點的編號(5) 若n為一目標節(jié)點，則有解并成功退出。此解是追蹤圖G中沿著指針從n到S這條路徑而得到的(指針將在第7步中設(shè)置)(6) 擴展節(jié)點n，生成不是n的祖

2、先的那些后繼節(jié)點的集合M。將M添入圖G中。 (7) 對那些未曾在G中出現(xiàn)過的(既未曾在OPEN表上或CLOSED表上出現(xiàn)過的)M成員設(shè)置一個通向n的指針，并將它們加進OPEN表。對已經(jīng)在OPEN或CLOSED表上的每個M成員，確定是否需要更改通到n的指針方向。對已在CLOSED表上的每個M成員，確定是否需要更改圖G中通向它的每個后裔節(jié)點的指針方向。(8) 按某一任意方式或按某個探試值，重排OPEN表。 (9) GO LOOP。重排OPEN表意味著，在第(6)步中，將優(yōu)先擴展哪個節(jié)點，不同的排序標準對應(yīng)著不同的搜索策略。重排的原則當視具體需求而定，不同的原則對應(yīng)著不同的搜索策略，如果想盡快地找到

3、一個解，則應(yīng)當將最有可能達到目標節(jié)點的那些節(jié)點排在OPEN表的前面部分，如果想找到代價最小的解，則應(yīng)當按代價從小到大的順序重排OPEN表。3-2 試舉例比較各種搜索方法的效率。寬度優(yōu)先搜索(1) 把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標節(jié)點，則求得一個解答)。(2) 如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。(3) 把第一個節(jié)點(節(jié)點n)從OPEN表移出，并把它放入CLOSED擴展節(jié)點表中。(4) 擴展節(jié)點n。如果沒有后繼節(jié)點，則轉(zhuǎn)向上述第(2)步。(5) 把n的所有后繼節(jié)點放到OPEN表的末端，并提供從這些后繼節(jié)點回到n的指針。(6) 如果n的任一個后繼節(jié)點是個目標節(jié)點，

4、則找到一個解答，成功退出；否則轉(zhuǎn)向第(2)步。有界深度優(yōu)先搜索(1) 把起始節(jié)點S放到未擴展節(jié)點OPEN表中。如果此節(jié)點為一目標節(jié)點，則得到一個解。(2) 如果OPEN為一空表，則失敗退出。(3) 把第一個節(jié)點(節(jié)點n)從OPEN表移到CLOSED表。(4) 如果節(jié)點n的深度等于最大深度，則轉(zhuǎn)向(2)。(5) 擴展節(jié)點n，產(chǎn)生其全部后裔，并把它們放入OPEN表的前頭。如果沒有后裔，則轉(zhuǎn)向(2)。(6) 如果后繼節(jié)點中有任一個為目標節(jié)點，則求得一個解，成功退出；否則，轉(zhuǎn)向(2)。等代價搜索方法以g(i)的遞增順序擴展其節(jié)點，其算法如下：(1) 把起始節(jié)點S放到未擴展節(jié)點表OPEN中。如果此起始節(jié)

5、點為一目標節(jié)點，則求得一個解;否則令g(S)=0。(2) 如果OPEN是個空表，則沒有解而失敗退出。(3) 從OPEN表中選擇一個節(jié)點i，使其g(i)為最小。如果有幾個節(jié)點都合格，那么就要選擇一個目標節(jié)點作為節(jié)點i(要是有目標節(jié)點的話)；否則，就從中選一個作為節(jié)點i。把節(jié)點i從OPEN表移至擴展節(jié)點表CLOSED中。(4) 如果節(jié)點i為目標節(jié)點，則求得一個解。(5) 擴展節(jié)點i。如果沒有后繼節(jié)點，則轉(zhuǎn)向第(2)步。(6) 對于節(jié)點i的每個后繼節(jié)點j，計算g(j)=g(i)+c(i,j)，并把所有后繼節(jié)點j放進OPEN表。提供回到節(jié)點i的指針。(7) 轉(zhuǎn)向第(2)步。3-3 化為子句形有哪些步驟

6、?請結(jié)合例子說明之。任一謂詞演算公式可以化成一個子句集。其變換過程由下列九個步驟組成：(1)消去蘊涵符號將蘊涵符號化為析取和否定符號(2)減少否定符號的轄域 每個否定符號最多只用到一個謂詞符號上，并反復(fù)應(yīng)用狄·摩根定律(3)對變量標準化對啞元改名以保證每個量詞有其自己唯一的啞元(4)消去存在量詞引入Skolem函數(shù)，消去存在量詞如果要消去的存在量詞不在任何一個全稱量詞的轄域內(nèi)，那么我們就用不含變量的Skolem函數(shù)即常量。(5)化為前束形把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。前束形 = (前綴) (母式) 前綴 = 全稱量詞串母式 = 無量詞

7、公式(6)把母式化為合取范式反復(fù)應(yīng)用分配律，將母式寫成許多合取項的合取的形式，而每一個合取項是一些謂詞公式和(或)謂詞公式的否定的析取(7)消去全稱量詞消去前綴，即消去明顯出現(xiàn)的全稱量詞(8)消去連詞符號(合取)用合取項1,合取項2替換明顯出現(xiàn)的合取符號(9)更換變量名稱更換變量符號的名稱，使一個變量符號不出現(xiàn)在一個以上的子句中3-4 如何通過消解反演求取問題的答案?給出一個公式集S和目標公式L，通過反證或反演來求證目標公式L，其證明步驟如下：(1)否定L，得L；(2)把L添加到S中去；(3)把新產(chǎn)生的集合L，S化成子句集；(4)應(yīng)用消解原理，力圖推導(dǎo)出一個表示矛盾的空子句NIL。3-5 什么

8、叫合適公式?合適公式有哪些等價關(guān)系?合式公式的遞歸定義為：(1) 原子謂詞公式是合式公式(2) 若A為合式公式，則A的否定也是合式公式(3) 若A、B都是合式公式，則A AND B, AOR B, AèB, Aß>B 也都是合式公式(4) 若A是合式公式，x為A中的自由變元，則(ANY x)A 和 (EXT x)A 都是合式公式(5) 只有按規(guī)則(1)(4)求得的公式，才是合式公式等價關(guān)系有：否定之否定蘊含與與或形式的等價狄.摩根定律分配律交換律結(jié)合律逆否律否定跨越量詞全稱量詞同與或連詞量詞中的啞元3-6 用寬度優(yōu)先搜索求圖3.33所示迷宮的出路。圖 3.33 迷宮一

9、例第一步SàAàB第二步BàHBàC第三步HàGCàF最終路徑為SàAàBàCàF3-7 用有界深度優(yōu)先搜索方法求解圖3.34所示八數(shù)碼難題。2812316384754765 So Sg圖 3-34八數(shù)碼難題按順時針方向(上、右、下、左)試探，嘗試移動空格，將最大深度定為5S0(So)28163754S128316754S228316475S328316475S428314765S523184765S62318476523184765S712384765S8(Sg)123847653-8 應(yīng)用最

10、新的方法來表達傳教士和野人問題，編寫一個計算機程序，以求得安全渡過全部6個人的解答。提示：在應(yīng)用狀態(tài)空間表示和搜索方法時，可用(Nm，Nc)來表示狀態(tài)描述，其中Nm和Nc分別為傳教士和野人的人數(shù)。初始狀態(tài)為(3，3)，而可能的中間狀態(tài)為(0，1)，(0，2)，(0，3)，(1，1)，(2，1)，(2，2)，(3，0)，(3，1)和(3，2)等。3-9 試比較寬度優(yōu)先搜索、有界深度優(yōu)先搜索及有序搜索的搜索效率，并以實例數(shù)據(jù)加以說明。3-10 一個機器人駕駛卡車，攜帶包裹(編號分別為1、2和3)分別投遞到林(LIN)、吳(WU)和胡(HU)3家住宅處。規(guī)定了某些簡單的操作符，如表示駕駛方位的dri

11、ve(x,y)和表示卸下包裹的unload(z)；對于每個操作符，都有一定的先決條件和結(jié)果。試說明狀態(tài)空間問題求解系統(tǒng)如何能夠應(yīng)用謂詞演算求得一個操作符序列，該序列能夠生成一個滿足AT(#1，LIN)AT(#2，WU)AT(#3,HU)的目標狀態(tài)。初始狀態(tài)可描述為：AT(#1, LIN) AND AT(#2, WU) AND AT(#1, HU) AND AT(#1, CAR) AND AT(#2, CAR) AND AT(#3, CAR)目標狀態(tài)可描述為：AT(#1, LIN) AND AT(#2, WU) AND AT(#1, HU) AND AT(#1, CAR) AND AT(#2,

12、CAR) AND AT(#3, CAR)對每個操作符都有一定的先決條件和結(jié)果，詳細如下drive(x, y)先決條件：AT(CAR, x)結(jié)果： AT(CAR, y)unload(z)先決條件：AT(z, CAR) AND AT(CAR, x)結(jié)果： AT(z, CAR) AND AT(z, x)原問題就轉(zhuǎn)換為尋找一個可將初始狀態(tài)轉(zhuǎn)換到目標狀態(tài)的操作序列如何求得該操作序列?3-11 規(guī)則演繹系統(tǒng)和產(chǎn)生式系統(tǒng)有哪幾種推理方式?各自的特點為何?規(guī)則演繹系統(tǒng)的推理方式有正向推理、逆向推理和雙向推理項目正向推理逆向推理推理方向從if部分向then部分推理的過程，它是從事實或狀況向目標或動作進行操作的從

13、then部分向if部分推理的過程，它是從目標或動作向事實或狀況進行操作的目標表達式文字的析取任意形式事實表達式任意形式文字的合取雙向推理組合了正向推理和逆向推理的優(yōu)點，克服了各自的缺點，具有更高的搜索求解效率。產(chǎn)生式系統(tǒng)的推理方式有正向推理、逆向推理和雙向推理項目正向推理逆向推理驅(qū)動方式數(shù)據(jù)驅(qū)動目標驅(qū)動推理方法從一組數(shù)據(jù)出發(fā)向前推導(dǎo)結(jié)論從可能的解答出發(fā)，向后推理驗證解答啟動方法從一個事件啟動由詢問關(guān)于目標狀態(tài)的一個問題而啟動透明程序不能解釋其推理過程可解釋其推理過程推理方向由底向上推理由頂向下推理優(yōu)點算法簡單，容易實現(xiàn)搜索目的性強，推理效率高缺點盲目搜索，可能會求解許多與總目標無關(guān)的子目標，每

14、當總數(shù)據(jù)庫內(nèi)容更新后都要遍歷整個規(guī)則庫，推理效率低目標的選擇具有盲目性，可能會求解許多假的目標；當可能的結(jié)論數(shù)目很多時，推理效率不高；當規(guī)則的右部是執(zhí)行某種動作而不是結(jié)論時，逆向推理不便使用適用場合已知初始數(shù)據(jù)，而無法提供推理目標，或解空間很大的一類問題，如監(jiān)控，預(yù)測，規(guī)劃，設(shè)計等問題結(jié)論單一或者已知目標結(jié)論，而要求驗證的系統(tǒng)，如選擇，分類，故障診斷等問題典型系統(tǒng)CLIPS, OPSPROLOG雙向推理結(jié)合了正向推理和逆向推理的長處，克服了兩者的短處，其控制策略比兩者都要復(fù)雜3-12 為什么需要采用系統(tǒng)組織技術(shù)?有哪幾種系統(tǒng)組織技術(shù)?如果不采用系統(tǒng)組織技術(shù)，而直接寫出包含所有知識的規(guī)則，并讓系

15、統(tǒng)利用這些規(guī)則，找出一條從給定狀態(tài)到目標狀態(tài)的路徑，這種方法有嚴重的缺點：(1) 隨著規(guī)則的增加，既要加入新的規(guī)則，又要使新規(guī)則不與現(xiàn)有規(guī)則產(chǎn)生沖突，這將使問題變得愈來愈困難(2) 在問題求解過程中，由于每一步都必須考慮所有規(guī)則，效率就會大大降低，然而，實際上卻往往是只有應(yīng)用完一組規(guī)則之后，才考慮另一組別的規(guī)則(3) 一種問題求解技術(shù)和知識表達形式可能對問題的某一部分是最好的，而對另一部分卻不是最好的因此，采用系統(tǒng)組織技術(shù)，將一個大系統(tǒng)中的知識分成一組相對獨立的模塊比較合適。有3種系統(tǒng)組織技術(shù)：議程表、黑板法和Delta極小搜索法3-13 研究不確定性推理有何意義?有哪幾種不確定性?不確定性推

16、理是研究復(fù)雜系統(tǒng)不完全性和不確定性的有力工具。有3種不確定性，關(guān)于證據(jù)的不確定性(觀測有誤差)，關(guān)于結(jié)論的不確定性和多個規(guī)則支持同一事實時的不確定性。3-14 單調(diào)推理有何局限性?什么叫缺省推理?非單調(diào)推理系統(tǒng)如何證實一個節(jié)點的有效性?單調(diào)系統(tǒng)不能很好地處理常常出現(xiàn)在現(xiàn)實問題領(lǐng)域中的3類情況，即不完全的信息、不斷變化的情況、以及求解復(fù)雜問題過程中生成的假設(shè)有兩種方法可以證實節(jié)點的有效性：(1) 支持表。 ( SL (IN-節(jié)點表) (OUT- 節(jié)點表) )如果某節(jié)點的IN節(jié)點表中提到的節(jié)點當前都是IN, 且OUT節(jié)點表中提到的節(jié)點當前都是OUT，則它是有效的(2) 條件證明。( CP(結(jié)論)(

17、IN-假設(shè))(OUT-假設(shè)) )條件證明(CP)的證實表示有前提的論點，無論何時，只要在IN假設(shè)中的節(jié)點為IN, OUT假設(shè)中的節(jié)點為OUT, 則結(jié)論節(jié)點往往為IN，于是條件證明的證實有效。3-15 在什么情況下需要采用不確定推理或非單調(diào)推理?不完全的信息、不斷變化的情況、以及求解復(fù)雜問題過程中生成的假設(shè)3-16 下列語句是一些幾何定理，把這些語句表示為基于規(guī)則的幾何證明系統(tǒng)的產(chǎn)生式規(guī)則：(1) 兩個全等三角形的各對應(yīng)角相等。(2) 兩個全等三角形的各對應(yīng)邊相等。(3) 各對應(yīng)邊相等的三角形是全等三角形。(4) 等腰三角形的兩底角相等。規(guī)則(1): IF 兩個三角形全等 THEN 各對應(yīng)角相等

18、規(guī)則(2): IF 兩個三角形全等 THEN 各對應(yīng)邊相等規(guī)則(3): IF 兩個三角形各對應(yīng)邊相等 THEN 兩三角形全等規(guī)則(4): IF 它是等腰三角形 THEN 它的兩底角相等 出師表兩漢：諸葛亮先帝創(chuàng)業(yè)未半而中道崩殂，今天下三分，益州疲弊，此誠危急存亡之秋也。然侍衛(wèi)之臣不懈于內(nèi)，忠志之士忘身于外者，蓋追先帝之殊遇，欲報之于陛下也。誠宜開張圣聽，以光先帝遺德，恢弘志士之氣，不宜妄自菲薄，引喻失義，以塞忠諫之路也。宮中府中，俱為一體；陟罰臧否，不宜異同。若有作奸犯科及為忠善者，宜付有司論其刑賞，以昭陛下平明之理；不宜偏私，使內(nèi)外異法也。侍中、侍郎郭攸之、費祎、董允等，此皆良實，志慮忠純，是以先帝簡拔以遺陛下：愚以為宮中之事，事無大小，悉以咨之，然后施行，必能裨補闕漏，有所廣益。將軍向?qū)櫍孕惺缇?，曉暢軍事，試用于昔日，先帝稱之曰“能”，是以眾議舉寵為督：愚以為營中之事，悉以咨之，必能使行陣和睦，優(yōu)劣得所。 親賢臣，遠小人，此先漢所以興隆也；親小人，遠賢臣，此后漢所以傾頹也。先帝在時，每與臣論此事，未嘗不嘆息痛恨于桓、靈也。侍中、尚書、長史、參軍，此悉貞良死節(jié)之臣，愿陛下親之、信之，則漢室之隆，可計日而待也。臣本布衣，躬耕于南陽，茍全性命于亂世，不求聞達于諸侯。先帝不以臣卑鄙，猥