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 number of paths that have to be generated and compared. My question is: how does using h*(n) instead of h(n) reduce the number of paths?

Thanks :)

Answer 1

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

Let us discuss this with an example:

Consider cities connected by roads. To know the travel distance to reach the goal city from any given city, you have to perform a search. Instead, you can 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. 

A is sort of a "hypothetical" algorithm and A* is what you'd practically use. A* design paths that are as good as A and are practical to implement.

If you are looking to learn more about Artificial Intelligence then you visit Artificial Intelligence Tutorial and Artificial Intelligence Course. Also, if you are appearing for job profiles of AI Engineer or AI Expert then you can prepare for the interviews on Artificial Intelligence Interview Questions.