3知情搜索ppt课件

搜索 知情搜索 概要 知情搜索与启发方式第一种尝试 最佳优先贪婪搜索A 算法最佳性启发函数的条件完全性局限性 空间复杂性等议题扩展 再看搜索 评价函数f s 经由s的最廉价路径的估计代价最佳优先搜索 选择f值最小的结点来优先扩展算法 对每个状态s 储存一个值f s 选择f最低的状态做下一步扩展 插入它的后续态 如果仔细地选择f 则可以最终找到最低代价序列 实例 UCS 等代价搜索 f A g A 当前从START到A的最短路径的总代价 把等待扩展的状态存储在一个优先队列中 以便有效地查询f的最小值 最佳就是保证找到最小代价序列 问题 对于任何给定状态离终态有多远 无指导 解决 设计一个估计某一状态与终态之间距离的函数 最乐观的猜测 如果A比B更接近于GOAL 则它是一个更有希望的扩展状态 启发函数 对该搜索问题 h是一个启发函数 h s 从s到GOAL的最短路径的代价估值 仅通过当前问题中的状态及转换 是不能计算出h的 如果可能的话 则已经知道最佳路径了 h是建立在关于该问题的外部知识上的 因此 称为知情搜索 问题 h的典型实例 怎么使用h 什么是h的必要性质 启发函数实例 h s 到GOAL的直线距离 从s出发的直线距离比从s 出发的短 因此 s成为最佳路径的机会更大 终点 起点 启发函数实例 怎样来定义h s 1 5 3 2 6 4 8 7 1 2 4 7 5 3 6 8 起点 终点 第一种尝试 最佳优先贪婪搜索 GBFS 最简单的启发函数 总是选择h最小的结点来扩展 即f s h s 初始化PQ插入 START h START 偶对到PQ中while PQ不空 且不包含终态 从PQ中弹出h值最小的状态s对在succs s 中的所有s 如果s 不在PQ中 且未访问过插入 s h s 偶对到PQ中 问题 在该场合下 能找到的答案是什么 虽然采用合理的启发函数 但贪婪搜索不是最佳的 解决问题的尝试 g s 仅是从START到s的代价 h s 估算从s到GOAL得代价 关键点 g s h s 估算从START经由s到达GOAL的最廉价路径的总代价 A 算法 A 能解决该问题吗 START 4 A 5 f A h A g A 3 g START cost START A 3 0 2 B 5 C 7 C与返回指针 A START 被放在队列中 f B h B g B 2 g A cost A B 2 2 1 f C h C g C 1 g A cost A C 1 2 4 C 5 发现f C 的一个较低值及返回指针 B A START f C h C g C 1 g B cost B C 1 3 1 GOAL 6 与A 有关的议题 终止条件状态重访算法最佳性避免状态重访选择好的启发式方法降低空间开销 A 终止条件 当GOAL从队列中弹出时 就停止 队列 B 4 A 8 C 4 A 8 D 4 A 8 A 8 GOAL 10 在访问经由A的路径前 就已遇上GOAL 出现此问题是由于每步利用的仅是到达目标的路径代价的一个估值 重访状态 队列 START 8 B 4 A 8 A 8 C 10 C 9 5 重访 在PQ中 D 3 5 GOAL 9 5 重访一个已扩展状态 怎样更新它的优先级 重访状态 队列 START 8 B 4 A 8 C 4 A 8 D 4 A 8 A 8 GOAL 10 C 3 5 GOAL 10 重访 D 3 5 GOAL 10 重访 GOAL 9 5 重访 在PQ中 重访一个已扩展状态 另一个例子 从队列中弹出f s 值最小的状态sifs GOALreturnSUCCESSelse扩展s 对在succs s 中的所有s f g s h s g s cost s s h s if s 之前没见到过ors 之前以f s f 被扩展过ors 在PQ中 且f s f 升级或插入 s 新的代价f 偶对到PQprevious s selse不处理s 这是因为它已被访问过 并且它的当前路径代价f s 仍是START到s 路径代价的最低值 A 算法中的内循环体 什么条件下A 是最佳的 问题 h 是到终态路径代价的一个差的估计 START 6 GOAL 3 A 8 最终路径 START GOAL 并且代价为3 允许的启发方式 定义h s 从s到目标的真实最小代价 如果h s h s 对所有状态s成立 则h是允许的 也即 一个允许的启发方式决不高估到达目标的代价 而是乐观地估计到目标的代价 A 保证找到最佳路径 如果h是允许的 一致 单调 启发方式 h s cost s s h s 这类三角形不等式表明 路径代价总是增加的 因此仅需要扩展结点一次 s h s GOAL cost s GOAL s cost s s h s 最终路径 s GOAL 从队列中弹出f s 值最小的状态sifs GOALreturnSUCCESSelse扩展s 对在succs s 中的所有s f g s h s g s cost s s h s if s 之前没见到过ors 之前以f s f 被扩展过or如果h是一致性的s 在PQ中 且f s f 升级或插入 s 新的代价f 偶对到PQprevious s selse不处理s 这是因为它已被访问过 并且它的当前路径代价f s 仍是START到s 路径代价的最低值 A 算法中的内循环体 实例 机器人导航问题 最短路径的长度至少是s到GOAL的距离 因此 直线距离是一个允许的启发方式 拼图怎样处理 终点 起点 终点 h s h1 错放的拼块数 h1 s 7h2 Manhattan距离 h2 s 4 2 2 2 2 0 3 3 18 5 4 2 1 3 8 6 7 2 3 1 6 4 8 7 5 起点 终点 启发方式比较 h1 错放的拼块数h2 Manhattan距离 IDS有重复扩展状态的倾向 因此 比较而言 会高估A 的性能 已扩展状态数没有包括访问队列所需的log 时间 启发方式比较 h1 s 7h2 s 4 2 2 2 2 0 3 3 18h2比h1大 同时 采用h2的A 似乎更有效 在这两个观察之间存在一种联系吗 如果对所有的s 有h2 s h1 s 则h2支配h1 对任何两个启发方式h2与h1 如果h2支配h1 则采用h2的A 更有效 扩展状态更少 因为h h 所以较大的h应是对真实路径代价的一个更好的近似 起点 终点 实例 最大的h h B 10 A 11 C 12 GOAL 10 A 11 C 12 最终路径 START B GOAL 较小的h B 2 A 3 C 12 A 3 C 12 GOAL 10 GOAL 10 C 12 最终路径 START B GOAL 实例 最小的h UCS搜索 A 1 B 1 C 1 B 1 C 1 GOAL 11 C 1 GOAL 10 GOAL 10 最终路径 START B GOAL A 最佳解的性质 以f s g s h s 为次序来扩展状态 C 为最佳路径的代价 A 搜索 将扩展f s C 的任何结点特例 h s 0 f s g s UCS搜索 需扩展所有当前态的后续态h s h s f s g s h s 只扩展一个当前态的最佳后续态 局限性 计算 在最坏的场合 可能需要检测所有的状态 即O N 好消息 A 是最有效的 即 对一个给定的h 不存在扩展结点较少的其它最佳算法 坏消息 存储也可能会较大 即O N 迭代加深搜索 IDS 需要使DFS最佳 IDS 执行DFS来搜索长度仅为1的路径 如果路径长度 1 则DFS停止 如果该搜索无答案 则重新执行DFS来搜索长度 2的路径 如果该搜索无答案 则重新执行DFS来搜索长度 3的路径 继续直到找到一个答案为止 实例 迭代加深A IDA 与迭代加深DFS相同的思路 不同之处是 用f s 而不是转换次数来控制搜索的深度 实例 假设整数代价 执行DFS 在f s 0的s状态处停止 如果已到达目标 则停止 执行DFS 在f