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.

Algorithm:

• 1. place the starting node in the OPEN list.
• 2. Check if the OPEN list is empty or not, if the list is empty then return failure and stops.
• 3. Select the node from OPEN list which has the smallest value of evaluation function (g+h), if the node n is the goal node then return success and stop else move to step-4.
• 4. Expand node n and generate all of its successors, and put n into the closest list. For each successor n' and place into OPEN list.
• 5. Else if node n' si already in OPEN and CLOSED, then it should be attached to the back pointer which reflects the lowest g(n') value.
• 6. return to step-2.

Advantages

• • A* search algorithm is the best algorithm than other search algorithms.
• • A* search algorithm is optimal and complete.
• • This algorithm can solve very complex problems.

Disadvantages:

• • It does not always produce the shortest path as it mostly based on heuristics and approximation.
• • A* search algorithm has some complexity issues.
• • The main drawback of A* is memory requirement as it keeps all generated nodes in the memory, so it is not practical for various large-scale problems.

Time Complexity:

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(b^d), where b is the branching factor.

Space Complexity:

The space complexity of A* search algorithm is O(b^d)

Optimal:

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.

Consistency:

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.

Complete::

A* algorithm is complete as long as: Branching factor is finite and cost at every action is fixed.

About the Author

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