Heuristic
A heuristic is a practical rule or estimate that guides a decision or search. It can save work without guaranteeing the best answer, although some search algorithms retain guarantees when their heuristic meets specific conditions.
A route planner can use straight-line distance to a destination as an estimate of the driving distance still required. It explores promising routes first instead of treating every branch equally. The estimate guides the search; the surrounding algorithm determines when a route can be accepted.
In A* search, an admissible heuristic never overestimates the remaining cost. That condition supports an optimality guarantee in the relevant search setting; graph-search variants also need suitable handling of repeated states. A heuristic is therefore not synonymous with “approximate answer” or “unreliable shortcut.” State the conditions of the algorithm using it.
The same word appears in product rules, such as trying the local cache before an expensive search. Such a rule may be useful without being universally best. Treat it as a choice to evaluate: measure what effort it saves and which cases it misses. A heuristic may be hand-written or learned; its role is to guide a decision.
Sources
- Poole and Mackworth: Informed (Heuristic) Search — Defines heuristic cost estimates, admissibility and search strategies including A*.
Go deeper
- UC Berkeley CS188: Informed search course
Work through heuristic estimates, A* and conditions for optimal search.