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

Question

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

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

Answer 1

这取决于图表。对于启发式算法的可接受性，它应该满足正三角形等式，就像用于 A* 搜索的一样。欧几里得距离在大多数情况下都可以很好地工作。与 A* 的不同之处在于，我们正在搜索的当前节点和开始节点之间的距离是计算的（因为对于 D* lite，最好的第一次搜索是从目标到开始的）。