人工智能复习资料汇编.doc

1、学习 - 好资料一、选择填空 产生式系统由 综合数据库，规则库，控制策略三个部分组成2. - 剪枝中，极大节点下界是 ，极小节点是 。3. 发生 剪枝的条件是 祖先节点 值 =后辈节点的 值。4. 发生 剪枝的条件是 后辈节点 值 =祖先节点的 值。5. 在 证 据 理 论 中 ， 信 任 函 数 Bel(A) 与 似 然 函 数 Pl(A) 的 关 系 为0=Bel(A)=Pl(A)=1 。6. 深度优先算法 的节点按深度递减 的顺序排列 OPEN 中的节点。7. 宽度优先算法 的节点按深度递增 的顺序排列 OPEN 中的节点。8. A 算法失败的充分条件是 OPEN 表为空。9. A 算法

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

3、有f(n)=f*(s)=h*(n) ，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 的走步序列。更多精品文档学习 - 好资料S状态G状态解： 综合数据库定义：矩阵（Sij）表示任何状态，其中：Sij 0,1,81 i,j 3Sij 互不相同状态空间： 9！ =362,88

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

6、山算法左上右n：任意状态设： W(n) ：不在位的数码个数目标状态， W(n)=0（每个数码都在规定的位置） W(n)= 5最不利状态， W(n)= 8（ 3） W(n)=（每个数码都不在规定的位置）上左（ 3）（ 3）左此路径 (略 )（ 2）下（ 1）右（ 0） 5其余 2种移动(略)更多精品文档学习 - 好资料可用规则：左、上、右（2）回溯策略限定搜索深度为6，移动次序为左上右下。左可用规则：上、右深度 =1可用规则：左、右、下深度 =4左右深度 =5限定搜索深度= 6规则排列次序：左移、上移、右移、下移可用规则：左、下此状态与深度 =3 的状态相同深度 =6左与深度 =4 状态相同且深

7、度 =6下更多精品文档学习 - 好资料（3） A 算法令： g(n)=d(n)h(n)=w(n)则f(n)=d(n)+w(n)8A(6)23164D(5)27 8335148768235321714G(6)4H(7)76655L(5)12384765s(4)28节点3深度11 6不在位的数码个数（启发函数）4822827B(4)3C(6)35161444262587E(5)7F(6)3351814476762552353I(5)18J(7)1844267615763K(5)5841276M(7)目标3578465nn10n2n4n3三、第二章和第四章n5（ 1）超图（与或图）找解图，并计算解图

8、耗散值n6n8n7更多精品文档学习 - 好资料左图耗散值 K(n0,N) 1+ K(n1,N) 1+1+ K(n3,N) 1+1+2+ K(n5,N)+ 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+ 08右图耗散值 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+07（ 2） -剪枝，并在博弈树

9、上给出是何处发生剪枝的标志， 并标明是哪种剪枝，各生成节点的到推值以及选择的走步路径。05-333-3022-3023541-30689-3（3）语义网络表示1.书本 p137，根据已知规则画出与或图答案：n1n0n0n4n3n5n5n6n8n7n7n8解图 1解图 2更多精品文档学习 - 好资料斑马长颈鹿信天翁企鹅鸵鸟虎金钱豹有蹄动物长脖会游子长腿泳不会飞善飞有黑白两身上有暗肉食动物黄褐黑色嚼反刍动哺乳动物有蹄鸟色斑点色条纹物有犬齿有爪眼盯吃肉有毛发有奶有羽毛会飞会下蛋前方2.王峰热爱祖国。答案：（热爱，王峰，祖国）3、Micheal 是一个雇员， Jack 是他老板，有一天Micheal

10、这个人 kickedpersonemployeeKickedbossisObjectMichealAgenteventJackboss-of答案：4、李强是某大学计算机系教师， 35 岁，副教授，该大学位于北京答案：35岁Age李强Is-a副教授A-kind-of教师Work-at计算机系Part-of某大学Located-at北京四、第五章（1）确定性推理1、已知： R1：A1 B1 CF（B1， A1） 0.8R2：A2 B1CF（B1，A2 ） 0.5R3：B1A3 B2CF（B2， B1A3 ） 0.8CF（A1）=CF（A2）=CF（A3）=1；CF（B1） = CF（B2）=0；计

