A* Search — KLAR

Phase 1f(x)

The Mathematics

Heuristic search, admissibility, and optimality guarantees

Evaluation Function

A* evaluates each node $n$ using a function that combines the actual cost from the start with a heuristic estimate to the goal:

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

$\bullet$ $g(n)$ : actual cost of the cheapest path from start to $n$

$\bullet$ $h(n)$ : heuristic estimate of the cost from $n$ to the goal

$\bullet$ $f(n)$ : estimated total cost of the cheapest path through $n$

Admissible Heuristic

A heuristic is admissible if it never overestimates the true cost to the goal:

0 \leq h(n) \leq h^*(n) \quad \forall n

For grid-based pathfinding, the Manhattan distance is admissible when only 4-directional movement is allowed:

h(n) = |n_{\text{row}} - g_{\text{row}}| + |n_{\text{col}} - g_{\text{col}}|

Optimality Proof

If $h$ is admissible, A* is optimal. Suppose A* returns a path with cost $C$ via goal node. For any unexpanded node $n$ on an optimal path:

f(n) = g(n) + h(n) \leq g(n) + h^*(n) = g^*(\text{goal}) \leq C

A* would have expanded $n$ before the goal (since $f(n) \leq C$ ), contradicting that the goal was chosen first. Therefore $C$ must be optimal.

A* vs. Dijkstra

Dijkstra is A* with $h(n) = 0$ . The heuristic focuses the search toward the goal, expanding fewer nodes. With a perfect heuristic $h = h^*$ , A* expands only nodes on the optimal path.

Phase 2▶

See It Work

A* pathfinding on a 5×5 grid with obstacles

Open Closed Current Path Wall

f(n) = g(n) + h(n),\quad f(\text{start}) = 0 + 8 = 8

Step 1 of 18

Initialize: add start (0,0) to open set. g(start)=0, f(start)=h(start)=8.

Phase 3</>

The Code

Bridge from heuristic search formulation to Python implementation

Mathematical Formulation

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

Each node's priority is cost-so-far plus heuristic estimate to goal

g(\text{start}) = 0

Initialize start node with zero cost

\min_{n \in \text{Open}} f(n)

Always expand the node with lowest f-score (priority queue min)

\text{current} = \text{goal} \Rightarrow \text{return path}

If we reached the goal, reconstruct and return the path

g'(v) = g(u) + w(u,v)

Tentative g-score through current node

g'(v) < g(v) \Rightarrow \text{update}

Only update if we found a shorter path to this neighbor

h(n) = |n_r - g_r| + |n_c - g_c|

Manhattan distance heuristic (admissible for grid movement)

Python Implementation

import heapq

def a_star(grid, start, goal):
    open_set = [(h(start, goal), start)]  # Priority queue: (f_score, node)
    came_from = {}
    g_score = {start: 0}                  # Cost from start to node
    closed = set()

    while open_set:
        f, current = heapq.heappop(open_set)   # Get lowest f-score
        if current == goal:
            return reconstruct(came_from, current)  # Path found
        closed.add(current)
        for neighbor in get_neighbors(grid, current):
            if neighbor in closed:
                continue                   # Skip already evaluated
            tentative_g = g_score[current] + 1
            if tentative_g < g_score.get(neighbor, float('inf')):
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f = tentative_g + h(neighbor, goal)  # f = g + h
                heapq.heappush(open_set, (f, neighbor))
    return None                            # No path exists

def h(node, goal):
    return abs(node[0]-goal[0]) + abs(node[1]-goal[1])  # Manhattan