知识卡片
放宽规则得到代价下界
按推箱次数求最短路时,可忽略箱子互挡和目标独占,再把每个箱到最近目标的距离相加。真实方案必须安排每个箱到一个目标,还要解决互相阻挡,放宽规则后的最低推数因此不会高于真实值。每格到最近目标的距离可预先按墙布局计算。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 2.2 推箱子
原书出处 · 1 处
- · 查看原书依据
这是对于所有箱子到达目标点最近路径的总和(只考虑墙)。在初始状态下可以通过查找除墙以外的每个方格到最近目标点的路程,轻松找到任何节点的启发式函数值。
参考来源
- 位置:《AI游戏开发和深度学习进阶》第2章 2.2 推箱子(book-source,`extracted/AI游戏开发和深度学习进阶/_epub-src/OEBPS/Text/0017.xhtml`)
- 结论依据:原文放宽箱子互斥和玩家行走限制,得到只按墙计算的总距离。
- 原始内容:这是对于所有箱子到达目标点最近路径的总和(只考虑墙)。在初始状态下可以通过查找除墙以外的每个方格到最近目标点的路程,轻松找到任何节点的启发式函数值。