Patterns/Part IV - Core Algorithms/A* Search

Pattern Reference

A* Search

"Heuristic-guided search for shortest path. Manhattan distance, admissible heuristics."

Loading...

Deep Dive Tutorial

A* uses a priority queue ordered by f = g + h. Expand the node with smallest f first. Guarantee: if h is admissible (h(n) ≤ true remaining distance), A* finds the optimal path. If h is consistent (h(n) ≤ cost(n,n') + h(n')), each node is expanded at most once — more efficient. Common heuristics: Manhattan distance (grid, 4-directional), Euclidean distance, Chebyshev distance (8-directional).

A* search with Manhattan distance heuristic
function aStar(grid, start, goal) {
    const [rows, cols] = [grid.length, grid[0].length];
    const h = (r, c) => Math.abs(r - goal[0]) + Math.abs(c - goal[1]); // Manhattan

    const g = Array.from({length: rows}, () => new Array(cols).fill(Infinity));
    g[start[0]][start[1]] = 0;

    // Min-heap: [f, r, c]
    const heap = [[h(start[0], start[1]), start[0], start[1]]];

    while (heap.length) {
        heap.sort((a, b) => a[0] - b[0]); // use real min-heap in production
        const [f, r, c] = heap.shift();
        if (r === goal[0] && c === goal[1]) return g[r][c];

        if (f > g[r][c] + h(r, c)) continue; // outdated entry

        for (const [dr, dc] of [[0,1],[0,-1],[1,0],[-1,0]]) {
            const [nr, nc] = [r+dr, c+dc];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] === 1) continue;
            const ng = g[r][c] + 1;
            if (ng < g[nr][nc]) {
                g[nr][nc] = ng;
                heap.push([ng + h(nr, nc), nr, nc]);
            }
        }
    }
    return -1; // unreachable
}

Worked Problems

1
Shortest Path in Binary Matrix
Medium
Solve ↗
2
K-th Shortest Path (Yen's Algorithm concept)
Medium
Solve ↗
3
Sliding Puzzle
Hard
Solve ↗
star
A* admissibility: h(n) is admissible if h(n) ≤ true remaining distance. Never overestimate.

Common heuristics:
- 4-directional grid: Manhattan distance |Δr| + |Δc|
- 8-directional grid: Chebyshev distance max(|Δr|, |Δc|)
- 2D Euclidean: √(Δr² + Δc²)
- Puzzle: sum of Manhattan distances for each tile

A* vs Dijkstra: Same algorithm structure, but A* uses f=g+h instead of f=g. When h=0, identical. With a good h, A* explores far fewer nodes.

Limitations: A* requires knowing the goal ahead of time. For multi-target problems or when goal is unknown, use Dijkstra.
← All Patterns