I know A* finds the shortest path to the target. I know basically how to implement it and I can see how it finds "a path," but how come the path it finds is the shortest?

The answer to that question probably involves a lot of mathematics on at least a sort of semi-advanced level (what do I mean by semi-advanced? Heck, I don''t know, I just thought it seemed a cool thing to write). Now, I don''t know how to really _show_ it in a strict mathematical way, but I guess that it basically comes down to showing that the cost function and the heuristic minimize the overall cost. Hm... this answer probably was more of a tautology than an answer...

My advice: don''t worry about. And if you still do, ask a mathematician.

hi

A* finds the shortest path because of the heuristic (its not complicated at all).

lets say you are using distance, and distance alone to determin the cost of a move. imagine the following scenario:




where s is the start node, and g is the goal. lets say the algoritm initially goes up the wrong side, and gets to node 'a'. now remember that node 'b' will still be on the open list. so when the list is sorted, b will appear at the front of the list (because you take into account the cost of getting to the node, and the euclidean distance to the goal node), and so the A* algorithm will then go back to that node, and continue from there. if you implement A*, you can see this working.

hope that helps.

[edited by - mchugh on April 28, 2003 5:53:39 AM]