# What kind of search method is A*?

What kind of search method is A*? Explain to me with an example.

More precisely, at each step, A* needs to select the next node to explore. It chooses the node $$n$$ with the smallest value of $$f(n) = g(n) + h(n),$$ where $$g(n)$$ is the actual distance from the starting node to node $$n$$ and $$h(n)$$ is the heuristic function that estimates the distance from node $$n$$ to the goal node.
For example, suppose that we want to find the shortest path from Paris to Madrid. If you are already in Madrid, then you can estimate that the distance from Madrid to Madrid is zero, so $$h(\text{Madrid}) = 0$$. However, if you're still in Paris, what is the estimate of the distance from Paris to Madrid? We can e.g. pick up a map of the world and choose $$h(\text{Paris})$$ to be the length of the straight segment that goes from Paris to Madrid. Similarly, we can do this for other intermediate cities. There are other ways of estimating this distance, but this is an understandable one, given that people are usually familiar with the Euclidean distance. (This example is a little bit misleading because the Earth is not flat and so the Euclidean geometry does not really apply, but, for simplicity, you can ignore this).