11、算 ：CF（ B1）、 CF（B2）解：依规则 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（B1 A3） CF(B2，B1 A3)（ 1-CF（B2） =0+0.90.8(1-0)=0.722、课本 p203 页

12、 作业 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,CF(E4)=0.5,CF(E5)=0.6， CF(E6)=0.8.求： CH(H).解：CF (E5E 6) max CF (E 5), CF ( E 6)0.8CF (E4(E5 E6)min CF (E 4), CF (E 5E6)0.5CF (E1)max0, CF (E 4(E 5E 6)CF (E1, E

13、4( E5E 6)0.5 0.80.4CF1( H )max0, CF (E1)CF (H , E1)0.40.90.36CF2( H )max0, CF ( E2)CF (H ,E2)0.80.60.48CF3( H )max0, CF ( E3)CF (H , E3)0.60.50.3CF12 (H )CF1( H ) CF2 (H )CF1( H )CF2 (H )0.36 0.480.360.480.6672CF(H)CF12(H)CF3 (H )0.66720.30.3672（2）证据理论1、设 U=a,b,c,d ，A=a,b ，B=a,b,c ，m(A)=0.6 ，m(U)=0.

14、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( )=1Bel(A)=m(a,b)+m(a)+m(b)+m()=0.6更多精品文档学习 - 好资料3 、 已 知 ： 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

15、.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,0.10,0.05); m2(U)=1- m2(b1)+m2(b2)+m2(b3)=0.70;求 m =m1 m21/K=m1(b1)*m2(b1)+ m1(b1)*m2(U)+ m1(b2)*m2(b2)+ m1(b2)*m2(U)+ m1(b3)*m2(b3)+ m1(b

16、3)*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)*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*(m

17、1(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)由于基本概率分配函数只定义在 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）基于归结的演绎

18、系统1、已知前提：（1）能阅读的人是识字的（2）海豚都不识字（3）有些海豚是聪明的求证：有些聪明的东西不会阅读证明：用谓词形式表达所有前提以及结论。 R(x)： x 会阅读更多精品文档学习 - 好资料 L(x) ： x 识字 D(x) ： x 是海豚 I(x) ： x 是聪明的解：结论：利用公式标准化方法求出上式的S 标准形，再写出对应的子句集求证过程：R(A)(4)， (5) 的归结式L (A)(1)， (6) 的归结式D (A)(2)，(7) 的归结式NIL(3) ，(8) 的归结式2、 证明R1：所有不贫穷且聪明的人都快乐：R2：那些看书的人是聪明的：R3：李明能看书且不贫穷：R4：快乐

19、的人过着激动人心的生活：结论李明过着激动人心的生活的否定：将上述谓词公式转化为子句集并进行归结如下：由 R1 可得子句： Poor( x)Smart( x)Happy(x)由 R2 可得子句：read( y)Smart( y)由 R3 可得子句： read (Li )Poor(Li )x( R( x)L ( x)由 R4 可x得(D子(x句)：I(x)x( I ( x) R( x)Happy( z) Exciting (z)x( D( x) L( x)有结论的否定可得子句： Exciting (Li )根据以S上0 6条W子句，归结R如(x下)：L(x), D ( y) L( y), D (

20、A), I ( A), I (z)R(z)Happy(Li )Li/z更多精品文档学习 - 好资料11Poor( Li )Smart(Li )Smart( Li )read( Li )Li/xLi/y由上可得原命题成立。x(AT (Peter, x)AT( Fido, x)AT ( Peter, school) AT (Fido, y)AT (Fido , y) AT ( Peter , x)AT ( Fido , x), AT ( Peter , school ), AT(Fido(fido,y) ,ATy)(Fido, y)（2）基于归结的问答系统如果 Peter 去哪儿，则 Fido 就去那儿如果 Peter 在学校问题： Fido 就去那儿？解：用谓词公式表达所有前提以及结论。结论子句集：练习：1、已知： U=a