人工智能课程复习

1、人工智能课程复习,南晓斐,考试题型设置,一、4道简答题，共20分； 二、7道计算题，共70分； 三、1道论述题，共10分。 考试范围为章节3.4.6之前。书本范围为186页。 考试题目来源于课本例题和课后习题。,问答部分,1.人工智能的概念 人工智能就是人造智能，主要研究用人工的方法和技术开发智能机器或智能系统，以模仿、延伸和扩展人的智能、生物智能、自然智能，实现机器的智能行为 2. 人工智能的研究领域 博弈（Game Playing）自动定理证明（Automatic Theorem Proving）专家系统（Expert System）模式识别(Pattern Recognition) 机器

2、学习（Machine Learning）计算智能（Computational Intelligence）自然语言处理（Natural Language Processing）分布式人工智能(Distributed Artificial Intelligence)机器人（Robot）,3.盲目搜索 盲目搜索，也就是无导向搜索。在搜索过程中，没有任何背景知识作指导不考虑任何与解有关的信息，随机的或按预定顺序机械地搜索，并判断是否为所求的解，直到找到解或是证明问题无解为止。盲目搜索效率太低，一般只适用于求解比较简单的问题。 4. 深度优先和宽度优先搜索的优缺点 深度优先效率高但有可能进入无限分支，在

3、问题有解的情况下而找不到系统的解，并且找到解也不能保证是最有解。如果问题有解，宽度优先搜索一定能够找到解，而且是最优解，但宽度优先搜索的效率较低。,5.启发式搜索和启发函数 启发式搜索就是利用启发信息进行制导的搜索。在启发式搜索中，常用启发函数来表示启发性信息，是用来估计搜索树节点与目标节点接近程度的一种函数。启发函数的定义一般可以参考：一个节点到目标节点的某种距离或差异的量度；一个节点处在最佳路径上的概率等。 6. OPEN表和ClOSED表的作用 OPEN表：动态数据结构，登记记录当前待考察的节点。 CLOSED表：动态数据结构，记录考察过得节点。 7.基于谓词逻辑的机器推理方法 自然演绎

4、推理，归结演绎推理，基于规则的演绎推理。,计算部分,考核内容包括： 1. 状态空间图表示 （1）描述状态 （2）定义操作 （3）写出状态空间的三元组 （4）绘制状态空间图 （5）在图中寻找答案,2020/9/15,人工智能,7,例2.2 翻转钱币问题（1）,三枚钱币处于反、正、反状态，每次只许翻动一枚钱币，问连续翻动三次后，能否出现全正或全反状态。,初始状态Qs,目标状态集合Q0, Q7,例2.2 翻转钱币问题（2）,引入一个三元组(q0,q1,q2)来描述总状态，钱币正面为0，反面为1，全部可能的状态为： Q0=(0,0,0) ; Q1=(0,0,1); Q2=(0,1,0) Q3=(0,1

5、,1) ; Q4=(1,0,0); Q5=(1,0,1) Q6=(1,1,0) ; Q7=(1,1,1)。,翻动钱币的操作抽象为改变上述状态的算子， 即Fa, b, c a:把钱币q0翻转一次 b:把钱币q1翻转一次 c:把钱币q2翻转一次 问题的状态空间为,2020/9/15,人工智能,8,例2.2 翻转钱币问题（4）,3.状态空间图 问题的状态空间为：,2020/9/15,人工智能,9,构造状态空间图：,aab aba baa bbb bcc cbc ccb,从状态空间图，可以找到初始Q5到Q7为3的7条路径，对应的操作序列分别为aab, aba, baa, bbb, bcc, cbc,

6、ccb。找不到Q5到Q0为3的路径.,补充例 二阶梵塔问题（1）,一号杆有A、B两个金盘，A小于B。要求将A、B移至三号杆，每次只可移动一个盘子，任何时刻B不能在A上。,（1）有关状态的知识： 用二元组（SA，SB）表示状态，SA表示A所在杆号，SB表示B所在杆号。其中: SA ,SB1,2,3 , 则全部状态如下： （1，1），（1，2），（1，3） （2，1），（2，2），（2，3） （3，1），（3，2），（3，3） 初始状态为（1，1），终止状态为：（3，3） 。,2020/9/15,人工智能,11,B,A,A,A,A,A,B,A,B,B,B,B,B,补充例 二阶梵塔问题（2）,202

7、0/9/15,人工智能,12,（2）有关操作的知识（规则）： A（i，j）表示金盘A从第I号杆移到j号杆，B（i，j）表示金盘B从第i号杆移到j号杆，其中：i,j 1,2,3，但i j ，全部操作为： A（1，2），A（1，3）， A（2，1） A（2，3），A（3，1）， A（3，2） B（1，2），B（1，3）， B（2，1） B（2，3），B（3，1）， B（3，2） 分析每个操作的条件和动作，得到下表：,补充例 二阶梵塔问题（3）,2020/9/15,人工智能,13,补充例 二阶梵塔问题（4）,2020/9/15,人工智能,14,补充例 二阶梵塔问题（5）,（3）状态空间图,1,1,2

8、,1,3,1,2,3,3,3,1,3,3,2,1,2,2,2,A(1,2),A(1,3),B(1,2),A(3,2),A(1,2),B(3,2),A(3,1),B(1,3),A(2,3),2020/9/15,人工智能,15,计算部分,2.启发式搜索和A*启发函数设计 启发函数h(x)满足,对所有的节点x均有： h（x） h* （x） 其中h* （x）是从节点x到目标节点的最小代价，这就称为A*算法。,例2.8 重排九宫问题,2020/9/15,人工智能,17,估价函数f（x）d（x）h（x）,方法一： 格局中将牌是否在家,启发函数如何定义？,h1（x）用 x的格局与目标节点格局相比，不在家的

