On Mar 30, 2011, at 12:28 PM, Cedric Laczny wrote:
Yes, thank you for this nice explanation. More formally, this seems to come down for the heuristic to be at least admissible, or even stronger, to be monotonic or consistent. I found that out only later on. Given the case of an overestimating heuristic, if the program aborts upon examination of the goal, it might miss the optimal path due to the overestimation. However, when it runs as long as the queue Q is not empty, I think it should find the optimal path nevertheless, although possibly reopening the closed goal-vertex. What do you think about that?
Not sure, but I think you might just use Dijkstra's shortest-path algorithm in that case. Will be faster than looking at all paths and still minimal.