人工智能课件

《人工智能课件》由会员分享，可在线阅读，更多相关《人工智能课件（32页珍藏版）》请在金锄头文库上搜索。

1、人 工 智 能徐长明第五章主 要 内 容 阅读教材5.1、 5.2、5.3、5.4、5.5。 爬山法和动态规划法 最佳优先搜索算法 可纳性、单调性以及信息性 博弈树搜索 计算复杂度最佳优先搜索g搜索就是寻找问题的解 的过程，即，寻找从初 始状态s到目标状态g的 路径。假设单步的路径耗散值 非负，即，cost (x, y) 0 。xys一般的图搜索一般的图搜索算法描述一般的启发式搜索算法 搜索算法的不同，归根结底在于，对OPEN表 节点扩展顺序的策略不同。 OPEN表节点扩展策略一般受制于一下因素： 称为评价函数的f(n) 。其中，n可以是任意节点。一般地，f(n) 有实际意义，如表示代价或耗

2、散时，值越小越好。 选择下一个节点时考虑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相比，错位数字

3、的数目”。 错位数h(n) = 5。显然， 5 “实际 需要的最 少步数”，满足h(n) h*(n)。1112384765目标状态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)

4、 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，通过过任何

5、行动动a 生成的n的每个后继结继结 点n，满满足下列三角 不等式：h(n) cost(n, a, n) + h(n)。该该三角 形是由n，n和离n最近的目标标构成。 试证明： 如果h(n)是一致的，那么，它一定也是可纳的。 如果h(n)是一致的，那么，沿着任何路径的f(n) 值是非递减的。具有单调性的启发函数的A*信息度 信息度。何时时一个启发发策略要比另一个 启发发策略好？ 在两个A*启发发策略的h1和h2中，如对对搜索 空间间中的任一状态态n都有h1(n) h2(n) h*(n) ，就称策略h2比h1具有更多的信息度 （或h2比h1更占优优） 须须注意的是：更多的信息性需要更多的计计 算时

6、间时间 ，从而有可能抵消减少搜索空间间所 带带来的益处处！ h1(n) = “x与sg相比， 错位数字的曼哈顿距 离之和”； h2(n) = “x与sg相比，错位数字的数目”。 h1 (n) = 6 ；h2 (n) = 5。2012384765目标状态sg当前状态x思 考 题寻找从城市A到城市G的最短路径21寻找从城市A到城市G的最短路径22A*搜索搜索最短路径的过程23g(A)=0 h(A)=300 f(A)=300270+210 =480ABCDA245+150 =395265+165 =430(a) 初始状态(b) 扩展A之后考虑将A*搜索用于树搜索。即，下述过程没有考虑 状态重复的问题

7、。(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思考题 如何

8、用A*求解旅行商问题？补充：如何设计A*的启发函数28启发函数的设计原则和方法29 降低了问题的行动（操作）限制，称为松弛。 以八数码为例。 八数码的行动描述：A与B水平或垂直相邻，且B是空 的。 松弛a：一个数字可以从方格A移动到方格B，如果A 与B相邻； 松弛b：一个数字可以从方格A移动到方格B，如果B 是空的。 松弛c：一个数字可以从方格A移动到方格B。 注意：将松弛问题作为启发函数时，应保证容 易求解。启发函数的设计原则和方法 如果有多个可纳式启发函数可用，h1, h2, , hn ，选择哪个最好？ 可以通过定义多个函数的复合h(n)= maxh1(n),h2(n),hn(n)来获得其中最好的启发。30子问题、模式库等 子问题的最优解的耗散是完整问题的耗散下界 。 因为只考虑了4个数字，所以是原问题的子问题。显然，两个模式对应的转换步数，是原问题的下 界。311234* 目标模式sg当前模式x预习阅读5.4、5.5。