人工智能课程复习.pptx

人工智能课程复习,南晓斐,考试题型设置,一、4道简答题，共20分； 二、7道计算题，共70分； 三、1道论述题，共10分。 考试范围为章节3.4.6之前。书本范围为1—86页。 考试题目来源于课本例题和课后习题。,问答部分,1.人工智能的概念 人工智能就是人造智能，主要研究用人工的方法和技术开发智能机器或智能系统，以模仿、延伸和扩展人的智能、生物智能、自然智能，实现机器的智能行为 2. 人工智能的研究领域 博弈（Game Playing）\自动定理证明（Automatic Theorem Proving）\专家系统（Expert System）\模式识别(Pattern Recognition) \机器学习（Machine Learning）\计算智能（Computational Intelligence）\自然语言处理（Natural Language Processing）\分布式人工智能(Distributed Artificial Intelligence)\机器人（Robot）,,3.盲目搜索 盲目搜索，也就是无导向搜索。在搜索过程中，没有任何背景知识作指导不考虑任何与解有关的信息，随机的或按预定顺序机械地搜索，并判断是否为所求的解，直到找到解或是证明问题无解为止。盲目搜索效率太低，一般只适用于求解比较简单的问题。 4. 深度优先和宽度优先搜索的优缺点 深度优先效率高但有可能进入无限分支，在问题有解的情况下而找不到系统的解，并且找到解也不能保证是最有解。如果问题有解，宽度优先搜索一定能够找到解，而且是最优解，但宽度优先搜索的效率较低。,,5.启发式搜索和启发函数 启发式搜索就是利用启发信息进行制导的搜索。在启发式搜索中，常用启发函数来表示启发性信息，是用来估计搜索树节点与目标节点接近程度的一种函数。启发函数的定义一般可以参考：一个节点到目标节点的某种距离或差异的量度；一个节点处在最佳路径上的概率等。 6. OPEN表和ClOSED表的作用 OPEN表：动态数据结构，登记记录当前待考察的节点。 CLOSED表：动态数据结构，记录考察过得节点。 7.基于谓词逻辑的机器推理方法 自然演绎推理，归结演绎推理，基于规则的演绎推理。,计算部分,考核内容包括： 1. 状态空间图表示 （1）描述状态 （2）定义操作 （3）写出状态空间的三元组 （4）绘制状态空间图 （5）在图中寻找答案,2019/7/2,人工智能,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,1) ; Q4=(1,0,0); Q5=(1,0,1) Q6=(1,1,0) ; Q7=(1,1,1)。,翻动钱币的操作抽象为改变上述状态的算子， 即F＝{a, b, c} a:把钱币q0翻转一次 b:把钱币q1翻转一次 c:把钱币q2翻转一次 问题的状态空间为,2019/7/2,人工智能,8,例2.2 翻转钱币问题（4）,3.状态空间图 问题的状态空间为：,2019/7/2,人工智能,9,构造状态空间图：,,,,,,,aab aba baa bbb bcc cbc ccb,,从状态空间图，可以找到初始Q5到Q7为3的7条路径，对应的操作序列分别为aab, aba, baa, bbb, bcc, cbc, ccb。找不到Q5到Q0为3的路径.,补充例 二阶梵塔问题（1）,一号杆有A、B两个金盘，A小于B。要求将A、B移至三号杆，每次只可移动一个盘子，任何时刻B不能在A上。,（1）有关状态的知识： 用二元组（SA，SB）表示状态，SA表示A所在杆号，SB表示B所在杆号。其中: SA ,SB{1,2,3} , 则全部状态如下： （1，1），（1，2），（1，3） （2，1），（2，2），（2，3） （3，1），（3，2），（3，3） 初始状态为（1，1），终止状态为：（3，3） 。,2019/7/2,人工智能,11,,B,,,,A,A,,,,,,,A,A,A,,,,,B,A,B,B,B,B,B,,补充例 二阶梵塔问题（2）,2019/7/2,人工智能,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）,2019/7/2,人工智能,13,补充例 二阶梵塔问题（4）,,2019/7/2,人工智能,14,补充例 二阶梵塔问题（5）,（3）状态空间图,1,1,2,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),2019/7/2,人工智能,15,,计算部分,2. 启发式搜索和A*启发函数设计 启发函数h(x)满足,对所有的节点x均有： h（x） h* （x） 其中h* （x）是从节点x到目标节点的最小代价，这就称为A*算法。,例2.8 重排九宫问题,,2019/7/2,人工智能,17,,,估价函数f（x）＝d（x）＋h（x）,方法一： 格局中将牌是否在家,启发函数如何定义？,,h1（x）用 x的格局与目标节点格局相比，不在家的 将牌数目来衡量。,,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 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,2019/7/2,人工智能,19,例2.9 修道士和野人问题,在河的左岸有五个修道士、五个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下条件的限制： （1）修道士和野人都会划船，但船一次最多只能运三个人； （2）在任何岸边及船上野人数目都不得超过修道士，否则修道士就会被野人吃掉。 假定野人会服从任何一种过河安排，试规划出一种确保修道士安全过河方案。请定义A*启发函数。,2019/7/2,人工智能,20,例2.9 修道士和野人问题,解：先建立问题的状态空间。问题的状态可以用一个三元数组来描述： S＝(m, c, b) m：左岸的修道士数 c：左岸的野人数 b：左岸的船数 初始状态为：（5，5，1） 终止状态为：（0，0，0）,2019/7/2,人工智能,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。,2019/7/2,人工智能,22,计算部分,3. 极大极小和－剪枝 注意最后在根节点标出最佳的一步走步,2019/7/2,人工智能,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）应用归结原理推理证明,2019/7/2,人工智能,25,2019/7/2,26,子句集,消去蕴含词和等值词,使否定词仅作用于原子公式,使量词间不含同名指导变元,消去存在量词,消去全称量词,化公式为合取范式,子句间无同名变元,组成一个集合,,,,,,,,“¬”作用原子谓词,没有量词( 、 ),合取范式,元素之间变元不同,集合形式,没有蕴含词、等值词,蕴含等价式,双重否定律、 摩根定律、 量词转换律,存在指定、 依赖关系,全称指定,分配律,例3.6 将谓词公式化为子句集,,2019/7/2,人工智能,27,,(1) 消蕴含词： (2) 缩小否定词作用范围： (3) 变量改名： (4) 消存在量词： (5) 消全称量词： (6) 化合取范式： (7) 适当改名： (8) 生成子句集：,,2019/7/2,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} 命题得证,2019/7/2,29,例题：Tom、Jerry、Sam是三只大象，关于它们，已知如下事实： （1）Tom是粉红色的； （2）Jerry是灰色的且喜欢Sam； （3）Sam是粉红色或者是灰色且喜欢Tom。 用归结反演方法证明一只灰色大象喜欢一只粉红色大象。 解 首先定义如下谓词： P(x)表示x是粉红色的大象。 G(x) 表示x是灰色的大象。 L（x，y）表示喜欢y。 定义常量：Tom为A，Jerry为B, Sam为C。 已知条件可以表示成如下谓词公式： （1）P（A） （2）G（B）L（B，C） （3）（G（C）P（C）） L（C，A） 设求证的公式为： G： x y（G（x） P（y） L（x，y））,,