Q12Principles of Artificial Intelligence
Question
Describe the A* search algorithm and its properties.
Answer
A* search is an optimal and complete informed search algorithm that uses both path cost and heuristic estimates to find the shortest path.
A* search is a best-first search algorithm that finds the least-cost path from a given initial node to a goal node. It evaluates nodes by combining the cost to reach the node, g(n), and the estimated cost to get from the node to the goal, h(n). The evaluation function is f(n) = g(n) + h(n).
Properties of A* include Completeness and Optimality. It is guaranteed to find a solution if one exists (Complete). Furthermore, it will always find the optimal (lowest cost) path, provided that the heuristic function h(n) is admissible, meaning it never overestimates the actual cost to reach the goal.