Heuristic ( /hjʉˈrɪstɨk/; or heuristics; Greek: "Εὑρίσκω", "find" or "discover") refers to experience-based techniques for problem solving, learning, and discovery. Where an exhaustive search is impractical, heuristic methods are used to speed up the process of finding a satisfactory solution. Examples of this method include using a rule of thumb, an educated guess, an intuitive judgment, or common sense.

In more precise terms, heuristics are strategies using readily accessible, though loosely applicable, information to control problem solving in human beings and machines.^[1]

Example[link]

The most fundamental heuristic is trial and error, which can be used in everything from matching nuts and bolts to finding the values of variables in algebra problems.

Here are a few other commonly used heuristics, from George Pólya's 1945 book, How to Solve It:^[2]

• If you are having difficulty understanding a problem, try drawing a picture.
• If you can't find a solution, try assuming that you have a solution and seeing what you can derive from that ("working backward").
• If the problem is abstract, try examining a concrete example.
• Try solving a more general problem first (the "inventor's paradox": the more ambitious plan may have more chances of success).

Psychology[link]

In psychology, heuristics are simple, efficient rules, hard-coded by evolutionary processes or learned, which have been proposed to explain how people make decisions, come to judgments, and solve problems, typically when facing complex problems or incomplete information. These rules work well under most circumstances, but in certain cases lead to systematic errors or cognitive biases.^{[citation needed]}

Although much of the work of discovering heuristics in human decision-makers was done by Amos Tversky and Daniel Kahneman,^[3] the concept was originally introduced by Nobel laureate Herbert A. Simon. Gerd Gigerenzer focuses on how heuristics can be used to make judgments that are in principle accurate, rather than producing cognitive biases – heuristics that are "fast and frugal".^[4] The Cognitive-Experiential Self-Theory (CEST) also supports an adaptive view of heuristic processing. From this perspective, heuristics are part of a larger experiential processing system that is often adaptive, but vulnerable to error in situations that require logical analysis.^[5]

In 2002, Daniel Kahneman and Shane Frederick proposed that cognitive heuristics work by a process called attribute substitution which happens without conscious awareness.^[6] According to this theory, when somebody makes a judgment (of a target attribute) which is computationally complex, a rather easier calculated heuristic attribute is substituted. In effect, a cognitively difficult problem is dealt with by answering a rather simpler problem, without being aware of this happening.^[6] This theory explains cases where judgments fail to show regression toward the mean.^[7] Heuristics can be considered to reduce the complexity of clinical judgements in healthcare.^[8]

Theorized psychological heuristics[link]

Well known[link]

• Anchoring and adjustment
• Availability heuristic
• Representativeness heuristic
• Naïve diversification
• Escalation of commitment

Less well known[link]

• Affect heuristic
• Contagion heuristic
• Effort heuristic
• Familiarity heuristic
• Fluency heuristic
• Gaze heuristic
• Peak-end rule
• Recognition heuristic
• Scarcity heuristic
• Similarity heuristic
• Simulation heuristic
• Social proof
• Take-the-best heuristic

Philosophy[link]

In philosophy, especially in Continental European philosophy, the adjective "heuristic" (or the designation "heuristic device") is used when an entity X exists to enable understanding of, or knowledge concerning, some other entity Y. A good example is a model which, as it is never identical with what it models, is a heuristic device to enable understanding of what it models. Stories, metaphors, etc., can also be termed heuristic in that sense. A classic example is the notion of utopia as described in Plato's best-known work, The Republic. This means that the "ideal city" as depicted in The Republic is not given as something to be pursued, or to present an orientation-point for development; rather, it shows how things would have to be connected, and how one thing would lead to another (often with highly problematic results), if one would opt for certain principles and carry them through rigorously.

"Heuristic" is also often commonly used as a noun to describe a rule-of-thumb, procedure, or method.^[9] Philosophers of science have emphasized the importance of heuristics in creative thought and constructing scientific theories.^[10] (See The Logic of Scientific Discovery, and philosophers such as Imre Lakatos,^[11] Lindley Darden, William C. Wimsatt, and others.)

Law[link]

In legal theory, especially in the theory of law and economics, heuristics are used in the law when case-by-case analysis would be impractical, insofar as "practicality" is defined by the interests of a governing body.^[12]

For instance, in all states in the United States the legal drinking age for unsupervised persons is 21 years, because it is argued that people need to be mature enough to make decisions involving the risks of alcohol consumption. However, assuming people mature at different rates, the specific age of 21 would be too late for some and too early for others. In this case, the somewhat arbitrary deadline is used because it is impossible or impractical to tell whether an individual is sufficiently mature for society to trust them with that kind of responsibility. Some proposed changes, however, have included the completion of an alcohol education course rather than the attainment of 21 years of age as the criterion for legal alcohol possession. This would put youth alcohol policy more on a case-by-case basis and less on a heuristic one, since the completion of such a course would presumably be voluntary and not uniform across the population.

