A heuristic is a problem-solving method that uses simplified rules, estimates, or selective exploration to obtain useful results. In computer science, a heuristic may be an entire algorithm or a rule that guides another algorithm. It is commonly used when finding an exact answer would require excessive computation. Heuristics do not necessarily guarantee correctness or optimality, although some can operate within algorithms that provide such guarantees. (xlinux.nist.gov)
Scope and distinctions
Heuristics address a practical trade-off between computational effort and solution quality. In mathematical optimization, a method may seek a sufficiently good feasible solution rather than establish the best possible one. The traveling salesman problem, for example, asks for a minimum-length tour visiting each location once and returning to the starting point; heuristic methods can produce useful tours when exact optimization is too expensive. (xlinux.nist.gov)
A heuristic is not synonymous with an approximation algorithm. In theoretical computer science, an approximation algorithm normally runs in polynomial time and has a proved performance guarantee describing how far its result can be from optimal. A heuristic need not have such a bound. The categories can overlap: a practical method may be called a heuristic while also possessing a formal approximation guarantee. (xlinux.nist.gov)
Likewise, heuristic does not mean random. Some heuristics are deterministic, while others use random choices. A metaheuristic is a higher-level framework for organizing or guiding heuristic search, rather than a rule tied to one particular problem. Its implementation must specify problem-dependent elements such as candidate representations, evaluation procedures, and available moves. (xlinux.nist.gov)
Heuristic search
In artificial intelligence, heuristics often guide exploration of possible states or partial solutions. A heuristic evaluation function assigns an estimated value to a candidate, allowing the search procedure to prioritize promising alternatives. For the shortest-path problem, a function (h(n)) commonly estimates the remaining cost from node (n) to a goal. Greedy best-first search prioritizes this estimate without incorporating the cost already incurred. (artint.info)
A* search combines the estimated remaining cost with the known cost of reaching the current node:
[ f(n)=g(n)+h(n), ]
where (g(n)) is the cost of the path found so far. The search selects a frontier candidate with the lowest estimated total cost. Thus, heuristic information changes the order of exploration rather than directly constituting the final answer. (artint.info)
An admissible heuristic never overestimates the true minimum remaining cost. Under suitable conditions, including finite branching and edge costs bounded above zero, admissibility makes A* tree search optimal. Graph-search implementations that discard previously expanded states require additional care: a consistent heuristic satisfies
[ h(n)\leq c(n,n')+h(n') ]
for every edge from (n) to (n'), with zero heuristic value at goals. Consistency allows standard A* graph search to avoid reopening expanded states while retaining optimality. An admissible but inconsistent heuristic may require reopening states when a cheaper path is discovered. (artint.info)
Optimization techniques
A greedy algorithm makes locally preferred choices while constructing a solution. Such a rule can serve as a heuristic when local preference does not establish global optimality. Its usefulness therefore depends on the problem’s structure, not merely on the apparent desirability of each individual choice. (xlinux.nist.gov)
Local search instead maintains one or more complete candidates and modifies them through neighboring solutions. Hill climbing repeatedly chooses improvements according to an objective function. It can stop at a local optimum even when better solutions exist elsewhere, and plateaus can make progress difficult. Random restarts explore different initial candidates to reduce dependence on one starting point. (inst.eecs.berkeley.edu)
Simulated annealing sometimes accepts worsening moves, helping search escape local optima. The likelihood of accepting such moves decreases as a control parameter called temperature is reduced. Genetic algorithms maintain a population of candidates and generate new ones through selection, recombination, and mutation. Neither approach automatically guarantees an optimal result within a finite computational budget. (cs.ubc.ca)
Performance and limitations
Evaluating a heuristic involves more than recording whether it found an answer. Relevant measures include solution quality, running time, memory consumption, sensitivity to initialization, and variation across repeated runs. For local search, the neighborhood definition and stopping rule also affect what results are reachable. Comparisons therefore depend on both the problem instances and the computational resources allowed. (inst.eecs.berkeley.edu)
There is also a cost to computing heuristic estimates. A more informative estimate may reduce the number of explored paths, yet require more work per evaluation. Even an admissible estimate does not by itself establish that a search will be fast: A* performance can depend strongly on tie-breaking and the number of candidates with similar estimated costs. (artint.info)
Human judgment
In psychology, heuristics are simplified procedures for making judgments under uncertainty. Amos Tversky and Daniel Kahneman’s 1974 research described representativeness, availability, and anchoring with adjustment. Representativeness judges likelihood through resemblance; availability uses the ease of recalling or imagining examples; anchoring begins with an initial value and adjusts from it. These procedures can be useful but can also produce systematic errors in judgments of probability. A heuristic is the judgment procedure, whereas a bias is a systematic pattern of error that may result from its use. (cebma.org)
References
- heuristicxlinux.nist.gov
- approximation algorithmxlinux.nist.gov
- metaheuristicxlinux.nist.gov
- 6 Informed (Heuristic) Search — Artificial Intelligence: Foundations of Computational Agents, 3rd Editionartint.info
- CS 188, Fall 2022, Note 2inst.eecs.berkeley.edu
- 5 Local Search — Introduction to Artificial Intelligenceinst.eecs.berkeley.edu
- Local Searchcs.cmu.edu
- 6 Local Search — Artificial Intelligence: Foundations of Computational Agents, 3rd Editioncs.ubc.ca
- Judgment under Uncertainty: Heuristics and Biasescebma.org