2

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

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

4

1 回答 1

2

我认为您正在尝试在 30 秒内找到大迷宫中最短路径的竞赛？

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

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

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

希望这足以让您走上正轨。

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

于 2012-10-13T22:29:59.747 回答