I am learning some heuristic algorithm recently like A* search algorithm. I know some basic facts about heuristic search algorithm like f(n)=g(n)+h(n), and I also know what admissible and consistent each means. But what confuses me is how does the heuristic algorithm work? Why is it better if the heuristic value is more close to the actual value of the cost? thanks!
Think about a perfect heuristic h(n). It gives the exact shortest distance to the goal from n.
Therefore the cost function f(s) for each node s on the shortest path will be the same and equal to the length of the shortest path: distance traveled so far plus the exact shortest distance to the goal.
So it's not hard to see that for all shortest path nodes s and any given non-shortest path node n, we have f(s) < f(n).
Now think about how the A* algorithm will behave with such a heuristic: at each node, the selected next node to expand onto the queue will also be the next node on the shortest path because this must have the smallest possible value of f. Therefore the algorithm will move directly from the start to goal nodes along the shortest path with no missteps!
If you don't have the perfect heuristic, the algorithm can obviously make missteps because f(n) < f(s) is possible, so the algorithm can "step off the shortest path" along an unnecessary branch.
The beauty of the algorithm is that so long as the heuristic is admissible, it will still find the shortest path, just slower than with the perfect one.