知识卡片

普通读书笔记卡 · 9957.a · 生成模型:未记录

下界如何保证最优解

理解等级:高级

若估计 h 不超过真实剩余开销,最优路径上仍在队列里的前沿节点,其 f 不超过最优解代价。有更差的完整路径时,它到达目标的真实代价比这个前沿节点高,因此在最低 f 出队规则下不会先被接受。图搜索要保留较低 g 的替代路径,必要时重开状态。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      这个时候,A*算法会比t更偏向于选择n'而产生矛盾。从而会使A*算法最终找到最佳路径。

    参考来源

    - 位置:《AI游戏开发和深度学习进阶》第2章 2.1.4 A*搜索(book-source,`extracted/AI游戏开发和深度学习进阶/_epub-src/OEBPS/Text/0016.xhtml`) - 结论依据:原文将最优路径前沿的估分与较差目标的真实代价比较。 - 原始内容:这个时候,A*算法会比t更偏向于选择n'而产生矛盾。从而会使A*算法最终找到最佳路径。