What kind of search method is A*? Explain to me with an example.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
A* is an informed search algorithm. A* informed because it is based on the use of a heuristic function, which estimates the distance of each node to the goal, that is, the heuristic function provides information about the distance from any node to the goal node. The heuristic function can e.g. be the Euclidean distance (in the case this can be defined).
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).
For info regarding the completeness and optimality of A*, have a look at https://ai.stackexchange.com/a/8907/2444.