Informed Search

Uniform-cost search is careful but directionless. It expands every state reachable below the current cost contour, even when the goal is visibly in one direction. Informed search adds a heuristic: problem-specific information estimating the remaining work.

A heuristic does not solve the problem. It changes the order in which possibilities are considered. A good heuristic concentrates computation on promising regions; a badly designed one can add expense, destroy optimality, or direct the search away from useful states.

Heuristics

For a state or search node n, a heuristic h(n) estimates the cost of a cheapest path from n to a goal.

Examples include:

• straight-line distance between two map locations;
• Manhattan distance on a four-direction grid;
• number of misplaced tiles in a sliding puzzle;
• remaining unsatisfied prerequisites in a planning task;
• a lower bound on remaining processing time in a schedule.

A heuristic is part of the model. Its value has meaning only relative to a specific state representation, action set, cost function, and goal.

Evaluation Functions

A heuristic typically estimates remaining path cost. An evaluation function may score any notion of desirability. The distinction matters because A*‘s guarantees require a cost estimate with specific mathematical properties; an arbitrary “goodness score” does not qualify.

Greedy Search

Greedy best-first search expands the frontier node with smallest h(n). It asks only which state appears closest to the goal.

This can be dramatically faster than uninformed search. It can also be badly misled because it ignores the cost already paid.

Consider:

S → A  cost 100, h(A)=1
S → B  cost   2, h(B)=4
A → G  cost   1
B → G  cost   4

Greedy search chooses A because its heuristic is smaller and returns cost 101. The route through B costs 6. The heuristic may be accurate about remaining distance while the decision is still poor because past cost was ignored.

Greedy search is useful when:

• a quick feasible solution matters more than an optimal one;
• heuristics are informative;
• memory or time limits dominate;
• a solution can later be improved.

It is not generally complete in infinite spaces and is not generally optimal.

A*

A* orders the frontier by:

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

where:

• g(n) is the exact path cost from the initial state to n;
• h(n) estimates the remaining cost;
• f(n) estimates the cost of a complete solution through n.

This unifies two algorithms:

• if h(n) = 0, A* becomes uniform-cost search;
• if g(n) is ignored, the ordering becomes greedy best-first search.

A* “hedges its bets.” It follows states that look promising but retains alternatives whose total estimated solution cost remains competitive.

Implementation

The implementation uses the same graph and result dictionary as uninformed search. Set show_steps=True when an exercise needs the priority queue after each expansion.

from heapq import heappop, heappush

def build_path(parent, goal):
    path = []
    current = goal

    while current is not None:
        path.append(current)
        current = parent[current]

    path.reverse()
    return path

def a_star(graph, heuristic, start, goal, show_steps=False):
    best_g = {start: 0.0}
    parent = {start: None}
    frontier = [(heuristic[start], 0.0, start)]
    expanded = 0

    while frontier:
        f, g, state = heappop(frontier)

        if g != best_g.get(state):
            continue
        expanded += 1

        if show_steps:
            print("Expanding:", state, "g =", g, "f =", f)
            print("Frontier:", frontier)

        if state == goal:
            return {
                "path": build_path(parent, goal),
                "cost": g,
                "expanded": expanded,
            }

        for next_state, step_cost in graph[state]:
            if step_cost < 0:
                raise ValueError("A* requires non-negative step costs")

            candidate_g = g + step_cost

            if candidate_g < best_g.get(next_state, float("inf")):
                best_g[next_state] = candidate_g
                parent[next_state] = state
                candidate_f = candidate_g + heuristic[next_state]
                heappush(
                    frontier,
                    (candidate_f, candidate_g, next_state),
                )

    return None

As with uniform-cost search, A* stops when a goal is removed from the frontier, not when one is generated. The first generated goal might not be the cheapest.

Weighted Graph Example

Keep graph data, heuristic data, and the algorithm separate. This makes it possible to test the same implementation with a zero heuristic, which must behave like uniform-cost search.

