人工智能复习资料培训讲学

1、一、选择填空 产生式系统由综合数据库，规则库，控制策略 三个部分组成2. a -B剪枝中，极大节点下界是a，极小节点是B。3. 发生B剪枝的条件是祖先节点B值<=后辈节点的a值。4. 发生a剪枝的条件是后辈节点B值<=祖先节点的a值。5. 在证据理论中，信任函数Bel(A)与似然函数PI(A)的关系为0v=Bel(A)v=PI(A)v=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)v=f*(s)vf(t)。14. h(n)与 h*(n)的关系是 h(n)>=h*(n

3、)，g(n)与 g*(n)的关系是 g(n) > g*(n)。15. 求解图的时候，选择一个正确的外向连接符是顺着现有的连接符的箭头方向去找，不能逆着箭头走。16. 根节点：不存在任何父节点的节点。叶节点：不存在任何后继节点的节点。17. 两个置换s1,s2的合成置换用s1s2表示。它是s2作用到s1的 项。18. LS和LN两个参数之间应该满足 LS、LN>=0,不独立，LS、LN可以同时=1, LS、LN不能同时>1或<1。19. 语义网络：一般用三元组(对象，属性，值)或(关系，对象 1,对象2)20. 反向推理方法：定义：首先提出假设，然后验证假设的真假性，找到

4、假设成 立的所有证据或事实。21. 证据A的不确定性范围：-1 < CF( A) < 1。22. 析取范式：仅由有限个简单 合取式组成的析取式。23. 合取范式：仅由有限个简单析取式组成的合取式。24. 原子公式：由原子符号与项(为常量、变量和函数)构成的公式为原子公式。二、产生式系统(第一章)给定一个初始状态S、一个目标状态G,求从S到G的走步序列|2 8 3|1 2 31 6 4847517 6 5S状态G状态解： 综合数据库定义：矩阵（Sij）表示任何状态，其中：Sij 0,1,81W i,j W 3 Sij 互不相同状态空间：9! =362,880 种状态 规则集设：空格移

