人工智能简略复习大纲

人工智能-复习纲领——马少平，朱小燕编著人工智能简略复习大纲第1页课程介绍经过人工智能课程学习，了解人工智能发展概况、人工智能与人类智能之间联络、人工智能应用领域、机器学习、神经计算、遗传算法、教授系统等基本概念，掌握知识表示方式和推理、搜索推理、消解原理等人工智能原理基本理论、方法及其应用技术，重视培养综合利用人工智能原理知识处理问题能力。人工智能简略复习大纲第2页课程重点章节介绍本教材共分7章，其中第1.2~1.4，第2章，3.2~3.4，4.1~4.4，6.1~6.6，7.4为重点章节。人工智能简略复习大纲第3页本课程重点和难点内容介绍第0章

人工智能定义，人工智能三种主要学派及其主要观点，人工智能应用领域人工智能简略复习大纲第4页人工智能定义定义1智能思索机器能够像人一样进行一些与心智能力相关思维活动。定义2智能行动机器能够像人一样执行一些需要智能才能完成功效。人工智能简略复习大纲第5页当前人工智能主要学派符号主义

认为人工智能源于数理逻辑。连接主义

认为人工智能源于仿生学，尤其是人脑模型研究。行为主义

认为人工智能源于控制论。人工智能简略复习大纲第6页第1章搜索问题图搜索普通技术

回溯策略；无信息图搜索技术，包含深度优先、宽度优先搜索；启发式图搜索技术，包含爬山法、分支界限法、动态规划法(均一代价法)、最正确优先搜索、A*算法等计算。人工智能简略复习大纲第7页图搜索普通过程开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n后继节点放入OPEN表末端，提供返回节点n指针修改指针方向重排OPEN表失败成功是是否否人工智能简略复习大纲第8页图搜索技术分类按照在搜索过程中，是否使用了中间结果给出提醒信息，可将搜索策略分为盲目搜索(未使用启发性信息)，和启发式搜索(使用了启发信息)两大类。人工智能简略复习大纲第9页盲目搜索搜索过程无须对OPEN表进行重排，如：宽度优先搜索、深度优先搜索。人工智能简略复习大纲第10页深度优先搜索深度优先搜索优先扩展新产生节点，如示意图。人工智能简略复习大纲第11页宽度优先搜索宽度优先搜索逐层进行，如示意图。人工智能简略复习大纲第12页宽度优先搜索与深度优先搜索主要区分每次新生成节点时，宽度优先搜索总是将其插入OPEN表末尾，而深度优先搜索总是将其插入到OPEN表前头。人工智能简略复习大纲第13页宽度优先搜索与深度优先搜索其它区分:只要问题有解，宽度优先搜索总是能找到，而且找到总是搜索路径最短解；而深度优先搜索却因为可能陷入一条“花园小径”，不一定能够找到解，而且找到解也不一定是搜索路径最短解。人工智能简略复习大纲第14页启发式图搜索搜索过程需要对OPEN表重排，如：爬山法、分支界限法、动态规划法(均一代价法)、最正确优先搜索法、A*算法等。人工智能简略复习大纲第15页爬山法爬山法是一个局部搜索方法，模仿瞎子爬山过程：从立足处用明杖向前一试，以为高些，就向前一步，假如前面不高，向左一试，高就向左一步，不高再试后面，高就退一步，不高再试右面，高就向右走一步，四面都不高，就原地不动.总之，高了就走一步，就这么一步一步地走，就走上了山顶。这个向各方向测试“步”，就是“爬山法”估价函数h(n)。人工智能简略复习大纲第16页登山法算法步骤：设定初始节点n；假如n是目标，则成功退出；扩展n，得到其子节点集合；从该集合中选取h(n)为最小节点n’；将n’设为n，返回第②步。人工智能简略复习大纲第17页分支界限法分支界限法则以宽度优先或以最小花费优先方式，搜索满足约束条件一个解，或是在满足约束条件解中找出在某种意义下最优解。缺点：要存放很多分支结点界限和对应花费矩阵，花费很多内存空间。

