algorithm - A* 启发式：在多个点中通过一次的最短路径

Question

我正在尝试为清晰地图的吃豆人游戏提出一个好的和快速的启发式方法。

我的启发式方法是尝试计算 pacman 到达地图上每个点的食物所需的最小距离。我目前的算法基本上是 Prim 的 MST，它可以让我获得 O(n logn) 的运行时间，但不考虑 pacman 需要跟随边缘吃东西以及返回到前一个顶点的情况......

有更好的吗？

换一种说法：不用提笔连接几个点的最低成本是多少？

谢谢

Answer 1

在运行全对最短路径算法并用食物识别顶点后，这变成了旅行商问题。您无法有效地解决它，但您可以在多项式时间内构建任意好的近似解。除非您可以预先计算所有内容，否则您可能希望使用近似值。如果您可以预先计算事物（或以其他方式保证您有足够的时间来找到精确的解决方案），那么一旦您获得了所有对最短路径，您就可以简单地找到所有可能的最小总步行长度你吃食物的顺序的排列。通过注意两个食物块之间的最短路径何时穿过另一个食物块，这种蛮力方法可能会有所改进。