Artificial Intelligence

Problem Solving By Search

Informed Search & Heuristics

A heuristic function, written h(n), estimates the cost from a given state n to the goal — an educated guess, not a guaranteed exact value, that lets a search al

JrCodex·9 min read

Jr Codex AI Notes

Level: Intermediate Prerequisites: Chapter 2 Time to complete: ~30 minutes

Table of Contents

  1. What is a Heuristic?
  2. Greedy Best-First Search
  3. A* Search
  4. Admissible & Consistent Heuristics
  5. Designing a Good Heuristic
  6. Why A* Is Optimal (Intuition)
  7. Comparing Every Algorithm So Far
  8. Summary & Next Steps

1. What is a Heuristic?

A heuristic function, written h(n), estimates the cost from a given state n to the goal — an educated guess, not a guaranteed exact value, that lets a search algorithm prioritize exploring more promising states first.

# For the Romania route-finding problem (Chapter 1), a natural heuristic
# is the STRAIGHT-LINE distance to Bucharest — easy to compute, and a
# reasonable estimate of the remaining travel distance
straight_line_to_bucharest = {
    "Arad": 366, "Zerind": 374, "Oradea": 380, "Sibiu": 253,
    "Timisoara": 329, "Lugoj": 244, "Mehadia": 241, "Drobeta": 242,
    "Craiova": 160, "Rimnicu": 193, "Fagaras": 176, "Pitesti": 100,
    "Bucharest": 0,
}
Why h(n) Matters
─────────────────────────────────────────
  Uninformed search (Ch.2) treats every unexplored state as
  EQUALLY worth investigating.

  h(n) gives the algorithm a sense of DIRECTION — "Fagaras looks
  much closer to Bucharest (176) than Timisoara (329), explore
  that way first" — without needing to actually search that far yet.
─────────────────────────────────────────

Expands the state with the lowest heuristic value — i.e., the state that looks closest to the goal, ignoring the cost already spent getting there.

import heapq
 
def greedy_best_first_search(problem, heuristic):
    frontier = [(heuristic[problem.initial_state], problem.initial_state, [])]
    visited = set()
 
    while frontier:
        _, state, path = heapq.heappop(frontier)      # lowest h(n) FIRST
 
        if problem.goal_test(state):
            return path
 
        if state in visited:
            continue
        visited.add(state)
 
        for action in problem.actions(state):
            next_state = problem.result(state, action)
            if next_state not in visited:
                heapq.heappush(frontier, (heuristic[next_state], next_state, path + [action]))
 
    return None
 
solution = greedy_best_first_search(from_arad_to_bucharest, straight_line_to_bucharest)
print(solution)
Greedy's Weakness — Ignoring Cost Already Spent
─────────────────────────────────────────
  Greedy can be FOOLED into a long detour if a nearby-looking
  state (low h(n)) is actually reached via an expensive path,
  while a slightly farther-looking state would have been reached
  via a much cheaper route overall.

  Greedy is FAST and often finds a decent path, but is NOT
  guaranteed optimal — it only looks at "how far to go,"
  never "how much have I already spent."
─────────────────────────────────────────