GRAPH = {
    "S": (("A", 6), ("B", 2), ("G", 10)),
    "A": (("S", 6), ("B", 3), ("C", 1)),
    "B": (("S", 2), ("A", 3), ("D", 6), ("E", 2)),
    "C": (("A", 1), ("D", 4)),
    "D": (("B", 6), ("C", 4), ("E", 3)),
    "E": (("B", 2), ("D", 3), ("G", 1)),
    "G": (("S", 10), ("E", 1)),
}

H = {"S": 5, "A": 3, "B": 3, "C": 2,
     "D": 4, "E": 1, "G": 0}

result = a_star(
    GRAPH, H, start="S", goal="G", show_steps=True
)

assert result is not None
assert result["path"] == ["S", "B", "E", "G"]
assert result["cost"] == 5

zero_heuristic = {state: 0 for state in GRAPH}
ucs_result = a_star(
    GRAPH, zero_heuristic, start="S", goal="G"
)
assert ucs_result is not None
assert ucs_result["cost"] == result["cost"]

The final assertion is a useful oracle: with h=0, A* and UCS should agree on cost. It does not prove the heuristic is admissible, but disagreement reveals an implementation or modelling error.

Admissibility

A heuristic is admissible if it never overestimates the true cheapest remaining cost:

0 ≤ h(n) ≤ h*(n)

where h*(n) is the actual optimal cost from n to a goal.

Admissibility is optimism. An admissible heuristic may underestimate badly, but it never makes an optimal route appear more expensive than it truly is.

Optimality Intuition

Suppose a suboptimal goal B is waiting on the frontier. Its heuristic is zero, so f(B) = g(B). Along an optimal route to goal A, some frontier node n must exist. Because h(n) does not overestimate:

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

Since A is better than B:

g(A) < g(B) = f(B)

Therefore n has smaller priority than B and is expanded first. A suboptimal goal cannot be selected while an optimal route remains promising on the frontier.

This is a blocking argument: optimistic frontier estimates block expensive goals.

Consistency

For graph search, admissibility alone is not always enough if states are permanently closed after expansion. A heuristic is consistent when, for every transition from n to n' with cost c:

h(n) ≤ c(n, n') + h(n')

This is a triangle inequality. The estimated distance from n cannot exceed one real step plus the estimate from the successor.

Consistency implies that f values do not decrease along a path:

