知识卡片
图搜索发现更优路径要更新
A星应为每个状态维护已知最小g及前驱:发现更小g时更新开放集中的优先级;若该状态已关闭且启发式不一致,则重新开放。取出优先队列中已过期的条目时应跳过,或使用支持更新的索引堆。
03344–03345只检查closed并在更优时移除,未展示开放集中重复状态的统一更新;同一状态h固定时比较f等价于比较g,否则不一定。代码用深度表示g,适用于单位步长,不直接支持不同代价。
199称未知状态数时不能用二叉堆,这不成立:动态数组堆可以扩容;可用索引堆实现decrease-key,或插入新条目并在弹出时丢弃过期项。平衡树也是一种可选实现。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 图搜索发现更优路径要更新
- · 驱动因素
原书出处 · 2 处
- · 查看原书依据
闭合集中删除,因为我们可能能够得到一个最小耗费的解。 每个棋面状态都存储了一个后链,叫做DepthTransition,记录的是(a)生成此棋面状态的走法,(b)之前的状态以及(c)初始位置开始的深度。在A*搜索中,g*(n)通常当作深度。算法多次复制一个棋面状态,用来尝试各种走法。
- · 查看原书依据
二叉堆,因为我们事先不知道有多少棋面状态需要评估。因此我们使用平衡二叉树,插入棋面状态和得到最小开销的棋面状态的性能都是O(log n)。
参考来源
- 位置:《算法技术手册》第7章《解决方案》(spine1604;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1567.html;u197-ch07-006)。
- 结论依据:197全文及03344–03345完整Java代码实读。
- 原始内容:闭合集中删除,因为我们可能能够得到一个最小耗费的解。 每个棋面状态都存储了一个后链,叫做DepthTransition,记录的是(a)生成此棋面状态的走法,(b)之前的状态以及(c)初始位置开始的深度。在A*搜索中,g*(n)通常当作深度。算法多次复制一个棋面状态,用来尝试各种走法。
- 位置:《算法技术手册》第7章《驱动因素》(spine1606;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1569.html;u199-ch07-006)。
- 结论依据:199称未知状态数时不能用二叉堆,这不成立:动态数组堆可以扩容;可用索引堆实现decrease-key,或插入新条目并在弹出时丢弃过期项。平衡树也是一种可选实现。
- 原始内容:二叉堆,因为我们事先不知道有多少棋面状态需要评估。因此我们使用平衡二叉树,插入棋面状态和得到最小开销的棋面状态的性能都是O(log n)。