artificial-intelligence - PACMAN:吃掉所有点的捷径

Question

我正在尝试为 PACMAN 问题找到一个解决方案，即找到一条能吃掉大迷宫中所有点的短路径(不是最短的，而是一条好的路径)。我看到很多人在谈论 TSP、Dijsktra、BFS、A*。我不认为这是一个 TSP，因为我不必回到我开始的地方，如果我愿意，我可以重复节点。而且我不认为 Dijsktra、BFS 和 A* 会有帮助，因为我不是在寻找最短路径，即使是这样，它也不会在合理的时间内给出答案。

谁能给我一些提示？这是什么问题？这是一种 TSP 吗？什么样的算法可以有效地解决这个问题？我将不胜感激有关实现的任何提示。

Answer 1

我猜你是想参加比赛，在 30 秒内找到大迷宫中的最短路径？

实际上我去年这样做是为了好玩(我的大学类(class)没有参加比赛)。经过数周的研究，我能够在 30 秒内完成迷宫的精确解。

我使用的启发式实际上是一种精确的启发式。我编写了一堆代码，使用基于图分解和动态规划的更高效的算法找到最小路径长度，然后将结果作为“启发式”值反馈回 A*。

要认识到的关键是，虽然图非常大(273 个节点)，但它的雕刻宽度 (5) 很低，这意味着可以使用固定参数的易处理算法有效地解决它。

希望这些关键字足以让您走上正轨。

更新: I wrote a blog post explaining the solution