人工智能作业解答廉师友.ppt

人工智能作业解答西安电子科技大学 廉师友习题三o6.解：用四元组解：用四元组(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}操作符操作符 条件条件动作作p1p1f=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 w＝＝1 1，，s s和和g g相异相异f=0f=0，，w w＝＝0 0q2q2f=1f=1，，s s＝＝1 1，，f=0f=0，，s s＝＝0 0q3q3f=1f=1，，g g＝＝1 1，，w w和和s s相异相异f=0f=0，，g g＝＝0 0o方案有两种：方案有两种：np2→→ q0 →→ p3→→ q2 →→ p2 →→ q0 →→ p2np2→→ q0 →→ p1→→ q2 →→ p3→→ q0→→ p2习题三o12 一棵解树由一棵解树由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)=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.修道士和野人问题在河的左岸有五个修道士、五修道士和野人问题在河的左岸有五个修道士、五个野人和一条船，修道士们想用这条船将所有的人都个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下条件的限制：运过河去，但受到以下条件的限制：（（1 1）修道士和野人都会划船，但船一次）修道士和野人都会划船，但船一次最多最多只能只能运三运三个人个人；；（（2 2）在任何岸边及船上）在任何岸边及船上野人数目野人数目都都不得超过修道士不得超过修道士，，否则修道士就会被野人吃掉。

否则修道士就会被野人吃掉 假定野人会服从任何一种过河安排，试规划出一种假定野人会服从任何一种过河安排，试规划出一种确保修道士安全过河方案确保修道士安全过河方案请定义启发函数，并给出请定义启发函数，并给出相应的搜索树相应的搜索树解：先建立问题的状态空间问题的状态可以用一个三元解：先建立问题的状态空间问题的状态可以用一个三元数组来描述：数组来描述： 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化简后为：化简后为： [（（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=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 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=10f=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)  ¬R(a,z, g(z,v))o化成子句集：化成子句集：o{p(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)) }o3.(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/y}]n（（6））¬P(u) [（（3）（）（5））{u/z}]n（（7））Q(u) [（（1）（）（6））{u/x}]n（（8））NIL [（（5）（）（7））]o所以原子句集所以原子句集S不可满足不可满足习题五o4.（4）o证明：利用归结反演法，先证明证明：利用归结反演法，先证明F1∨∨F2∨∨¬G是不可满足是不可满足的。

化子句集：的化子句集：oF1： (1) ¬P(x) ∨∨Q(x)o (2) ¬P(z) ∨∨R(z)oF2： (3)P(a)o (4)S(a)o¬G：： (5) ¬S(y)∨∨¬R(y)o利用归结原理进行归结利用归结原理进行归结o (6) R(a) [(2),(3), σ1={a/z}]o (7) ¬R(a) [(4),(5), σ2 ={a/y}]o (8) NIL [(6),(7)]o所以所以F1∨∨F2∨∨¬G是不可满足是不可满足 ，从而，从而G是是F1和和F2的逻辑结的逻辑结果o5.证明：定义如下谓词：证明：定义如下谓词： C(x)：：x是清洁的是清洁的 P(x)：：x是人是人 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/x}]n⑦⑦ L(f(a),a) [②②,⑤⑤,{a/y}]n⑧⑧ ¬ F(v)   ¬ L(f(a),v) [③③,⑥⑥,{f(a)/u}]n⑨⑨ ¬ L(f(a),a) [④④,⑧⑧,{a/v}]n⑩⑩ NIL [⑦⑦,⑨⑨,]o所以，苍蝇是不清洁的．所以，苍蝇是不清洁的．o此题需注意谓词的定义：此题需注意谓词的定义：x喜欢喜欢y 定义成定义成L(x,y)，另外要定义谓词：人。

