知识卡片
网格移动规则决定距离启发值
网格寻路的启发距离要与允许的移动相配。设当前格到目标的横向差 dx、纵向差 dy(取绝对值),D 为每步最小代价:
| 允许的移动 | 启发值 | 演示 dx=3、dy=4、D=1 |
|---|---|---|
| 仅上下左右 | 曼哈顿 D·(dx+dy) | 7 |
| 八方向,斜走也只花 D | 对角线 D·max(dx,dy) | 4 |
| 任意角度 | 欧几里得 D·√(dx²+dy²) | 5 |
每个公式恰好是在对应移动规则下、没有障碍时的最短代价;障碍与额外成本只会让真实路线更长,所以它们不会高估。规则配错就会出问题:只能走四方向时若用欧几里得的 5,只是偏低、搜索更慢;八方向且斜走代价为 D 时若用曼哈顿的 7,就高估了真实的 4,可能失去最短路保证。若斜走另有成本(如 √2·D),最大值公式不再等于无障碍真实代价,需按实际斜向代价重算。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- * · 查看原书依据
常用的启发函数有曼哈顿距离、对角线距离、欧几里得距离等。 曼哈顿距离是一种标准的启发函数。
参考来源
- 位置:《智能算法导论》第 175 项《18.2 A*算法实现/18.2.1 A*算法原理》(源文件:`_epub-src/EPUB/xhtml/chapter18_0003.xhtml`)
- 结论依据:式(18-2)至(18-4)分别给出曼哈顿、等价八方向对角线与欧几里得距离;正文说明它们对应不同移动规则。dx=3、dy=4 的数值为依据三式补充的教学演算;“配错会高估或偏低”由各式与对应移动规则下的无障碍最短代价比较推出,非书中案例。
- 原始内容:常用的启发函数有曼哈顿距离、对角线距离、欧几里得距离等。曼哈顿距离……常用于在地图上只能前后左右移动的情况。地图中若允许对角运动,则可以使用对角线距离作为启发函数……地图中若允许任意角度的运动,则可以使用欧几里得距离。