我正在尝试为 PACMAN 问题找到一个解决方案,即找到一条能吃掉大迷宫中所有点的短路径(不是最短的,而是一条好的路径)。我看到很多人在谈论 TSP、Dijsktra、BFS、A*。我不认为这是一个 TSP,因为我不必回到我开始的地方,如果我愿意,我可以重复节点。而且我不认为 Dijsktra、BFS 和 A* 会有帮助,因为我不是在寻找最短路径,即使是这样,它也不会在合理的时间内给出答案。
谁能给我一些提示?这是什么问题?这是一种 TSP 吗?什么样的算法可以有效地解决这个问题?我将不胜感激有关实现的任何提示。
最佳答案
我猜你是想参加比赛,在 30 秒内找到大迷宫中的最短路径?
实际上我去年这样做是为了好玩(我的大学类(class)没有参加比赛)。经过数周的研究,我能够在 30 秒内完成迷宫的精确解。
我使用的启发式实际上是一种精确的启发式。我编写了一堆代码,使用基于图分解和动态规划的更高效的算法找到最小路径长度,然后将结果作为“启发式”值反馈回 A*。
要认识到的关键是,虽然图非常大(273 个节点),但它的雕刻宽度 (5) 很低,这意味着可以使用固定参数的易处理算法有效地解决它。
希望这些关键字足以让您走上正轨。
关于artificial-intelligence - PACMAN:吃掉所有点的捷径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12877560/