A* (pronounced "A-star") fixes Greedy's blind spot by combining both pieces of information: cost already spent (g(n), exactly UCS's ordering from Chapter 2) and estimated cost remaining (h(n), Greedy's ordering).

The A* Evaluation Function
─────────────────────────────────────────
  f(n) = g(n) + h(n)
          │       │
          │       └── estimated cost from n to the GOAL (heuristic)
          └── actual cost from the START to n (already spent)

  A* expands the state with the LOWEST f(n) — balancing
  "cheap so far" AND "looks close to the goal."
─────────────────────────────────────────

import heapq
 
def a_star_search(problem, heuristic):
    # frontier entries: (f(n), g(n), state, path)
    frontier = [(heuristic[problem.initial_state], 0, problem.initial_state, [])]
    visited = {}
 
    while frontier:
        f, g, state, path = heapq.heappop(frontier)
 
        if problem.goal_test(state):
            return path, g
 
        if state in visited and visited[state] <= g:
            continue
        visited[state] = g
 
        for action in problem.actions(state):
            next_state = problem.result(state, action)
            new_g = g + problem.step_cost(state, action)
            new_f = new_g + heuristic[next_state]
            if next_state not in visited or visited[next_state] > new_g:
                heapq.heappush(frontier, (new_f, new_g, next_state, path + [action]))
 
    return None, float("inf")
 
solution, cost = a_star_search(from_arad_to_bucharest, straight_line_to_bucharest)
print(f"A* path: {solution}, cost: {cost}")      # guaranteed OPTIMAL, given a good heuristic (Section 4)

A* is UCS (Chapter 2) plus a heuristic — set every heuristic[state] = 0 and A* becomes exactly UCS, confirming they share the same underlying mechanism, just with different guidance.

4. Admissible & Consistent Heuristics

A*'s optimality guarantee (Section 6) depends entirely on the heuristic satisfying specific properties — an arbitrary or badly-designed heuristic can break the guarantee.

Admissible Heuristic
─────────────────────────────────────────
  h(n) NEVER overestimates the true cost to the goal.
  h(n) <= actual_cost(n, goal), for EVERY state n.

  Straight-line distance is admissible for route-finding:
  you can NEVER actually travel in a straighter (shorter)
  line than the direct geometric distance.
─────────────────────────────────────────

Consistent (Monotonic) Heuristic
─────────────────────────────────────────
  For every state n and successor n' (reached via action costing c):
  h(n) <= c + h(n')

  (i.e., the heuristic's estimate never "jumps up" by more than
  the actual step cost — it decreases smoothly and reliably as
  you get closer to the goal)

  Every CONSISTENT heuristic is also ADMISSIBLE — but not
  every admissible heuristic is consistent (consistency is
  the STRONGER, more useful property in practice).
─────────────────────────────────────────

# Checking admissibility conceptually — h(n) must never exceed the REAL cost
def check_admissible_example():
    actual_cost_arad_to_bucharest = 418      # the true optimal path cost (via Sibiu-Rimnicu-Pitesti)
    heuristic_estimate = straight_line_to_bucharest["Arad"]      # 366
 
    print(heuristic_estimate <= actual_cost_arad_to_bucharest)      # True — admissible, doesn't overestimate
 
check_admissible_example()

Why this property matters so much: an admissible heuristic guarantees A* never mistakenly rules out the true optimal path by overestimating it — Section 6 explains exactly how this connects to A*'s optimality proof.

5. Designing a Good Heuristic

A heuristic needs to be both admissible/consistent (Section 4) and practically useful — a heuristic of h(n) = 0 everywhere is technically admissible (it never overestimates — trivially true) but gives zero guidance, degenerating A* back into plain UCS.

The Trade-off in Heuristic Design
─────────────────────────────────────────
  h(n) = 0 (uninformative)          Perfect h(n) (impossible in practice)
  ─────────────────────────         ─────────────────────────
  Degenerates to UCS                  Would go STRAIGHT to the goal,
  (correct, but slow — no                no wasted exploration at all
   guidance at all)                       (but computing it would usually
                                            require already SOLVING the
                                            problem!)

  A GOOD heuristic sits between these extremes: informative
  enough to meaningfully speed up search, cheap enough to
  compute quickly, and never overestimating (admissible).
─────────────────────────────────────────

# A classic heuristic-design example: the 8-puzzle (Chapter 1's example problem)
 
def misplaced_tiles_heuristic(state, goal_state):
    """h1: count of tiles in the WRONG position. Admissible, but weak."""
    return sum(1 for a, b in zip(state, goal_state) if a != b and a != 0)
 
def manhattan_distance_heuristic(state, goal_state, size=3):
    """h2: sum of each tile's grid distance from its goal position. Admissible AND stronger than h1."""
    total = 0
    for i, tile in enumerate(state):
        if tile == 0:
            continue
        goal_index = goal_state.index(tile)
        row1, col1 = divmod(i, size)
        row2, col2 = divmod(goal_index, size)
        total += abs(row1 - row2) + abs(col1 - col2)
    return total
Dominance — Comparing Two Admissible Heuristics
─────────────────────────────────────────
  If h2(n) >= h1(n) for EVERY state n (and both are admissible),
  h2 is said to DOMINATE h1 — and A* using h2 will typically
  explore FEWER states, since it has more accurate guidance.

  Manhattan distance DOMINATES misplaced-tiles for the 8-puzzle:
  it's always at least as informative, never overestimates,
  and leads to a faster search in practice.
─────────────────────────────────────────

Practical rule of thumb for designing heuristics: relax the problem's constraints to make it trivially solvable, then use that trivial solution's cost as your heuristic — Manhattan distance is exactly this: "if a tile could move directly to its goal position, ignoring other tiles in the way, how far would it travel?"

6. Why A* Is Optimal (Intuition)

A* Optimality — the Core Argument
─────────────────────────────────────────
  Suppose A* is about to expand the goal state G, reached via
  path cost g(G). f(G) = g(G) + h(G) = g(G) + 0 = g(G).

  For A* to have chosen G over some OTHER frontier node n:
    f(G) <= f(n) = g(n) + h(n)

  Since h is ADMISSIBLE, h(n) never overestimates the true
  remaining cost from n. This means no node claiming to lead
  to a cheaper solution was being unfairly skipped — A*
  would have expanded it FIRST if it truly offered a better path.

  This is why an admissible heuristic is REQUIRED for the
  optimality guarantee — an overestimating heuristic could
  cause A* to wrongly prioritize a worse path that merely
  LOOKED cheaper.
─────────────────────────────────────────

This is a simplified version of the formal proof found in AI textbooks — the essential takeaway is that admissibility (Section 4) is precisely the property that prevents A* from ever being misled into missing the true optimal solution.

7. Comparing Every Algorithm So Far

bfs_path = breadth_first_search(from_arad_to_bucharest)
dfs_path = depth_first_search(from_arad_to_bucharest)
ucs_path, ucs_cost = uniform_cost_search(from_arad_to_bucharest)
greedy_path = greedy_best_first_search(from_arad_to_bucharest, straight_line_to_bucharest)
astar_path, astar_cost = a_star_search(from_arad_to_bucharest, straight_line_to_bucharest)
 
print(f"BFS:     {bfs_path}")
print(f"DFS:     {dfs_path}")
print(f"UCS:     {ucs_path} (cost={ucs_cost})")
print(f"Greedy:  {greedy_path}")
print(f"A*:      {astar_path} (cost={astar_cost})")      # matches UCS's optimal cost, usually faster to find
AlgorithmUses g(n)?Uses h(n)?Optimal?
BFS/DFSNoNoNo (DFS) / steps only (BFS)
UCSYesNoYes
GreedyNoYesNo
A*YesYesYes (with admissible h)

8. Summary & Next Steps

Key Takeaways

  • A heuristic h(n) estimates remaining cost to the goal, giving search algorithms a sense of direction that uninformed search entirely lacks.
  • Greedy Best-First Search uses only h(n) — fast, but not optimal, since it ignores cost already spent.
  • A* uses f(n) = g(n) + h(n), combining UCS's cost-so-far with Greedy's goal-direction — guaranteed optimal when the heuristic is admissible (never overestimates).
  • A good heuristic is informative (speeds up search meaningfully), cheap to compute, and admissible; a common design technique is solving a "relaxed" version of the problem and using its cost as the heuristic.
  • Consistency is a stronger property than admissibility and is what most practical heuristics (like Manhattan distance) actually satisfy.

Concept Check

  1. Why is Greedy Best-First Search not guaranteed to find the optimal path, even though it usually finds a path quickly?
  2. What does it mean for a heuristic to be "admissible," and why is that property required for A*'s optimality guarantee?
  3. Why does the Manhattan distance heuristic dominate the misplaced-tiles heuristic for the 8-puzzle?

Next Chapter

→ Chapter 4: Local Search

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index