Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 46 ยท Informed Search

Heuristic Functions

Learn what a heuristic is, build misplaced-tiles and Manhattan distance for the 8-puzzle, try greedy best-first search and measure the effective branching factor.

Uninformed search treats every direction as equally promising. That is why solving a 20-move 8-puzzle took tens of thousands of expanded nodes in the previous lesson. A person looking at the same puzzle does not behave that way. You glance at the board, notice that most tiles are far from home, and prefer moves that bring tiles closer. That glance is a heuristic.

A heuristic function h(n) is a cheap estimate of the cost of getting from state n to the nearest goal. It is not guaranteed to be exact, and it is allowed to be wrong, but a good one lets a search focus on the part of the state space that looks promising. Search that uses such an estimate is called informed search (or heuristic search), and it is the subject of this whole chapter. In this lesson you will build two heuristics, use them in greedy best-first search and then measure how much they actually help.

What makes a good heuristic

A heuristic takes a state and returns a number, usually "estimated remaining cost". Three properties matter in practice:

  • It is cheap to compute. It is called for every generated state, so a heuristic that costs as much as solving the problem is pointless.
  • It is informative. A function that always returns 0 is legal but tells the search nothing. The closer h(n) is to the true remaining cost, the fewer wrong turns the search takes.
  • It is zero at goals. By convention h(goal) = 0.

Later lessons add the properties that decide whether the answer is optimal (admissible and consistent heuristics). For now, the question is simply: how do you invent one?

Two heuristics for the 8-puzzle

The 8-puzzle is a 3x3 grid with eight numbered tiles and one blank. A move slides a tile into the blank. The goal puts the tiles in order. Two classic estimates come almost for free from the rules:

  1. Misplaced tiles. Count the tiles that are not on their goal square (the blank does not count). Every misplaced tile needs at least one move, so this is a sensible rough estimate.
  2. Manhattan distance. For each tile, add the number of rows plus columns separating it from its goal square. A tile can only move one square at a time horizontally or vertically, so this tells you the minimum number of moves that tile alone needs.

Manhattan distance is the stricter, more informative of the two, because a tile that is three squares from home contributes 3, not 1.

Python Computing two heuristics by hand

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Tiles 2 and 6 are already home, so six tiles are misplaced. Tile 1 sits in the bottom-right corner and must travel four squares; that single tile accounts for 4 of the Manhattan total of 14. The two estimates (6 and 14) disagree a lot, and the second is much closer to what the puzzle really needs.

The simplest way to use a heuristic is greedy best-first search. It is exactly the search skeleton you already know, with a priority queue ordered by h(n) alone: always expand the frontier node that looks closest to the goal.

graph TD
    S["Start<br/>h = 3"] --> A["Child A<br/>h = 4"]
    S --> B["Child B<br/>h = 2"]
    S --> C["Child C<br/>h = 5"]
    B --> B1["B1<br/>h = 1"]
    B --> B2["B2<br/>h = 3"]
    B1 --> G["Goal<br/>h = 0"]

Greedy search follows the smallest h at every step: S, then B, then B1, then the goal. It ignores how much each step cost.

Greedy search is often fast, because it dives toward the goal. Its weakness is the same as its strength: it ignores the cost already paid. It can be led down a path that looks good locally, then spend a long way wandering. It is not optimal, and in graphs with dead ends or loops it can be incomplete if you forget to track visited states (ours does track them).

The next program runs greedy search with Manhattan distance on three puzzles and compares the result with the true shortest solution, found by the more careful A* algorithm that the next lesson explains.

Python Greedy best-first search is fast but not optimal

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first puzzle is easy and greedy matches the optimum. On the other two, greedy finds a solution of 32 and 40 moves where 18 would do: a path almost twice as long as needed, although on the last puzzle it expanded only 112 nodes against 439 for the careful search. That is the greedy bargain. It trades solution quality for speed, which is sometimes exactly what you want (for example, a game character finding any acceptable route quickly) and sometimes unacceptable.

Greedy best-first search uses only the estimate to go, h(n). Uniform-cost search uses only the cost so far, g(n). The next lesson combines them as f(n) = g(n) + h(n), and that combination is A*.

Measuring how good a heuristic is

"Manhattan is better than misplaced tiles" is a claim you can test. The standard yardstick is the effective branching factor b*. Suppose a search expanded N nodes and found a solution at depth d. The effective branching factor is the branching factor that a uniform tree of depth d would need in order to hold N + 1 nodes:

N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d

A perfect heuristic would need no wasted expansions, so b* would be close to 1. A useless one pushes b* up toward the real branching factor (about 2.1 for the 8-puzzle, because the blank has two to four moves). Because b* is mostly independent of the puzzle's depth, it lets you compare heuristics fairly across puzzles of different difficulty. The program below solves the same eight puzzles with three heuristics and averages the results, and it finds b* by bisection.

Python Effective branching factor, measured

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With no heuristic, the search expands about 30,739 nodes on average (b* of 1.66). Misplaced tiles cuts that to about 2,324 (b* of 1.38), and Manhattan distance to about 349 (b* of 1.20). Going from "nothing" to a one-line formula removes roughly 99% of the work. The lesson is practical: time spent on a better heuristic often beats time spent on a faster computer.

Where heuristics come from

Good heuristics are rarely guessed. A reliable recipe is to relax the problem: remove some rules so that it becomes easy to solve, then use the exact cost of the easy problem as the estimate for the hard one. Misplaced tiles is the exact solution cost if a tile may jump to any square in one move. Manhattan distance is the exact cost if a tile may slide onto an occupied square. Route-finding uses straight-line distance, which is the cost if roads could be ignored. The lesson on admissible heuristics explains why this recipe gives you estimates you can trust.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a heuristic function h(n) estimate?

    h(n) is an estimate of the remaining cost. The cost already paid is g(n), a different quantity.
  2. 2. Greedy best-first search orders its frontier by which value?

    Greedy search always expands the node with the smallest heuristic value and ignores the path cost so far, which is why it is fast but not optimal.
  3. 3. Why is Manhattan distance usually a better 8-puzzle heuristic than the number of misplaced tiles?

    A misplaced tile counts 1 however far it is from home. Manhattan distance counts the actual rows and columns, giving a more informative estimate and fewer expanded nodes.
  4. 4. A search expanded many nodes and had an effective branching factor close to the real branching factor. What does that say about the heuristic?

    An informative heuristic keeps b* near 1, because the search wastes few expansions. A b* close to the true branching factor means the search was barely guided.

Summary

  • A heuristic h(n) is a cheap estimate of the remaining cost from n to a goal; it guides the search but does not have to be exact.
  • Misplaced tiles and Manhattan distance are two 8-puzzle heuristics; Manhattan is more informative.
  • Greedy best-first search orders the frontier by h(n) alone: fast, but its solutions can be far from optimal.
  • The effective branching factor b* measures how well a heuristic prunes the search; closer to 1 is better.
  • Heuristics usually come from relaxing the problem's rules.

Next, combine the cost so far with the estimate to go in A* Search.