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

1、第三章 搜索推理技術(shù)3-1 什么是圖搜索過(guò)程?其中，重排OPEN表意味著什么，重排的原則是什么?圖搜索的一般過(guò)程如下：(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表中。稱(chēng)此節(jié)點(diǎn)為節(jié)點(diǎn)n，它是CLOSED表中節(jié)點(diǎn)的編號(hào)(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) 對(duì)那些未曾在G中出現(xiàn)過(guò)的(既未曾在OPEN表上或CLOSED表上出現(xiàn)過(guò)的)M成員設(shè)置一個(gè)通向n的指針，并將它們加進(jìn)OPEN表。對(duì)已經(jīng)在OPEN或CLOSED表上的每個(gè)M成員，確定是否需要更改通到n的指針?lè)较?。?duì)已在CLOSED表上的每個(gè)M成員，確定是否需要更改圖G中通向它的每個(gè)后裔節(jié)點(diǎn)的指針?lè)较颉?8) 按某一任意方式或按某個(gè)探試值，重排OPEN表。 (9) GO LOOP。重排OPEN表意味著，在第(6)步中，將優(yōu)先擴(kuò)展哪個(gè)節(jié)點(diǎn)，不同的排序標(biāo)準(zhǔn)對(duì)應(yīng)著不同的搜索策略。重排的原則當(dāng)視具體需求而定，不同的原則對(duì)應(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è)空表，則沒(méi)有解，失敗退出；否則繼續(xù)。(3) 把第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放入CLOSED擴(kuò)展節(jié)點(diǎn)表中。(4) 擴(kuò)展節(jié)點(diǎn)n。如果沒(méi)有后繼節(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表的前頭。如果沒(méi)有后裔，則轉(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è)空表，則沒(méi)有解而失敗退出。(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。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向第(2)步。(6) 對(duì)于節(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、?請(qǐng)結(jié)合例子說(shuō)明之。任一謂詞演算公式可以化成一個(gè)子句集。其變換過(guò)程由下列九個(gè)步驟組成：(1)消去蘊(yùn)涵符號(hào)將蘊(yùn)涵符號(hào)化為析取和否定符號(hào)(2)減少否定符號(hào)的轄域 每個(gè)否定符號(hào)最多只用到一個(gè)謂詞符號(hào)上，并反復(fù)應(yīng)用狄·摩根定律(3)對(duì)變量標(biāo)準(zhǔn)化對(duì)啞元改名以保證每個(gè)量詞有其自己唯一的啞元(4)消去存在量詞引入Skolem函數(shù)，消去存在量詞如果要消去的存在量詞不在任何一個(gè)全稱(chēng)量詞的轄域內(nèi)，那么我們就用不含變量的Skolem函數(shù)即常量。(5)化為前束形把所有全稱(chēng)量詞移到公式的左邊，并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分。前束形 = (前綴) (母式) 前綴 = 全稱(chēng)量詞串母式 = 無(wú)量詞

7、公式(6)把母式化為合取范式反復(fù)應(yīng)用分配律，將母式寫(xiě)成許多合取項(xiàng)的合取的形式，而每一個(gè)合取項(xiàng)是一些謂詞公式和(或)謂詞公式的否定的析取(7)消去全稱(chēng)量詞消去前綴，即消去明顯出現(xiàn)的全稱(chēng)量詞(8)消去連詞符號(hào)(合取)用合取項(xiàng)1,合取項(xiàng)2替換明顯出現(xiàn)的合取符號(hào)(9)更換變量名稱(chēng)更換變量符號(hào)的名稱(chēng)，使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的子句中3-4 如何通過(guò)消解反演求取問(wèn)題的答案?給出一個(gè)公式集S和目標(biāo)公式L，通過(guò)反證或反演來(lái)求證目標(biāo)公式L，其證明步驟如下：(1)否定L，得L；(2)把L添加到S中去；(3)把新產(chǎn)生的集合L，S化成子句集；(4)應(yīng)用消解原理，力圖推導(dǎo)出一個(gè)表示矛盾的空子句N(xiāo)IL。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中的自由變?cè)瑒t(ANY x)A 和 (EXT x)A 都是合式公式(5) 只有按規(guī)則(1)(4)求得的公式，才是合式公式等價(jià)關(guān)系有：否定之否定蘊(yùn)含與與或形式的等價(jià)狄.摩根定律分配律交換律結(jié)合律逆否律否定跨越量詞全稱(chēng)量詞同與或連詞量詞中的啞元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í)針?lè)较?上、右、下、左)試探，嘗試移動(dòng)空格，將最大深度定為5S0(So)28163754S128316754S228316475S328316475S428314765S523184765S62318476523184765S712384765S8(Sg)123847653-8 應(yīng)用最

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