f(n') = g(n') + h(n')
      = g(n) + c(n,n') + h(n')
      ≥ g(n) + h(n)
      = f(n)

Therefore, when consistent A* expands a state, it has already found a cheapest path to that state. No reopening is necessary.

Every consistent heuristic with h(goal)=0 is admissible. Not every admissible heuristic is consistent.

Reopening

The implementation above allows an improved g value to create a new heap entry. This supports reopening when necessary. A simpler closed-set implementation is correct only under stronger assumptions such as consistency.

Relaxed Problems

One reliable technique is to remove constraints from the original problem. The relaxed problem cannot be harder, so its exact solution cost is a lower bound for the original.

For a sliding-tile puzzle:

• If tiles may jump directly to their goal positions, the number of misplaced tiles is a lower bound.
• If tiles may move through one another but still travel one grid step at a time, total Manhattan distance is a stronger lower bound.

For route planning, straight-line distance is a lower bound when road cost is physical distance and no road is shorter than the direct geometric separation.

For scheduling, the sum of remaining processing times may be a lower bound on completion work, though resource conflicts can make the real schedule longer.

Pancake Puzzle

The pancake puzzle makes heuristic design concrete. A state is a stack of pancakes with different sizes. An action chooses a position and reverses the whole prefix above it. Two common cost models are:

• unit cost for every flip, which minimizes the number of flips;
• cost k for flipping the top k pancakes, which minimizes the total amount flipped.

For example, from [3, 1, 4, 2], flipping the first three pancakes produces [4, 1, 3, 2]. The action changes several positions at once, so counting misplaced pancakes can overestimate: one flip may fix multiple misplaced pancakes.

A useful unit-cost heuristic counts gaps. Add an imaginary pancake larger than all real pancakes below the stack. Two adjacent pancakes form a gap when their sizes are not consecutive. One prefix flip can repair at most one such boundary, so the number of gaps is a lower bound on the remaining flips.

For size-weighted flips, another heuristic identifies the largest pancake that is still out of place and uses its required displacement to form a lower bound. The idea is that a deeply misplaced large pancake cannot be repaired using only cheap flips that never reach it.

The model matters. A lower bound on the number of flips does not describe the same quantity as a lower bound on total pancakes flipped. A heuristic is justified relative to a particular state model, action set, goal arrangement, and cost function.

Eight Puzzle

The 8-puzzle contains eight numbered tiles and one blank on a 3 × 3 board.

• A state records the position of every tile and the blank.
• An action moves a tile adjacent to the blank into the blank position.
• A step cost is usually 1.
• The goal test compares the board with a chosen goal arrangement.

Only half of all arrangements are reachable from a given start state. The parity of the tile permutation divides the state space into two disconnected sets. Search cannot repair an unsolvable instance; the formulation or input validation must detect it.

Two classic heuristics come from relaxed versions of the puzzle:

• misplaced tiles counts numbered tiles outside their goal position;
• Manhattan distance adds how many horizontal and vertical moves each tile needs to reach its goal.

Misplaced tiles imagines that a tile can jump directly home. Manhattan distance still requires grid movement but allows tiles to pass through one another. Both relaxations remove constraints, so both produce lower bounds. Manhattan distance dominates misplaced tiles because every misplaced tile is at least one grid step from its goal, while some are farther away.

The true remaining solution cost would be a perfect heuristic, but computing it is the original search problem. Useful heuristics are cheaper approximations whose savings outweigh their computation.

Dominance

If admissible heuristic h₂(n) ≥ h₁(n) for every state, then h₂ dominates h₁. It is at least as informed while remaining optimistic, so A* using h₂ generally expands no more nodes than A* using h₁, aside from tie behavior.

The maximum of admissible heuristics is also admissible:

h(n) = max(h₁(n), h₂(n), ..., hₖ(n))

This combines independent lower bounds safely. Adding them is not automatically safe because the same remaining work may be counted twice.

Grid Example

An agent moves north, south, east, or west. Each legal move costs 1.

For state (r, c) and goal (rg, cg), Manhattan distance is:

h = |r - rg| + |c - cg|

Why is it admissible? Every action changes at most one coordinate by one. Reaching the goal requires at least the sum of the horizontal and vertical differences. Obstacles may force additional movement but cannot make the required number smaller.

Why is it consistent? For neighboring cells n and n', Manhattan distance changes by at most 1:

h(n) ≤ 1 + h(n')

If diagonal movement is allowed at cost 1, Manhattan distance becomes inadmissible because one diagonal step can reduce both coordinate differences. The correct heuristic depends on the action model. Chebyshev distance, max(|dr|, |dc|), is then a suitable lower bound.

def manhattan(state, goal):
    return abs(state[0] - goal[0]) + abs(state[1] - goal[1])

Maze Example

The graph implementation already accepts grid coordinates, so only the neighbor and heuristic functions change. Battery is treated as a path-cost constraint rather than hidden mutable state.

MAZE = (
    ".....",
    ".###.",
    "...#.",
    ".#...",
    ".....",
)
MOVES = ((1, 0), (0, 1), (-1, 0), (0, -1))

def make_maze_graph(maze):
    graph = {}

    for row in range(len(maze)):
        for column in range(len(maze[0])):
            if maze[row][column] == "#":
                continue

            state = (row, column)
            graph[state] = []

            for row_step, column_step in MOVES:
                next_row = row + row_step
                next_column = column + column_step
                inside = (
                    0 <= next_row < len(maze)
                    and 0 <= next_column < len(maze[0])
                )
                if inside and maze[next_row][next_column] != "#":
                    graph[state].append(
                        ((next_row, next_column), 1)
                    )

    return graph

start = (0, 0)
goal = (4, 4)
battery = 10

maze_graph = make_maze_graph(MAZE)
maze_heuristic = {}
for state in maze_graph:
    maze_heuristic[state] = manhattan(state, goal)

route = a_star(maze_graph, maze_heuristic, start, goal)

if route is None or route["cost"] > battery:
    print("No route within the battery limit")
else:
    print("path:", route["path"])
    print("moves:", int(route["cost"]))
    print("battery left:", battery - int(route["cost"]))

If remaining battery affects which actions are legal or if recharging is possible, battery must become part of the state: (row, column, remaining_charge). A final cost check is sufficient only when every move consumes a fixed amount and no action changes the budget.

Heuristic Cost

A stronger heuristic reduces expansions but may be expensive to compute. The total runtime is approximately:

expanded nodes × heuristic cost per node

An exact remaining-cost function would make A* expand only an ideal route, but computing it would solve the original problem. Good heuristic design balances informativeness and computational expense.

Caching can help when the same state is evaluated repeatedly. A beginner-friendly implementation can store calculated values in a dictionary and reuse them. Caching consumes memory and is useful only when repeated evaluation is common.

Heuristic Tests

On a finite graph, heuristic properties can be checked directly:

def consistency_violations(graph, heuristic):
    violations = []
    for state, edges in graph.items():
        for next_state, cost in edges:
            if heuristic[state] > cost + heuristic[next_state]:
                violations.append((state, next_state))
    return violations

assert H["G"] == 0
assert consistency_violations(GRAPH, H) == []

This test establishes consistency only for the listed graph. For a general family of states, a mathematical argument is still needed. Tests search for counterexamples; they do not replace proof.

Weighted A*

Weighted A* uses:

f(n) = g(n) + w × h(n), with w > 1

Increasing w makes search more goal-directed and often faster, but sacrifices ordinary A* optimality. Under suitable conditions it can provide a bounded-suboptimal solution. This is a deliberate engineering trade-off, not a free improvement.

An anytime strategy may begin with a larger weight to find a feasible route quickly and reduce the weight while time remains, improving the solution.

Applications

Heuristic search appears in:

• navigation and robot motion planning;
• puzzle solving;
• game pathfinding;
• automated planning;
• sequence alignment;
• parsing and speech recognition;
• resource allocation;
• network routing;
• design-space exploration.

In each case, the main intellectual work is the model and heuristic, not the priority queue.

Common Mistakes

• Using a heuristic borrowed from a different action or cost model.
• Claiming optimality without proving admissibility or consistency.
• Stopping when a goal is inserted into the frontier.
• Permanently closing states with an inconsistent heuristic.
• Comparing algorithms using runtime alone while ignoring solution cost.
• Treating fewer expanded nodes as automatically faster despite an expensive heuristic.
• Using negative edge costs.
• Breaking ties unpredictably and then reporting unstable results.

Exercises

1. Prove that Euclidean distance is admissible for movement in any direction when step cost is at least geometric distance traveled.
2. Construct an admissible but inconsistent heuristic for a small graph.
3. Trace UCS, greedy search, and A* on the same weighted graph. Record g, h, and f for every popped node.
4. Implement misplaced-tile and Manhattan heuristics for the 8-puzzle. Compare nodes expanded across several instances.
5. Show why adding two admissible heuristics can overestimate when they count overlapping work.
6. Experiment with weighted A* for several weights. Plot solution cost against expansions and explain the trade-off.
7. Design a lower-bound heuristic for a delivery problem with several remaining destinations.
8. Extend the maze example to include diagonal moves and select a matching heuristic.
9. Record priority-queue snapshots and explain every stale heap entry.
10. Generate random weighted graphs and compare A* against the zero-heuristic oracle.