9、将牌数目来衡量。,h2(x)是x格局中每个将牌离家（Sg中的位置）的最短 距离（不论路上是否放有其他将牌）的总和。,方法二： 将牌离家最短距离,2,5,5,6,7,1 4 2 8 3 7 6 5,1 4 2 8 3 5 7 6,1,扩展顺序,f2(x)值,1 4 8 3 2 7 6 5,1 4 8 3 2 7 6 5,4,5,1 3 4 8 2 7 6 5,6,3,6,1 3 8 2 4 7 6 5,5,1 3 4 8 2 5 7 6,7,9,8 1 4 3 2 7 6 5,7,3 4 1 8 2 7 6 5,1 3 4 7 8 2 6 5,8,8,4,7,8,10,1 3 8 2 4 7 6

10、 5,5,11,1 2 8 4 3 7 6 5,1 4 2 8 6 3 7 5,1 4 2 8 3 7 6 5,7,8,8,1 2 3 8 4 7 6 5,5,12,8,1 3 8 2 4 7 6 5,1,扩展顺序,f3(x)值,1 4 8 3 2 7 6 5,1 4 8 3 2 7 6 5,7,7,1 3 4 8 2 7 6 5,7,2,3,1 3 8 2 4 7 6 5,5,1 3 4 8 2 5 7 6,7,4,1 3 8 2 4 7 6 5,5,5,1 2 3 8 4 7 6 5,5,6,8,1 3 8 2 4 7 6 5,2020/9/15,人工智能,19,例2.9 修道士和野人问题

11、,在河的左岸有五个修道士、五个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下条件的限制： （1）修道士和野人都会划船，但船一次最多只能运三个人； （2）在任何岸边及船上野人数目都不得超过修道士，否则修道士就会被野人吃掉。 假定野人会服从任何一种过河安排，试规划出一种确保修道士安全过河方案。请定义A*启发函数。,2020/9/15,人工智能,20,例2.9 修道士和野人问题,解：先建立问题的状态空间。问题的状态可以用一个三元数组来描述： S(m, c, b) m：左岸的修道士数 c：左岸的野人数 b：左岸的船数 初始状态为：（5，5，1） 终止状态为：（0，0，0）,2020/

12、9/15,人工智能,21,提示：不考虑限制条件的运送次数一定小于有限制条 件的运送次数。,例2.9 修道士和野人问题,先考虑船在左岸的情况： 如果不考虑限制条件，至少需要 （M+C-3）/2*2+1 化简后为： （M+C-3）/2*2+1=M+C-2 再考虑船在右岸的情况： 同样不考虑限制条件。船在右岸，需要一个人将船运往左岸，因此，对于状态（M，C，0），需要的摆渡数，相当于船在左岸的（M+1，C，1）或（M，C+1，1）再加1次。所以需要的最少摆渡数为：M+C+1-2+1=M+C 综合条件，需要的最少摆渡数为M+C-2B。,2020/9/15,人工智能,22,计算部分,3. 极大极小和剪枝

13、 注意最后在根节点标出最佳的一步走步,2020/9/15,人工智能,24,例2.19 用-剪枝技术求博弈问题的最佳走步,2,9,3,1,1,1,3,6,8,1,2,0,3,5,7,4,2,6,1,8,7,1,0,3,A,B,C,E,H,J,K,P,Q,D,L,D,R,T,I,F,G,M,U,N,V,S,2, 2, 1, 1,2, 2,2,2, 2,6, 6,0, 0, 0,5,0,计算问题,4. 应用归结原理和谓词逻辑的推理 （1）定义谓词 （2）化子句集 （3）应用归结原理推理证明,2020/9/15,人工智能,25,2020/9/15,26,子句集,消去蕴含词和等值词,使否定词仅作用于原子

14、公式,使量词间不含同名指导变元,消去存在量词,消去全称量词,化公式为合取范式,子句间无同名变元,组成一个集合,“”作用原子谓词,没有量词( 、 ),合取范式,元素之间变元不同,集合形式,没有蕴含词、等值词,蕴含等价式,双重否定律、 摩根定律、 量词转换律,存在指定、 依赖关系,全称指定,分配律,例3.6 将谓词公式化为子句集,2020/9/15,人工智能,27,(1) 消蕴含词： (2) 缩小否定词作用范围： (3) 变量改名： (4) 消存在量词： (5) 消全称量词： (6) 化合取范式： (7) 适当改名： (8) 生成子句集：,2020/9/15,28,例3.15求证G是F1 F2和F3的逻辑结果,F1： F2 ： F3： G：,证： 求F1 F2 F3 G子句集： (1) D(x) B(x) (2) D(y) F(y) (3) F(z) N(z) (4) G(u) D(u) (5) G(a) (6) N(b),应用归结原理，得： (7)D(a) （4）与（5）归结，a/u (8) F(a) （2）与（7）归结，a/y (9) F(b) （3）与（6）归结，b/z (10)Nil （8）与（9） 归结, a/b 命题得证,2020/9/15,29,例题：Tom、Jerry、Sam是三只大象，关于它们，已知如下事实： （1）Tom是粉红色的； （2）Jerry是