人工智能简略复习大纲第18页含有动态规划原理分支界限法含有动态规划原理分支界限法，依据分支界限法得出各种可能局部解，依据最小耗散值标准，舍弃那些必定不能得到最优解局部解，在每一步都经过筛选，以每一步都是最优解来确保全局是最优解。这种方法，也可称为均一代价法或等代价法。

人工智能简略复习大纲第19页耗散值概念及应用搜索图中，在任意两节点弧线间移动付出代价，叫弧线耗散值。而一条路径耗散值等于，连接这条路径各节点间全部弧线耗散值总和。分支界限法、动态规划法（均一代价法、等代价搜索法）中，均采取路径耗散值作为评价函数，即每次扩展优先选择含有最小路径耗散值节点进行，记做f(n)=g*(n)。人工智能简略复习大纲第20页最正确优先搜索算法是“爬山法”推广，但它是对OPEN表中全部节点h(n)进行比较，按从小到大次序重排OPEN表，所以是一个全局寻优法。其算法效率类似于深度优先搜索算法，但使用了当前节点与目标估测距离h(n)函数，来确定下一步待扩展节点，所以是一个启发式搜索方法。人工智能简略复习大纲第21页A算法最正确优先算法有时无法得到最优解，因为它估价函数f选取时，忽略了从初始节点到当前节点代价值。所以，可考虑每个节点n估价函数f(n)分为两个分量：从起始节点到节点n代价g(n)以及从节点n抵达目标节点代价估算值h(n)。

f(n)=g(n)+h(n)人工智能简略复习大纲第22页f(n)——节点n估价函数；

g(n)——从初始节点S到n节点实际代价；

h(n)——从n到目标节点Sg最正确路径预计代价。这里h(n)表达了搜索启发信息，因为g(n)是已知。假如说详细点，g(n)代表了搜索宽度优先趋势。不过当h(n)

g(n)时，能够省略g(n),而提升效率。A算法引入：人工智能简略复习大纲第23页g(n)计算方法：g(n)就是在搜索树中从S到n这段路径代价，这一代价能够由从n到S寻找指针时，把所碰到各段弧线代价加起来给出(这条路径就是到当前为止用搜索算法找到从S到n最小代价路径)。人工智能简略复习大纲第24页h(n)计算方法：h(n)依赖于相关问题领域启发信息。这种信息与当前节点到目标差距相关，h(n)叫做启发函数。人工智能简略复习大纲第25页A*算法定义：在图搜索过程中，假如重排OPEN表是依据f*(n)=g*(n)+h*(n)进行，则称该过程为A*算法。其中，g*(n)——实际代价函数g(n)最优值，即g*(n)g(n)。

