A*启发式:在多个点中传递一次的最短路径

Question

我正试图为一个清晰的地图pacman游戏提出一个良好而快速的启发式算法.

我的启发式试图计算出pacman需要前往地图上每个食物点的最小距离.我当前的算法基本上是Prim的MST,它给我一个O(n logn)的运行时间,但是没有考虑pacman需要跟随边吃的情况,以及返回到前一个顶点......

有更好的吗？

用另一种方式说:在不抬起笔的情况下连接几个点的最低成本是多少？

谢谢

Answer 1

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