人工智能課后題答案20

定義三元組m,c,b）,表示野人在河左岸的認(rèn)輸。規(guī)則集可以用兩種方式表示，兩種方法均可。中(xy)表示x個傳教士和y個野人上船渡河），因此共有16個規(guī)則（從左岸到右岸、右岸到左岸各八個）。注意：這里沒有(12)，因?yàn)樵摻M合在船上的傳教士人數(shù)少于野人人數(shù)。規(guī)則集如下：第二種方法：將規(guī)則集綜合在一起，簡化表示。規(guī)則集如下：定義兩元組L5,L2）定義三元組：(A,B,C)其中A,B,C分別表示三根立柱，均為表，表的元素為1～N之間的整數(shù)，表示N個不同大小的盤子，數(shù)值小的數(shù)表示小盤子，數(shù)值大的數(shù)表示大盤子。表的第一個元素表示立柱最上面的柱子，其余類推。為了方便表示規(guī)則集，引入以下幾個函數(shù)：規(guī)則集：r1:IF(A,B,C)and(first(A)<first(B))THEN(tail(A),cons(first(A),B),C)r2:IF(A,B,C)and(first(A)<first(C))THEN(tail(A),B,cons(first(A),C))r3:IF(A,B,C)and(first(B)<first(C))THEN(A,tail(B),cons(first(B),C))r4:IF(A,B,C)and(first(B)<first(A))THEN(cons(first(B),A),tail(B),C)r5:IF(A,B,C)and(first(C)<first(A))THEN(cons(first(C),A),B,tail(C))r6:IF(A,B,C)and(first(C)<first(B))THEN(A,cons(first(C),B),tail(C))），(),())問題的狀態(tài)規(guī)模：每一個盤子都有三中選擇：在A上、或者在B上、定義5元組M,B,Box,On,H）其中：其中x,y,z,w為變量定義四元組：（x,y,z,n）提示：將十進(jìn)制數(shù)分為整數(shù)部分和小數(shù)部分兩部分。用四元組(a,b,c,d)表示綜合數(shù)據(jù)庫分別定義整數(shù)的轉(zhuǎn)換規(guī)則和小數(shù)的轉(zhuǎn)換規(guī)則，一次規(guī)則的執(zhí)行，轉(zhuǎn)換得到二進(jìn)制數(shù)的一位。答：說明一個產(chǎn)生式系統(tǒng)是可交換的，就是要證明該產(chǎn)生式系統(tǒng)滿足可交換產(chǎn)生式系統(tǒng)的三條性質(zhì)。（1）該產(chǎn)生式系統(tǒng)以整數(shù)的集合為綜合數(shù)據(jù)庫，其規(guī)則是將集合中的兩個整數(shù)相乘后加入到數(shù)據(jù)庫的子集，所以原來的規(guī)則在新數(shù)據(jù)庫中均可以使用。所以滿足可交換產(chǎn)生式系統(tǒng)的第一條性質(zhì)。（2）該產(chǎn)生式系統(tǒng)以某個整數(shù)的子集的出現(xiàn)為目標(biāo)條件，由于規(guī)則執(zhí)行的結(jié)果只是向數(shù)據(jù)足目標(biāo)了，即出現(xiàn)了所需要的整數(shù)子集，規(guī)則的執(zhí)行結(jié)果不可交換產(chǎn)生式系統(tǒng)的第二個性質(zhì)。中一條規(guī)則的執(zhí)行與其他的規(guī)則無關(guān)，所以R1中規(guī)則的執(zhí)行順序不件。因此這樣一個產(chǎn)生式系統(tǒng)是一個可交換的產(chǎn)生式系統(tǒng)。答：為了方便起見，我們用((AB)()())這樣的表表示一個狀態(tài)。這樣得到搜索圖如下：提示：可定義h為：設(shè)j節(jié)點(diǎn)是i節(jié)點(diǎn)的子節(jié)點(diǎn)，則根據(jù)走法不同，h(i)-h(j)的值和C(i,j)分為如下幾種情況：（1）B或W走到了相鄰的一個空格位置，此時：h(i)-h(j)=0,C(i），），），），ki是還未走過的城市間距離中n個最小的距離。顯然這兩個有意義的。對于像四皇后這樣的問題，啟發(fā)函數(shù)應(yīng)該是對找到解角線的長度來進(jìn)行評價。也可以定義h2=M+C。h1是滿足A*條件的，而h2不滿足。下面我們來證明h(n)＝M+C-2B是滿足A*我們分兩種情況考慮。先考慮船在左岸的情況。如果不考慮限制船送回來。這樣，船一個來回可以運(yùn)過河2人，而船仍然在左岸。而最后剩下的三個人，則可以一次將他們?nèi)繌淖蟀哆\(yùn)到右岸。所以，是因?yàn)橐粋€來回可以運(yùn)過去2人，需要個來回，而"來回"數(shù)不能是小數(shù)，需要向上取整，這個化簡有：擺渡?；営校?M+C+1)-2+1=M+C。岸。由于該擺渡次數(shù)是在不考慮限制條件下，推出的最少所需要的擺渡次數(shù)。因此，當(dāng)有限制擺渡次數(shù)。所以該啟發(fā)函數(shù)h是滿足A*條件的。答：題目的另一個說法是：當(dāng)A*結(jié)束時，OPEN表中任何一個具有f(n)<f*(s)的節(jié)點(diǎn)都被擴(kuò)展了。用反證法證明。的節(jié)點(diǎn)，不會影響A*的可采納性。而F是f*(s)的上界范圍，提示：對于8數(shù)碼問題，逆向搜索和正向搜索是完全一樣的，只是把目標(biāo)狀態(tài)和初始狀態(tài)對調(diào)就可以了。該性質(zhì)，我們可以提出另一種動態(tài)修改h以f(j)作為節(jié)點(diǎn)j的f值。f值的改變，隱含了h值的改變。當(dāng)h不滿足單調(diào)條件時，經(jīng)過這樣修正后的h具有一定的單調(diào)性質(zhì)，可為了敘述方便，我們將兩個相對的扇區(qū)稱為相對扇區(qū)，圖中陰影部分的扇區(qū)稱為陰影扇區(qū)為此，我們可以將目標(biāo)進(jìn)行分解，首先滿足陰影扇區(qū)的數(shù)字之和為48（這過程中，我們希望不破壞第一個目標(biāo)。為此我們采用轉(zhuǎn)動90o的方式實(shí)現(xiàn)，這樣即可以調(diào)我們采用轉(zhuǎn)動180o的方式實(shí)現(xiàn)。這樣同樣是即可以保證前兩個目標(biāo)不被破壞，又可以實(shí)現(xiàn)答：此題要求按照課中例題的方式，給出算法，以下是每個循環(huán)結(jié)束時的搜索圖。上面這種做法比較簡單，也可以如下做：從該搜索圖可以看出，無論先走者選擇哪個走步，后走者都可以走到標(biāo)記為A的節(jié)點(diǎn)，該節(jié)點(diǎn)只剩下一枚錢幣，所以先走者必輸。答：第1題~(x){~P(x)□{(y)[~P(y)□P(f(x，y))]□(z(x){P(x)□{(y)[P(y)□~P(f(x，y))]□(z(x)(y)(z){P(x)□{[P(y)□~P(f(x(x)(y)(z){P(x)□[P(y)□~Q(x，z)□P(z二者不相等。所以說，置換的合成是不可交換的。：（），），），答1x）{[P（x）→P（A）]□[P（x）→P（B）]}~（x）{[P（x）→P（A）]□[P（x）→P（B）]}~~（x）{[~P（x）□P（A）]□[~P（x）□P（B）]}~（x）{[P（x）□~P（A）]□[P（x）□~P（B）]}（x）{[P（x）□~P（A）]□P（x）}□{[P（x）□~P（A）]□~P（B）}}（x）{P（x）□[~P（A）□P（x）]□[P（x）□~P（B）]□[~P（A）□~P（B）]}P（x）□[~P（A）□P（x）]□[P（x）□~P（B）]□[~P（A）□~P（B）]得子句集：2,~P(A)□P{x2}3,P(x3)□~P(B)4,~P(A)□~P(B)（2z）[Q（z）→P（z）]→{（x）[Q（x）→P（A）]□[Q（x）→P（B）]}~{(z)[Q(z)→P(z)]→{(x)[Q(x)→P(A)]□[Q(x)→P(B)]}}~{(z)[~Q(z)□P(z)]→{(x)[~Q(x)□P(A)]□[~Q(x)□P(B)]}}~{~{(z)[~Q(z)□P(z)]}□{(x)[~Q(x)□P(A)]□[~Q(x)□P(B)]}}(z)(x){[~Q(z)□P(z)]□{[Q(x)□~P(A)]□[Q(x)□~P(B)]}}(z)(x){[~Q(z)□P(z)]□{Q(x)□[Q(x)□~P(B)]□[~P(A)□Q(x)]□[~P(A)□~P(B)]}[~Q(z)□P(z)]□Q(x)□[Q(x)□~P(B)]□[~P(A)□Q(x)]□[~P(A)□~P(B)]得子句集：1,~Q(z)□P(z)3,Q(x3)□~P(B)4,~P(A)□Q(x4)5,~P(A)□~P(B)（3xy）{[P（f（x□Q（f（B]→[P（f~(x)(y){[P(f(x))□Q(f(B))]→[P(f(A))□P(y)□Q(y)]}~(x)(y){~[P(f(x))□Q(f(B))]□[P(f(A))□P(y)□Q(y)]}(x)(y){[P(f(x))□Q(f(B))]□[~P(f(A))□~P(y)□~Q(y)]}P(f(x))□Q(f(B))□[~P(f(A))□~P(y)□~Q(y)]得子句集：3，~P(f(A))□~P(y3)□~Q(y3)得子句集：（5）（x）{P（x）∈[Q（A）∈Q（B）]}→（x）[P（x）∈Q（x）]~{(x){P(x)∈[Q(A)∈Q(B)]}→(x)[P(x)∈Q(x)]}~{~{(x)P(x)∈[Q(A)∈Q(B)]}∈(x)[P(x)∈Q(x)]}{(x)P(x)∈[Q(A)∈Q(B)]}∈(x)[~P(x)∈~Q(x)]}{(x)P(x)∈[Q(A)∈Q(B)]}∈(y)[~P(y)∈~Q(y)]}(x)(y){P(x)∈[Q(A)∈Q(B)]∈[~P(y)∈~Q(y)]}P(x)∈[Q(A)∈Q(B)]∈[~P(y)∈~Q(y)]得子句集：答1）將（x）P（x）取反化為子句：與條件[P（A1）∈P（A2）]合在一起得子句集：{~P（x）,P（A1）∈P（A2）}所以，公式（x）P（x）是[P（A1）∈P（A2）]的邏輯推論。），），{~P（A）,P（A1）∈P（A2）}該子句集不能進(jìn)行歸結(jié)，故P（A）不是[P（A1）∈P（A2）]的邏輯推論。答：該問題用謂詞公式描述如下：已知：（1）(x){Food(x)→Like(Joh（5）(x){Eat(Bill,x)→Eat(Sue,x)}已知條件化子句集：（1）(x){Food(x)→Like(Joh（5）(x){Eat(Bill,x)→Eat(Sue,x)}修改證明樹如下：是不同的變量，在歸結(jié)時，如果用不同的變量分別表示，就不會出現(xiàn)這樣的問題了。比如B中的y用y1代替，則歸結(jié)結(jié)果如下：答：化子句集：），），（xwywzLAST（y，z）→LAST（cons（x，yz），）），）），）），經(jīng)變量換名后，得子句集：），），）），歸結(jié)樹如下：修改證明樹：通過以上歸結(jié)過程，我們可以看出，該方法求解長表的最后個元素的表，該元素就是長表的最后一個元素。已知：化子句集：(8)(x){~Like(Tony,x)→Like(M經(jīng)變量換名后，得到子句集：結(jié)樹如下：答：狀態(tài)草圖：知識的謂詞表示：(x)(y){[BIG(x)∈BLUE(x)]→ON(x,y)∈GREEN(y)}(x){[HEAVY(x)∈WOODEN(x)]→BIG(x)}(x){CLEAR(x)→BLUE(x)}(x){WOODEN(x)→BLUE(x)}目標(biāo)：(x)(y)GREEN(y)∈ON(x,y)事實(shí)：ONTABLE（A）CLEAR（E）ONTABLE（C）CLEAR（D）ON（D，C）HEAVY（D）ON（B，A）WOODEN（B）HEAVY（B）ON（