人工智能复习大纲

人工智能复习大纲——马少平，朱小燕编著课程简介•通过人工智能课程的学习，了解人工智能的发展概况、人工智能与人类智能之间的联系、人工智能的应用领域、机器学习、神经计算、遗传算法、专家系统等基本概念，掌握知识表示方式和推理、搜索推理、消解原理等人工智能原理的基本理论、方法及其应用技术，注重培养综合运用人工智能原理的知识解决问题的能力。课程重点章节介绍•本教材共分7章，其中第0.1，0.4，0.6，1.2~1.4，第2章，3.2，3.3，4.1~4.4，6.1，6.3~6.5，7.4为重点章节。本课程重点和难点内容简介•第0章人工智能的定义，人工智能三种主要学派及其主要观点，人工智能的应用领域人工智能的定义定义1智能思考机器能够像人一样进行一些与心智能力相关的思维活动。定义2智能行动机器能够像人一样执行某些需要智能才能完成的功能。目前人工智能的主要学派•符号主义认为人工智能源于数理逻辑。•连接主义认为人工智能源于仿生学，特别是人脑模型的研究。•行为主义认为人工智能源于控制论。第1章搜索问题•图搜索的一般技术回溯策略；无信息图搜索技术，包括深度优先、宽度优先搜索；启发式图搜索技术，包括爬山法、分支界限法、动态规划法(均一代价法)、最佳优先搜索、A*算法等的计算。图搜索的一般过程开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功是是否否图搜索技术的分类•按照在搜索过程中，是否使用了中间结果给出的提示信息，可将搜索策略分为盲目搜索(未使用启发性信息)，和启发式搜索(使用了启发信息)两大类。盲目搜索•搜索过程无须对OPEN表进行重排，如：宽度优先搜索、深度优先搜索。深度优先搜索•深度优先搜索优先扩展新产生的节点，如示意图。宽度优先搜索•宽度优先搜索逐层进行，如示意图。宽度优先搜索与深度优先搜索的主要区别•每次新生成节点时，宽度优先搜索总是将其插入OPEN表的末尾，而深度优先搜索总是将其插入到OPEN表的前头。宽度优先搜索与深度优先搜索的其他区别:•只要问题有解，宽度优先搜索总是能找到，并且找到的总是搜索路径最短的解；而深度优先搜索却因为可能陷入一条“花园小径”，不一定能够找到解，并且找到的解也不一定是搜索路径最短的解。启发式图搜索•搜索过程需要对OPEN表重排，如：爬山法、分支界限法、动态规划法(均一代价法)、最佳优先搜索法、A*算法等。爬山法•爬山法是一种局部搜索方法，模仿瞎子爬山的过程：从立足处用明杖向前一试，觉得高些，就向前一步，如果前面不高，向左一试，高就向左一步，不高再试后面，高就退一步，不高再试右面，高就向右走一步，四面都不高，就原地不动.总之，高了就走一步，就这样一步一步地走，就走上了山顶。这个向各方向的测试“步”，就是“爬山法”的估价函数h(n)。登山法算法步骤：①设定初始节点n；②如果n是目标，则成功退出；③扩展n，得到其子节点集合；④从该集合中选取h(n)为最小的节点n’；⑤将n’设为n，返回第②步。分支界限法•分支界限法则以宽度优先或以最小耗费优先的方式，搜索满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。•缺点：要存储很多分支结点的界限和对应的耗费矩阵，花费很多内存空间。具有动态规划原理的分支界限法•具有动态规划原理的分支界限法，根据分支界限法得出的各种可能的局部解，根据最小耗散值原则，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。•这种方法，也可称为均一代价法或等代价法。耗散值的概念及应用•搜索图中，在任意两节点弧线间移动付出的代价，叫弧线耗散值。•而一条路径的耗散值等于，连接这条路径各节点间所有弧线耗散值的总和。•分支界限法、动态规划法（均一代价法、等代价搜索法）中，均采用路径耗散值作为评价函数，即每次扩展优先选择具有最小路径耗散值的节点进行，记做f(n)=g*(n)。最佳优先搜索算法•是“爬山法”的推广，但它是对OPEN表中所有节点的h(n)进行比较，按从小到大的顺序重排OPEN表，因此是一种全局寻优法。•其算法效率类似于深度优先搜索算法，但使用了当前节点与目标的估测距离h(n)函数，来确定下一步待扩展的节点，因此是一种启发式搜索方法。A算法•最佳优先算法有时无法得到最优解，因为它的估价函数f的选取时，忽略了从初始节点到目前节点的代价值。所以，可考虑每个节点n的估价函数f(n)分为两个分量：从起始节点到节点n的代价g(n)以及从节点n到达目标节点代价的估算值h(n)。f(n)=g(n)+h(n)•f(n)——节点n的估价函数；g(n)——从初始节点S到n节点的实际代价；h(n)——从n到目标节点Sg最佳路径的估计代价。•这里h(n)体现了搜索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的宽度优先趋势。但是当h(n)g(n)时，可以省略g(n),而提高效率。A算法的引入：g(n)的计算方法：•g(n)就是在搜索树中从S到n这段路径的代价，这一代价可以由从n到S寻找指针时，把所遇到的各段弧线的代价加起来给出(这条路径就是到目前为止用搜索算法找到的从S到n的最小代价路径)。h(n)的计算方法：•h(n)依赖于有关问题的领域的启发信息。这种信息与当前节点到目标的差距有关，h(n)叫做启发函数。A*算法的定义：•在图搜索的过程中，如果重排OPEN表是依据f*(n)=g*(n)+h*(n)进行的，则称该过程为A*算法。•其中，g*(n)——实际代价函数g(n)的最优值，即g*(n)g(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-连接符的表示方法，与或图解图的耗散值计算方法，能解和不能解节点的定义，与或图的启发式搜索算法AO*的应用等；•博弈树的极大极小搜索过程，、参数的定义，-剪枝法的定义及应用。与或图表示的问题•在用某一中方法求解问题时，可能需要求解几个子问题，这些子问题必须全部求解，才能用该方法求解原始问题。这些“子”问题间的关系，就是“与”的关系，此类问题可用与或图来表示。目标目标初始节点sabck-连接符的定义…...K个解图耗散值的计算•k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N为终节点集；Cn为连接符的耗散值，在单连接符为单位耗散的情况下，k-连接符的耗散值为k；n1，，ni为节点n的子节点，k(ni,N)表示子节点ni的耗散值，可用启发值h(ni)代替。能解节点•终节点是能解节点•若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。•若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。不能解节点•没有后裔的非终节点是不能解节点。•若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。•若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。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初始节点n0n