How does Heuristic algorithm work?

Question

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!

Answer 1

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.

Answer 2

A heuristic is only a good educated guess. An approximation has a guarantee to be within some bounds. The christofides algorithm is an approximation algorithm but works only with graph satisfy the triangle inequality (metric tsp). Source: https://cs.stackexchange.com/questions/10182/difference-between-heuristic-and-approximation-algorithm

Answer 3

The heuristic function acts like an estimate for the lowest remaining cost to finish a end to end path. f(n) = g(n) + h(n) bounded from the bottom the lowest cost to extend and finish path g(n). Thus for admissible heuristic functions, it is guaranteed that the search will succeed.

The closer the heuristic function, the faster the search is. Think of the extreme case, that h(n) = 0 , you will have a A search instead, while if h(n) is exactly the remaining cost which means f(n) is the real cost then the search is done.