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

Question

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

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

Answer 1

这取决于图表。它应该像 A* 搜索一样满足启发式可接受性的正三角形等式。欧几里德距离在大多数情况下都适用。与 A* 的唯一区别是计算我们正在搜索的当前节点与起始节点之间的距离（因为对于 D* lite，最好的第一次搜索是从目标到开始完成的）。