The same reasoning applies to patent law. Patents are justified on the grounds that inventors need to be protected in order to have incentive to invent. It is therefore argued that, in society's best interest, inventors should be issued a temporary government-granted monopoly on their product, so that they can recoup their investment costs and make economic profit for a limited period. In the United States the length of this temporary monopoly is 20 years from the date the application for patent was filed, though the monopoly does not actually begin until the application has matured into a patent. However, like the drinking-age problem above, the specific length of time would need to be different for every product in order to be efficient; a 20-year term is used because it is difficult to tell what the number should be for any individual patent. More recently, some, including University of North Dakota law professor Eric E. Johnson, have argued that patents in different kinds of industries – such as software patents – should be protected for different lengths of time.^[13]

Mass communication[link]

This unreferenced section requires citations to ensure verifiability.

In the study of media effects, judgmental heuristics have been shown to play an active role in the simplifying of news and political communication. Use of these cues and other signals from elites allow average people the opportunity to achieve a modest level of rationality in reaching a decision. This can be accomplished without having to devote any significant measure of cognitive effort normally required to arrive at thoughtful and considered choices. The limited capacity theory model and other information processing models have been influential in the study of how people encode, store and retrieve political information. Most people maintain a minimum level of interest in public affairs, and therefore employ simplifying shortcuts to arrive at political judgments. Common examples include referring to the complex military and intelligence activities by NATO forces in the Middle East simply as “the war on terror,” a reversal of a specific policy or position as a “flip-flop,” and the homogenization of any type of broad government assistance program as “socialism.”

Risk assessment of new technologies offers another example of how ordinary citizens seek shortcuts to expediently arrive at judgments. Most people maintain a low level of interest in issues that are not center to their daily lives, such as developments in the various fields of science and technology. Media frames can produce powerful heuristics that can have significant impact on public opinion about a given new technology. Research has shown media frames that suggest high risk often lead to strong negative perceptions and possible rejection of a technology. An example is the casting of genetically modified foods as “Frankenfoods” and using illustrations containing visual cues to Frankenstein’s monster.

Computer science[link]

In computer science, a heuristic is a technique designed to solve a problem that ignores whether the solution can be proven to be correct, but which usually produces a good solution or solves a simpler problem that contains or intersects with the solution of the more complex problem. Most real-time, and even some on-demand, anti-virus scanners use heuristic signatures to look for specific attributes and characteristics for detecting viruses and other forms of malware.

Heuristics are intended to gain computational performance or conceptual simplicity, potentially at the cost of accuracy or precision.

In their Turing Award acceptance speech, Herbert A. Simon and Allen Newell discuss the Heuristic Search Hypothesis: a physical symbol system will repeatedly generate and modify known symbol structures until the created structure matches the solution structure.

That is, each successive iteration depends upon the step before it, thus the heuristic search learns what avenues to pursue and which ones to disregard by measuring how close the current iteration is to the solution. Therefore, some possibilities will never be generated as they are measured to be less likely to complete the solution.

A heuristic method can accomplish its task by using search trees. However, instead of generating all possible solution branches, a heuristic selects branches more likely to produce outcomes than other branches. It is selective at each decision point, picking branches that are more likely to produce solutions.^[14]

Pitfalls of heuristics[link]

This section needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (October 2009)

Heuristic algorithms are often employed because they may be seen to "work" without having been mathematically proven to meet a given set of requirements. One common pitfall in implementing a heuristic method to meet a requirement comes when the engineer or designer fails to realize that the current data set does not necessarily represent future system states.

While the existing data can be pored over and an algorithm can be devised to successfully handle the current data, it is imperative to ensure that the heuristic method employed is capable of handling future data sets. This means that the engineer or designer must fully understand the rules that generate the data and develop the algorithm to meet those requirements and not just address the current data sets.

Statistical analysis should be conducted when employing heuristics to estimate the probability of incorrect outcomes.

If one seeks to use a heuristic as a means of solving a search or knapsack problem, then one must be careful to make sure that the heuristic function which one is choosing to use is an admissible heuristic. Given a heuristic function labeled as:

Failed to parse (Missing texvc executable; please see math/README to configure.): h(v_i, v_g)

which is meant to approximate the true optimal distance Failed to parse (Missing texvc executable; please see math/README to configure.): d^\star(v_i,v_i)
to the goal node Failed to parse (Missing texvc executable; please see math/README to configure.): v_g
in a directed graph Failed to parse (Missing texvc executable; please see math/README to configure.): G
containing Failed to parse (Missing texvc executable; please see math/README to configure.): n
total nodes or vertexes labeled Failed to parse (Missing texvc executable; please see math/README to configure.): v_0,v_1,\cdots,v_n

