第二次作業(yè)_搜索與問(wèn)題求解、推理以及神經(jīng)網(wǎng)絡(luò)_參考答案(共9頁(yè))

1、人工智能(rn n zh nn)基礎(chǔ)（2014-2015-1）第二(d r)次習(xí)題(xt)（搜索與問(wèn)題求解、推理、人工神經(jīng)網(wǎng)絡(luò)）第一題、請(qǐng)用狀態(tài)空間表示法與A*搜索算法求解如下問(wèn)題：U2合唱團(tuán)在17分鐘內(nèi)得趕到演唱會(huì)場(chǎng)，途中必需跨過(guò)一座橋，四個(gè)人從橋的同一端出發(fā)，你得幫助他們到達(dá)另一端，天色很暗，而他們只有一只手電筒。一次同時(shí)最多可以有兩人一起過(guò)橋，而過(guò)橋的時(shí)候必須持有手電筒，所以就得有人把手電筒帶來(lái)帶去，來(lái)回橋兩端。手電筒是不能用丟的方式來(lái)傳遞的。四個(gè)人的步行速度各不同，若兩人同行則以較慢者的速度為準(zhǔn)。Bono需花1分鐘過(guò)橋，Edge需花2分鐘過(guò)橋，Adam需花5分鐘過(guò)橋，Larry需花10

2、分鐘過(guò)橋。他們要如何在17分鐘內(nèi)過(guò)橋呢？（微軟筆試題）答：令橋的兩端表示為甲和乙，甲端為出發(fā)端，乙端為目的端。令狀態(tài)表示為（甲，乙），同時(shí)B=Bono，E=Edge，A=Adam，L=Larry，當(dāng)手電筒在乙端時(shí)，易知此時(shí)應(yīng)讓乙端中花費(fèi)時(shí)間最少的人來(lái)把手電筒送到甲端，因此，取g為實(shí)際花費(fèi)的時(shí)間，啟發(fā)函數(shù)h為乙端所有人中時(shí)間最小的+甲端所有人中時(shí)間最大的；則開始狀態(tài)為（BEAL ， ），此時(shí)g=0，h=10，s=g+h。流程圖如下：（BEAL ，）g=0，h=10，s=10（BE,AL） (BA,EL) (BL,EA) (EA,BL) (EL,BA) (AL,BE)g=10,h=5+2 g=10

3、,h=2+5 g=5,h=2+10 g=10,h=1+5 g=5,h=1+10 g=2,h=1+10s=17 s=17 s=17 s=16 s=16 s=13 (BAL,E) g=3 (B,EAL) (A, EBL) (L,EBA) g=13.h=3 g=13,h=6 g=8,h=11 s=16 s=19 s=19 (BE,AL)g=15 ( ,BEAL) g=17 ,h=0 s=17最優(yōu)路徑(ljng)如黑色粗箭頭標(biāo)示，相應(yīng)的解答用文字描述為： Step1. Bono和 Edge過(guò)河 Step2. Bono返回(fnhu) Step3. Adam和 Larry過(guò)河 Step4. Edge返回

4、(fnhu) Step5. Bono和 Edge過(guò)河第二題：設(shè)有如圖所示的一顆博弈樹，其中末一行的數(shù)字是葉頂點(diǎn)的靜態(tài)估值，請(qǐng)對(duì)博弈樹做如下工作：用極大極小值法計(jì)算各節(jié)點(diǎn)的倒推值。按從左到右搜索順序，用-剪枝技術(shù)剪去不必要的分枝。（在剪枝處用標(biāo)記）。說(shuō)明最后計(jì)算結(jié)果的作用。MAX節(jié)點(diǎn)MIN節(jié)點(diǎn) RA DB C J KD E F G H L M N O 2 4 1 - 3 6 2 4 5 1 3 0 1 2 -1 0 3 5 2 4解：（1）（2）（3）最后計(jì)算結(jié)果的作用是確定行動(dòng)(xngdng)方案，此處將選擇A作為下一步(y b)的行動(dòng)。第三(d sn)題、將課件中福爾摩斯的推理過(guò)程用一階謂詞

5、邏輯形式表達(dá)出來(lái)。解：（1）表達(dá)知識(shí)與推理目標(biāo)事實(shí)：ink(Mary) necklace(Mary) lightfinger(Mary) England(Mary) doctor(Waston)規(guī)則：necklace(x)rewarded(x) ink(x)rewarded(x)teacher(x) lightfinger(x)ringbefore(x)abroad(x) ringbefore(x)engaged(x) engaged(x) abroad(x)England(x)marrydoc(x)推理目標(biāo)： marrydoc(Mary)（2）自然演繹推理根據(jù)necklace(Mary)與n

6、ecklace(x)rewarded(x)，得rewarded(Mary)根據(jù)ink(Mary)、rewarded(Mary)與ink(x)rewarded(x)teacher(x)，得teacher(Mary)根據(jù)lightfinger(Mary)與lightfinger(x)ringbefore(x)abroad(x)，得ringbefore(Mary)，abroad(Mary)根據(jù)ringbefore(Mary)與ringbefore(x)engaged(x)，得engaged(Mary) 根據(jù)(gnj)engaged(Mary)、abroad(Mary)、England(Mary)與e

