2
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • $\begingroup$ Can you describe the problem? Links tend to break. $\endgroup$
    – Juho
    Oct 22, 2012 at 3:54
  • $\begingroup$ For getting heuristic you can simple sum all edges weights $\endgroup$
    – user6429
    Jan 15, 2013 at 13:58
  • $\begingroup$ @txt_flow Can you explain why that would be a good solution? $\endgroup$
    – Raphael ♦
    Jan 15, 2013 at 14:12

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

This is quite an old question, but for anyone coming across it - read up on the Chebyshev Distance. It is one of the three most referenced pathfinding heuristics and will solve this problem.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Welcome! This feels like a good start to an answer but we're looking for a bit more information than just a search term. Could you at least summarize what Chebyshev distance is? $\endgroup$
    – David Richerby
    Feb 29, 2016 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.