.

"Admissible" means that Failed to parse (Missing texvc executable; please see math/README to configure.): h(v_i, v_g) \leq d^\star(v_i,v_g)

for all Failed to parse (Missing texvc executable; please see math/README to configure.): (v_i, v_g)
where Failed to parse (Missing texvc executable; please see math/README to configure.): {i,g} \in [0, 1, ... , n]

.

If a heuristic is not admissible, it might never find the goal, by ending up in a dead end of graph Failed to parse (Missing texvc executable; please see math/README to configure.): G

or by skipping back and forth between two nodes Failed to parse (Missing texvc executable; please see math/README to configure.): v_i
and Failed to parse (Missing texvc executable; please see math/README to configure.): v_j
where Failed to parse (Missing texvc executable; please see math/README to configure.): {i, j}\neq g

.

Human-computer interaction[link]

This section is written like a personal reflection or essay rather than an encyclopedic description of the subject. Please help improve it by rewriting it in an encyclopedic style. (February 2011)

In human-computer interaction, heuristic evaluation is a usability-testing technique devised by expert usability consultants. In heuristic evaluation, the user interface is reviewed by experts and its compliance to usability heuristics (broadly stated characteristics of a good user interface, based on prior experience) is assessed, and any violating aspects are recorded.

In software development, the use of a heuristic approach can facilitate a well-designed user interface, enabling users to navigate complex systems intuitively and without difficulty. The interface may guide the user when necessary using tooltips, help buttons, invitations to chat with support, etc., providing help when needed. However, in practice, the designer of the user interface may not find it easy to strike the optimum balance for assistance of the user.

Software developers and targeted end-users alike disregard heuristics at their own peril. End users often need to increase their understanding of the basic framework that a project entails (so that their expectations are realistic), and developers often need to push to learn more about their target audience (so that their learning styles can be judged). Business rules crucial to the organization are often so obvious to the end-user that they are not conveyed to the developer, who may lack domain knowledge in the particular field of endeavor the application is meant to serve.

A proper Software Requirements Specification (SRS) models the heuristics of how a user will process the information being rendered on-screen. An SRS is ideally shared with the end-user well before the actual Software Design Specification (SDS) is written and the application is developed, so users' feedback about their experience can be used to adapt the design of the application. This saves much time in the Software Development Life Cycle (SDLC). Unless heuristics are adequately considered, the project will likely suffer many implementation problems and setbacks.

Engineering[link]

In engineering, a heuristic is an experience-based method that can be used as an aid to solve process design problems, varying from size of equipment to operating conditions. By using heuristics, time can be reduced when solving problems. There are several methods which are available to engineers. These include Failure mode and effects analysis and Fault tree analysis. The former relies on a group of qualified engineers to evaluate problems, rank them in order of importance and then recommend solutions. The methods of forensic engineering are an important source of information for investigating problems, especially by elimination of unlikely causes and using the weakest link principle.

Because heuristics are fallible, it is important to understand their limitations. They are intended to be used as aids in order to make quick estimates and preliminary process designs.

See also[link]

• Algorithm
• Behavioral economics
• Daniel Kahneman
• Failure mode and effects analysis
• Problem solving
• Teachable moment
• List of cognitive biases
• HAL 9000#Origin of name
• Bias

References[link]

Further reading[link]

• How To Solve It: Modern Heuristics, Zbigniew Michalewicz and David B. Fogel, Springer Verlag, 2000. ISBN 3-540-66061-5
• Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2, http://aima.cs.berkeley.edu/ 
• The Problem of Thinking Too Much, 2002-12-11, Persi Diaconis

External links[link]

Look up heuristic in Wiktionary, the free dictionary.

Gerd Gigerenzer (born September 3, 1947, Wallersdorf) is a German psychologist who has studied the use of bounded rationality and heuristics in decision making, especially in medicine. A critic of the work of Daniel Kahneman and Amos Tversky, he argues that heuristics should not lead us to conceive of human thinking as riddled with irrational cognitive biases, but rather to conceive rationality as an adaptive tool that is not identical to the rules of formal logic or the probability calculus.^[1]

With Daniel Goldstein he first theorized the recognition heuristic.

He has written several books on the subject of heuristics and decision making, including Simple Heuristics That Make Us Smart (1999), and Bounded Rationality: The Adaptive Toolbox (2001) with Reinhard Selten. His two books for a lay audience, Reckoning with Risk: Learning to Live with Uncertainty (2002, published in the U.S. as Calculated Risks: How to Know When Numbers Deceive You), and Gut Feelings: The Intelligence of the Unconscious (2007), have been translated into 18 languages. "Rationality for Mortals", his most recent book, investigates decisions under limited time and information. He has trained U.S. Federal Judges, German physicians, and top managers in decision making and understanding risks and uncertainties.

