D * lite：我应该使用什么启发式函数？

Question

[我正在尝试实现D * -Lite寻路算法，如Koenig和Likhachev在2002年的文章中对基于网格的导航图所描述的。

但是我在该论文中没有看到任何启发式功能。那么，我应该选择什么功能呢？我可以使用直线距离还是曼哈顿距离？

Answer 1

取决于图表。它应该满足规则三角相等性，以允许启发式算法，就像A *搜索中的规则一样。欧几里得距离在大多数情况下会很好地工作。与A *的不同之处在于，计算的是我们正在搜索的当前节点与起始节点之间的距离（因为对于D * lite，从目标到起点都进行了最佳的首次搜索）。