algorithm - A* 启发式 : Shortest path passing once in multiple points

Question

我正在尝试为清晰 map 的吃 bean 人游戏想出一个又好又快的启发式方法。

我的启发式方法是尝试计算吃 bean 人到达 map 上每个有食物的点所需的最小可能距离。我当前的算法基本上是 Prim 的 MST，它让我的运行时间为 O(n logn)，但没有考虑 pacman 需要跟随边缘进食以及返回到前一个顶点的情况...

还有更好的吗？

换句话说:在不提笔的情况下连接几个点的最小成本是多少？

谢谢

Answer 1

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