Heuristics

A heuristic is a rule of thumb: a shortcut that usually leads to a good answer quickly, but comes with no guarantee of correctness or optimality.

The word comes from the Greek heurisko, "I find" — the same root as Archimedes' eureka.

The trade-off, stated precisely

You give up certainty and buy speed. That's the whole bargain, and stating it in those terms earns marks.

Everyday heuristics

• Estimating a restaurant's quality by how crowded it is
• Judging distance by apparent size
• Buying the mid-priced option, assuming it balances cost and quality
• Reading only the first line of each paragraph to skim a chapter

Each is quick, usually reasonable, and occasionally wrong. That's the signature.

Computational heuristics

• Nearest neighbour for the travelling salesman problem: always go to the closest unvisited city. Fast, and usually within about 25% of optimal — but not optimal.
• Spell check suggesting the dictionary word with the fewest character edits.
• Chess engines valuing a queen at 9 and a pawn at 1 rather than searching every possible continuation.
• Caching the most recently used item, assuming it will be needed again.

Why we accept "usually right"

For many problems the exact answer is computationally out of reach. Visiting 20 cities in every possible order is $19!$ routes — roughly $1.2 \times 10^{17}$. Checking a billion routes a second would still take about four years.

A heuristic returns a good route in milliseconds. For a delivery company that is not merely acceptable — it is the only option that exists.

The characteristic risk

A heuristic can fail badly on inputs that violate its hidden assumption. Nearest neighbour performs poorly when the closest city sits at the end of a long detour, because the rule "closest is best" quietly assumes local choices don't trap you later.

When you use a heuristic, you should be able to say what assumption it makes and what kind of input would break it.