人工智能复习资料(共11页).doc

《人工智能复习资料(共11页).doc》由会员分享，可在线阅读，更多相关《人工智能复习资料(共11页).doc（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上一、选择填空1. 产生式系统由综合数据库，规则库，控制策略三个部分组成2. -剪枝中，极大节点下界是，极小节点是。3. 发生剪枝的条件是祖先节点值=后辈节点的值。4. 发生剪枝的条件是后辈节点值=祖先节点的值。5. 在证据理论中，信任函数Bel(A)与似然函数Pl(A)的关系为0=Bel(A)=Pl(A)=1。6. 深度优先算法的节点按深度递减的顺序排列OPEN中的节点。7. 宽度优先算法的节点按深度递增的顺序排列OPEN中的节点。8. A 算法失败的充分条件是OPEN 表为空。9. A算法中OPEN中的节点按f值从小到大排序。10. 爬山算法（不可撤回方式） 是只考

2、虑局部信息，没有从全局角度考虑最佳选择。f(n)= g(n) 只考虑搜索过的路径已经耗费的费用11. 分支界限算法（动态规划算法）：f(n)= h(n)只考虑未来的发展趋势。仅保留queue中公共节点路径中耗散值最小的路径，余者删去，按g 值升序排序。12. 回溯策略是试探性地选择一条规则，如发现此规则不合适，则退回去另选其它规则。定义合适的回溯条件新产生的状态在搜索路径上已经出现过。深度限制(走到多少层还没有到目标，就限制往回退) 当前状态无可用规则。13. A*选中的任何节点都有 f(n)=f*(s)=h*(n)，g(n)与g*(n)的关系是g(n) g*(n) 。15. 求解图的时候，选

3、择一个正确的外向连接符是 顺着现有的连接符的箭头方向去找，不能逆着箭头走。16. 根节点：不存在任何父节点的节点。叶节点：不存在任何后继节点的节点。17. 两个置换s1,s2的合成置换用s1s2表示。它是s2作用到s1的 项。18. LS和LN两个参数之间应该满足 LS、LN=0,不独立，LS、LN可以同时=1，LS、LN不能同时1或1。19. 语义网络：一般用三元组（对象，属性，值）或（关系，对象1，对象2）20. 反向推理方法：定义：首先提出假设，然后验证假设的真假性，找到假设成立的所有证据或事实。21. 证据A的不确定性范围：-1 CF( A) 1。22. 析取范式：仅由有限个简单合取式

4、组成的析取式。23. 合取范式：仅由有限个简单析取式组成的合取式。24. 原子公式：由原子符号与项（为常量、变量和函数）构成的公式为原子公式。二、 产生式系统（第一章）给定一个初始状态S、一个目标状态G，求从S到G的走步序列。 S状态 G状态解： 综合数据库 定义：矩阵（Sij）表示任何状态，其中： Sij0,1, 8 1i,j3 Sij 互不相同状态空间：9！=362,880 种状态 规则集设：空格移动代替数码移动。至多有四种移动的可能： 上、下、左、右。 定义：Sij为矩阵第i行j列的数码;其中：i0,j0表示 空格所在的位置，则Si0j0=0 （0代表空格）空格左移规则： if j0-1

5、1 then j0j0-1; Si0j00如果当前空格不在第一列，则空格左移一位，新的空格位置赋值为0同理： 右移规则：if j0+13 then j0j0+1; Si0j00 上移规则：if i0-11 then i0i0-1; Si0j00 下移规则：if i0+13 then i0i0+1; Si0j00 控制策略（1） 爬山算法设： W(n)：不在位的数码个数 n：任意状态 目标状态， W(n)=0 （每个数码都在规定的位置） 最不利状态， W(n)= 8 （每个数码都不在规定的位置）左右上W(n)= 4W(n)= 5W(n)= 5（3）（3）（3）其余2种移动(略)此路径(略)上左左

6、（2）下（1）（0）右（2） 回溯策略 限定搜索深度为6，移动次序为左上右下。深度=1可用规则：左、上、右此状态与深度=3的状态相同左深度=4左深度=5可用规则：上、右右可用规则：左、右、下左与深度=4状态相同且深度=6可用规则：左、下深度=6下限定搜索深度 = 6规则排列次序：左移、上移、右移、下移（3）A算法令： g(n)=d(n) 节点深度 h(n)=w(n) 不在位的数码个数（启发函数）则 f(n)=d(n)+w(n)2 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 3

