A* Search Algorithm – Complete Explanation

A* (A-star) is the most popular and powerful informed search algorithm used in Artificial Intelligence for finding the shortest path from a start node to a goal node in a weighted graph (where edges have different costs).

It combines the strengths of:
- Dijkstra’s Algorithm (guarantees optimal path because it always expands the lowest-cost path so far)
- Greedy Best-First Search (uses heuristic to guide search toward the goal quickly)

A is both complete and optimal if the heuristic is admissible* (and consistent for better performance).

Why A* is Better Than Others

Key Idea of A*

For every node n, A* computes an evaluation function:

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

Where:
- g(n) = actual (exact) cost from start node to node n (path cost so far)
- h(n) = heuristic estimated cost from node n to the goal
- f(n) = estimated total cost of a path going through node n

A always expands the node with the smallest f(n)* value (using a priority queue).

Properties Required for Heuristic h(n)

1. Admissible Heuristic (Must for optimality)
   h(n) ≤ true cost from n to goal
   → Never overestimates the real distance
   Example: In a map, straight-line (Euclidean) distance or Manhattan distance is admissible.

2. Consistent (Monotonic) Heuristic (Stronger condition – gives better performance)
   For every node n and successor n' of n:
   h(n) ≤ cost(n, n') + h(n')
   → Triangle inequality holds
   If consistent → A* expands each node at most once (like Dijkstra).

Most real-world problems use consistent heuristics (e.g., Manhattan, Euclidean).

A* Algorithm – Step by Step (Pseudocode)

function A_Star(start, goal):
    open_set   = priority_queue()      # Nodes to be explored (sorted by f(n))
    open_set.insert(start) with f=0

    came_from  = {}                    # To reconstruct path
    g_score    = {}                    # Known cost from start to node
    g_score[start] = 0

    f_score    = {}                    # Estimated total cost
    f_score[start] = h(start)          # h = heuristic function

    while open_set is not empty:
        current = node in open_set with lowest f_score

        if current == goal:
            return reconstruct_path(came_from, current)

        remove current from open_set
        mark current as closed (or just track visited)

        for each neighbor of current:
            tentative_g = g_score[current] + cost(current, neighbor)

            if neighbor not visited or tentative_g < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score[neighbor] = tentative_g + h(neighbor)

                if neighbor not in open_set:
                    open_set.insert(neighbor)
                else:
                    update priority of neighbor in open_set

    return failure  # No path exists

Example: 8-Puzzle (or Grid Pathfinding)

Imagine finding shortest path from Bucharest to other cities (Romania map – classic AI example).

A* expands nodes in increasing order of f(n).

Time & Space Complexity

• Worst case: O(b^d) same as BFS (b = branching factor, d = depth)
• With good heuristic: dramatically faster (often exponential speedup)
• Space: Keeps all generated nodes in memory → can be a bottleneck

Advantages of A*

• Optimal and complete (with admissible heuristic)
• Very efficient with good heuristic
• Widely used in real applications:
• GPS navigation (Google Maps, etc.)
• Video games (pathfinding for NPCs)
• Robotics
• Puzzle solvers (15-puzzle, Rubik’s cube)

Disadvantages

• Memory intensive (stores all open/closed nodes)
• Solutions: Use Iterative Deepening A (IDA) or Memory-bounded A (SMA)

Summary Table: A* vs Others

Key Takeaway:
A is the gold standard for pathfinding when you need the shortest/optimal path and have a reasonable heuristic*. It intelligently balances exploring known costs (g) and estimated remaining costs (h).

Master A* → You’ve mastered 80% of real-world pathfinding problems in AI! 🚀