另外要定义谓词：人o6.证明：用命题公式表述题意为：证明：用命题公式表述题意为： (1)A B C (2)A ¬B C (3)B C 结论：结论：C是子句集是子句集{A B C,A ¬BC,BC}的逻辑结果的逻辑结果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}施施以归结，最后推出空子句，所以子句集不可满足，所以以归结，最后推出空子句，所以子句集不可满足，所以C是是子句集子句集{A B C ,¬ A  B C ,¬B C}的逻辑结果，所以的逻辑结果，所以公司一定要录取公司一定要录取C.习题五o解：设谓词解：设谓词P(x)表示表示x是盗窃犯．则题意可表是盗窃犯．则题意可表述为如下的谓词公式：述为如下的谓词公式：nF1:P(zhao)   P(qian)nF2: P(qian)   P(sun)nF3: P(sun)   P(li)nF4: ¬ P(zhao)   ¬ P(sun)nF5: ¬ P(qian)   ¬ P(li)n求证的公式为：求证的公式为：  xP(x)o子句集如下：子句集如下：n①① P(zhao)   P(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/x}]n(11)P(qian) [⑦⑦,⑨⑨]n(12)GA(qian) [⑥⑥,(11),{qian/x}o所以，所以，sun和和qian都是盗窃犯．即：孙和钱都是盗窃犯．都是盗窃犯．即：孙和钱都是盗窃犯．习题六o7 猴子摘香蕉问题。

n用四元组来（w，x，y，z）表示状态，w：表示猴子的位置；x：表示猴子是否在箱顶；y：箱子的水平位置；z：猴子是否拿到香蕉初始位置为（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 ）控制策略：习题七4.解：植物会结果水中果树小草草树樱桃树樱桃有根 有叶特点ISA果实ISALive in特点特点ISAISAISA5o（1） o(2) Ssubjectobject程度摇海浪军舰轻轻地Sgiverrecipienttimeobject李老师从第一周到第十周计算机1班上课人工智能注意:此题大部分同学都没有做对.对此题,要用谓词公式表示的形式语言语句来表示此语义网络.此外,语义子空间应该框住x,study1和程序设计语言.GScollegestudent 编程语言studystudy1R程序设计语言 xISAFsubjectobjectISAISAISA 5.o(3) 用：collegestudent(x) 表示x是大学生 study(x,y)表示 x学过y表示为： x(collegestudent(x)→study(x,程序设计语言))其语义网络表示为：o框架名：框架名：<学生学生> 性别性别:(:(男男, ,女女) )成绩成绩:(:(优优, ,良良, ,中中, ,差差) )类型类型:(<:(<小学生小学生>,<>,<中学生中学生>,<>,<大学生大学生>,<>,<研究生研究生>)>)民族民族:(:(汉族汉族, ,回族回族, ,白族白族, ,朝鲜族朝鲜族, ,等等) ) 缺省缺省: :汉族汉族籍贯籍贯:(:(河南河南, ,山东山东, ,河北河北, ,湖南等湖南等) ) 缺省缺省: :河南河南 实例如下实例如下:框架名：框架名：<学生学生-1> 姓名姓名:李明李明性别性别: :男男成绩成绩: :优优类型类型:<:<大学生大学生> >民族民族: :汉族汉族籍贯籍贯: :河南河南地震框架框架名框架名 : 地震地震地点：汶川地点：汶川日期：日期：2008年年5月月12日日强度：强度：8级级人员伤亡：死亡人员伤亡：死亡XX人人 受伤受伤XX人人财产损失：直接损失财产损失：直接损失XX亿亿 间接损失间接损失XX亿亿roadLeadISACityRomaLead1xobjectsubjectISAISARGSF ISAAll Roads Lead to Rome  x (Dog(x) →   y(Postman(y)  Bite(x,y))DogBiteISAPostmanISAISAyBxVICTINASSILIANRtGSISARF 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+0.36-0.168*0.36=0.468CF（H）=0.4689.解:oS低={1,0.8,0.5,0.2,0}S大={0,0.2,0.5,0.8,1}S有些低={1,1,0.6,0.3,0}oS大=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.8 0.81 1 1 1 1(i, j=1, 2, …) ))(1 ())()(=(),(jiiAjBiARuμvuμvu-ÚÙmm10.o纯净水，可信度，0.8，有可能不是纯净水，是毒药！o纯净水，隶属度，0.7，是水，但不一定纯净，但喝了不会致命有一个变量x，它的可能取值为a,b,c,其基本概率分配函数为：om({a})=0.4om({a,c})=0.4om({a,b,c})=0.2o请填写下表：Aφ{a}{b}{c}{a,b}{b,c}{a,c}{a,b,c}m(A)00.400000.40.2Bel(A)00.4000.400.81Pl(A)110.20.610.611确定性理论例题o设有如下一组知识：设有如下一组知识：or1:IF E1 THEN H (0.9)or2:IF E2 THEN H (0.6)or3:IF E3 THEN H (-0.5)or4: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.80.80.60.6确定性理论例题-求解过程解解: 由由r4得得:CF(E1)=CF(E1,E4^E5 E6)×max{0,min{CF(E4),max{CF(E5),CF(E6)}}} =0.8×0.8＝＝0.64由由r1得得: CF1(H)＝＝CF(H,E1) ×max{0,CF(E1)} = 0.9×0.64=0.576由由r2得得: CF2(H) ＝＝CF(H,E2) ×max{0,CF(E2)} = 0.6×0.8=0.48由由r3得得: CF3(H) ＝＝CF(H,E3) ×max{0,CF(E3)} = -0.5×0.6=-0.3CF1,2(H)= CF1(H) ＋＋CF2(H)－－CF1(D)×CF2(H) ＝＝0.576+0.48-0.576×0.48 ＝＝0. 77952CF(H)= CF1,2(H) ＋＋CF3(H) ＝＝0.77952-0.3＝＝0.47952。