7、1 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目标123456三、第二章和第四章（1）超图（与或图）找解图，并计算解图耗散值n0n1n3n6n7n2n5n4n8n0n3n6n7n5n4n8解图1n1n5n0n8n7解图2左图耗散值 K(n0,N) 1+ K(n1,N) 1+1+ K(n3,N) 1+1+2+ K(n5,N)+

8、 K(n6,N) 1+1+2+2+ K(n7,N)+ K(n8,N)+2+ K(n7,N)+ K(n8,N) 1+ 1+ 2+ 2+ 0+ 0+ 2+ 0+ 0 8右图耗散值 K(n0,N) 2+ K(n4,N) + K(n5,N) 2+ 1+K(n5N) + 2+K(n7,N) +K(n8,N) 2+ 1+ 2+K(n7,N) +K(n8,N) + 2+K(n7,N) +K(n8,N) 2+ 1+ 2+ 0+ 0+ 2+ 0+ 0 70 5 -3 3 3 -3 0 2 2 -3 0 2 3 5 4 1 -3 0 6 8 9 -3 （2） -剪枝，并在博弈树上给出是何处发生剪枝的标志，并标明是

9、哪种剪枝，各生成节点的到推值以及选择的走步路径。（3）语义网络表示1.书本p137，根据已知规则画出与或图答案：2.王峰热爱祖国。答案：（热爱，王峰，祖国）3、Micheal是一个雇员，Jack是他老板，有一天Micheal这个人kicked 答案：4、 李强是某大学计算机系教师，35岁，副教授，该大学位于北京答案：四、 第五章（1） 确定性推理1、已知：R1：A1B1CF（B1，A1）0.8 R2：A2B1 CF（B1，A2）0.5 R3：B1A3B2CF（B2，B1A3）0.8 CF（A1）=CF（A2）=CF（A3）=1； CF（B1）= CF（B2）=0；计算 ：CF（B1）、CF（B

10、2）解：依规则R1，CF（B1|A1）CF（B1）CF（B1，A1）（1CF（B1）0.8， 即更新后CF（B1）0.8依规则R2：CF（B1|A2）CF（B1）CF（B1，A2）（1CF（B1）0.9 更新后CF（B1）0.9依R3，先计算CF（B1A3）min（CF（A3），CF（B1）0.9由于CF（B1A3）1，CF（B2| B1A3）= CF（B2）+ CF（B1A3）CF(B2，B1A3)（1-CF（B2）=0+0.90.8(1-0)=0.722、 课本p203页 作业5.10设有以下知识：R1：IF E1 THEN H(0.9);R2：IF E2 THEN H(0.6);R3：I

