《人工智能简略复习大纲(共58页)》由会员分享，可在线阅读，更多相关《人工智能简略复习大纲(共58页)（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为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的
3、指针修改指针方向重排OPEN表失败成功是是否否图搜索技术的分类按照在搜索过程中，是否使用了中间结果给出的提示信息，可将搜索策略分为盲目搜索(未使用启发性信息)，和启发式搜索(使用了启发信息)两大类。盲目搜索搜索过程无须对OPEN表进行重排，如：宽度优先搜索、深度优先搜索。深度优先搜索 深度优先搜索优先扩展新产生的节点，如示意图。宽度优先搜索 宽度优先搜索逐层进行，如示意图。宽度优先搜索与深度优先搜索的主要区别 每次新生成节点时，宽度优先搜索总是将其插入OPEN表的末尾，而深度优先搜索总是将其插入到OPEN表的前头。宽度优先搜索与深度优先搜索的其他区别: 只要问题有解，宽度优先搜索总是能找到，并
4、且找到的总是搜索路径最短的解；而深度优先搜索却因为可能陷入一条“花园小径”，不一定能够找到解，并且找到的解也不一定是搜索路径最短的解。启发式图搜索 搜索过程需要对OPEN表重排，如：爬山法、分支界限法、动态规划法(均一代价法)、最佳优先搜索法、A*算法等。爬山法 爬山法是一种局部搜索方法，模仿瞎子爬山的过程：从立足处用明杖向前一试，觉得高些，就向前一步，如果前面不高，向左一试，高就向左一步，不高再试后面，高就退一步，不高再试右面，高就向右走一步，四面都不高，就原地不动.总之，高了就走一步，就这样一步一步地走，就走上了山顶。这个向各方向的测试“步”，就是“爬山法”的估价函数h(n)。登山法算法步
5、骤： 设定初始节点n； 如果n是目标，则成功退出； 扩展n，得到其子节点集合； 从该集合中选取h(n)为最小的节点n； 将n设为n，返回第步。分支界限法 分支界限法则以宽度优先或以最小耗费优先的方式，搜索满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 缺点：要存储很多分支结点的界限和对应的耗费矩阵，花费很多内存空间。 具有动态规划原理的分支界限法 具有动态规划原理的分支界限法，根据分支界限法得出的各种可能的局部解，根据最小耗散值原则，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。 这种方法，也可称为均一代价法或等代价法。
6、 耗散值的概念及应用 搜索图中，在任意两节点弧线间移动付出的代价，叫弧线耗散值。 而一条路径的耗散值等于，连接这条路径各节点间所有弧线耗散值的总和。 分支界限法、动态规划法（均一代价法、等代价搜索法）中，均采用路径耗散值作为评价函数，即每次扩展优先选择具有最小路径耗散值的节点进行，记做f(n)=g*(n)。最佳优先搜索算法 是“爬山法”的推广，但它是对OPEN表中所有节点的h(n)进行比较，按从小到大的顺序重排OPEN表，因此是一种全局寻优法。 其算法效率类似于深度优先搜索算法，但使用了当前节点与目标的估测距离h(n)函数，来确定下一步待扩展的节点，因此是一种启发式搜索方法。A算法最佳优先算法
7、有时无法得到最优解，因为它的估价函数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这段路
8、径的代价，这一代价可以由从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为起始
9、节点，E为目标节点，各节点的启发值表示在括号内。FGHECADB42348243385(15)(14)(10)(2)(11)(9)(5)(0)1) 深度优先搜索算法FGHEAB1234CD搜索出的路径为： ABCDE5OPEN:B,HCLOSED:AOPEN:C,HCLOSED:A,BOPEN:D,G,HCLOSED:A,B,COPEN:E,F,G,HCLOSED:A,B,C,DOPEN:F,G,HCLOSED:A,B,C,D2) 宽度优先搜索算法FGHEAB1234CD567搜索到的路径为：ABC DE8OPEN:B,HCLOSED:AOPEN:H,CCLOSED:A,BOPEN:C,GCL
10、OSED:A,B,HOPEN:G,DCLOSED:A,B,H,COPEN:D,FCLOSED:A,B,H,C,GOPEN:F,ECLOSED:A,B,H,C,G,DOPEN:ECLOSED:A,B,H,C,G,D,FOPEN:CLOSED:A,B,H,C,G,D,F3) 均一(等)代价搜索算法FGHEA B1234CD567搜索出的路径为： AHGFDE，整条路径的代价和为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(
11、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),F(10)OPEN:E(15)CLOSED:A(0),B(3),H(4),G(6),C(7),F(10),D(1413)OPEN:CLOSED:A(0),B(3),H(4),G(6),C(7),F(10),D(13)4) 最佳优先搜索算法FGHEAB1234CD搜索出的路径为： AHGDE，整条路径的代价和为16。OPEN:H(11),B(14)CLOSED
12、: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搜索出的路径为： AHGDE，整条路径的代价和为15。6OPEN:H(15),B(17)CLOSED:A(15)OPEN:G(15),B(17)CLOSED:A(15),H(1
13、5)OPEN:F(15),D(16),B(17),C(19)CLOSED:A(15),H(15),G(15)OPEN:D(1615),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*的应用等； 博弈树
14、的极大极小搜索过程，、参数的定义，-剪枝法的定义及应用。与或图表示的问题 在用某一中方法求解问题时，可能需要求解几个子问题，这些子问题必须全部求解，才能用该方法求解原始问题。这些“子”问题间的关系，就是“与”的关系，此类问题可用与或图来表示。目标目标初始节点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)代替。能解节点 终节点是能解节点 若非终节点有“或”子节点时，
15、当且仅当其子节点至少有一能解时，该非终节点才能解。 若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。不能解节点 没有后裔的非终节点是不能解节点。 若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。 若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。AO*算法 评估函数采用解图的耗散值k(n,N)，即每次扩展选择解图耗散值最小的节点进行。 搜索的两个过程： 图生成过程，即扩展节点 从最优的局部图中选择一个节点扩展 计算耗散值的过程 对当前的局部图重新计算耗散值AO*算法举例其中： h(n0)=3 h(n1)=2 h(n2
16、)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(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极小极大搜索过程 模拟人类下棋的方法，尤其是初学者，走一步，看看对方的反应，思考应对的方法再走一步，。所谓高手，就是能对几个，甚至几十个棋步后，有较准确的局面预测。 对目前的局部解图进行评价，选择评价值最好的子节点(对Max节点)，或评价值最差的子节点(对Min节点)
