A Star Search Algorithm – Artificial Intelligence

 

A Star ( A*) Search Algorithm, Advantages and Disadvantages – Artificial Intelligence – Artificial Intelligence

A* is a cornerstone name of many AI systems and has been used since it was developed in 1968 by Peter Hart; Nils Nilsson and Bertram Raphael. It is the combination of Dijkstra’s algorithm and the Best first search. It can be used to solve many kinds of problems. A* search finds the shortest path through a search space to the goal state using the heuristic function. This technique finds minimal cost solutions and is directed to a goal state called A* search. In A*, the * is written for optimality purposes. The A* algorithm also finds the lowest-cost path between the start and goal state, where changing from one state to another requires some cost.

A* requires the heuristic function to evaluate the cost of the path that passes through the particular state. This algorithm is complete if the branching factor is finite and every action has a fixed cost. A* requires the heuristic function to evaluate the cost of the path that passes through the particular state. It can be defined by the following formula.

f(n) = g(n) + h(n)

Where

  • g(n): The actual cost path from the start state to the current state.
  • h(n): The actual cost path from the current state to the goal state.
  • f(n): The actual cost path from the start state to the goal state.

For the implementation of the A* algorithm, we will use two arrays namely OPEN and CLOSE.

For the implementation of the A* algorithm, we will use two arrays namely OPEN and CLOSE.

OPEN: An array that contains the nodes that have been generated but have not been yet examined.

CLOSE: An array that contains the nodes that have been examined.

A* Search Algorithm in Artficial Intelligence:

Step 1: Place the starting node into OPEN and find its f (n) value.

Step 2: Remove the node from OPEN, having the smallest f (n) value. If it is a goal node then stop and return success.

Step 3: Else remove the node from OPEN, find all its successors.

Step 4: Find the f (n) value of all successors; place them into OPEN and place the removed node into CLOSE.

Step 5: Go to Step-2.

Step 6: Exit.

Advantages of A* Star

  • It is complete and optimal.
  • It is the best one from other techniques.
  • It is used to solve very complex problems.
  • It is optimally efficient, i.e. there is no other optimal algorithm guaranteed to expand fewer nodes than A*.

Disadvantages of A* Star

  • This algorithm is complete if the branching factor is finite and every action has a fixed cost.
  • The speed execution of the A* search is highly dependent on the accuracy of the heuristic algorithm that is used to compute h (n).
  • It has complexity problems.

Summary

This article discusses A Star ( A*) Search Algorithm, Advantages, and Disadvantages – Artificial Intelligence. If you like the material share it with your friends. Like the Facebook page for regular updates and YouTube channel for video tutorials.

Leave a Comment

Your email address will not be published. Required fields are marked *