Optimality of A*
A* search is a best-first search algorithm that combines both the cost of the path from the start node and an admissible heuristic function that estimates the cost of reaching the goal node.
A* search is guaranteed to find the optimal solution if the following conditions are met:
The heuristic function used in A* search is admissible. This means that the heuristic function never overestimates the cost of reaching the goal node from any node.
The heuristic function used in A* search is consistent. This means that the estimated cost of reaching a node and the estimated cost of reaching its successors plus the cost of moving from the current node to the successor are always less than or equal to the estimated cost of reaching the current node.
When these two conditions are satisfied, A* search is guaranteed to find the optimal solution, i.e., the path with the lowest cost from the start node to the goal node.
The optimality of A* search can be proven by contradiction. Suppose that A* search does not find the optimal solution. This means that there exists a path that has a lower cost than the path found by A* search. Let p be such a path and let n be the first node on p that is expanded by A* search. Since A* search expands nodes in order of their f values (f(n) = g(n) + h(n)), and since h is admissible, we have that f(n) <= f(n') for any unexpanded node n' on p.
Therefore, the cost of the path found by A* search, g(n) + h(n), is less than or equal to the cost of path p, g(p), and since h is admissible, we have that h(n) <= g(p) - g(n). This means that the estimated cost of reaching the goal node from n is less than or equal to the actual cost of reaching the goal node from n on path p. But this contradicts the admissibility of h.
Therefore, we can conclude that A* search is optimal when the heuristic function used is admissible and consistent.
Comments
Post a Comment