computer science//algorithms//heuristic

A heuristic is a decision rule that gives good answers fast without guaranteeing the best one, and it is how most real systems decide when the clock is running: send the nearest free robot, serve the most urgent order first, alarm when vibration passes 7 mm/s. The word has a second, narrower sense in search: the heuristic function \(h(n)\) of A* search, an estimate of the cost still to go that guides which node to expand. Both are shortcuts that trade a guarantee for speed.

A heuristic is a decision rule that gives good answers fast without guaranteeing the best one, and it is how most real systems decide when the clock is running: send the nearest free robot, serve the most urgent order first, alarm when vibration passes 7 mm/s. The word has a second, narrower sense in search: the heuristic function h(n)h(n)h(n) of A* search, an estimate of the cost still to go that guides which node to expand. Both are shortcuts that trade a guarantee for speed.

A few heuristics carry a bound on how bad they can be (weighted A* stays within a factor ε\varepsilonε of the optimum, greedy selection on a submodular function reaches at least 63% of it); most carry none, and can be arbitrarily bad on the rare case nobody tested. The question to ask of any rule is how much worse than the optimum it can be, and on which inputs.

A simple rule is enough more often than it looks.

It suffices when the options cost about the same (there is nothing to optimize), when decisions are replanned often (a fast rule every second on fresh data beats an optimum every minute on stale data), when the decision must be explained or certified, and when the cost model is doubtful, because optimizing a wrong model precisely is being wrong precisely.

The honest method is to measure. Implement the rule, compute in simulation how far it falls from the optimum on instances small enough to solve exactly, and decide with that number. If the gap is a few percent, the rule ships; if it is large and the stakes are high, the exact tools of combinatorial optimization earn their cost. That is the flyswatter rule, applied to decisions.

The book's ladder of rule against optimizer runs through the whole decision toolbox: an alarm threshold from the cost table before CUSUM, A* on a grid before sampling planners, nearest-neighbour association before global assignment, the nearest free robot before the Hungarian method, a fixed rule-based policy before an MDP.

The commonest heuristic is the greedy algorithm, and the usual way to make a heuristic better with time is a local search on top of it (anytime algorithm).