广工人工智能2014复习大纲

人工智能复习大纲——马少平，朱小燕编著课程重点章节介绍•本教材共分7章，其中第0章，第1.2~1.4章，第2章，第3.2~3.4章，第4.1~4.4章，第6.1~6.6章，第7.4为重点章节。本课程重点和难点内容简介•第0章人工智能的定义，人工智能三种主要学派及其主要观点，人工智能的应用领域人工智能的定义定义1智能思考机器能够像人一样进行一些与心智能力相关的思维活动。定义2智能行动机器能够像人一样执行某些需要智能才能完成的功能。目前人工智能的主要学派•符号主义认为人工智能源于数理逻辑。•连接主义认为人工智能源于仿生学，特别是人脑模型的研究。•行为主义认为人工智能源于控制论。•符号主义–认为人是一个物理符号系统，计算机也是一个物理符号系统，因此，能够用计算机来模拟人的智能行为，即用计算机的符号操作来模拟人的认知过程。–认为人工智能的研究方法应为功能模拟方法。通过分析人类认知系统所具备的功能和机能，然后用计算机模拟这些功能，实现人工智能。•连接主义–认为人的思维基元是神经元，而不是符号处理过程。它对物理符号系统假设持反对意见，认为人脑不同于电脑，并提出联结主义的大脑工作模式，用于取代符号操作的电脑工作模式。–认为人工智能的研究方法应为结构模拟方法。通过分析人脑的生理结构和工作机理，然后用计算机模拟这些结构与机理，实现人工智能。•行为主义–认为智能取决于感知和行为，取决于对外界复杂环境的适应，而不是知识表示和推理，提出智能行为的“感知－动作”模式。–认为人工智能的研究方法应采用行为模拟方法，模拟人在控制过程中的智能活动和行为特性（自寻优，自适应，自学习），强调“现场AI”。第1章搜索问题•图搜索的一般技术回溯策略；无信息图搜索技术，包括深度优先、宽度优先搜索；启发式图搜索技术，包括爬山法、分支界限法、动态规划法(均一代价法)、最佳优先搜索、A*算法等的计算。图搜索技术的分类•盲目搜索——未使用启发性信息–搜索过程无须对OPEN表进行重排，如：宽度优先搜索、深度优先搜索。•启发式搜索——使用了启发信息–搜索过程需要对OPEN表重排，如：爬山法、分支界限法、动态规划法(均一代价法)、最佳优先搜索法、A*算法等。宽度优先搜索与深度优先搜索的主要区别•每次新生成节点时，宽度优先搜索总是将其插入OPEN表的末尾，而深度优先搜索总是将其插入到OPEN表的前头。爬山法•爬山法是一种局部搜索方法，通过评价当前节点的各个子节点与目标的距离h(n)，然后优先选取距离最短的子节点，作为下一步搜索的方向。分支界限法•分支界限法则评价初始点到当前节点的各个子节点的耗散值g(n)，然后按照最小耗费优先的方式，选择下一步搜索的子节点。•缺点：要存储很多分支结点的界限和对应的耗费矩阵，花费很多内存空间。动态规划法•在分支界限法得出的各种可能的局部解中，根据最小耗散值原则，舍弃那些肯定不能得到最优解的局部解，以节约存储空间，提高搜索效率。最佳优先搜索算法•是“爬山法”的推广，但它是对OPEN表中所有节点的h(n)进行重排，因此是一种全局寻优法。A算法•A算法对当前节点n的评价函数f(n)分为两部分：–从初始点到n的耗散值g(n)–从n到达目标点的距离值h(n)。f(n)=g(n)+h(n)A*算法•在A算法中，如果满足条件：h(n)≤h*(n)，g*(n)≤g(n)则A算法称为A*算法。即f*(n)=g*(n)+h*(n)对右图所示的状态空间图进行：1)深度优先搜索;2)宽度优先搜索；3)动态规划(均一代价)搜索；4)最佳优先搜索；5)A*搜索。其中A为起始节点，E为目标节点，各节点的启发值表示在括号内。FGHECADB42348243385(15)(14)(10)(2)(11)(9)(5)(0)1)深度优先搜索算法FGHEAB1234CD搜索出的路径为：ABCDE5OPEN:{B,H}CLOSED:{A}OPEN:{C,H}CLOSED:{A,B}OPEN:{D,G,H}CLOSED:{A,B,C}OPEN:{E,F,G,H}CLOSED:{A,B,C,D}OPEN:{F,G,H}CLOSED:{A,B,C,D}2)宽度优先搜索算法FGHEAB1234CD567搜索到的路径为：ABCDE8OPEN:{B,H}CLOSED:{A}OPEN:{H,C}CLOSED:{A,B}OPEN:{C,G}CLOSED:{A,B,H}OPEN:{G,D}CLOSED:{A,B,H,C}OPEN:{D,F}CLOSED:{A,B,H,C,G}OPEN:{F,E}CLOSED:{A,B,H,C,G,D}OPEN:{E}CLOSED:{A,B,H,C,G,D,F}OPEN:{}CLOSED:{A,B,H,C,G,D,F}3)动态规划(均一代价)搜索算法FGHEAB1234CD567搜索出的路径为：AHGFDE，整条路径的代价和为15。8OPEN:{B(3),H(4)}CLOSED:{A(0)}OPEN:{H(4),C(7)}CLOSED:{A(0),B(3)}OPEN:{G(6),C(7)}CLOSED:{A(0),B(3),H(4)}OPEN:{C(7),F(10),D(14)}CLOSED:{A(0),B(3),H(4),G(6)}OPEN:{F(10),D(14)}CLOSED:{A(0),B(3),H(4),G(6),C(7)}OPEN:{D(14→13)}CLOSED:{A(0),B(3),H(4),G(6),C(7),F(10)}OPEN:{E(15)}CLOSED:{A(0),B(3),H(4),G(6),C(7),F(10),D(14→13)}OPEN:{}CLOSED:{A(0),B(3),H(4),G(6),C(7),F(10),D(13)}4)最佳优先搜索算法FGHEAB1234CD搜索出的路径为：AHGDE，整条路径的代价和为16。OPEN:{H(11),B(14)}CLOSED:{A(15)}OPEN:{G(9),B(14)}CLOSED:{A(15),H(11)}OPEN:{D(2),F(5),C(10),B(14)}CLOSED:{A(15),H(11),G(9)}OPEN:{E(0),F(5),C(10),B(14)}CLOSED:{A(15),H(11),G(9),D(2)}5OPEN:{F(5),C(10),B(14)}CLOSED:{A(15),H(11),G(9),D(2)}5)A*算法FGHEAB1234CD5搜索出的路径为：AHGDE，整条路径的代价和为15。6OPEN:{H(15),B(17)}CLOSED:{A(15)}OPEN:{G(15),B(17)}CLOSED:{A(15),H(15)}OPEN:{F(15),D(16),B(17),C(19)}CLOSED:{A(15),H(15),G(15)}OPEN:{D(16→15),B(17),C(19)}CLOSED:{A(15),H(15),G(15),F(15)}OPEN:{E(15),B(17),C(19)}CLOSED:{A(15),H(15),G(15),F(15),D(16→15)}OPEN:{B(17),C(19)}CLOSED:{A(15),H(15),G(15),F(15),D(16→15)}第2章与或图搜索问题•在用某一中方法求解问题时，可能需要求解几个子问题，这些子问题必须全部求解，才能求解原始问题。这些“子”问题间的关系，就是“与”的关系，此类问题可用与或图来表示。…...K个耗散值的计算k(n,N)=Ci+k(n1,N)+…+k(ni,N)其中：N为终节点集Ci为连接符的耗散值…...i个nn1n2ni图2.2n0→{n7，n8}的3个解图设N={n7,n8},且kn7=kn8=0。则0022678=？=？能解节点•终节点是能解节点•若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。•若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。不能解节点•没有后裔的非终节点是不能解节点。•若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。•若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。AO*算法•评估函数采用局部解图的耗散值k(n,N)，即每次扩展选择局部解图耗散值最小的节点进行。•搜索的两个过程：–图生成过程，即扩展节点•从最优的局部图中选择一个节点扩展–计算耗散值的过程•对当前的局部图重新计算耗散值AO*算法举例其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0设：k连接符的耗散值为k目标目标初始节点n0n1n2n3n4n5n6n7n8目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n1(2)n4(1)n5(1)红色：4黄色：3目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n4(1)n5(1)红色：4黄色：6n1n2(4)n3(4)5目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)21博弈树搜索•博弈问题–双人–一人一步，轮流进行–双方信息完备，即双方得到的信息是一样的–零和，即双方是寻找置对手于必败态的过程–双方都无法干预对方的选择–可用图搜索技术进行，但效率很低极小极大过程05-333-3022-30-23541-30689-30-33-3-3-21-36-30316011极大极小ab-剪枝法•在极小极大法中，必须求出所有终端节点的评估值，当预先考虑的棋步比较多时，计算量会大大增加。为了提高搜索的效率，引入了通过对评估值的上下限进行估计，从而减少需进行评估的节点范围的-剪枝法。-剪枝•极大节点的下界为。•极小节点的上界为。•剪枝的条件：–后辈节点的值≤祖先节点的值时，剪枝–后辈节点的值≥祖先节点的值时，剪枝•简记为：–极小≤极大，剪枝–极大≥极小，剪枝86-31453-350-剪枝（续）3-3022-30-2309-300-303305411-31661abcdefghijkmn第3章谓词逻辑与归结原理•基本概念–个体词：表示主语的词–谓词：刻画个体性质或个体之间关系的词–量词：表示数量的词谓词归结原理基础•公式及其解释–个体常量：a,b,c–个体变量：x,y,z–谓词符号：P,Q,R–量词符号：，–辖域：xA，xA中的A例()x{()()[()(,)]PxyDyLxy}谓词归结原理基础量词辖域收缩与扩张等值式：(x）(P（x）∨Q)=(x）P（x）∨Q(x）(P（x）∧Q)=(x）P（x）∧Q(x）(P（x）→Q)=(x）P（x）→Q(x）(Q→P（x）)=Q→(x）P（x）(x）(P（x）∨Q)=(x）P（x）∨Q(x）(P（x）∧Q)=(x）P（x）∧Q(x）(P（x）→Q)=(x）P（x）→Q(x）(Q→P（x）)=Q→(x）P（x）前束范式•把所有的量词都提到最左端后的谓词公式，称为前束范式。(Q1x1)(Q2x2)…(Qnxn)P(x1,x2,…xn)例如(x)(z){[P(x)S(z)]L(x,z)}Skolem标准形•消去前束范式的所有量词，得到Skolem标准形。–对任意量词来说，只需将其取消，其辖域中的变量代表任意个体即可。–对存在量词来说，左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数；如左边没有全程量词，将存在量词改写成为常量。将谓词公式G化为Skolem标准