人工智能简略复习大纲第26页对右图所表示状态空间图进行：1)深度优先搜索;2)宽度优先搜索；3)均一(等)代价搜索；4)最正确优先搜索；5)A*搜索。其中A为起始节点，E为目标节点，各节点启发值表示在括号内。FGHECADB42348243385(15)(14)(10)(2)(11)(9)(5)(0)人工智能简略复习大纲第27页1)深度优先搜索算法FGHEAB1234CD搜索出路径为：ABCDE5OPEN:{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}人工智能简略复习大纲第28页2)宽度优先搜索算法FGHEAB1234CD567搜索到路径为：ABCDE8OPEN:{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}人工智能简略复习大纲第29页3)均一(等)代价搜索算法FGHEAB1234CD567搜索出路径为：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(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)}人工智能简略复习大纲第30页4)最正确优先搜索算法FGHEAB1234CD搜索出路径为：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:{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)}人工智能简略复习大纲第31页5)A*算法FGHEAB1234CD5搜索出路径为：AHGDE，整条路径代价和为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)}人工智能简略复习大纲第32页第2章与或图搜索问题与或图定义，k-连接符表示方法，与或图解图耗散值计算方法，能解和不能解节点定义，与或图启发式搜索算法AO*应用等；博弈树极大极小搜索过程，、参数定义，-剪枝法定义及应用。人工智能简略复习大纲第33页与或图表示问题在用某一中方法求解问题时，可能需要求解几个子问题，这些子问题必须全部求解，才能用该方法求解原始问题。这些“子”问题间关系，就是“与”关系，这类问题可用与或图来表示。目标目标初始节点sabc人工智能简略复习大纲第34页k-连接符定义…...K个人工智能简略复习大纲第35页解图耗散值计算k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N为终节点集；Cn为连接符耗散值，在单连接符为单位耗散情况下，k-连接符耗散值为k；n1，，ni为节点n子节点，k(ni,N)表示子节点ni耗散值，可用启发值h(ni)代替。人工智能简略复习大纲第36页能解节点终节点是能解节点若非终节点有“或”子节点时，当且仅当其子节点最少有一能解时，该非终节点才能解。若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。人工智能简略复习大纲第37页不能解节点没有后代非终节点是不能解节点。若非终节点有“或”子节点，当且仅当全部子节点均不能解时，该非终节点才不能解。若非终节点有“与”子节点时，当最少有一个子节点不能解时，该非终节点才不能解。人工智能简略复习大纲第38页AO*算法评定函数采取解图耗散值k(n,N)，即每次扩展选择解图耗散值最小节点进行。搜索两个过程：图生成过程，即扩展节点从最优局部图中选择一个节点扩展计算耗散值过程对当前局部图重新计算耗散值人工智能简略复习大纲第39页AO*算法举例其中：

h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0设：k连接符耗散值为k目标目标初始节点n0n1n2n3n4n5n6n7n8人工智能简略复习大纲第40页目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n1(2)n4(1)n5(1)红色：4黄色：3人工智能简略复习大纲第41页目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n4(1)n5(1)红色：4黄色：6n1n2(4)n3(4)5人工智能简略复习大纲第42页目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2人工智能简略复习大纲第43页目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)21人工智能简略复习大纲第44页极小极大搜索过程模拟人类下棋方法，尤其是初学者，走一步，看看对方反应，思索应正确方法再走一步，。所谓高手，就是能对几个，甚至几十个棋步后，有较准确局面预测。对当前局部解图进行评价，选择评价值最好子节点(对Max节点)，或评价值最差子节点(对Min节点)，作为下一步走法，即选择棋步极大极小法。人工智能简略复习大纲第45页极大极小法评定函数评定函数：以我方为标准设定。比如，在一字棋情况下，Max方赢评定值设为+∞，Max方输评定值设为-∞，平局评定值设为0，另外依据与Max方赢局相关棋子数目，能够设为1，2，3，

。人工智能简略复习大纲第46页极小极大过程05-333-3022-30-23541-30689-30-33-3-3-21-36-30316011极大极小ab人工智能简略复习大纲第47页-剪枝法引入在极小极大法中，必须求出全部终端节点评定值，当预先考虑棋步比较多时，计算量会大大增加。为了提升搜索效率，引入了经过对评定值上下限进行预计，从而降低需进行评定节点范围

-

剪枝法。人工智能简略复习大纲第48页MAX节点评定下限值

作为正方出现MAX节点，取它第一个MIN子节点评定值

。当有其它子节点评定值超出

，则该MAX节点会取新值作为自己评定值；假如没有，则该MAX节点评定值就是

。总之，该MAX节点评定值不会低于

，这个

就称为该MAX节点评定下限值。人工智能简略复习大纲第49页MIN节点评定上限值

作为反方出现MIN节点，取它第一个MAX子节点评定值

。当有其它子节点评定值低于

，则该MIN节点会取新值作为自己评定值；假如没有，则该MIN节点评定值就是

。总之，该MIN节点评定值不会高过

，这个

就称为该MIN节点评定上限值。人工智能简略复习大纲第50页-剪枝极大节点下界为。极小节点上界为。剪枝条件：后辈节点值≤祖先节点值时，剪枝后辈节点值≥祖先节点值时，剪枝简记为：极小≤极大，剪枝极大≥极小，剪枝人工智能简略复习大纲第51页86-31453-350-剪枝（续）3-3022-30-2309-300-3033054