第四章、有信的搜索和探索.ppt

第四章、有信息的搜索和探索 有信息的（启发式）搜索策略 启发函数 局部搜索算法和最优化问题 连续空间的搜索问题 联机搜索智能体和未知环境 有信息的（启发式）搜索策略 最佳优先搜索的思想（best-first-search） 基于评价函数f(n)选择要扩展的节点，通常选择评价值最低的节点进行扩展。 算法中的关键元素：启发函数h(n) h(n)＝从节点n到目标节点的最低耗散路径的耗散估计值 例如，在罗马尼亚问题中最低耗散路径的耗散估计值可以是相应的两个城市之间的直线距离。 主要算法 贪婪最佳优先算法 A*搜索 存储限制的启发式搜索 贪婪最佳优先算法 f(n)=h(n)，例如在罗马尼亚问题中采用hSLD 算法分析 非最优的，找到的路径比经过Rimnicu Vilcea到Pitesti到Bucharest的路径长32公里 使h(n)最小化会对错误的起点较敏感，例如从Iasi到Fagaras。 和深度优先一样倾向于沿着一条路径搜索下去直到目标，但在遇到死路时会退回。 非完备的 如果有一个好的启发函数，时间和空间复杂度会很好地降低。 A*搜索：最小化总的估计解耗散 f(n)=g(n)+h(n) g(n)：从起点到节点n的路径耗散 如果h从不高估到达目标的最低路径耗散值，我们称h是可容纳启发式。 性质：如果h是可容纳的，那么使用树搜索的A*算法是最优的。 用反证法证明 如果用图搜索代替树搜索，则解有可能是非最优解。 在图搜索下保证返回的解是最优解：解决方案 扩展图搜索算法使它丢弃重复路径中耗散大的那条，或 保证到达任何重复状态的最优路径总是第一条被追随。办法是： 对h加上一致性的要求：对于每个节点n和通过任何行动a生成的n的每个后继节点n’ ，h(n) ? c(n,a, n’ )+h(n’ ) h是一致的? A*算法最优和f非递减 在状态空间上绘制等值线 算法分析 完备的 最优的 效率最优的 但，在搜索空间中处于目标等值线内的节点数仍然是解长度的指数级， 并且，它在内存空间中保存了所有的节点。 存储限制的启发式搜索：迭代深入的思想 截断值是超过上一次迭代截断值的节点中最小的f的耗散值 主要算法：RBFS和MA* 算法分析 如果h是可采纳的，那么RBFS是最优的 空间复杂度是O(bd) 但，利用的内存太小了。 第四章、有信息的搜索和探索 有信息的（启发式）搜索策略 启发函数 局部搜索算法和最优化问题 连续空间的搜索问题 联机搜索智能体和未知环境 启发函数的选择 h1＝不在位的棋子数 h2＝所有棋子到其目标位置的距离和 HW 4.1, 4.5 4.7,4.8 启发函数的精确度对性能的影响 刻画启发式质量的途径?有效分支因子b* 假设A*算法生成的节点数为N*，解的深度为d，考虑 IDS和A*算法的搜索代价和有效分支因子的比较 设计可采纳的启发函数 降低了行动限制的问题称为松弛问题 例子：八数码游戏的规则是一个棋子可以从方格A移到B，如果B和A相邻，而且B是空格。 一个松弛问题的最优解的耗散是原问题的一个可采纳、一致的启发式 从数个可采纳的启发函数中构造新的启发函数，例如取它们的最大值。 从给定问题的子问题的解耗散中得到可采纳的启发式 从经验中学习启发函数 归纳学习方法 Predict solution cost for other states that arise during the search. 例如，“不在位的旗子数”可用来预测从一个状态到目标状态的距离。 第四章、有信息的搜索和探索 有信息的（启发式）搜索策略 启发函数 局部搜索算法和最优化问题 连续空间的搜索问题 联机搜索智能体和未知环境 背景知识 某些问题不关心到达解的路径 局部搜索算法：从单独的一个当前状态出发，通常只移动到与之相邻的状态，并且不保留解的路径。优点： 需要很少的内存 经常能在很大或无限的状态空间中找到合理的解 局部搜索算法 爬山法搜索 模拟退火搜索 局部剪枝搜索 遗传算法 爬山法搜索 向值增加的方向持续移动 例子：8皇后问题 目标：任何一个皇后都不会攻击到其他的皇后（皇后可以攻击和它在同一行、同一列或同一对角线上的皇后） h取作可以彼此攻击的皇后对的数目（忽略障碍） 爬山法遇到的问题 局部极值 高原 山脊 解决办法 在山肩时允许侧向移动 不完备?随机重新开始 完备的概率接近1 但，效率低下。 模拟退火搜索：结合爬山法和随机行走 比喻：在冶金中退火是为了增强金属和玻璃的韧性和硬度而先把它们加热到高温然后逐渐冷却的过程 局部剪枝（beam）搜索 记录k个状态而不是一个 在这些k个状态的后继状态中选择 遗传算法 通过把两个父状态结合来生成后继 讨论 遗传算法最主要的优点（如果有的话）来自于杂交的操作 但，数学上可以证明，如果基因编码的位置在初始时候就随机