Unit 4 · Algorithms & Simulation · Lesson 4.8

Heuristics: Good Enough on Purpose

When the perfect answer would take longer than the universe has, you take a good answer now. Build a route by hand, run a real heuristic on it, and see exactly what you gave up for the speed.

Big Idea 3 — Algorithms & ProgrammingCED 3.17 · approximate solutions

Before this lesson

No reading — this page is the reading. Runestone doesn’t cover Unit 4 (search, efficiency, limits, simulation), so everything you need is right here.

Where We Are

People→ Bits→ Programs→ Internet→ Security→ Big Data→ Impact

Programs, Algorithms region. Yesterday: some problems take unreasonable time to solve exactly. Today: what real software does about it — because your phone answers those problems every day, in seconds.

The Hook

Your GPS did not check every possible route. It couldn’t — you saw yesterday how fast the number of routes explodes. So how did it answer in two seconds? And is the route it gave you actually the best one?

Honest answer to the second question: probably close. Not guaranteed.

The Idea

When the exact answer takes unreasonable time, you can trade the guarantee for speed. A heuristic is an approach that finds a good-enough answer quickly, without promising it’s the best. The answer it gives is an approximate solution.

A classic heuristic for the route problem is nearest neighbor: from wherever you are, go to the closest city you haven’t visited yet. When none are left, go home.

Python

route = [start]
while len(unvisited) > 0:
    i = closest_index(route[-1], unvisited)
    route.append(unvisited[i])
    unvisited.pop(i)
route.append(start)   # go home

AP Pseudocode

route ← [start]
REPEAT UNTIL (LENGTH(unvisited) = 0)
{ i ← closestIndex(route[LENGTH(route)], unvisited)
  APPEND(route, unvisited[i])
  REMOVE(unvisited, i) }
APPEND(route, start)

Hover or tap a line to light its twin. closest_index is 3.9’s min algorithm over distances — nothing new. Note the last-element flip on line 3: Python’s route[-1] is AP’s route[LENGTH(route)].

The trade, in one sentence: a heuristic gives up the guarantee of the best answer in exchange for an answer in reasonable time. Checking every route of 6 cities means 120 orderings; nearest neighbor makes 5 quick choices.

Try It — Six Cities

Start at A. Click cities to build your own round trip, then run nearest neighbor and compare. Last, reveal the true best route — found by checking all 120 orderings.

Your route: A

distances in miles; totals rounded to the nearest mile; nearest-neighbor ties go to the earlier letter

Vocabulary

heuristic Programs: A technique that finds a good-enough solution quickly when finding the best one would take unreasonable time. Not guaranteed to be optimal.
approximate solution Programs: An answer that is close to the best, but not guaranteed to be the best.
optimization problem Programs: A problem that asks for the best answer among many possible ones — shortest, cheapest, fastest.

Check

Five questions. The key idea every time: what is being traded for what?

0 of 5 answered

Impact Check

When the thing being approximated is a person

A company gets 5,000 applications for 10 jobs. Nobody reads them all. Software ranks them with a heuristic — keywords, school names, gaps in work history — and a human reads the top 100. Fast. Good enough, on average.

But “good enough on average” means some strong candidates get filtered out, and the heuristic decides which ones. A route that’s 12% too long costs gas. A résumé screen that’s 12% wrong costs people jobs. Unit 8 comes back to this.

Connections

Came from 4.7 — heuristics exist because some problems take unreasonable time.

Uses 3.9 — nearest neighbor is the min algorithm, run over and over.

Next in 4.9 — problems that aren’t slow, but impossible. No heuristic fixes those completely.

Returns in Unit 8 — recommendation feeds and screening tools are heuristics making decisions about people.