第二次作业_搜索与问题求解、推理以及神经网络_参考答案

1、人工智能基础（2014-2015-1）第二次习题（搜索与问题求解、推理、人工神经网络）第一题、请用状态空间表示法与A*搜索算法求解如下问题：U2合唱团在17分钟内得赶到演唱会场，途中必需跨过一座桥，四个人从桥的同一端出发，你得帮助他们到达另一端，天色很暗，而他们只有一只手电筒。一次同时最多可以有两人一起过桥，而过桥的时候必须持有手电筒，所以就得有人把手电筒带来带去，来回桥两端。手电筒是不能用丢的方式来传递的。四个人的步行速度各不同，若两人同行则以较慢者的速度为准。Bono需花1分钟过桥，Edge需花2分钟过桥，Adam需花5分钟过桥，Larry需花10分钟过桥。他们要如何在17分钟内过桥呢？（

2、微软笔试题）答：令桥的两端表示为甲和乙，甲端为出发端，乙端为目的端。令状态表示为（甲，乙），同时B=Bono，E=Edge，A=Adam，L=Larry，当手电筒在乙端时，易知此时应让乙端中花费时间最少的人来把手电筒送到甲端，因此，取g为实际花费的时间，启发函数h为乙端所有人中时间最小的+甲端所有人中时间最大的；则开始状态为（BEAL ， ），此时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,h=2+5 g=5,h=2+10 g=1

3、0,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最优路径如黑色粗箭头标示，相应的解答用文字描述为： Step1. Bono和 Edge过河 Step2. Bono返回 Step3. Adam和 Larry过河 Step4. Edge返回 Step5. Bono和 Edge过河第二题：设有如图所示的一颗

4、博弈树，其中末一行的数字是叶顶点的静态估值，请对博弈树做如下工作：（1） 用极大极小值法计算各节点的倒推值。（2） 按从左到右搜索顺序，用-剪枝技术剪去不必要的分枝。（在剪枝处用标记）。（3） 说明最后计算结果的作用。MAX节点MIN节点 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）最后计算结果的作用是确定行动方案，此处将选择A作为下一步的行动。第三题、将课件中福尔摩斯的推理过程用一阶谓词逻辑形式表达出来。解：（1）表达知识与推理目标事实：ink(Mary) necklace(M

5、ary) lightfinger(Mary) England(Mary) doctor(Waston)规则：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)推理目标： marrydoc(Mary)（2）自然演绎推理根据necklac

6、e(Mary)与necklace(x)èrewarded(x)，得rewarded(Mary)根据ink(Mary)、rewarded(Mary)与ink(x)Ùrewarded(x)èteacher(x)，得teacher(Mary)根据lightfinger(Mary)与lightfinger(x)èringbefore(x)Ùabroad(x)，得ringbefore(Mary)，abroad(Mary)根据ringbefore(Mary)与ringbefore(x)èengaged(x)，得engaged(Mary) 根据en

7、gaged(Mary)、abroad(Mary)、England(Mary)与engaged(x) Ù abroad(x)ÙEngland(x)èmarrydoc(x)，得marrydoc(Mary)第四题、兹有以下知识： （1）约翰喜欢吃牛排，或者约翰喜欢吃土豆。 （2）如果约翰既喜欢吃牛排又喜欢吃土豆，那么约翰是一个不偏食的人。 （3）如果某人喜欢吃牛排，那么他喜欢吃土豆。 （4）如果某人喜欢吃土豆，那么他喜欢吃牛排。 应用归结演绎推理方法证明：约翰是一个不偏食的人。解：（1）定义谓词 eat(x, y) x喜欢吃y；pianshi(s) s是一个偏食的人；

8、常量J：约翰；D：牛排；E：土豆 （2）表达知识 1）eat(J, D) eat(J, E) 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）结论求反并做为子句： pianshi(J) （5）执行归结： àeat(J, E) àeat(J, D) àeat(J, D)pianshi(J) àpianshi(J) &#

9、224;Nil 因为归结出空子句，得到结论：约翰是一个不偏食的人第五题、请利用人工神经网络表示如下布尔函数：。解：的映射关系为：(0, 0)à0, (0, 1)à0, (1, 0)à1, (1, 1)à0。则以下两层感知器（采用阈值型激活函数）可实现该函数：ABw1=1w2=-2第六题、使用双曲正切函数取代Sigmoid函数，作为误差反向传播网络中神经元的输出函数。设表示神经元的输出，分别表示神经元的第i个输入及其对应权值，（包括阈值），则每个神经元的输出是：。试推导相应BP算法中输出层和隐含层的权值更新法则。提示：。解：(1)输出层的权值调整法则输出误

10、差与相应连接权值的关系如下：e=12i=1m(di-yi)2yi=tanhi2=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即输出层神经元连接权值的调整法则：ji=ji-yi-di(1-yi2)xji（2）隐含层的权值调整法则输出误差与相应连接权值的关系如下：e=12i=1m(di-yi)2yi=tanh2=1-e-1+e-=jixji=jiyj'yj'=tanh'2=1-e

11、-'1+e-''=kjxkiekj=i=1meyiyiyj'yj'''kjeyi=yi-di,yii=1-yi2,iyj'=ji,yj'j'=1-yj2,j'kj=xkj综合可得：ekj=xkj(1-y'j2)i=1mji(1-yi2)(yi-di)即隐含层神经元连接权值的调整法则：kj=kj-xkj(1-y'j2)i=1mji(1-yi2)(yi-di)第七题、如何利用SOFM网络实现课件中所述的颜色聚类？答：1.设置输入层为颜色向量，输出层神经元二维排列，大小根据颜色量化情况设置。2.随机设置输入层到输出层的连接权值