Gigerenzer is currently director at Max Planck Institute for Human Development and former Professor of Psychology at the University of Chicago and John M. Olin Distinguished Visiting Professor, School of Law at the University of Virginia. He is also the director of the Harding Center for Risk Literacy, Berlin, Batten Fellow at the Darden Business School, University of Virginia, and Fellow of the Berlin-Brandenburg Academy of Sciences and the German Academy of Sciences Leopoldina. He is married to Lorraine Daston, director at Max Planck Institute for the History of Science and has one daughter, Thalia Gigerenzer.

References[link]

External links[link]

• Resume
• Books
• Edge.org bio
• Article: Simple tools for understanding risks: from innumeracy to insight
• Harding Center for Risk Literacy
• Gerd Gigerenzer in the German National Library catalogue (German)

Richard Manning Karp
Richard Karp giving a talk at the EPFL on 13th of July 2009
Born	(1935-01-03) January 3, 1935 (age 77) Boston, Massachusetts
Nationality	American
Fields	Computer Science
Institutions	University of California, Berkeley IBM
Alma mater	Harvard University
Doctoral advisor	Anthony Oettinger[1]
Doctoral students	Narendra Karmarkar Michael Luby Rajeev Motwani Barbara Simons
Known for	Edmonds–Karp algorithm Karp's 21 NP-complete problems Hopcroft–Karp algorithm Karp–Lipton theorem Rabin–Karp string search algorithm
Notable awards	Turing Award National Medal of Science Harvey Prize Benjamin Franklin Medal Kyoto Prize

Not to be confused with Richard A. Karp, one of the developers of TCP.

Richard Manning Karp (born January 3, 1935) is a computer scientist and computational theorist at the University of California, Berkeley, notable for research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.^[2]

Biography[link]

Born to Abraham and Rose Karp in Boston, Massachusetts, Karp has three younger siblings: Robert, David, and Carolyn. He attended Harvard University, where he received his Bachelor's degree in 1955, his Master's degree in 1956, and his Ph.D. in applied mathematics in 1959.

He started working at IBM's Thomas J. Watson Research Center. In 1968, he became Professor of Computer Science, Mathematics, and Operations Research at the University of California, Berkeley. Apart from a 4-year period as a professor at the University of Washington, he has remained at Berkeley. From 1988 to 1995 and 1999 to the present he has also been a Research Scientist at the International Computer Science Institute in Berkeley, where he currently leads the Algorithms Group.

Richard Karp was awarded the National Medal of Science, and was the recipient of the Harvey Prize of the Technion and the 2004 Benjamin Franklin Medal in Computer and Cognitive Science for his insights into computational complexity. In 1994 he was inducted as a Fellow of the Association for Computing Machinery. He is the recipient of several honorary degrees.

Work[link]

He has made many other important discoveries in computer science and operations research in the area of combinatorial algorithms. His major current research interests include bioinformatics.

In 1971 he co-developed with Jack Edmonds the Edmonds–Karp algorithm for solving the max-flow problem on networks, and in 1972 he published a landmark paper in complexity theory, "Reducibility Among Combinatorial Problems", in which he proved 21 Problems to be NP-complete.^[3]

In 1973 he and John Hopcroft published the Hopcroft–Karp algorithm, still the fastest known method for finding maximum cardinality matchings in bipartite graphs.

In 1980, along with Richard J. Lipton, Karp proved the Karp-Lipton theorem (which proves that, if SAT can be solved by Boolean circuits with a polynomial number of logic gates, then the polynomial hierarchy collapses to its second level).

In 1987 he co-developed with Michael O. Rabin the Rabin-Karp string search algorithm.

Turing Award[link]

His citation^[4] for the Turing Award was as follows:

For his continuing contributions to the theory of algorithms including the development of efficient algorithms for network flow and other combinatorial optimization problems, the identification of polynomial-time computability with the intuitive notion of algorithmic efficiency, and, most notably, contributions to the theory of NP-completeness. Karp introduced the now standard methodology for proving problems to be NP-complete which has led to the identification of many theoretical and practical problems as being computationally difficult.

References[link]

1. ^ Richard M. Karp at the Mathematics Genealogy Project.
2. ^ http://www.inamori-f.or.jp/laureates/k24_a_richard/prs_e.html
3. ^ Richard M. Karp (1972). "Reducibility Among Combinatorial Problems". In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103. http://www.cs.berkeley.edu/~luca/cs172/karp.pdf. 
4. ^ Association for Computing Machinery. "ACM Award Citation/Richard M. Karp". http://awards.acm.org/citation.cfm?id=3256708&srt=all&aw=140&ao=AMTURING&yr=1985. Retrieved 2010-01-17. 

External links[link]

Wikimedia Commons has media related to: Richard Karp

• ACM Crossroads magazine interview/bio of Richard Karp
• Karp's Home Page at Berkeley