知识卡片

普通读书笔记卡 · 5654.d.1.f.4.n.5 · 生成模型:未记录

图搜索发现更优路径要更新

理解等级:中级

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)。