PACMAN: 吃掉所有点的简短路径

Question

我正在尝试解决PACMAN问题，即找到一个短路径（不一定是最短的，但是合适的）来吃掉迷宫中的所有豆子。我看到很多人谈论TSP、Dijsktra、BFS和A*算法，但我认为这不是TSP，因为我不必回到起点，而且如果需要，我可以重复经过某些节点。此外，我认为Dijsktra、BFS和A*算法并不能帮助我，因为我不是在寻找最短路径，即使是这种情况，也无法在合理的时间内得出答案。

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

- Bruno Calza

---

看这里：http://stackoverflow.com/questions/7437489。你也在学同样的课程吗？ - Junuxx

同一门课程，不同的问题。 - Bruno Calza

Answer 1

我猜您正在尝试在30秒内找到大迷宫中的最短路径进行比赛？

实际上，去年我为了好玩也做了这个（我的大学班级没有参加比赛）。经过几周的研究，我能够在30秒内找到迷宫的确切解决方案。

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

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

希望这些关键字足够让您找到正确的方向。

更新：我写了一篇博客文章解释解决方案

- Antimony