D 启发式搜索 人工智能(AI)ppt课件.ppt

1,启发式（有信息）搜索Heuristic (Informed) Search(我们试着做一些聪明的选择) R&N: Chap. 4, Sect. 4.13,2,启发函数 h(N) 0 估计从状态（N）到目标状态的耗散其值与当前的搜索树无关；仅取决于状态STATE(N) 和目标测试 GOAL?Example:h1(N) = 不在位的牌数 = 6为什么它是对目标距离的一个估计呢？,启发函数Heuristic Function,3,h1(N) =不在位的牌数 = 6h2(N) = 每个数码牌与其目标位置的(Manhattan) 距离和 = 2 + 3 + 0 + 1 + 3 + 0 + 3 + 1 = 13h3(N) = sum of permutation inversions = n5 + n8 + n4 + n2 + n1 + n7 + n3 + n6 = 4 + 6 + 3 + 1 + 0 + 2 + 0 + 0 = 16,Other Examples,4,8-Puzzle,f(N) = h(N) = 不在位数码牌的个数,白色为空位,5,8-Puzzle,f(N) = g(N) + h(N) 式中 h(N) =不在位数码牌的个数,6,8-Puzzle,f(N) = h(N) = S 数码牌与其目标位置的距离,7,最佳优先效率Best-First Efficiency,f(N) = h(N) = 与目标的直线距离,Local-minimum problem,8,什么是我们能证明的？,如果状态空间是无限的，通常搜索是不完备的如果状态空间是有限的，但不丢弃那些重复访问的状态的话，通常搜索也是不完备的如果状态空间是有限的，并丢弃那些重复访问的状态，那么搜索是完备的，但通常不是最优的,9,可采纳的启发Admissible Heuristic,令h*(N)为从节点N到目标节点的最优路径的耗散 启发式函数h(N) 是可纳的，若： 0 h(N) h*(N)可纳的启发式函数总是最优的！,10,h1(N) = 不在位数码牌的个数 = 6是 ?h2(N) = sum of the (Manhattan) distances of every tile to its goal position = 2 + 3 + 0 + 1 + 3 + 0 + 3 + 1 = 13is admissibleh3(N) = sum of permutation inversions = 4 + 6 + 3 + 1 + 0 + 2 + 0 + 0 = 16 is not admissible,8-Puzzle Heuristics,11,h1(N) = 不在位数码牌的个数 = 6是可纳的h2(N) =每个数码牌与其目标位置的(Manhattan) 距离和 = 2 + 3 + 0 + 1 + 3 + 0 + 3 + 1 = 13是 ?h3(N) = sum of permutation inversions = 4 + 6 + 3 + 1 + 0 + 2 + 0 + 0 = 16 is not admissible,8-Puzzle Heuristics,12,h1(N) = 不在位数码牌的个数 = 6是可纳的h2(N) =每个数码牌与其目标位置的(Manhattan) 距离和 = 2 + 3 + 0 + 1 + 3 + 0 + 3 + 1 = 13是 可纳的h3(N) = sum of permutation inversions = 4 + 6 + 3 + 1 + 0 + 2 + 0 + 0 = 16 is not admissible,8-Puzzle Heuristics,13,h1(N) = 不在位数码牌的个数 = 6是可纳的h2(N) =每个数码牌与其目标位置的(Manhattan) 距离和 = 2 + 3 + 0 + 1 + 3 + 0 + 3 + 1 = 13是 可纳的h3(N) = sum of permutation inversions = 4 + 6 + 3 + 1 + 0 + 2 + 0 + 0 = 16 is not admissible,8-Puzzle Heuristics,14,怎样构造一个可纳的 h ？,一个可纳的启发函数通常可看作是一个松弛问题（通过去除一些约束限制得到）的最优解的耗散在机器人导航中:曼哈顿距离对应于去除障碍物的限制欧几里得距离对应于去除障碍物的限制及机器人只能在格子内移动的约束详情在本课稍后叙述,15,A* 搜索(AI中被最广泛应用的算法),f(N) = g(N) + h(N), 其中:g(N) = 从起始节点到节点N的路径耗散h(N) = 可纳启发函数对于所有的弧: c(N,N) 0采用 SEARCH#2 搜索算法（节点扩展时目标测试）最佳优先（Best-first）搜索于是被称为 A* search,16,结论 1,A* 完备 最优即使不丢弃重复访问的节点，以上结论也是成立的,17,时间限制问题,当一个问题无解时，如果该问题的状态空间是无限的或者不限制重复访问的次数，那么A*将不停的永远运行下去。其他的一些情况，也可能使A*花费大量的时间才会停止。因此，实际应用中，对A*将会给定一个时间的限制。如果在时间限制内没有找到解，则停止运行。这样的话，将没有办法知道该问题是否无解，或者是否需要更多的时间就能找到解当AI系统“小”且一次只是解决一个搜索问题时，以上的问题不会成为太大的问题，不必过虑. 但是当AI系统变得很大，需要同时解决许多个搜索问题，其中一些是无解问题的时候，该如何定义相应的时间限制呢？有兴趣的同学可以进一步阅读相关文献 （如Motion Planning .）,18,8-Puzzle,f(N) = g(N) + h(N) 式中 h(N) = 不在位的数码牌个数,19,Robot Navigation,20,Robot Navigation,f(N) = h(N), 其中 h(N) = 与目标的Manhattan 距离(不是 A*),21,Robot Navigation,0,2,1,1,5,8,7,7,3,4,7,6,7,6,3,2,8,6,4,5,2,3,3,3,6,5,2,4,4,3,5,5,4,6,5,6,4,5,f(N) = h(N), 其中 h(N) = 与目标的Manhattan 距离(不是 A*),7,0,22,Robot Navigation,f(N) = g(N)+h(N), 式中 h(N) = 与目标的Manhattan距离(A*),7+0,8+1,0+11,23,最佳优先搜索（贪婪搜索）Best-First Search,评价函数 f 将搜索树的每一个节点N映射为一个实际的数值f(N) 0 最佳优先搜索按照节点的f值升序排列边缘队列,24,A* 搜索,f(N) = g(N) + h(N), 其中:g(N) = 从起始节点到节点N的路径耗散h(N) = 可纳启发函数对于所有的弧: c(N,N) 0采用 SEARCH#2 搜索算法（节点扩展时目标测试）最佳优先（Best-first）搜索于是被称为 A* search,25,结论 1,A* 完备 最优即使不丢弃重复访问的节点，以上结论也是成立的,26,如何处理可重复访问状态?,此处的启发函数h无疑是可纳的,27,?,如果因为该新节点的状态是重复访问的，就将它丢弃的话，那么搜索算法下一个就将扩展目标节点，因此返回一个非最优解,如何处理可重复访问状态?,28,2+90,相反的，如果不因为状态的重复访问而丢弃新节点，那么搜索算法将会找到最优解，并停止,如何处理可重复访问状态?,29,但是 .,如果不丢弃那些重复访问状态的节点，搜索树可能会达到指数级的访问状态数量,30,如果新路径耗散 之前的路径耗散，那么丢弃该重复访问状态的节点对 A* 不会产生负面影响因此，实际上如果一个节点的重复访问状态是已经被其祖先节点访问过的话，可以将其丢弃A* 仍然是最优的，但状态仍可能会被多次访问搜索树可能会变得庞大，达到访问状态的指数级幸运的是，对于许多可纳函数，是所谓一致可纳的，这使得算法在处理重复访问状态上变得非常高效,31,一致启发函数Consistent Heuristic,一个启发函数 h 是一致 (或单调)的，若 1) 对于每个节点N及其每一个子节点N : h(N) c(N,N) + h(N) 2) 对于每个目标节点G: h(G) = 0,(三角形不等式),N,N,h(N),h(N),c(N,N),一致启发函数也是可纳的, 直觉: 一致启发函数将会随着搜索树的深入变得越来越精确,32,一致启发函数也是可纳的可纳启发函数不一定是一致的，但许多的可纳启发函数是一致的,一致性和可纳性Admissibility and Consistency,33,8-Puzzle,STATE(N),goal,h1(N) = 不在位的数码牌个数 h2(N) = 与目标位置的Manhattan距离的和都是一致的吗? (为什么呢？),34,若启发函数h是一致的，则只要A*扩展一个节点，那一定是找到了到达该节点状态的最优路径,结论 #2,35,证明 (1/2),考虑节点N及其子节点N 由于h是一致的: h(N) c(N,N)+h(N)f(N) = g(N)+h(N) g(N)+c(N,N)+h(N) = f(N)因此，其它任何一条路径都不可能使f更低,N,N,36,一致启发函数下的状态重复访问,当一个节点被扩展时，保存其状态到CLOSED表中当一个新的节点N生成时:如果STATE(N)已在CLOSED中，则丢弃N如果在边缘里存在节点N有STATE(N) = STATE(N) ，则丢弃其中f最大的一个（ N 或 N ）,37,是否采用一致启发函数的A*就是我们追求的全部?,No ! 有许多一致函数是毫无作用的,38,例如: h 0,它是一致的 (因此也是可纳的) !采用h0的A* 其实就是代价一致搜索 uniform-cost search广度优先和代价一致搜索其实就是A*的特例,39,启发函数的精确度Heuristic Accuracy,h1 和 h2 为两个一致启发函数，对于所有的节点N有: h1(N) h2(N)h2 被称为比h1更精确（或更有启发知识）,h1(N) = 不在位的数码牌个数h2(N) = 与目标位置的曼哈顿距离和h2 比h1更精确,40,结论 #3,令 h2 比h1更精确令A1*为采用h1的A* A2*为采用h2的A*只要有解， A2*扩展的所有节点（除了可能某些节点f1(N) = f2(N) = C* (最优解耗散)，都会被A1*所扩展，即A2* 不会比A1* 扩展更多的节点,41,证明,C* = h*(initial-node) 最优解的耗散所有f(N) C*的节点N最终都会被扩展； f(N) C*的节点N没有一个会被扩展所有h(N) C*g(N)的节点N最终都会被扩展。因此，所有h2(N) C*g(N)的节点N都会被A2*扩展，由于h1(N) h2(N) ，所以节点N也一定会被A1*扩展如果有多个节点N有f1(N) = f2(N) = C* (若问题有解则这些节点包含了最优目标节点) ，A1* and A2* 可能按相同的次序扩展这些节点（直到有一个目标节点被扩展），也可能按照不相同的次序扩展,42,有效分支因子Effective Branching Factor,用来刻画启发函数的效能针对某具体问题，令N为A*扩展的总节点数， d为解的深度有效分支因子b* 由下式定义n = 1 + b* + (b*)2 +.+ (b*)d,43,实验结果(see R&N for details),8-puzzle :h1 = 不在位数码牌个数h2 = 所有数码牌与其目标位置的曼哈顿距离和随机产生许多问题实例有效分支因子的平均值 (及扩展节点数) :,44,通过对每一个节点求解松弛问题8数码问题中，每个数码牌与其目标位置的曼哈顿距离和其实相当于解决8个简单的问题:即忽略了其他数码牌的负面相互影响,怎样构造一个好的启发函数?,di 是将数码牌i移动到其目标位置的最短路径，移动的过程忽略了其他数码牌的存在,e.g., d5 = 2h2 = Si=1,.8 di,45,考虑如下两个稍复杂的松弛问题:,能做得更好吗?,d1234 = 将数码牌1, 2, 3, 和4移动到对应的目标位置的最短路径的长度，（在不考虑其它的数码牌的情况下）, h = d1234 + d5678 两个子问题,如何计算 d1234 和 d5678?,46,考虑如下两个稍复杂的松弛问题:,能做得更好吗?,d1234 = 将数码牌1, 2, 3, 和4移动到对应的目标位置的最短路径的长度，（在不考虑其它的数码牌的情况下）, h = d1234 + d5678 两个子问题,这些距离被预先计算出来并保存在模式数据库中每个子问题将生成一个有着3024个节点/状态的图,这样的方法使15- and 24-puzzle问题的解决速度加快了几个数量级 (see R&N p87),47,完备性和最优性,采用一致启发函数的A* 有着很好的特性: 完备，最优，无需重复访问状态理论上的完备性不意味着“实际”的完备，比如需要很长的时间才能得到一个解（如前所述时间因此，如果不能设计出精确的一致启发函数，不如设法找一个非可纳的启发函数，即使无法保证其完备性和最优性，却能在实际应用中做得不错，这样的思路反而更好,48,迭代深入的A*搜索 Iterative Deepening A* (IDA*),思想: 通过对f的值设置一个截至范围，以减少所需的内存一致启发函数 hIDA*算法:将截至值设定为f(initial-node)重复:执行深度优先搜索，扩展所有f(N) cutoff的节点重新设定截至值cutoff 未扩展节点（叶节点）中的最小f值,49,8-Puzzle,f(N) = g(N) + h(N) with h(N) = number of misplaced tiles,Cutoff=4,50,8-Puzzle,Cutoff=4,f(N) = g(N) + h(N) with h(N) = number of misplaced tiles,51,8-Puzzle,Cutoff=4,f(N) = g(N) + h(N) with h(N) = number of misplaced tiles,52,8-Puzzle,Cutoff=4,f(N) = g(N) + h(N) with h(N) = number of misplaced tiles,53,8-Puzzle,Cutoff=4,f(N) = g(N) + h(N) with h(N) = number of misplaced tiles,54,8-Puzzle,Cutoff=5,f(N) = g(N) + h(N) with h(N) = number of misplaced tiles,55,8-Puzzle,Cutoff=5,f(N) = g(N) + h(N) with h(N) = number of misplaced tiles,56,8-Puzzle,Cutoff=5,f(N) = g(N) + h(N) with h(N) = number of misplaced tiles,57,8-Puzzle,Cutoff=5,f(N) = g(N) + h(N) with h(N) = number of misplaced tiles,58,8-Puzzle,Cutoff=5,f(N) = g(N) + h(N) with h(N) = number of misplaced tiles,59,8-Puzzle,Cutoff=5,f(N) = g(N) + h(N) with h(N) = number of misplaced tiles,60,8-Puzzle,Cutoff=5,f(N) = g(N) + h(N) with h(N) = number of misplaced tiles,5,61,IDA*的优点/缺点,优点:仍是完备与最优的所需的内存比A*小避免了对边缘队列进行大量的排序搜索工作缺点:无法避免重复访问那些不在当前路径上的状态只利用了可用内存的很小 一部分，内存没有得到充分利用( 内存限制搜索, 参见 R&N p. 101-104),62,局部搜索Local Search,“轻”-内存搜索方法无搜索树；描述的只是当前状态!只能应用于那些路径无关的问题（例如8皇后问题），除非将路径编码到状态与最优化技术有着许多相似点,63,“并行” 局部搜索技术,同时（但并非独立）执行多个局部搜索: 剪枝搜索 Beam search 遗传算法 Genetic algorithmsSee R&N, pages 88-95,64,搜索问题,盲目搜索,启发式搜索: 贪婪 和 A*,构造启发函数,局部搜索,A*的变化,65,66,67,68,69,70,71,72,何时使用搜索技术?,搜索空间小，且无其他的有效方法，或者不值得投入开发一个更为高效的技术搜索空间大，且无其他的有效方法，或者有一个“好”启发函数,