On Sun, Oct 30, 2011 at 8:44 AM, Anton Kholomiov
I'm misunderstanding astar. I've thought that 'whole route'-heuristic will prevent algorithm from going in circles. The more you circle around the more the whole route distance is.
Sort of. Consider the tree in my example graph: A -1- B -1- C -1- D -1- E -9- J -2- F -1- C -1- D -1- E -9- J -2- G -1- D -1- E -9- J -2- H -1- E -9- J -2- I -1- J There's no circling going on as you depth-first search this tree, even though you are wasting time visiting the same node multiple times. However, the thing you know with A*/djikstra is this: If I have visited a node, there is no shorter path to that node. So any time I encounter that node again, I must have at least as long of a path, and so any later nodes along that path can't be any better along this path. Effectively, you are pruning the tree: A -1- B -1- C -1- D -1- E -9- J *** -2- F -1- C *** -2- G -1- D *** -2- H -1- E *** -2- I -1- J GOAL (*** = pruned branches) since the second time you visit C, you know the first path was faster, so there is no reason to continue to visit D/E again. This is even more noticable in graphs with multidirectional edges, as the tree is infinitely deep at every cycle. I wonder if there is a way to represent this more directly as tree-pruning. It's weird, because you are pruning the tree based on visiting other branches of the tree.