A* heuristic: Shortest path passing once in multiple points

Question

I'm trying to come up with a good and fast heuristic for a clear-map pacman game.

My heuristic is trying to calculate the smallest distance possible that the pacman needs to travel to go to every points with food on the map. My current algorithm is basicly Prim's MST which gets me a O(n logn) running time, but doen't account for situations where the pacman needs to follow a edge to eat, and the return to the previous vertex...

Is there anything better?

Saying in another way: What is the minimum cost of connecting several dots without lifting my pen?

Thanks

Answer 1

After running an all-pairs-shortest-path algorithm and identifying the vertices with food, this becomes the traveling salesman problem. You can't solve it efficiently, but you can construct arbitrarily good approximations to a solution in polynomial time. You'll probably want to use an approximation unless you can pre-compute everything. If you can pre-compute things (or otherwise guarantee that you have enough time to find an exact solution), then once you've got the all-pairs-shortest-paths, you can simply find the minimum total walk length over all possible permutations of the order in which you eat the food pieces. This brute-force method can probably be improved somewhat by watching out for when the shortest path between two food pieces crosses another food piece.