Heuristic

From DDL Wiki

A heuristic is a type of algorithm for solving an optimization problem. It also refers to a type of decision-making procedure.

In optimization, a heuristic is an algorithm that constructs or finds a feasible solution to the problem. The distinguishing characteristic of heuristics is that they do not seek to find an optimal solution. Instead, their goal is to get a near-optimal solution relatively quickly. The analysis of heuristics is concerned not only with estimating the computational effort of the algorithm but also with finding bounds on the worst-case performance of the heuristic.

Researchers have developed heuristics for many hard optimization problems. For example, for the traveling salesman problem, a well-known heuristic is the nearest neighbor heuristic. For the bin packing problem, the first-fit decreasing algorithm is a popular heuristic.

In decision-making, a heuristic refers to a method for making a decision without considering all of the alternatives and relevant important attributes of the alternatives. Heuristics are useful because they are fast; when using a heuristic, making a decision does not require substantial time or mental effort. Heuristics are thus related to the idea of bounded rationality. Gigerenzer and Todd (1999) present an example of a decision-making heuristic that can be used to classify heart attack patients according to risk using at most three variables. They also present a more general heuristic (called one-reason decision making) that is used to choose between two alternatives: Stop looking for cues as soon as one is found that differentiates between the two options being considered.

References

Gigerenzer, Gerd, Peter M. Todd, and the ABC Research Group, Simple Heuristics That Make Us Smart, Oxford University Press, 1999. A precis is available online at http://www-abc.mpib-berlin.mpg.de/users/ptodd/SimpleHeuristics.BBS/