I am trying to understand some notes regarding the A-star algorithm. The example used is to show how the algorithm can be used as a (more efficient) alternative to Dijkstra's algorithm for finding shortest path. I am reading about A* search starting page 71 of the UK GCE Computing textbook, Rouse to find shortest path. I have also read the Wikipedia entry - but to no avail. Two things do not makes sense to me.(i) Where do the heuristic values for shortest distance come from? There is mention of straight roads but I don't understand this. I know heuristic is informed guess but why not values 1237, 978, 516, ... etc. or any other arbitrary, descending values for the heuristic distance still to go ?(ii) What is the significance and meaning of the heuristic must never make an over-estimate? How do we know that, and why is it important? Surely all the intermediate distances before the completion of the A* algorithm are over-estimates.Regards,Clive
Where does the heuristic come from in the A-star algorithm and how do we know it has the right properties?
algorithms;search algorithms;shortest path