5、动代替数码移动。至多有四种移动的可能： 上、下、左、右。定义：Sij为矩阵第i行j列的数码 淇中：i0,j0表示 空格所在的位置，则Si0j0=0 （0代表空格）空格左移规则：if j0-1 仝 1 the n j0 = j0-1; Si0j0 = 0如果当前空格不在第一列，则空格左移一位，新的空格位置赋值为0同理：then备=i(if j0+1 w 3 then j0 = j0+1; Si0j0 = 0if i0-1 仝 1 the n © = i0-1; Si0j0 = 0if i0+1 w 3右移规则：上移规则： 下移规则： 控制策略+1; Si0j0 = 0V(n )= 4V

6、(n)= 5 最（1 ）爬山算法设：一W附：目标状态， 不利状态F在位的数码个数2（W(n )=0n：:数码都在规定的位置仁个数码都不在规定【勺位置）-W(n)W（n）=节 % （每171其余2种移动（略）深度=12 8 316 4可用规则：左、上、右6，移动次序为左上右下。限定搜索深度 =6 规则排列次序：左移、上移、右移、下移2 8 316 4可用规则：上、右深度=4左g 3工64可用规则：左、右、下17 5S 32 6 4可用规则：左、下17 5左S 32 6 417 5：深度=5厂此状态与深 度=3的状态 相同深度=6与深度=4 状 态相同且深度=6(3) A算法令：g( n)=d(

7、n)D(5)n)+w( n831642r873176?53f(n )=d(A(64G7 5(52 8节点深度s4C(6)F(6)8316146525 82Q o658616757/(.(7标 目7)64h(742 735.4 2/ 0321f81264756123784和第四章n5n7n4n8值三、第（1）图左图耗散值 K(n0,N) = 1+ K(n 1,N) = 1 + 1+ K(n3,N) = 1+1+2+ K(n5,N)+ K(n6,N)=1+1+2+2+ K(n 7,N)+ K( n8,N)+2+ K( n7,N)+ K(n 8,N)=1+ 1+ 2+ 2+ 0+ 0+ 2+ 0+

8、0 = 8右图耗散值 K(nO,N) = 2+ K(n4,N) + K(n5,N)= 2+ 1+K(n5N) + 2+K(n7,N) +K(n8,N)-3(3)语义网络表示1书本p137,根据已知规则画出与或图 答案：n5n8解图1n4n8解图2斑马长颈鹿信大翁企鹅鸵鸟有毛发I I有奶有羽毛会飞会下蛋2. 王峰热爱祖国。答案：（热爱，王峰，祖国）3、Micheal是一个雇员，Jack是他老板，有一天 Micheal这个人kicked答案:35岁4、李强是某大学计算机系教师，35岁，副教授，该大学位于北京答案：四、第五章(1)确定性推理1、已知：R1: A1 B1 CF (B1，A1 )= 0.

9、8R2: A2 B1 CF (B1，A2 )= 0.5R3: B1 A A3 B2CF (B2，B1 A A3 )= 0.8CF (A1) =CF (A2) =CF (A3) =1;CF (B1) = CF (B2) =0;计算：CF (B1)、CF (B2)解：依规则R1，CF (B1|A1 )= CF (B1) + CF (B1，A1)(1 CF (B1 )= 0.8,即更新后CF (B1 )= 0.8依规则R2:CF (B1|A2 )= CF (B1) + CF (B1 , A2)(1 CF (B1 )= 0.9更新后 CF (B1 )= 0.9依R3,先计算CF (B1 A A3)=

10、min (CF (A3) , CF (B1)= 0.9 由于 CF (B1 A A3) <1,CF (B2| B1 A A3) = CF (B2) + CF (B1 A A3) X CF(B2, B1 A A3) X( 1-CF (B2) =0+0.9 X 0.8(1-0)=0.722、课本p203页 作业5.10设有以下知识：R1: IF E1 THEN H(0.9);R2: IF E2 THEN H(0.6);R3: IF E3 THEN H(-0.5);R4: IF E4 AND (E5 OR E6) THEN E1(0.8);已知 CF(E2)=0.8, CF(E3)=0.6,C

11、F(E4)=0.5,CF(E5)=0.6, CF(E6)=0.8. 求：CH(H).解：CF (E5E6) =maxCF (E5),CF (E6) =0.8CF (E4(E5E6) =min CF (E4), CF (E5E6) =0.5CF (E1) =max0, CF (E4(E5E6) CF (E1,E4(E5E6)=0.5 0.8 = 0.4CF1(H) =max0, CF (E1) CF (H , E1) =0.4 0.9 =0.36CF2(H) =max0, CF(E2) CF(H ,E2) =0.8 0.6=0.48CF3(H ) =max0, CF(E3) CF(H , E3)

12、 =0.6泊 一0.5 = -0.3CF12(H) =CF.j(H) CF2(H) -CF1(H )CF2(H 0.36，0.480.36 0.48 = 0.6672CF (H) =CF12(H) CF3(H) =0.6672 -0.3 =0.3672(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.6PI(A)=1-Bel(a,b')=1-Bel(c,

13、d)=1-(m(c,d)+m(c)+m(d)+m(© )=1Bel(A)=m(a,b)+m(a)+m(b)+m(© )=0.63、已知：f1(A1) = 0.40, f1(A2)=0.50 , |U| = 20, A1 B=b1,b2,b3,(c1,c2,c3)=(0.1,0.2,0.3), A2 B=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;

14、 m2(b1,b2,b3)=(0.5*0.5,0.5*0.2,0.5*0.1)=(0.25,0.10,0.05); m2(U)=1- m2(b1)+m2(b2)+m2(b3)=0.70;求 m =m10 m21/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.5

15、32 =1/1.082有：m(b1)=K*(m1(b1)*m2(b1)+m1(b1)*m2(U) +m1(U)*m2(b1)=1.082*(0.01+0.028+0.19)=0.247m(b2)=K*(m1(b2)*m2(b2)+m1(b2)*m2(U)+m1(U)*m2(b2)=1.082*(0.008+0.056+0.076) =0.151m(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(

16、b1)+ m(b2)+ m(b3)= 0.536P1(B)= 1-Bel(B)由于基本概率分配函数只定义在B集合和全集U之上，所以其它集合的分配函数值为0,即Bel(B)=0所以，可得P1(B)= 1-Bel(B)=1f1(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是海豚l(x):x是聪明的

17、解： 结论:利用公式标准化方法求出上式的 S标准形，再写出对应的子句集求证过程： R(A)，(5)的归结式 L (A)(1)，(6)的归结式 D (A)(2)，(7)的归结式 NIL(3)，(8)的归结式2、证明R1 :所有不贫穷且聪明的人都快乐：R2 :那些看书的人是聪明的：R3：李明能看书且不贫穷：R4:快乐的人过着激动人心的生活： 结论李明过着激动人心的生活的否定： 将上述谓词公式转化为子句集并进行归结如下: 由R1可得子句： Poor(x) |_ Smart(x) Happy(x)由R2可得子句： L read(y) Smart(y)由R3可得子句： read(Li) 昭龈尸L(x)由

18、R4可得子句: I (x) L HapZM-ExCitngZ)X/x(D(x)t L(x)有结论的否定可得子句： L Exciting(Li)根据以上 6条W句亍归结如下:L(x), D(y)L(y),D(A), 1(A),l(z) R(z) L Happy(Li) Li/zPoor(Li) |_ Smart(Li)Li/x|_ Smart(Li)|_ read (Li)Li/y11由上可得原命题成立。曽x(AT(Peter, x) t AT(Fido,x)AT (Peter,school)AT(Fido,y) AT(Fido,y) AT (Peter, x) AT(Fido , x), AT (Peter, school),AAF(fi,do ,Af)Fido,y)(2)基于归结的问答系统 如果Peter去哪儿，则Fido就去那儿 如果Peter在学校 问题：Fido就去那儿？解：用谓词公式表达所有前提以及结论。 结论 子句集:54虫T(Fido, v)i - ATPeter?x) v虫aAT(Fido. x)v 貝 T(Pawn) / T(Pw也讥 school)school xAT(Fidochool)练习：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=m1O m22、设