Why is A* search algorithm better than A?

Question

I am trying to understand why, theoretically, A* search algorithm is considered better than A search algorithm.

In both algorithms, the nodes are expanded according to the function f(n).

In A: f(n) = g(n) + h(n)

In A*: f(n) = g(n) + h*(n) (the * means that the function is an estimate).

A* is supposed to reduce the amount of paths that have to be generated and compared. My question is: how does using h*(n) instead of h(n) reduce the amount of paths?

Thanks :)

Answer 1

Because you generally don't know the exact value of h(n). To calculate this you'll have to do a complete search from that node to the goal, and doing this for each node will be very expensive.

---

Consider cities connected by roads. How will you know what the travel distance to reach the goal city from any given city is? You can't do this without searching. Instead, you can, for example, use direct distance as an estimate of the actual travel distance, which is a very simple and fast calculation if you have the coordinates of both cities.