人工智能课件

人工智能徐长明第五章主要内容•阅读教材5.1、5.2、5.3、5.4、5.5。•爬山法和动态规划法•最佳优先搜索算法•可纳性、单调性以及信息性•博弈树搜索•计算复杂度最佳优先搜索g搜索就是寻找问题的解的过程，即，寻找从初始状态s到目标状态g的路径。假设单步的路径耗散值非负，即，cost(x,y)≥0。xys基本要素：•初始状态•后继函数•目标测试•路径耗散一般的图搜索数据结构•OPEN表：保存待扩展的节点（也称前端节点或边缘节点）。•CLOSED表：保存已扩展了的节点。评价函数•量化从任意状态n到某个目标状态代价的评价函数f(n)。算法的三个关键步骤：•选择、目标检测、扩展。一般的图搜索算法描述图搜索算法的执行过程描述：•1.初始化：•OPEN={初始状态s}，CLOSED=。•2.选择：•(1)若OPEN=，搜索算法失败；•(2)OPEN，从OPEN表中按照某种策略选择一个状态node。•3.目标检测：•(1)若IsGoal(node)=True,则得一解,算法结束;•(2)若IsGoal(node)=False,则执行”4.扩展”.•4.扩展：•(1)生成直接后继的集合TGenAllSuccessors(node);•(2)计算f(suc)，更新OPEN表和CLOSED表。将node移至CLOSE表，对sucT：•若suc不OPEN表或CLOSED表中，则计算f(suc)，并将suc加入OPEN表中；•若suc已经在OPEN表中，且新路径更短，则更新f(suc)的值为新代价；•若suc已经在closed表中，且新路径更短，则将closed表从CLOSED表移至OPEN表，并更新f(suc)；•(3)跳转到”2.选择”.一般的启发式搜索算法•搜索算法的不同，归根结底在于，对OPEN表节点扩展顺序的策略不同。•OPEN表节点扩展策略一般受制于一下因素：–称为评价函数的f(n)。其中，n可以是任意节点。一般地，f(n)有实际意义，如表示代价或耗散时，值越小越好。–选择下一个节点时考虑OPEN表哪些节点。•一般地，评价函数定义为f(n)=g(n)+h(n)–搜索算法或许已发现多条从初始节点s到节点n的路径，它们的最小代价为g(n)。–虽然从节点n到任一目标节点g的所有路径的最小代价尚不知道，但是可由领域知识对其作出估计，通过启发函数h(n)实现。–于是，f(n)表示从初始节点s经由节点n到达目标节点g的最优路径的代价估计值。•启发式搜索是OPEN表是优先队列的搜索。启发式搜索算法举例•八数码•f(n)=g(n)+h(n)的选取g(n)=“x所在的搜索深度”；h(n)=“x与sg相比，错位数字的数目”。•错位数h(n)=5。显然，5≤“实际需要的最少步数”，满足h(n)≤h*(n)。112831576412384765目标状态sg当前状态x贪婪搜索•启发式搜索也称最佳优先搜索。•贪婪搜索或贪婪最佳优先搜索：–f(n)=h(n)–若n是目标节点，则h(n)=0。•启发函数h(n)基于领域知识，前瞻（或猜测）从当前节点抵达任意目标节点的最小代价。h(n)越小，代表n越有希望好。可纳性、单调性、信息度A*搜索•若一个启发式搜索：对任意节点n，h(n)h*(n)，且对所有目标节点g有h(g)=0，则称之为A*搜索。•可纳性。启发函数对任意节点n满足满足h(n)h*(n)，则称该算法是可纳的，称h是可纳的启发函数。•根据A*定义，所有A*搜索都是可纳的。可纳性•请证明：A*算法是最优的。证：若问题有解，令最优解G的耗散为C*。•假设一个非最优解G‘出现在边缘上。G‘是解，故h(G’)=0，f(G‘)=g(G’)+h(G‘)=g(G’)C*。•对于任意一个处于最优解路径上的结点n，而f(n)不会高估经过n的最优解的路径耗散，总有f(n)≤f(G)=C*。•f(n)≤C*f(G’)综上，故G’将不会得到扩展，算法最终将得到最优解。单调性•单调性（一致性）。h(n)满足以下条件就是一致的：对于每个结点n，通过任何行动a生成的n的每个后继结点n‘，满足下列三角不等式：h(n)≤cost(n,a,n‘)+h(n‘)。该三角形是由n，n‘和离n最近的目标构成。•试证明：–如果h(n)是一致的，那么，它一定也是可纳的。–如果h(n)是一致的，那么，沿着任何路径的f(n)值是非递减的。具有单调性的启发函数的A*启发函数具有单调性的A*搜索算法的执行过程描述：•1.初始化：•OPEN={初始状态s}，CLOSED=。•2.选择：•(1)若OPEN=，搜索算法失败；•(2)OPEN，从OPEN表中按照某种策略选择一个状态node。•3.目标检测：•(1)若IsGoal(node)=True,则得一解,算法结束;•(2)若IsGoal(node)=False,则执行”4.扩展”.•4.扩展：•(1)生成直接后继的集合TGenAllSuccessors(node);•(2)sucT,suc在OPEN表，则更新f(suc)；若suc在CLOSED表，则不做任何操作；否则，将f(suc)赋予suc并放入OPEN表；•(3)OPENOPENT,CLOSEDCLOSED{node};•(4)跳转到”2.选择”.信息度•信息度。何时一个启发策略要比另一个启发策略好？•在两个A*启发策略的h1和h2中，如对搜索空间中的任一状态n都有h1(n)h2(n)h*(n)，就称策略h2比h1具有更多的信息度（或h2比h1更占优）•须注意的是：更多的信息性需要更多的计算时间，从而有可能抵消减少搜索空间所带来的益处！•h1(n)=“x与sg相比，错位数字的曼哈顿距离之和”；•h2(n)=“x与sg相比，错位数字的数目”。•h1(n)=6；h2(n)=5。202831576412384765目标状态sg当前状态x思考题寻找从城市A到城市G的最短路径21启发函数h(n)城市到G的直线距离A300B210C150D165E80F120G0寻找从城市A到城市G的最短路径22启发函数h(n)城市到G的直线距离A300B210C150D165E80F120G0A*搜索搜索最短路径的过程23g(A)=0h(A)=300f(A)=300270+210=480ABCDA245+150=395265+165=430(a)初始状态(b)扩展A之后考虑将A*搜索用于树搜索。即，下述过程没有考虑状态重复的问题。(a)～(e)描述了搜索的几个阶段。24f(B)=480ABCD395+210=605(c)扩展C之后f(D)=430BAE490+300=790370+80=45025f(B)=480ABCD(d)扩展D之后f(D)=430BAEAGf(B)=605f(A)=790f(E)=450530+300=830480+0=480问题：（1）生成的搜索树中出现了目标G，算法结束了么？（2）为什么？26f(B)=480ABCD(e)扩展E之后BAEAGf(B)=605f(A)=790370+100=470f(A)=830f(G)=480CG495+150=64527思考题•如何用A*求解旅行商问题？补充：如何设计A*的启发函数松弛子问题多个启发函数的复合迭加28启发函数的设计原则和方法29•降低了问题的行动（操作）限制，称为松弛。•以八数码为例。–八数码的行动描述：A与B水平或垂直相邻，且B是空的。–松弛a：一个数字可以从方格A移动到方格B，如果A与B相邻；–松弛b：一个数字可以从方格A移动到方格B，如果B是空的。–松弛c：一个数字可以从方格A移动到方格B。•注意：将松弛问题作为启发函数时，应保证容易求解。启发函数的设计原则和方法•如果有多个可纳式启发函数可用，h1,h2,…,hn，选择哪个最好？•可以通过定义多个函数的复合h(n)=max{h1(n),h2(n),…,hn(n)}来获得其中最好的启发。30子问题、模式库等•子问题的最优解的耗散是完整问题的耗散下界。因为只考虑了4个数字，所以是原问题的子问题。显然，两个模式对应的转换步数，是原问题的下界。31*24***311234****目标模式sg当前模式x预习阅读5.4、5.5。