11、ve(x,y)和表示卸下包裹的unload(z)；對(duì)于每個(gè)操作符，都有一定的先決條件和結(jié)果。試說(shuō)明狀態(tài)空間問(wèn)題求解系統(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)對(duì)每個(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)原問(wèn)題就轉(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部分推理的過(guò)程，它是從事實(shí)或狀況向目標(biāo)或動(dòng)作進(jìn)行操作的從

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

14、當(dāng)總數(shù)據(jù)庫(kù)內(nèi)容更新后都要遍歷整個(gè)規(guī)則庫(kù)，推理效率低目標(biāo)的選擇具有盲目性，可能會(huì)求解許多假的目標(biāo)；當(dāng)可能的結(jié)論數(shù)目很多時(shí)，推理效率不高；當(dāng)規(guī)則的右部是執(zhí)行某種動(dòng)作而不是結(jié)論時(shí)，逆向推理不便使用適用場(chǎng)合已知初始數(shù)據(jù)，而無(wú)法提供推理目標(biāo)，或解空間很大的一類(lèi)問(wèn)題，如監(jiān)控，預(yù)測(cè)，規(guī)劃，設(shè)計(jì)等問(wèn)題結(jié)論單一或者已知目標(biāo)結(jié)論，而要求驗(yàn)證的系統(tǒng)，如選擇，分類(lèi)，故障診斷等問(wèn)題典型系統(tǒng)CLIPS, OPSPROLOG雙向推理結(jié)合了正向推理和逆向推理的長(zhǎng)處，克服了兩者的短處，其控制策略比兩者都要復(fù)雜3-12 為什么需要采用系統(tǒng)組織技術(shù)?有哪幾種系統(tǒng)組織技術(shù)?如果不采用系統(tǒng)組織技術(shù)，而直接寫(xiě)出包含所有知識(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)生沖突，這將使問(wèn)題變得愈來(lái)愈困難(2) 在問(wèn)題求解過(guò)程中，由于每一步都必須考慮所有規(guī)則，效率就會(huì)大大降低，然而，實(shí)際上卻往往是只有應(yīng)用完一組規(guī)則之后，才考慮另一組別的規(guī)則(3) 一種問(wèn)題求解技術(shù)和知識(shí)表達(dá)形式可能對(duì)問(wèn)題的某一部分是最好的，而對(duì)另一部分卻不是最好的因此，采用系統(tǒng)組織技術(shù)，將一個(gè)大系統(tǒng)中的知識(shí)分成一組相對(duì)獨(dú)立的模塊比較合適。有3種系統(tǒng)組織技術(shù)：議程表、黑板法和Delta極小搜索法3-13 研究不確定性推理有何意義?有哪幾種不確定性?不確定性推

16、理是研究復(fù)雜系統(tǒng)不完全性和不確定性的有力工具。有3種不確定性，關(guān)于證據(jù)的不確定性(觀測(cè)有誤差)，關(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í)問(wèn)題領(lǐng)域中的3類(lèi)情況，即不完全的信息、不斷變化的情況、以及求解復(fù)雜問(wèn)題過(guò)程中生成的假設(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)，無(wú)論何時(shí)，只要在IN假設(shè)中的節(jié)點(diǎn)為IN, OUT假設(shè)中的節(jié)點(diǎn)為OUT, 則結(jié)論節(jié)點(diǎn)往往為IN，于是條件證明的證實(shí)有效。3-15 在什么情況下需要采用不確定推理或非單調(diào)推理?不完全的信息、不斷變化的情況、以及求解復(fù)雜問(wèn)題過(guò)程中生成的假設(shè)3-16 下列語(yǔ)句是一些幾何定理，把這些語(yǔ)句表示為基于規(guī)則的幾何證明系統(tǒng)的產(chǎn)生式規(guī)則：(1) 兩個(gè)全等三角形的各對(duì)應(yīng)角相等。(2) 兩個(gè)全等三角形的各對(duì)應(yīng)邊相等。(3) 各對(duì)應(yīng)邊相等的三角形是全等三角形。(4) 等腰三角形的兩底角相等。規(guī)則(1): IF 兩個(gè)三角形全等 THEN 各對(duì)應(yīng)角相等

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