我正在尝试解决PACMAN问题，寻找一条短路径（不是最短的，但足够好），能够在一个大迷宫中吃掉所有点。我看到很多人讨论TSP、Dijsktra、BFS、A*。我认为这不是TSP，因为我不需要回到起点，而且我可以重复经过节点。另外，我认为Dijsktra、BFS和A*不会有帮助，因为我不是在寻找最短路径，即使是那样，它们也无法在合理的时间内给出答案。

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

回答：

你是说你在参加一个比赛，要在30秒内在大迷宫中找到最短路径吗？

去年我为了好玩也做过这个（我的大学课程没有参加比赛）。经过几周的研究，我能够在30秒内找到迷宫的精确解。

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

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

希望这些关键词能让你走上正确的轨道。

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