Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I'm a none-computer-science-student and get some knowledge on AI by taking the CS188.1x Course (Artificial Intelligence) on www.edx.org .

Currently, I am working on the "Search in Pacman" Project; the sources can be found online at Berkley CS188 . I have problems finding an good solution for "Finding All the Corners", so I need a good Multiple Goal Heuristic.

I allready tried the simple approach described in here. I used the minimum of all manhattan distances to all goals. This works, but is considered a rather poor heuistic, because my A-Star Algorithm expands 2606 nodes for the given maze. Using the same with euclidean distance expands even 103081 nodes. A good heuristic should expand 1600 nodes or less. A very good one 1200 nodes, an excellent one even 800 or less.

I got a hint by other students who use minimum spanning trees created with Kruskal's Algorithm. I wanted to investigate into that direction, but I am somehow confused how the Kruskal Algorithm can be used to get a Heuristic? As far as I understood, this Algorithm returns a minimum spanning tree (MST) which is a path, right? So it is a solution to the Traveling Salesman Problem (TSP); it returns a sequence of nodes. But I need a heuristic, so a cost function which can be applied to this problem and called by an Algorithm (like A*).

Can anyone of you give me a hint on how to proceed? Every help is highly appreciated!

share|improve this question

migrated from cstheory.stackexchange.com Oct 21 '12 at 3:55

This question came from our site for theoretical computer scientists and researchers in related fields.

Can you describe the problem? Links tend to break. –  Juho Oct 22 '12 at 3:54
For getting heuristic you can simple sum all edges weights –  user6429 Jan 15 '13 at 13:58
@txt_flow Can you explain why that would be a good solution? –  Raphael Jan 15 '13 at 14:12

1 Answer 1

MST is actually a tree, not a path (generally). Therefore, it is not a solution to TSP. (Although, MST can help you to find a solution that is not more than twice as long as the optimal solution, if you solve this in a metric space on a complete graph. That's unrelated story.)

Now, I must admit that I do not see a way spanning trees can help you if the maze contains loops. And in the case that the maze does not contain loops, it is somehow weird to talk about MST, because the graph of the maze is a tree.

However, maybe you can start to think about this: in a tree, for any two nodes, there is exactly one path that connects them. That's a trivial, but quite a nice property, isn't it? Length of this unique path is an easy lower bound that is more precise than Manhattan distance.

If you build MST over a graph with loops, this would probably not make an admissible heuristic, because the path using only MST edges can be longer than some path over edges you haven't choose to the spanning tree.

"Minimality" of MST is somehow a local property -- it's not like all the shortest paths are preserved. This is why I would never think about solving your problem with MST.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.