A* Search algorithm is one of the most efficient and widely used techniques for pathfinding and graph traversal. It is designed to find the shortest path between a starting point and a goal point in a graph or search space. The strength of A* comes from the fact that it combines the actual cost from the start node with an estimated cost (heuristic) to the goal node, making it both optimal and complete when an admissible heuristic is used.

The evaluation function is: f(n) = g(n) + h(n)

• g(n): The exact cost of the path from the start node to the current node n.
• h(n): The heuristic estimate of the cost from node n to the goal node.
• f(n): The total estimated cost of the cheapest path through node n.

By always choosing the node with the lowest f(n), A* efficiently balances exploration and exploitation.

Algorithm for A* Search

1. Initialization:
• Define two lists:
  • OPEN list: A priority queue that stores nodes to be explored, sorted by their f(n) value.
  • CLOSED list: A list that stores nodes already explored.
• Add the start node S to the OPEN list with g(S) = 0 and f(S) = h(S).
2. Check OPEN List:
• If the OPEN list is empty, it means no path exists. The algorithm terminates with failure.
3. Select Node:
• Remove the node n with the smallest f(n) from the OPEN list.
• Move this node to the CLOSED list, marking it as visited.
• If node n is the goal state, the algorithm succeeds and the path is reconstructed by backtracking.
4. Expand Node:
• Generate all successor nodes (neighbors) of the selected node n.
• For each successor, calculate:
  • g(successor) = g(n) + cost(n, successor)
  • h(successor) = heuristic(successor, goal)
  • f(successor) = g(successor) + h(successor)
5. Goal Test:
• For each generated successor node:
  • If the successor is the goal node, return success and reconstruct the path from the start node to the goal node.
  • If not, proceed to the next step.
6. Evaluation and Add to OPEN List:
• For each successor node:
  • If the successor is not in OPEN or CLOSED, add it to the OPEN list with its f(n) value.
  • If it is already in OPEN with a higher f(n), update it with the new lower f(n) (path improvement).
  • If it is in CLOSED but the new path is better, move it back to OPEN with the updated cost.
7. Repeat:
• Go back to Step 2 and continue the process until:
  • The goal is reached (success), or
  • The OPEN list becomes empty (failure).

Advantages:

• Always finds the optimal path if the heuristic is admissible.
• More efficient than uninformed search algorithms like Dijkstra’s.
• Balances exploration (g) and heuristic guidance (h).

Drawbacks:

• Memory-intensive: Requires storing many nodes in OPEN and CLOSED lists.
• Performance heavily depends on the quality of the heuristic function.
• May become slow for very large and complex graphs.

Applications:

• GPS navigation and route planning
• Robot motion planning
• Game AI for shortest path and movement
• Network routing problems