《人工智能简略复习大纲.ppt》由会员分享，可在线阅读，更多相关《人工智能简略复习大纲.ppt（58页珍藏版）》请在金锄头文库上搜索。
1、人工智能-复习大纲,马少平，朱小燕编著,课程简介,通过人工智能课程的学习，了解人工智能的发展概况、人工智能与人类智能之间的联系、人工智能的应用领域、机器学习、神经计算、遗传算法、专家系统等基本概念，掌握知识表示方式和推理、搜索推理、消解原理等人工智能原理的基本理论、方法及其应用技术，注重培养综合运用人工智能原理的知识解决问题的能力。,课程重点章节介绍,本教材共分7章，其中第1.21.4，第2章，3.23.4，4.14.4，6.16.6，7.4为重点章节。,本课程重点和难点内容简介,第0章 人工智能的定义，人工智能三种主要学派及其主要观点，人工智能的应用领域,人工智能的定义,定义1 智能思考机器
2、 能够像人一样进行一些与心智能力相关的思维活动。 定义2 智能行动机器 能够像人一样执行某些需要智能才能完成的功能。,目前人工智能的主要学派,符号主义 认为人工智能源于数理逻辑。 连接主义 认为人工智能源于仿生学，特别是人脑模型的研究。 行为主义 认为人工智能源于控制论。,第1章 搜索问题,图搜索的一般技术 回溯策略；无信息图搜索技术，包括深度优先、宽度优先搜索；启发式图搜索技术，包括爬山法、分支界限法、动态规划法(均一代价法)、最佳优先搜索、A*算法等的计算。,图搜索的一般过程,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,n为目标节点吗？,
3、把n的后继节点放入OPEN表的末端，提供返回节点n的指针,修改指针方向,重排OPEN表,失败,成功,是,是,否,否,图搜索技术的分类,按照在搜索过程中，是否使用了中间结果给出的提示信息，可将搜索策略分为盲目搜索(未使用启发性信息)，和启发式搜索(使用了启发信息)两大类。,盲目搜索,搜索过程无须对OPEN表进行重排，如：宽度优先搜索、深度优先搜索。,深度优先搜索,深度优先搜索优先扩展新产生的节点，如示意图。,宽度优先搜索,宽度优先搜索逐层进行，如示意图。,宽度优先搜索与深度优先搜索的主要区别,每次新生成节点时，宽度优先搜索总是将其插入OPEN表的末尾，而深度优先搜索总是将其插入到OPEN表的前头
4、。,宽度优先搜索与深度优先搜索的其他区别:,只要问题有解，宽度优先搜索总是能找到，并且找到的总是搜索路径最短的解；而深度优先搜索却因为可能陷入一条“花园小径”，不一定能够找到解，并且找到的解也不一定是搜索路径最短的解。,启发式图搜索,搜索过程需要对OPEN表重排，如：爬山法、分支界限法、动态规划法(均一代价法)、最佳优先搜索法、A*算法等。,爬山法,爬山法是一种局部搜索方法，模仿瞎子爬山的过程：从立足处用明杖向前一试，觉得高些，就向前一步，如果前面不高，向左一试，高就向左一步，不高再试后面，高就退一步，不高再试右面，高就向右走一步，四面都不高，就原地不动.总之，高了就走一步，就这样一步一步地走
5、，就走上了山顶。 这个向各方向的测试“步”，就是“爬山法”的估价函数h(n)。,登山法算法步骤：,设定初始节点n； 如果n是目标，则成功退出； 扩展n，得到其子节点集合； 从该集合中选取h(n)为最小的节点n； 将n设为n，返回第步。,分支界限法,分支界限法则以宽度优先或以最小耗费优先的方式，搜索满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 缺点：要存储很多分支结点的界限和对应的耗费矩阵，花费很多内存空间。,具有动态规划原理的分支界限法,具有动态规划原理的分支界限法，根据分支界限法得出的各种可能的局部解，根据最小耗散值原则，舍弃那些肯定不能得到最优解的局部解，在每一
6、步都经过筛选，以每一步都是最优解来保证全局是最优解。 这种方法，也可称为均一代价法或等代价法。,耗散值的概念及应用,搜索图中，在任意两节点弧线间移动付出的代价，叫弧线耗散值。 而一条路径的耗散值等于，连接这条路径各节点间所有弧线耗散值的总和。 分支界限法、动态规划法（均一代价法、等代价搜索法）中，均采用路径耗散值作为评价函数，即每次扩展优先选择具有最小路径耗散值的节点进行，记做f(n)=g*(n)。,最佳优先搜索算法,是“爬山法”的推广，但它是对OPEN表中所有节点的h(n)进行比较，按从小到大的顺序重排OPEN表，因此是一种全局寻优法。 其算法效率类似于深度优先搜索算法，但使用了当前节点与目
7、标的估测距离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) 时，可
8、以省略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
9、) 深度优先搜索; 2) 宽度优先搜索； 3) 均一(等)代价搜索； 4) 最佳优先搜索； 5) A*搜索。 其中A为起始节点，E为目标节点，各节点的启发值表示在括号内。,F,G,H,E,C,A,D,B,4,2,3,4,8,2,4,3,3,8,5,(15),(14),(10),(2),(11),(9),(5),(0),1) 深度优先搜索算法,F,G,H,E,A,B,1,2,3,4,C,D,搜索出的路径为： ABCDE,5,OPEN: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,
10、B,C,D,OPEN:F,G, H CLOSED:A,B,C,D,2) 宽度优先搜索算法,F,G,H,E,A,B,1,2,3,4,C,D,5,6,7,搜索到的路径为：ABC DE,8,OPEN: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) 均一(等)代价搜索算法,
11、F,G,H,E,A,B,1,2,3,4,C,D,5,6,7,搜索出的路径为： AHGFDE，整条路径的代价和为15。,8,OPEN: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(1413) CLOSED:A(0),B(3),H(4),G(6),C(7)
12、,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) 最佳优先搜索算法,F,G,H,E,A,B,1,2,3,4,C,D,搜索出的路径为： AHGDE，整条路径的代价和为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:
13、E(0),F(5),C(10),B(14) CLOSED:A(15),H(11),G(9),D(2),5,OPEN:F(5),C(10),B(14) CLOSED:A(15),H(11),G(9),D(2),5) A*算法,F,G,H,E,A,B,1,2,3,4,C,D,5,搜索出的路径为： AHGDE，整条路径的代价和为15。,6,OPEN: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(1615)
14、,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(1615),OPEN:B(17),C(19) CLOSED:A(15),H(15),G(15),F(15), D(1615),第2章 与或图搜索问题,与或图的定义，k-连接符的表示方法，与或图解图的耗散值计算方法，能解和不能解节点的定义，与或图的启发式搜索算法AO*的应用等； 博弈树的极大极小搜索过程，、参数的定义，-剪枝法的定义及应用。,与或图表示的问题,在用某一中方法求解问题时，可能需要求解
15、几个子问题，这些子问题必须全部求解，才能用该方法求解原始问题。这些“子”问题间的关系，就是“与”的关系，此类问题可用与或图来表示。,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)=3 h(n1)=2 h(n2)=4
