人工智能导论(本科生)深刻复习大纲-参考资料答案解析.pdf

目录目录 绪论.1 搜索技术.1 遗传算法.8 谓词逻辑.8 结构化知识表示 .12 绪论绪论 1、 什么是人工智能？ 答：人工智能又称机器智能，是用计算机模拟或实现的智能；(人工智能是研究如何制造出 人造的智能机器或系统，来模拟人类智能活动的能力，以延伸人们智能的科学) 2、 什么是符号智能与计算智能？并举例说明。 答：符号智能是模拟闹智能的人工智能，是以符号形式的知识和信息为基础，主要通过逻辑 推理，运用知识进行问题求解。如搜索技术、专家系统、定理证明等；计算智能是模拟群智 能的人工智能，以数值数据为基础，主要通过数值计算，运用算法进行问题求解。 搜索技术搜索技术 1. 状态图是由什么组成的？ 答：状态图是由节点与有向边组成； 2. 简述图搜索的方式和策略。 答：搜索方式：线式搜索和树式搜索；搜索策略：盲目搜索和启发式搜索； 3. 阐述图搜索策略中 OPEN 表与 CLOSED 表的作用。 答：OPEN 表用来保存当前待考察的节点，并按照某种排列，来控制搜索的方向和顺序； CLOSED 表用来记录搜索过程中已考察过的节点，保存全局搜索信息，并可根据节点返回指 针得到搜索解路径。 4. 简述广度优先策略与深度优先策略的不同点。 答： 广度优先搜索是始终在同一级节点中考查， 当同一级节点考查完毕， 才考查下一级节点。 因此，是自顶向下一层一层逐渐搜索的，属于横向搜索策略，其搜索是完备的，得到的解为 最优解； 深度优先搜索是在搜索树的每一层始终只扩展一个子节点， 不断向纵深前进， 直到不能 再前进时，才从当前节点返回到上一级节点，沿另一方向又继续前进。因此，是从树根开始 一枝一枝逐渐搜索的，属于纵向搜索策略，其搜索是不完备的，得到的解不一定为最优解。 5. 什么是启发式搜索？并以八数码难题为例，说明其原理。 答：启发式搜索是利用问题拥有的启发信息来引导搜索，达到减少搜索范围，降低问题复杂度的目的。对 于八数码难题，可以利用不在位将牌数或者与目标距离信息来作为启发函数，可以加快搜索目标的步数。 6. 简述启发函数的单调性判别。 答：设 m 是 n 的子节点，t 为目标节点，当 h(n)h(m)C(n,m),h(t)=0 成立时，则可称启发 函数 h 是单调的。 7. 分别用深度优先搜索方法、宽度优先算法、启发式搜索算法求解下图所示八数码难题。 28123 16384 754765 初始状态 目标状态 答：略 设定启发式函数 h(n)为当前节点“不在位”的将牌数； 对于空格，有向左、向上、向下，向右的启发式规则； （根据启发函数定义以及启发式规则使用顺序的不同，答案不唯一） 2 8 1 6 3 7 5 4 g=0 h=7 f=7 2 8 1 6 3 7 5 4 g=1 h=7 f=8 2 8 3 1 6 7 5 4 g=1 h=6 f=7 2 8 3 1 6 7 5 4 g=2 h=6 f=8 2 8 3 1 6 4 7 5 g=2 h=5 f=7 2 8 3 1 6 4 7 5 g=3 h=4 f=7 2 8 3 1 6 4 7 5 g=4 h=5 f=9 2 8 3 1 4 7 6 5 g=4 h=3 f=7 2 8 3 1 4 7 6 5 g=5 h=4 f=9 2 3 1 8 4 7 6 5 g=5 h=3 f=8 2 8 3 1 4 7 6 5 g=5 h=3 f=8 2 8 1 6 3 7 5 4 g=2 h=6 f=8 2 6 8 1 3 7 5 4 g=2 h=7 f=9 1 2 8 6 3 7 5 4 g=3 h=5 f=8 1 2 8 7 6 3 5 4 g=4 h=6 f=10 1 2 8 6 3 7 5 4 g=4 h=5 f=9 2 8 3 1 5 6 7 4 g=3 h=6 f=9 2 3 1 8 6 7 5 4 g=3 h=6 f=9 2 8 3 1 6 7 5 4 g=3 h=6 f=9 2 8 3 1 4 7 6 5 g=6 h=3 f=9 8 3 2 1 4 7 6 5 g=6 h=3 f=9 2 3 1 8 4 7 6 5 g=6 h=2 f=8 2 3 1 8 4 7 6 5 g=6 h=4 f=10 1 2 3 7 8 4 6 5 g=8 h=2 f=10 1 2 3 8 4 7 6 5 g=8 h=0 f=8 1 2 3 8 4 7 6 5 g=7 h=1 f=8 1 3 2 4 10 97 8 6 5 11 12 13 目标 8. 下图为五大城市之间的交通图，边上的数字是城市之间的距离。用图搜索算法，求解 A 到 E 的最短路径 答：可利用分支界限法进行求解。 1、加权图转换为加权树 2、利用分支界限可得搜索图 OPEN: C5、E7、E1、C2、E4、B2 A C1 D1 E1 8 9 4 3 4 B1 C2 E7 B2 D3 E2 E4 D4 C5 2 4 4 4 9 46 A C1 D1 E1 8 9 4 6 3 4 B1 B3 C4C2 E7 C3 B2 C6 B4 E6 D3 E2 E3D2 E4 D4 E5 C5 2 4 4 4 4 9 4 3 6 66 6 6 3 3 A C D E 8 9 2 4 6 3 4 B CLOSED：A、B1、C1、D4、D1、D3、E2 解路径：A、B1、C1、E2 9. 比较 A 算法与 A*算法的特点。 答： A 算法为一种启发式搜索算法， 当 A 算法的启发函数满足 h(x)h *(x)时， 该 A 算法即为 A*算法。 A*算法可以保证搜索取得最优解。 10. 什么是与或图的终止节点？ 什么是能解节点？什么是解树？ 答：本原问题对应的节点为终止节点； 当一个节点满足以下三个条件时，该节点为能解节点：1)该节点为终止节点；2）当该节点 为与节点时，当且仅当其所有子节点能解；3）当该节点为或节点时，只要其任一子节点能解皆 可。 解树是在一个与或图中从初始节点到目标节点的图或树形路径。 11. 什么是解树的代价？ 答：解树的代价即树根的代价，是从树叶开始自下而上逐层计算而求得的。 12. 什么是希望树？ 答：希望树是当前与或图中具有最小代价的解树。 13. 判断下图各节点的能解性，并确定解树。 答：略。 14. 指出下图的解树，并计算每个解树的代价，以及希望树。 答：解树 1：Q0，A，t1，t2 g(t1)=g(t2)=0,g(A)=11,g(Q0)=13 解树 2：Q0，B，D，G，t4，t5 g(t4)=g(t5)=0,g(G)=3,g(D)=4,g(B)=6,g(Q0)=8 所以，解树 2 为最优解树，即希望树 15. 比较极大极小算法与 剪枝技术的区别。 答：极大极小算法是一种静态搜索算法，搜索树的生成与格局估值分开的，搜索效率低。 Q0 1 t1 2 1 t2 A 5 6 t3 t4 2 B C 3 2 1 G F E D 2 21 t5 1 4 t1 2 7t2 3 5 6 t3t4 剪枝为动态搜索算法，利用有限深度优先搜索技术，节点的扩展与格局估值是同时进行的，提 高了搜索效率，同时保证解的完备性。 16. 下图所示博弈树，按从左到右的顺序进行 剪枝搜索 （1）计算各节点的倒推值。 （2）利用-剪枝技术剪去不必要的分枝。 答： 2 3 4 10 2 5 7 8 5 10 5 6 1 2 1 2 5 6 3 6 4 4 3 4 24 2 2 2 2 5 5 56 3 3 34 5 53 2 3 4 10 2 5 7 8 5 10 5 6 1 2 1 2 5 6 3 6 4 4 3 4 2 遗传算法遗传算法 1、 什么是遗传算法？ 答： 遗传算法是你们从生物界按自然选择和有性繁殖、 遗传变异的自然进化现象中得到启发， 而设计出来的一种优化搜索算法。 2、 举例说明遗传算法的三种操作。 答：选择、交叉、变异。 3、 简述基本遗传算法的过程。 答：略。 4、 对某一问题的遗传算法的选择操作过程，初始种群为 S=s1=13,s2=24，s3=8，s4=19， 个体 s1，s2，s3，s4 的适应度函数计算分别为 169，576，64，361 a) 在从区间0,1产生 4 个随机数 r1=0.45,r2=0.11,r3=0.57,r4=0.98，试用轮盘赌选择 法进行选择操作； b) 分析该过程的遗传优化机制。 答：1. s1，s2，s3，s4 的适应度值分别为 169，576，64，361 2.s1，s2，s3，s4 的选择概率分别为 0.14,0.49,0.06,0.31, 累计概率分别为 0.14,0.63, 0.69,1.00 3. 轮盘赌选择操作可得下一代种群为 s2,s1,s2,s4 适应度越高的染色体被随机选中的概率越大， 被选中的次数就越多， 从而在新种群中被 复制的次数就越多， 而适应度较低的染色体被选中的次数也就越少， 从而在新种群中复制的 次数就越少，充分体现了优胜劣汰的自然选择法则。 谓词逻辑谓词逻辑 1. 什么是知识？知识的组成要素是什么？ 答：知识是经过加工处理的信息。组成要素：事实、规则、控制、元知识。 2. 简述知识常用表示方法。 答：谓词逻辑、产生式、语义网络、框架、状态空间法、面向对象法； 3. 用谓词逻辑表示下列知识： （1）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。 （2）他每天下午都去打篮球。 （3）夏天既干燥又炎热。 （4）并不是每一个人都喜欢吃臭豆腐。 答： 1） 定义谓词 like(x,y):x 喜欢 y （ x）(like(x,meihua) （ y）(like(y,juhua) （ z）(like(z,meihua) like(z,juhua) 2） 定义谓词 time（x）:x 是下午，play（x,y） ：x 玩 y x(time(x)play(he,basketball) 3） 定义谓词 dry(x):x 干燥，hot(x):x 炎热，实体 x 表示夏天 dry(x) hot(x) 4） 定义谓词 human(x):x 是人，like (x,y):x 喜欢吃 y (x)(human(x)like(x,臭豆腐) 4. 用谓词逻辑表示下列知识： （1）人人爱劳动。 （2）所有整数要么是偶数要么就是奇数。 （3）自然数都是大于零的整数。 答： 1） 定义谓词 human(x):x 是人，love(x,y):x 喜欢 y （x）(human(x) love(x,labour) 2） 定义谓词 I（x）:x 是整数，E(x):x 是偶数，O(x)：x 是奇数 (x)(I(x)E(x) O(x) 3） 定义谓词 N(x):x 是自然数，I（x）:x 是整数，GZ(x):x 大于 0 (x)(N(x)I(x) GZ(x) 5. 试用谓词逻辑表达描述下述推理： （1）如果张三比李四大，那么李四比张三小。 （2）甲和乙结婚了，则或者甲为男，乙为女；或者甲为女，乙为男。 （3）如果一个人是老实人，他就不会说谎；张三说谎了，所以张三不是老实人。 答： 1） 定义谓词 BIGGER(x,y):x 比 y 大，SMALLER(x,y):x 比 y 小 BIGGER(zhangsan,lisi) SMALLER(lisi,zhangsan) 2） 定义谓词 MARRY(x,y):x 和 y 结婚，MAN(x):x 是男人，WOMAN(x)：x 是女人 MARRY(甲，乙)(MAN(甲) WOMAN(乙)(MAN(乙) WOMAN(甲) 3） 定义谓词 HONEST(x):x 是老实人，LIE（x）:x 说谎 (x)(HONEST(x)LIE(x) )LIE(zhangsan) HONEST(zhangsan) 6. 设 1 / ,( )/ ,/a xf by y z= ， 2 / ,/ ,( )/b x z y g xz= ， 求置换 12 i和 21 i。 答： 12 / ,( )/ ,/ )/ , / ,/ ,( )/ / ,( )/ a xf byz yz b x z y g xz a xf by = ( = i 21 / ,( / )/ ,( / )/ ,/ ,( )/ ,/ / ,( )/ b xy zy g a xz a xf byy z b x g az = = i 7. 设 ( )/ ,/ f yx zy= ， / ,/ ,/ a x b yy z= ，求置换 i。 答： ( / )/ ,/ ,/ ,/ ( )/ ,/ ,/ ,/ ( )/ ,/ f b yxy a x b y y z f bxy a x b y y z f bx y z = / = / = i（y/z） y 8. 判断以下公式对是否可合一？若可合一，则求出最一般的合一。 P(x,y) P(y,x) 答：不可合一。 9. 某公司招聘工作人员，A、B、C 三人应试，经面试后公司表示如下想法： （1）三人中至少录取一人。 （2）如果录取 A 而不录取 B，则一定录取 C。 （3）如果录取 B，则一定录取 C。 求证：公司一定录取 C。 证明： 谓词 P(x)表示公司录取 x；将已知条件表示如下： P(A) P(B) P(C) (P(A) P(B) ) P(C) P(B) P(C) 结论的否定式表示如下： P(C) 将上述 4 个公式化为子句集： 1. P(A) P(B) P(C) 2. P(A) P(B) P(C) 3. P(B) P(C) 4. P(C) 应用归结原理进行归结： 5. P(B) P(C) 1、2 归结 6. P(C) 3、5 归结 7. NIL 4、6 归结 10. 任何通过历史考试并中了彩票的人是快乐的。任何肯学习或幸运的人可以通过所有考试。 John 不学习但很幸运。任何人只要是幸运的就能中彩。 求证：John 是快乐的。 证明：先将问题用谓词表示如下： R1:任何通过历史考试并获奖的人都是快乐的 (x)(Pass(x, history)Win(x, prize)Happy(x) R2:任何肯学习或幸运的人都可以通过所有考试 (x)( y)(Study(x)Lucky(x)Pass(x, y) R3:John 不肯学习但他是幸运的 Study(John)Lucky(John) R4:任何幸运的人都能获奖 ( x)(Luck(x)Win(x,prize) 结论John 是快乐的的否定 Happy(John) 将上述谓词公式转化为子句集： (1) Pass(x,history)Win(x,prize)Happy(x) (2) Study(y)Pass(y,z) (3) Lucky(u)Pass(u,v) (4) Study(John) (5)Lucky(John) (6) Lucky(w)Win(w，prize) (7) Happy(John) 归结如下： (8) Pass(w,history)Happy(w)Luck(w) (1)，(6)归结，w/x (9) Pass(John,history)Lucky(John) (8)，(7)归结，John/w (10) Pass(John,history) (9)，(5)归结 (11) Lucky(John) (10),(3)归结, John/u,history/v (12) (11),(5)归结 得证：John 是快乐的。 结构化知识表示结构化知识表示 1. 什么是语义网络知识表示？语义网络表示方法的特点是什么？ 答：语义网络是一种通过实体及其语义关系来表示知识的有向图。 特点： 结构性好， 可以实现信息共享； 是一种直观的知识表达方式； 推理规则不明了； 表达范围有限； 2. 用语义网络表示下列命题： （1）树和草都是植物。 （2）树和草是有根、有叶的。 （3）水草是草，且长在水中。 （4）果树是树，且会结果。 （5）苹果树是果树中的一种，它结苹果。 答： 3. 用语义网络表示下列事实： 猎狗是一种狗，而狗是一种动物。狗除了动物的有生命、能吃食物、有繁殖能力、能运 动外，还有以下特点：身上有毛、有尾巴、四条腿；猎狗的特点是吃肉、奔跑速度快、能狩猎、 个头大；而狮子狗也是一种狗，它的特点是吃饲料、身体小、奔跑速度慢、不咬人、供观赏。 答： 4. 用语义网络表示下列事实： 山西大学是一所具有百年历史的综合性大学，她位于太原市笔直、宽广的坞城路。张广 义同志今年 36 岁，男性，中等身材，他任职于山西大学。 答： 动物狗 猎狗 狮子狗 狩猎 生命 奔跑快 吃肉 大个头 吃饲料 不咬人 奔跑慢 身体小 吃食物运动 繁殖能力毛尾巴 四条腿 供观赏 5. 请把下列命题用一个语义网络表示出来： （1）猪和羊都是动物。 （2）猪和羊都是哺乳动物。 （3）野猪是猪，但生长在森林中。 （4）山羊是羊，且头上长着角。 （5）绵羊是一种羊，它能生产羊毛。 答： 动物 头上有角 哺乳动物 山羊 羊猪 绵羊 羊毛森林 野猪 AKO AKO AKO have AKO AKO AKO Locatedat ISA 男mike 中等身材 26 岁 山西大学 百年历史 综合性大学 坞城路 太原 笔直、宽广