1、人工智能作业解答西安电子科技大学 廉师友习题三o 6.解：用四元组解：用四元组(f、w、s、g)表示状态，表示状态， f代表农夫，代表农夫，w 代表狼，代表狼，s 代表羊，代表羊，g 代表菜，其中每个元素都可代表菜，其中每个元素都可为为0或或1，用，用0表示在左岸，用表示在左岸，用1表示在右岸表示在右岸 。 初始状态初始状态S0：(0,0,0,0)，目标状态，目标状态Sg ：(1,1,1,1) 不合法的状态不合法的状态: (1,0,0,*),(1,*,0,0),(0,1,1,*),(0,*,1,1)操作集操作集F=P1，P2，P3，P4，Q1，Q2，Q3，Q4操作符操作符 条件条件动作动作p1
2、p1f=0f=0，w=0w=0，s s和和g g相异相异f=1f=1，w=1w=1p2p2f=0f=0，s=0s=0，f=1f=1，s=1s=1p3p3f=0f=0，g=0g=0，w w和和s s相异相异f=1f=1，g=1g=1q0q0f=1f=1，s s和和g g相异，相异，w w和和s s相异相异f=0f=0q1q1f=1f=1，w w1 1，s s和和g g相异相异f=0f=0，w w0 0q2q2f=1f=1，s s1 1，f=0f=0，s s0 0q3q3f=1f=1，g g1 1，w w和和s s相异相异f=0f=0，g g0 0o 方案有两种：方案有两种：n p2 q0 p3
3、q2 p2 q0 p2n p2 q0 p1 q2 p3 q0 p2(0,0,0,0)(1,0,1,0)p2q2(0,0,1,0)(1,1,1,0)p1q1(1,0,1,1)(0,0,0,1)q0p3q3(0,1,0,0)q2p2(1,1,0,1)p3q3q2p2p2q2(0,1,0,1)(1,1,1,1)p2q2q0习题三o 12 一棵解树由一棵解树由S0,A,D,t1,t2,t3组成；另一棵解树由组成；另一棵解树由S0,B,E,t4,t5组成。组成。左边的解树：左边的解树：o 按和代价：按和代价： g(D)=4,g(A)=7,g(S0)=12o 按最大代价：按最大代价： g(D)=2,g(A
4、)=5,g(S0)=10 右边的解树：右边的解树：o 按和代价：按和代价：g(E)=2,g(B)=11,g(S0)=18按最大代价：按最大代价： g(E)=2,g(B)=7,g(S0)=14 按和代价计算，左边的解树为最优解树；按最大代价计按和代价计算，左边的解树为最优解树；按最大代价计算，仍然是左边的解树为最优解树。算，仍然是左边的解树为最优解树。因此，左边的解树为最优解树。因此，左边的解树为最优解树。习题三习题三14.14.修道士和野人问题。在河的左岸有五个修道士、五修道士和野人问题。在河的左岸有五个修道士、五个野人和一条船，修道士们想用这条船将所有的人都个野人和一条船，修道士们想用这条船
5、将所有的人都运过河去，但受到以下条件的限制：运过河去，但受到以下条件的限制：（1 1）修道士和野人都会划船，但船一次）修道士和野人都会划船，但船一次最多最多只能只能运三运三个人个人；（2 2）在任何岸边及船上）在任何岸边及船上野人数目野人数目都都不得超过修道士不得超过修道士，否则修道士就会被野人吃掉。否则修道士就会被野人吃掉。 假定野人会服从任何一种过河安排，试规划出一种假定野人会服从任何一种过河安排，试规划出一种确保修道士安全过河方案。确保修道士安全过河方案。请定义启发函数，并给出请定义启发函数，并给出相应的搜索树。相应的搜索树。解：先建立问题的状态空间。问题的状态可以用一个三元解：先建立问
6、题的状态空间。问题的状态可以用一个三元数组来描述：数组来描述： S S(m, c, b)(m, c, b) m m：左岸的修道士数：左岸的修道士数 c c：左岸的野人数：左岸的野人数 b b：左岸的船数：左岸的船数定义启发函数，若满足定义启发函数，若满足h（n）h*（n），即满足），即满足A*条条件的。件的。 启发函数启发函数1：h（n）=0; 启发函数启发函数2： h（n）=M+C; 对状态（对状态（1，1，1），不满足），不满足h（n）h*（n） o 先考虑船在左岸的情况：先考虑船在左岸的情况：n如果不考虑限制条件，至少需要如果不考虑限制条件，至少需要 （M+C-3）/2*2+1化简后为：
7、化简后为： （M+C-3）/2*2+1=M+C-2o 再考虑船在右岸的情况：再考虑船在右岸的情况：n同样不考虑限制条件。船在右岸，需要一个人将船运往同样不考虑限制条件。船在右岸，需要一个人将船运往左岸，因此，对于状态（左岸，因此，对于状态（M，C，0），需要的摆渡数，），需要的摆渡数，相当于船在左岸的（相当于船在左岸的（M+1，C，1）或（）或（M，C+1，1），所以需要的最少摆渡数为：），所以需要的最少摆渡数为：M+C+1-2+1=M+Co 综合条件，需要的最少摆渡数为综合条件，需要的最少摆渡数为M+C-2B。（5 5，5 5，1 1）1h=8h=8f=9f=9（5,3,05,3,0）11h
8、=8h=8f=9f=9（5,4,05,4,0）20h=9h=9f=10f=10（5,2,05,2,0）2h=7h=7f=8f=8（4,4,04,4,0）12h=8h=8f=9f=9（5,4,25,4,2）10h=7h=7f=9f=9（5,3,15,3,1）3h=6h=6f=8f=8（3,3,03,3,0）8h=6h=6f=9f=9（5,1,05,1,0）9h=6h=6f=9f=9（5,0,05,0,0）4h=5h=5f=8f=8（4,4,14,4,1）19h=6h=6f=10f=10（5,2,15,2,1）6h=5h=5f=9f=9（5,1,15,1,1）5h=4h=4f=8f=8（2 2，2
9、 2，0 0）7h=4h=4f=9f=9（3 3，3 3，1 1）13h=4h=4f=10f=10（0 0，3 3，0 0）14h=3h=3f=10f=10状态空间图状态空间图（0 0，3 3，0 0）14h=3h=3f=10f=10（0,4,10,4,1）15h=2h=2f=10f=10（0,5,10,5,1）h=3h=3f=11f=11（1,1,11,1,1）17h=8h=8f=9f=9（0,2,10,2,1）18h=7h=7f=8f=8（0,3,10,3,1）h=8h=8f=9f=9（0 0，0 0，0 0）21h=0h=0f=11f=11（0,1,00,1,0）16h=1h=1f=10
10、f=10（0,2,00,2,0）h=2h=2f=11f=11状态空间图（续）状态空间图（续）习题五o1.(6)解：解：o去掉存在量词变为：去掉存在量词变为：o z v(p(a,b,z,f(z),v,g(z,v) (Q(a,b,z,f(z),v,g(z,v) R(a,z,g(z,v)o去掉全称量词变为：去掉全称量词变为：op(a,b,z,f(z),v,g(z,v) (Q(a,b,z,f(z),v, g(z,v) R(a,z, g(z,v)o适当改名，使子句间不含同名变元：适当改名，使子句间不含同名变元：op(a,b,x,f(x),y,g(x,y) (Q(a,b,z,f(z),v, g(z,v)
11、R(a,z, g(z,v)o化成子句集：化成子句集：op(a,b,x,f(x),y,g(x,y) , Q(a,b,z,f(z),v, g(z,v) R(a,z, g(z,v) o 3.(5)解：解：n（1）P(x) Q(x)n（2） Q(y) R(y)n（3） P(z) Q(z)n（4） R(u)o 利用归结原理来判断利用归结原理来判断n（5）Q(u) （2）（）（4）u/yn（6）P(u) （3）（）（5）u/zn（7）Q(u) （1）（）（6）u/xn（8）NIL （5）（）（7）o 所以原子句集所以原子句集S不可满足不可满足习题五o 4.（4）o 证明：利用归结反演法，先证明证明：利用归
12、结反演法，先证明F1F2G是不可满足的。是不可满足的。化子句集：化子句集：o F1： (1) P(x) Q(x)o (2) P(z) R(z)o F2： (3)P(a)o (4)S(a)o G： (5) S(y)R(y)o 利用归结原理进行归结利用归结原理进行归结o (6) R(a) (2),(3), 1=a/zo (7) R(a) (4),(5), 2 =a/yo (8) NIL (6),(7)o 所以所以F1F2G是不可满足是不可满足 ，从而，从而G是是F1和和F2的逻辑结的逻辑结果。果。o 5.证明：定义如下谓词：证明：定义如下谓词： C(x)：x是清洁的是清洁的 P(x)：x是人是人
13、L(x,y)：x喜欢喜欢y F(x):x是苍蝇是苍蝇o 然后将上述各条件翻译为谓词公式：然后将上述各条件翻译为谓词公式：n(1) x(C(x) y(P(y) L(y,x)n(2) x y(P(x) F(y) L(x,y)n需证结论：需证结论：(3) x(F(x) C(x)o 题设与结论否定的子句集题设与结论否定的子句集: C(x) P(f(x) C(y) L(f(y),y) P(u) F(v) L(u,v) F(a) C(a)o 然后应用消解原理得然后应用消解原理得:n P(f(a) ,a/xn L(f(a),a) ,a/yn F(v) L(f(a),v) ,f(a)/un L(f(a),a)
14、 ,a/vn NIL ,o 所以，苍蝇是不清洁的所以，苍蝇是不清洁的o 此题需注意谓词的定义：此题需注意谓词的定义：x喜欢喜欢y 定义成定义成L(x,y)，另外要定义谓词：人。，另外要定义谓词：人。o 6.证明：用命题公式表述题意为：证明：用命题公式表述题意为： (1)A B C (2)A B C (3)B C 结论：结论：C是子句集是子句集A B C,A BC,BC的逻辑结果。的逻辑结果。o 证：证：n A B C n A B C n B C n Cn B C ,n C ,n Null ,o 即：对子句集即：对子句集S=A B C , A B C ,B C, C施以施以归结，最后推出空子句，
15、所以子句集不可满足，所以归结，最后推出空子句，所以子句集不可满足，所以C是子是子句集句集A B C , A B C ,B C的逻辑结果，所以公司的逻辑结果，所以公司一定要录取一定要录取C.习题五o 解：设谓词解：设谓词P(x)表示表示x是盗窃犯则题意可表是盗窃犯则题意可表述为如下的谓词公式：述为如下的谓词公式：n F1:P(zhao) P(qian)n F2: P(qian) P(sun)n F3: P(sun) P(li)n F4: P(zhao) P(sun)n F5: P(qian) P(li)n 求证的公式为：求证的公式为： xP(x)o子句集如下：子句集如下：n P(zhao) P(
16、qian)n P(qian) P(sun)n P(sun) P(li)n P(zhao) P(sun)n P(qian) P(li)n P(x) GA(x)n P(qian) P(sun) ,n P(sun) P(li) ,n P(sun) ,n GA(sun) ,sun/xn(11)P(qian) ,n(12)GA(qian) ,(11),qian/xo所以，所以，sun和和qian都是盗窃犯即：孙和钱都是盗窃犯都是盗窃犯即：孙和钱都是盗窃犯习题六o 7 猴子摘香蕉问题。n 用四元组来（w，x，y，z）表示状态，w：表示猴子的位置；x：表示猴子是否在箱顶；y：箱子的水平位置；z：猴子是否拿到
17、香蕉。初始位置为（a，0，b，0），目标位置为（ c，1，c，1 ）规则集中的规则：If（w，0，y，z）then goto（u），状态为（u，0，y，z）If（w，0，w，z）then pushbox（v），状态为（v，0，v，z）If（w，0，w，z）then climbbox，状态为（w，1，w，z）If（c，1，c，0）then grasp，状态为（ c，1，c，1 ）控制策略：产生式举例o 有两个无刻度标志的水壶，分别可装有两个无刻度标志的水壶，分别可装5升和升和2升的水。设另有一水缸，可用来向水壶灌升的水。设另有一水缸，可用来向水壶灌水或倒出水，两个水壶之间，水也可以相互水或倒出水
18、，两个水壶之间，水也可以相互倾灌。已知倾灌。已知5升壶为满壶，升壶为满壶，2升壶为空壶，升壶为空壶，问如何通过倒水或灌水操作，使能在问如何通过倒水或灌水操作，使能在2升的升的壶中量出一升的水来。壶中量出一升的水来。 产生式举例产生式举例答：答： 1，全局数据库，全局数据库定义两元组：（定义两元组：（L5, L2）其中：其中：0=L5=5，表示容量为，表示容量为5升的壶的当前水量。升的壶的当前水量。0=L2=2，表示容量为，表示容量为2升的壶的当前水量。升的壶的当前水量。2，规则集，规则集r1：IF (L5, L2) THEN (5, L2) /* 将将L5灌满水灌满水 */ r2：IF (L5
19、, L2) THEN (L5, 2) /* 将将L2灌满水灌满水 */r3：IF (L5, L2) THEN (0, L2) /* 将将L5水倒光水倒光 */r4：IF (L5, L2) THEN (L5, 0) /* 将将L2水倒光水倒光 */ r5：IF (L5, L2) and L5+L25 THEN (5, L5+L2-5) /* L2倒入倒入L5中中 */ r7：IF (L5, L2) and L5+L22 THEN (L5+L2-2, 2) /* L5倒入倒入L2中中 */3，初始状态：，初始状态：(5, 0) 4，结束条件：，结束条件：(x, 1)，其中，其中x表示不定。当然结束
20、条件也可以写成：表示不定。当然结束条件也可以写成：(0, 1) 习题七4.解：植物会结果水中果树小草草树樱桃树樱桃有根 有叶特点ISA果实ISALive in特点特点ISAISAISA5o（1） o(2) Ssubjectobject程度摇海浪军舰轻轻地Sgiverrecipienttimeobject李老师从第一周到第十周计算机1班上课人工智能注意:此题大部分同学都没有做对.对此题,要用谓词公式表示的形式语言语句来表示此语义网络.此外,语义子空间应该框住x,study1和程序设计语言.GScollegestudent 编程语言studystudy1R程序设计语言 xISAFsubjectob
21、jectISAISAISA 5.o(3) 用：collegestudent(x) 表示x是大学生 study(x,y)表示 x学过y表示为： x(collegestudent(x)study(x,程序设计语言)其语义网络表示为：o框架名：框架名： 性别性别:(:(男男, ,女女) )成绩成绩:(:(优优, ,良良, ,中中, ,差差) )类型类型:(:(,)民族民族:(:(汉族汉族, ,回族回族, ,白族白族, ,朝鲜族朝鲜族, ,等等) ) 缺省缺省: :汉族汉族籍贯籍贯:(:(河南河南, ,山东山东, ,河北河北, ,湖南等湖南等) ) 缺省缺省: :河南河南 实例如下实例如下:框架名：框
22、架名： 姓名姓名:李明李明性别性别: :男男成绩成绩: :优优类型类型: 民族民族: :汉族汉族籍贯籍贯: :河南河南地震框架框架名框架名 : 地震地震地点：汶川地点：汶川日期：日期：2008年年5月月12日日强度：强度：8级级人员伤亡：死亡人员伤亡：死亡XX人人 受伤受伤XX人人财产损失：直接损失财产损失：直接损失XX亿亿 间接损失间接损失XX亿亿roadLeadISACityRomaLead1xobjectsubjectISAISARGSF ISAAll Roads Lead to Rome x (Dog(x) y(Postman(y) Bite(x,y)DogBiteISAPostman
23、ISAISAyBxVICTINASSILIANRtGSISARF Every dog has bitten a postman x y(Postman(y) Dog(x) Bite(x,y)DogBiteISAPostmanyBxVICTINASSAILIANTISAISARGSF ISA Every dog has bitten every postman习题八7. 解：由r1：CF（E2）=0.5*0.6=0.3由r2：CF（E4）=min（0.3，0.6）*0.8=0.24由r3：CF（H）=0.24*0.7=0.168由r4：CF（H）=0.4*0.9=0.36CF（H）=0.168+
24、0.36-0.168*0.36=0.468CF（H）=0.4689.解:o S低=1,0.8,0.5,0.2,0S大=0,0.2,0.5,0.8,1S有些低=1,1,0.6,0.3,0o S大=S有些低 Rm=1,1,0.6,0.3,0 =0.5,0.5,0.5,0.8,1 o 决策是:将风门开大.0 0.2 0.5 0.8 10.2 0.2 0.5 0.8 0.80.5 0.5 0.5 0.5 0.50.8 0.8 0.8 0.8 0.81 1 1 1 1Rm=0 0.2 0.5 0.8 10.2 0.2 0.5 0.8 0.80.5 0.5 0.5 0.5 0.50.8 0.8 0.8 0
25、.8 0.81 1 1 1 1(i, j=1, 2, ) )(1 ()()(=(),(jiiAjBiARuvuvu-mmnjnitsrljilklij,.,2 , 1;,.,2 , 1)(110.o 纯净水，可信度，0.8，有可能不是纯净水，是毒药！o 纯净水，隶属度，0.7，是水，但不一定纯净，但喝了不会致命有一个变量x，它的可能取值为a,b,c,其基本概率分配函数为：o m(a)=0.4o m(a,c)=0.4o m(a,b,c)=0.2o 请填写下表：A abca,bb,ca,ca,b,cm(A)00.400000.40.2Bel(A)00.4000.400.81Pl(A)110.20.
26、610.611确定性理论例题o 设有如下一组知识：设有如下一组知识：o r1:IF E1 THEN H (0.9)o r2:IF E2 THEN H (0.6)o r3:IF E3 THEN H (-0.5)o r4:IF E4 AND (E5 OR E6) THEN E1 (0.8)o 已知：已知：CF(E2)=0.8, CF(E3)=0.6, CF(E4)=0.5, CF(E5)=0.6, CF(E6)=0.8,求：求：CF(H)=?确定性理论例题-推理网络H HE E1 10.80.80.60.60.90.9E E2 2E E3 3E E4 4E E5 5E E6 6-0.5-0.50.
27、80.80.60.6确定性理论例题-求解过程解解: 由由r4得得:CF(E1)=CF(E1,E4E5 E6)max0,minCF(E4),maxCF(E5),CF(E6) =0.80.80.64由由r1得得: CF1(H)CF(H,E1) max0,CF(E1) = 0.90.64=0.576由由r2得得: CF2(H) CF(H,E2) max0,CF(E2) = 0.60.8=0.48由由r3得得: CF3(H) CF(H,E3) max0,CF(E3) = -0.50.6=-0.3CF1,2(H)= CF1(H) CF2(H)CF1(D)CF2(H) 0.576+0.48-0.5760.48 0. 77952CF(H)= CF1,2(H) CF3(H) 0.77952-0.30.47952