7、ngaged(x) abroad(x)England(x)marrydoc(x)，得marrydoc(Mary)第四題、茲有以下(yxi)知識(shí)： （1）約翰喜歡(x huan)吃牛排，或者約翰喜歡吃土豆。 （2）如果約翰既喜歡吃牛排又喜歡吃土豆，那么約翰是一個(gè)不偏食的人。 （3）如果某人喜歡吃牛排，那么他喜歡吃土豆。 （4）如果某人喜歡吃土豆，那么他喜歡吃牛排。 應(yīng)用歸結(jié)演繹推理方法證明：約翰是一個(gè)不偏食的人。解：（1）定義謂詞 eat(x, y) x喜歡吃y；pianshi(s) s是一個(gè)偏食的人； 常量J：約翰；D：牛排；E：土豆 （2）表達(dá)知識(shí) 1）eat(J, D) eat(J, E)

8、 2）eat(J, D) eat(J, E)pianshi(J) 3） 4） （3）將上述謂詞化為子句： eat(J, D) eat(J, E) eat(J, D) eat(J, E)pianshi(J) eat(x, D) eat(x, E) eat(x, E) eat(x, D) （4）結(jié)論(jiln)求反并做為子句： pianshi(J) （5）執(zhí)行(zhxng)歸結(jié)： eat(J, E) eat(J, D) eat(J, D)pianshi(J) pianshi(J) Nil 因?yàn)闅w結(jié)(guji)出空子句，得到結(jié)論：約翰是一個(gè)不偏食的人第五題、請(qǐng)利用人工神經(jīng)網(wǎng)絡(luò)表示如下布爾函數(shù)：。解：

9、的映射關(guān)系為：(0, 0)0, (0, 1)0, (1, 0)1, (1, 1)0。則以下兩層感知器（采用閾值型激活函數(shù)）可實(shí)現(xiàn)該函數(shù)：ABw1=1w2=-2第六題、使用雙曲正切函數(shù)(hnsh)取代Sigmoid函數(shù)(hnsh)，作為誤差反向傳播網(wǎng)絡(luò)中神經(jīng)元的輸出函數(shù)。設(shè)表示(biosh)神經(jīng)元的輸出，分別表示神經(jīng)元的第i個(gè)輸入及其對(duì)應(yīng)權(quán)值，（包括閾值），則每個(gè)神經(jīng)元的輸出是：。試推導(dǎo)相應(yīng)BP算法中輸出層和隱含層的權(quán)值更新法則。提示： QUOTE tanhx=1-tanh2x 。解：(1)輸出層的權(quán)值調(diào)整法則輸出誤差與相應(yīng)連接權(quán)值的關(guān)系如下：e=12i=1m(di-yi)2yi=tanhi2=

10、1-e-i1+e-ii=jixjieji=eyiyiiijie=12i=1m(di-yi)2eyi=(yi-di)yi=tanhi2=1-e-i1+e-iyii=1-yi2i=jixjiiji=xji所以eji=yi-di(1-yi2)xji即輸出層神經(jīng)元連接權(quán)值的調(diào)整法則：ji=ji-yi-di(1-yi2)xji（2）隱含層的權(quán)值調(diào)整法則輸出誤差與相應(yīng)連接權(quán)值的關(guān)系如下：e=12i=1m(di-yi)2yi=tanh2=1-e-1+e-=jixji=jiyjyj=tanh2=1-e-1+e-=kjxkiekj=i=1meyiyiyjyjkjeyi=yi-di,yii=1-yi2,iyj=j

11、i,yjj=1-yj2,jkj=xkj綜合(zngh)可得：ekj=xkj(1-yj2)i=1mji(1-yi2)(yi-di)即隱含層神經(jīng)元連接權(quán)值的調(diào)整(tiozhng)法則：kj=kj-xkj(1-yj2)i=1mji(1-yi2)(yi-di)第七題、如何(rh)利用SOFM網(wǎng)絡(luò)實(shí)現(xiàn)課件中所述的顏色聚類？答：1.設(shè)置輸入層為顏色向量，輸出層神經(jīng)元二維排列，大小根據(jù)顏色量化情況設(shè)置。2.隨機(jī)設(shè)置輸入層到輸出層的連接權(quán)值。3.隨機(jī)從輸入樣本集合中采樣獲得當(dāng)前顏色數(shù)據(jù)。4.依據(jù)(yj)輸入向量與連接權(quán)值的歐氏距離度量各神經(jīng)元與輸入顏色的相似度，確定本次輸入中獲勝的神經(jīng)元。5.對(duì)本次獲勝(hu shn)的神經(jīng)元及其鄰域神經(jīng)元的對(duì)應(yīng)權(quán)重按照使其更靠近輸入向量的原則進(jìn)行調(diào)整。6. 更新鄰域(ln y)大小。7.重復(fù)2-6，直到神經(jīng)元連接權(quán)重?zé)o顯著變化。8. SOFM中相互鄰近的神經(jīng)元代表聚類在一起