PACMAN: a short path for eating all the dots

Question

I am trying to find a solution for the PACMAN problem of finding a short path (not the shortest, but a good one) that eats all the dots in a big maze. I've seen a lot of people talking about TSP, Dijsktra, BFS, A*. I don't think this is a TSP since I don't have to go back where I started and I can repeat node if I want. And I don't think Dijsktra, BFS and A* would help because I'm not looking for the shortest path and even if that was the case, it wouldn't give a answer in a reasonable time.

Could anyone give me hints on this? What kind of problem is this? Is this a kind of TSP? What kind of algorithms approach this problem in a efficient way? I'd appreciate any hints on implementation.

Answer 1

I take it you're trying to do contest where you find the shortest path in the big maze in under 30 seconds?

I actually did this last year for fun (my college class didn't do the contest). After weeks of research, I was able to do an exact solution of the maze in under 30 seconds.

The heuristic I used was actually an exact heuristic. I wrote a bunch of code to find the minimal path length using a much more efficient algorithm based on graph decomposition and dynamic programming, and then fed the results back into A* as the 'heuristic' value.

The key thing to realize is that while the graph is very big (273 nodes), it has a low carving width (5), meaning that it can be solved efficiently using a fixed parameter tractable algorithm.

Hopefully that's enough keywords to get you on the right track.

Update: I wrote a blog post explaining the solution