A* Search Algorithm

In this article A* Search Algorithm Learn A* Search Algorithm with evaluation function f(n)=g(n)+h(n), working steps, example, advantages, limitations, and applications in AI.

A* Search Algorithm:

A Search Algorithm (Heuristic Search)*

Introduction

• A* Search is an Informed Search (Heuristic Search) technique.
• Considered one of the most effective search algorithms.
• Combines Best First Search and Uniform Cost Search.
• Nodes are selected based on the total estimated cost to reach the goal.

Diagram: Concept of A*

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

g(n) → cost so far

h(n) → estimated cost to goal

Node with lowest f(n) → Expanded first

Evaluation Function

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

Where:

• g(n) = actual cost from the start node to node n
• h(n) = estimated cost (heuristic) from node n to the goal
• f(n) = total estimated cost to reach the goal

The node with the lowest f(n) is expanded first.

Role of Heuristic Function

• Guides the search towards the goal efficiently.
• If admissible (h(n) ≤ actual cost):
  • A* is complete
  • Produces optimal solution

Working Principle

1. Keep the start node in the open list.
2. Select the node with lowest f(n) from the open list.
3. If it is the goal node, stop.
4. Otherwise, generate successors, compute g(n), h(n), and f(n), and add them to the open list.
5. Keep explored nodes in the closed list to avoid revisiting.

Algorithm (Steps)

1. Open list = {Start node}
2. Closed list = ∅
3. Remove the node with lowest f(n) from the open list
4. If node = goal, stop
5. Otherwise, generate successors
6. Calculate g(n), h(n), and f(n) for each successor
7. Move node to closed list
8. Repeat until the goal is reached

Flowchart: A Search*

Start → Add Start Node to Open List

↓

Is Open List Empty?

↓ No

Select Node with Lowest f(n) → Is Goal?

↓ No → Generate Successors → Calculate g, h, f → Add to Open List → Repeat

↓ Yes → Goal Found → Stop

Example

• Traversal: Node with lowest f(n) is expanded first → A* finds optimal path.

Time and Space Complexity

Where:

• b = branching factor
• d = depth of the optimal solution

Features of A Search*

• Heuristic-based search
• Complete and optimal
• Goal-oriented and efficient
• Memory-intensive

Advantages of A Search*

• Guarantees optimal solution
• Explores fewer nodes than uninformed search
• Effective in real-world problems

Limitations of A Search*

• Designing a good heuristic is difficult
• High memory requirement
• Computationally costly for large search spaces

Applications of A Search*

• GPS navigation systems
• Robotics path planning
• Game AI
• Network routing
• Puzzle solving (8-puzzle, 15-puzzle)

Conclusion

• A* Search is a powerful and reliable heuristic search technique.
• If the heuristic is admissible, it always provides the lowest-cost optimal solution.
• Widely used in modern AI systems for optimal path and decision-making problems.