11、F E3 THEN H(-0.5);R4：IF E4 AND (E5 OR E6) THEN E1(0.8);已知CF(E2)=0.8，CF(E3)=0.6,CF(E4)=0.5,CF(E5)=0.6，CF(E6)=0.8.求：CH(H).解：（2） 证据理论1、设U=a,b,c,d，A=a,b，B=a,b,c，m(A)=0.6，m(U)=0.4，U的其它子集的m值均为0。解：Bel(B)=m(a,b,c)+m(a,b)+m(a,c)+m(b,c)+m(a)+m(b) +m(c)+m()=0.6Pl(A)=1-Bel(a,b)=1-Bel(c,d)=1-(m(c,d)+m(c)+m(d)+m(

12、)=1Bel(A)=m(a,b)+m(a)+m(b)+m()=0.63、已知：f1(A1) = 0.40，f1(A2)=0.50，|U| = 20，A1B=b1,b2,b3，(c1,c2,c3)=(0.1,0.2,0.3)，A2B=b1,b2,b3，(c1,c2,c3)=(0.5,0.2,0.1)求：f1(B) 解：先求：m1(b1,b2,b3)=(0.4*0.1,0.4*0.2,0.4*0.3)=(0.04,0.08,0.12); m1(U)=1- m1(b1)+m1(b2)+m1(b3)=0.76; m2(b1,b2,b3)=(0.5*0.5,0.5*0.2,0.5*0.1)=(0.25,

13、0.10,0.05); m2(U)=1- m2(b1)+m2(b2)+m2(b3)=0.70;求m =m1 m2 1/K=m1(b1)*m2(b1)+ m1(b1)*m2(U)+ m1(b2)*m2(b2)+ m1(b2)*m2(U)+ m1(b3)*m2(b3)+ m1(b3)*m2(U)+ m1(U)*m2(b1)+ m1(U)*m2(b2)+ m1(U)*m2(b3)+ m1(U)*m2(U) =0.01+0.028+0.008+0.056+0.06+0.084+0.19+0.076+0.038+0.532 =1/1.082有： m(b1)=K*(m1(b1)*m2(b1)+m1(b1)

14、*m2(U) +m1(U)*m2(b1) =1.082*(0.01+0.028+0.19)=0.247 m(b2)=K*(m1(b2)*m2(b2)+m1(b2)*m2(U)+m1(U)*m2(b2) =1.082*(0.008+0.056+0.076) =0.151 m(b3)=K*(m1(b3)*m2(b3)+m1(b3)*m2(U)+m1(U)* m2(b3) =1.082*(0.06+0.084+0.038)=0.138m(U)=1- m(b1)+ m(b2)+ m(b3)=0.464最后： Bel（B）m(b1)+ m(b2)+ m(b3)0.536P1(B)1-Bel(B)由于基本

15、概率分配函数只定义在B集合和全集U之上，所以其它集合的分配函数值为0，即Bel(B)=0 所以，可得 P1(B)1-Bel(B)=1 f1(B)=Bel(B)+(P1(B)-Bel(B)*|B|/|U|=0.536+(1-0.536)*3/20=0.606五、 第三章（1） 基于归结的演绎系统1、已知前提： （1）能阅读的人是识字的 （2）海豚都不识字 （3）有些海豚是聪明的 求证：有些聪明的东西不会阅读 证明：用谓词形式表达所有前提以及结论。 R(x)： x 会阅读 L(x)： x 识字 D(x)： x 是海豚 I(x)： x 是聪明的解：结论：利用公式标准化方法求出上式的S标准形，再写出对

16、应的子句集求证过程： R(A) (4)，(5) 的归结式 L (A) (1)，(6) 的归结式 D (A) (2)，(7) 的归结式 NIL (3)，(8) 的归结式2、 证明R1：所有不贫穷且聪明的人都快乐：R2：那些看书的人是聪明的：R3：李明能看书且不贫穷：R4：快乐的人过着激动人心的生活：结论李明过着激动人心的生活的否定：将上述谓词公式转化为子句集并进行归结如下：由R1可得子句：由R2可得子句：由R3可得子句：由R4可得子句：有结论的否定可得子句：根据以上6条子句，归结如下： Li/z Li/x Li/y11由上可得原命题成立。（2） 基于归结的问答系统 如果Peter去哪儿，则Fid

17、o就去那儿 如果Peter在学校 问题： Fido就去那儿？ 解：用谓词公式表达所有前提以及结论。结论子句集：练习：1、已知：U=a，b;m1(,aba,b)=(0,0.3,0.5,0.2);m2(,aba,b)=(0,0.6,0.3,0.1);求m=m1m22、设有以下知识：R1：IF E1 THEN H，CF(H,E1)=0.9;R2：IF E2 THEN H，CF(H,E2)=0.6;R3：IF E3 THEN H，CF(H,E3)=-0.5;R4：IF E4 AND (E5 OR E6) THEN E1，CF(E1(E5 E6)=0.9;已知CF(E2)=0.8，CF(E3)=0.6,

18、CF(E4)=0.5,CF(E5)=0.6，CF(E6)=0.8,CH(H)=.求：CH(H).3、 有如下推理规则R1：IF E1 THEN H(0.9);R2：IF E2 THEN H(0.7);R3：IF E3 THEN H(-0.8);R4：IF E4 AND E5 THEN E1(0.7);R5：IF E6 AND (E77 OR E8) THEN E2(1.0);已知CF(E3)=0.3，CF(E4)=0.9,CF(E5)=0.6,CF(E6)=0.7，CF(E7)=-0.3.CF(E8)=0.8求：CH(H).4、 请把下列命题用一个语义网络表示出来。（1）树和草都是植物（2）树和草都有叶和根（3）水草是草，且生长在水中。（4）果树是树，且会结果。（5）梨树是果树中的一种，它会结梨5、 剪枝6、 画出由A到T0，T1的2个解图，并计算解图耗散值。专心-专注-专业