A* search is the most commonly known as a form of best-first search algorithm. It uses heuristic function h(n), and cost to reach the node from the start state g(n), the sum of heuristic function and cost to reach is called fitness number. It solves problem efficiently since it uses the UCS and greedy best-first search algorithms. A* algorithm is similar to the UCS except it uses the heuristic function h(n) i.e., g(n)+h(n) instead of g(n). A* algorithm returns the path which occurred first, and it does not search for all remaining paths. The efficiency of A* algorithm depends on the quality of heuristic. A* algorithm expands all nodes which satisfy the condition f(n)
f(n) = g(n) + h(n), where, f(n) is the estimated cost of the cheapest solution, g(n) is the cost to reach node n from the start state and h(n) is cost to reach from node n to the goal node.
The time complexity of A* search algorithm depends on heuristic function, and the number of nodes expanded is exponential to the depth of solution d. So the time complexity is O(bd), where b is the branching factor.
The space complexity of A* search algorithm is O(bd)
A* search algorithm is optimal if it follows below two conditions:
Admissible: the first condition requires for optimality is that h(n) should be an admissible heuristic for A* tree search. An admissible heuristic is optimistic in nature.
Second required condition is consistency for only A* graph-search.
If the heuristic function is admissible, then A* tree search will always find the least cost path.
A* algorithm is complete as long as: Branching factor is finite and cost at every action is fixed.
Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.
We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc