Heuristic Search: A* Algorithm

What Is a Heuristic?

A heuristic is an estimate of the cost from a given node to the goal. It is not exact — it only needs to guide the search toward the goal faster than exploring blindly.

h(n) = estimated cost from node n to the goal

Figure 1: Heuristic search reaches the goal by visiting far fewer nodes than blind search.

Uninformed vs Informed Search

What Is the A* Algorithm?

A* is a graph search algorithm that finds the lowest-cost path between a start node and a goal node. Published in 1968 by Hart, Nilsson, and Raphael, it combines the exact cost already spent reaching a node with an estimated cost to the goal, so it prioritizes nodes that are both cheap to reach and likely close to the goal.

Properties:

• Complete: finds a solution if one exists.
• Optimal: finds the shortest path if the heuristic is admissible.
• Efficient: expands fewer nodes than uninformed search when the heuristic is accurate.

The A* Formula: f(n) = g(n) + h(n)

A* expands the node with the lowest f(n) at each step.

Figure 2: f(n) combines the known cost so far with the estimated remaining cost.

How A* Works

A* maintains an open list (discovered, unexplored nodes) and a closed list (fully explored nodes).

1. Add start to open list; g(start) = 0, f(start) = h(start).
2. While open list is not empty: 
   • Pick the node with lowest f(n) — call it current.
   • If current is the goal, reconstruct and return the path.
   • Move current to the closed list.
   • For each neighbor not in the closed list:  
     • Compute tentative g = g(current) + cost(current, neighbor).
     • If this is better than any known g for the neighbor, update g, h, f, and set current as its parent. Add the neighbor to the open list if not already present.
3. If the open list empties without reaching the goal, no path exists.

Step-by-Step Example

A step-by-step example demonstrates how the A* algorithm explores nodes and chooses the shortest path to the goal. By calculating the g(n), h(n), and f(n) values at each step, you can clearly see why A* selects one node over another and how the optimal path is found.

Grid (4×4), each move costs 1, # = wall:
S  . .  .
.  # #  .
.  . #  .
.  # .  G

Heuristic: Manhattan distance, h(n) = |row - goal_row| + |col - goal_col|.

Path: (0,0) → (0,1) → (0,2) → (0,3) → (1,3) → (2,3) → (3,3) — 6 steps, optimal.

Figure 3: A visits only the cells needed to reach the goal.*

A* Algorithm Pseudocode

Pseudocode provides a language-independent representation of the A* algorithm. It focuses on the algorithm's logic rather than programming syntax, making it easier to understand before implementing it in any programming language.

function A_STAR(start, goal):
    open_list = priority queue containing start
    g_score[start] = 0
    f_score[start] = heuristic(start, goal)
    came_from = empty map

    while open_list is not empty:
        current = node in open_list with lowest f_score
        if current == goal:
            return reconstruct_path(came_from, current)

        remove current from open_list
        add current to closed_list

        for each neighbor of current:
            if neighbor in closed_list:
                continue
            tentative_g = g_score[current] + cost(current, neighbor)
            if neighbor not in open_list or tentative_g < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score[neighbor] = tentative_g + heuristic(neighbor, goal)
                if neighbor not in open_list:
                    add neighbor to open_list

    return failure

Python Implementation

Now that you understand the working of the A* algorithm, let's implement it in Python. This implementation uses Python's built-in heapq module to efficiently manage the priority queue, ensuring that the node with the smallest f(n) value is always processed first.

import heapq
def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])  # Manhattan distance

def a_star(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    open_list = [(heuristic(start, goal), 0, start)]  # (f, g, node)
    came_from = {}
    g_score = {start: 0}
    visited = set()

    while open_list:
        f, g, current = heapq.heappop(open_list)

        if current == goal:
            path = [current]
            while current in came_from:
                current = came_from[current]
                path.append(current)
            return path[::-1]

        if current in visited:
            continue
        visited.add(current)

        row, col = current
        for neighbor in [(row+1, col), (row-1, col), (row, col+1), (row, col-1)]:
            nr, nc = neighbor
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != '#':
                tentative_g = g + 1
                if neighbor not in g_score or tentative_g < g_score[neighbor]:
                    g_score[neighbor] = tentative_g
                    f_score = tentative_g + heuristic(neighbor, goal)
                    heapq.heappush(open_list, (f_score, tentative_g, neighbor))
                    came_from[neighbor] = current

    return None

grid = [list("S..."), list(".##."), list("..#."), list(".#.G")]
path = a_star(grid, (0, 0), (3, 3))
print("Path found:", path)

Output:

Path found: [(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)]

• Explanation:
• heuristic() computes h(n) using Manhattan distance.
• open_list is a min-heap, so the lowest f(n) node is always processed first.
• g_score stores the cheapest known cost to each node.
• came_from stores parent pointers for path reconstruction.
• The loop expands the best node, checks for the goal, and updates neighbor scores when a cheaper path is found.
• Returns None if no path exists.

Admissible Heuristics

A heuristic h(n) is admissible if it never overestimates the true remaining cost:

h(n) ≤ actual cost from n to goal

An overestimating heuristic can cause A* to skip a shorter path, producing a suboptimal result.

Consistency is a stricter property: for every node n and neighbor n', h(n) ≤ cost(n, n') + h(n'). Every consistent heuristic is admissible; consistency also guarantees a node's shortest path is found the first time it is expanded, so it never needs reopening.

Figure 4: An inadmissible heuristic can cause A to miss the true shortest path.*

A* vs Dijkstra's Algorithm vs BFS

Dijkstra's algorithm is equivalent to A* with h(n) = 0 for all nodes.

Figure 5: A expands fewer nodes than Dijkstra's algorithm because the heuristic directs the search toward the goal.*

Use Cases

• GPS navigation
• Video game NPC pathfinding
• Robot and drone motion planning
• Network packet routing
• Puzzle solving (8-puzzle, 15-puzzle)
• Delivery route optimization

Best Practices

• Use a heuristic close to the true cost without overestimating it.
• Prefer consistent heuristics to avoid reopening nodes.
• Implement the open list as a min-heap.
• Match the heuristic to the movement model (Chebyshev for 8-directional, Euclidean for free movement).
• Track visited nodes to prevent redundant work in graphs with cycles.

Common Mistakes

• Using an inadmissible heuristic, causing a suboptimal path.
• Not updating g(n) when a cheaper path to a node is found later.
• Scanning a plain list for the minimum f(n) instead of using a priority queue.
• Applying equal cost to diagonal and straight moves when diagonal movement should cost more (e.g., √2 vs 1).
• Failing to reverse the reconstructed path after backtracking from goal to start.
• Setting h(n) = 0 unintentionally, which reduces A* to Dijkstra's algorithm.

Summary

A* finds the shortest path using f(n) = g(n) + h(n), expanding the node with the lowest total estimated cost at each step. Optimality requires an admissible heuristic — one that never overestimates the true remaining cost. Compared to Dijkstra's algorithm and BFS, A* expands fewer nodes because the heuristic directs the search toward the goal.