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

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

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

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

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

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

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

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

8、叫合適公式?合適公式有哪些等價(jià)關(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)求得的公式，才是合式公式等價(jià)關(guān)系有：否定之否定蘊(yùn)含與與或形式的等價(jià)狄.摩根定律分配律交換律結(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ù)碼難題按順時(shí)針方向(上、右、下、左)試探，嘗試移動空格，將最大深度定為5S0(So)28163754S128316754S228316475S328316475S428314765S523184765S62318476523184765S712384765S8(Sg)123847653-8 應(yīng)用最

10、新的方法來表達(dá)傳教士和野人問題，編寫一個(gè)計(jì)算機(jī)程序，以求得安全渡過全部6個(gè)人的解答。提示：在應(yīng)用狀態(tài)空間表示和搜索方法時(shí)，可用(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í)例數(shù)據(jù)加以說明。3-10 一個(gè)機(jī)器人駕駛卡車，攜帶包裹(編號分別為1、2和3)分別投遞到林(LIN)、吳(WU)和胡(HU)3家住宅處。規(guī)定了某些簡單的操作符，如表示駕駛方位的dri

11、ve(x,y)和表示卸下包裹的unload(z)；對于每個(gè)操作符，都有一定的先決條件和結(jié)果。試說明狀態(tài)空間問題求解系統(tǒng)如何能夠應(yīng)用謂詞演算求得一個(gè)操作符序列，該序列能夠生成一個(gè)滿足AT(#1，LIN)AT(#2，WU)AT(#3,HU)的目標(biāo)狀態(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)目標(biāo)狀態(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)對每個(gè)操作符都有一定的先決條件和結(jié)果，詳細(xì)如下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)換為尋找一個(gè)可將初始狀態(tài)轉(zhuǎn)換到目標(biāo)狀態(tài)的操作序列如何求得該操作序列?3-11 規(guī)則演繹系統(tǒng)和產(chǎn)生式系統(tǒng)有哪幾種推理方式?各自的特點(diǎn)為何?規(guī)則演繹系統(tǒng)的推理方式有正向推理、逆向推理和雙向推理項(xiàng)目正向推理逆向推理推理方向從if部分向then部分推理的過程，它是從事實(shí)或狀況向目標(biāo)或動作進(jìn)行操作的從

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

14、當(dāng)總數(shù)據(jù)庫內(nèi)容更新后都要遍歷整個(gè)規(guī)則庫，推理效率低目標(biāo)的選擇具有盲目性，可能會求解許多假的目標(biāo)；當(dāng)可能的結(jié)論數(shù)目很多時(shí)，推理效率不高；當(dāng)規(guī)則的右部是執(zhí)行某種動作而不是結(jié)論時(shí)，逆向推理不便使用適用場合已知初始數(shù)據(jù)，而無法提供推理目標(biāo)，或解空間很大的一類問題，如監(jiān)控，預(yù)測，規(guī)劃，設(shè)計(jì)等問題結(jié)論單一或者已知目標(biāo)結(jié)論，而要求驗(yàn)證的系統(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)到目標(biāo)狀態(tài)的路徑，這種方法有嚴(yán)重的缺點(diǎn)：(1) 隨著規(guī)則的增加，既要加入新的規(guī)則，又要使新規(guī)則不與現(xiàn)有規(guī)則產(chǎn)生沖突，這將使問題變得愈來愈困難(2) 在問題求解過程中，由于每一步都必須考慮所有規(guī)則，效率就會大大降低，然而，實(shí)際上卻往往是只有應(yīng)用完一組規(guī)則之后，才考慮另一組別的規(guī)則(3) 一種問題求解技術(shù)和知識表達(dá)形式可能對問題的某一部分是最好的，而對另一部分卻不是最好的因此，采用系統(tǒng)組織技術(shù)，將一個(gè)大系統(tǒng)中的知識分成一組相對獨(dú)立的模塊比較合適。有3種系統(tǒng)組織技術(shù)：議程表、黑板法和Delta極小搜索法3-13 研究不確定性推理有何意義?有哪幾種不確定性?不確定性推

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

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

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