PACMAN:吃掉所有点的短途径

问题描述 投票:2回答:1

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

有人能给我一些暗示吗?这有什么问题?这是一种TSP吗?什么样的算法以有效的方式解决这个问题?我很欣赏任何有关实施的提示。

artificial-intelligence path-finding traveling-salesman pacman
1个回答
2
投票

我认为你正试图在30秒内找到大迷宫中最短路径的比赛?

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

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

要实现的关键是虽然图形非常大(273个节点),但它具有较低的雕刻宽度(5),这意味着它可以使用固定的参数易处理算法有效地求解。

希望足够的关键词可以让你走上正轨。

更新:I wrote a blog post explaining the solution

© www.soinside.com 2019 - 2024. All rights reserved.