Copyright © Philip M. Parker, INSEAD. Terms of Use.
Definition: Heuristic |
HeuristicAdjective1. (computer science) relating to or using a heuristic rule. 2. Ofo or relating to a general formulation that serves to guide investigation. Noun1. A commonsense rule (or set of rules) intended to increase the probability of solving some problem. Source: WordNet 1.7.1 Copyright © 2001 by Princeton University. All rights reserved. |
Date "heuristic" was first used in popular English literature: sometime before 1781. (references) |
Etymology: Heuristic \Heu*ris"tic\, adjective. [Greek expression to discover.]. (references) |
| Domain | Definition |
Computing | Heuristic 1. |
Math | An algorithm that usually, but not always, works or that gives nearly the right answer. (references) |
Source: compiled by the editor from various references; see credits. | |
(From Wikipedia, the free Encyclopedia)
Heuristic is the art and science of discovery. The word comes from the same Greek root as "eureka", meaning "to find". A heuristic is a way of directing your attention fruitfully.
The mathematician George Polya brought heuristics into popularity in the twentieth century in his book How to Solve It. He learned mathematical proofs as a student, but didn't know how mathematicians think of proofs, nor was this taught. How to Solve It is a collection of ideas about heuristics that he taught to math students: ways of looking at problems and casting about for solutions that often lead somewhere fruitful very quickly.
In computer science, a heuristic is an algorithm or procedure designed to solve a problem that ignores whether the solution is provably 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.
A heuristic is not guaranteed always to solve the problem, but often solves it well enough for most uses, and often does so more quickly than a more complete solution would.
Methodic is another way of solving a problem.
More formally, a heuristic is a function, defined on the nodes of a search tree , which serves as an estimate of the cost of the cheapest path from that node to the goal node. Heuristics are used by informed search algorithms such as Greedy Best-first search and A* to choose the best node to explore. Greedy Best-first search will choose the node that has the lowest value for the heuristic function. A* will expand nodes that have the lowest value for , where is the (exact) cost of the path from the initial state to the current node. When h(n) is admissible - that is if never overestimates the costs of reaching the goal - A* is provably optimal.
The classical problem involving heuristics is the n-puzzle. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the manhattan distances between each block and its position in the goal configuration. Note that both are admissible.
Effect of heuristics on computational performance
In any searching problem where there are choices at each node and a depth of d at the goal node, a naive searching algorithm would have to potentially search around nodes before finding a solution. Heuristics improve the effeciency of search algorithms by reducing the branching factor from to (ideally) a low constant b*.
Although any admissible heuristic will give an optimal answer, a heuristic that gives a lower branching factor is more computationally effecient for a particular problem. It can be shown that a heuristic is better than another heuristic , if dominates , ie. for all .
Finding heuristics
The problem of finding an admissible heuristic with a low branching factor for common search tasks has been extensively researched in the AI community. A number of common techniques are used:
Using these techniques a program called ABSOLVER was written by A.E. Prieditis for automatically generating heuristics for a given problem. ABSOLVER generated a new heuristic for the 8-puzzle better than any pre-existing heuristic and found the first useful heuristic for solving the Rubik's Cube.
- Solution costs of sub-problems often serve as useful estimates of the overall solution cost. These are always admissible. For example, a heuristic for a 10-puzzle might be the cost of moving tiles 1-5 into their correct places. A common idea is to use a pattern database that stores the exact solution cost of every subproblem instance.
- The solution of a relaxed problem often serves as a useful admissible estimate of the original. For example manhattan distance is a relaxed version of the n-puzzle problem, because we assume we can move each tile to its position in a single step.
- Given a set of admissible heuristic functions , the function is an admissible heuristic that dominates all of them.
External links
- http://greenlightwiki.com/heuristic A wiki devoted to heuristic.
Further reading
Judgement under Uncertainty: Heuristics & Biases, edited by: Daniel Kahneman, Amos Tversky and Paul Slovic, Cambridge University Press, 1982, trade paperback 544 pages, ISBN 0521284147
Source: adapted by the editor from Wikipedia, the free encyclopedia under a copyleft GNU Free Documentation License (GFDL) from the article "Heuristic."
| The following table is compiled from various sources, across various languages. When English abbreviations or acronyms come from a non-English source, this is noted. | |||
| Entry | Source | Expression | Field |
| HERMES | English | Heuristic Emergency Response Management Expert System | Computer - (XPS) |
Source: compiled by the editor, based on several corpora (additional references). | |||
Synonyms: HeuristicSynonyms: heuristic program (n), heuristic rule (n). (additional references) |
| Antonym: algorithmic (adj). (additional references) |
Crosswords: Heuristic |
| English words defined with "heuristic": lateral thinking. (references) |
| Specialty definitions using "heuristic": best first search, best-first search ♦ case based reasoning, Christofides algorithm ♦ frequency count heuristic ♦ halting problem, heuristics ♦ Integrated formal approach to industrial software development ♦ Miller-Rabin, minimax, move-to-front heuristic, move-to-root heuristic ♦ nearest neighbor algorithm, non-algorithmic procedure ♦ ordered search ♦ self-organizing heuristic, self-organizing list ♦ to a first approximation, TPS. (references) |
| Domain | Title |
Books |
|
Source: compiled by the editor from various references; see credits. | |
| "Heuristic" is generally used as an adjective (general or positive) -- approximately 100.00% of the time. "Heuristic" is used about 94 times out of a sample of 100 million words spoken or written in English. Its rank is based on over 700,000 words used in the English language. Some parts-of-speech are not covered due to the samples used by the British National Corpus. (note: percents less than one-hundredth of one percent have been omitted) |
| Parts of Speech | Percent | Usage per 100 Million Words | Rank in English |
| Adjective (general or positive) | 100% | 94 | 33,845 |
Source: compiled by the editor from several corpora; see credits.
Expressions using "heuristic": heuristic method ♦ heuristic problem solving ♦ heuristic program ♦ heuristic pruning ♦ heuristic rule. Additional references. | |
| Hyphenated Usage | |
Beginning with "heuristic": heuristic-based. | |
Ending with "heuristic": anti-heuristic. | |
| Source: compiled by the editor from various references; see credits. | |
| The following statistics estimate the number of searches per day across the major English-language search engines as identified by various trade publications. Hyperlinks lead to commercial use of the expression at Amazon.com. |
| Language | Translations for "heuristic"; alternative meanings/domain in parentheses. | |
Albanian | zhbiruese, udhëheqës (chief, chieftain, conductor, directive, director, directory, fugleman, guide, headman, instructor, leader, manager, managing, mentor, organizer, supervisor), orientues (key point, orientator), ndihmues (conducive, contributory, helper, helpful, instrumental), deduktive. (various references) | |
Arabic | مساعد على الكشف, مشجع الطالب على الاكتشاف. (various references) | |
Bulgarian | евристичен. (various references) | |
Chinese | 启发式. (various references) | |
Czech | heuristický. (various references) | |
Danish | heuristisk regel (heuristic method, heuristic rule), heuristisk metode (heuristic method, heuristic rule), heuristik (heuristic method, heuristic rule). (various references) | |
Dutch | heuristische methode (heuristic method, heuristic rule), heuristiek (heuristic method, heuristic rule), vuistregel (empirical rule, heuristic method, heuristic rule, rule of thumb). (various references) | |
Finnish | heuristinen ongelmanratkaisu (heuristic problem solving), heuristinen karsiminen (forward pruning, heuristic pruning, plausible move generation), karsiminen eteenpäin (forward pruning, heuristic pruning, plausible move generation). (various references) | |
French | heuristique (heuristic method, heuristic rule). (various references) | |
German | heuristische Regel (heuristic method, heuristic rule), heuristische Methode (heuristic method, heuristic rule), heuristisch (heuristical). (various references) | |
Greek | Ευρετική μέθοδος (heuristic method, heuristic rule), Ευρετική (heuristic method, heuristic rule), ευρετικός κανόνας (heuristic method, heuristic rule), ευρετική μέθοδος (heuristic method, heuristic rule), ευρετική (heuristic method, heuristic rule). (various references) | |
Hungarian | heurisztikus, megértést szolgáló, felfedezést szolgáló. (various references) | |
Italian | euristico, euristica (heuristic method, heuristic rule). (various references) | |
Japanese Kanji | 'ドロ シ類 (CHI, close call, fuse, fuse cock, HE, hearing, Hewlett, Hewlett Packard, Hilbert, hill, hill climb, hillbilly music, Himalaya, Houston, HP, HR, human, human assessment, human document, human ecology, human engineering, human interest, human interface, human relations, humanism, humanist, humanistic, humanity, humanization, humanlike, humanoid, hut, hydrozoan, hypochondria, interview, listening comprehension, near miss, public hearing). (various references) | |
Japanese Katakana | 'ューリスティック . (various references) | |
Korean | 발견 (Discoveries, Discovering, Discovery, find, finding, founding). (various references) | |
Pig Latin | euristichay.(various references) | |
Portuguese | heuristico, heuristica, heurística (heuristic method, heuristic rule), método heurístico (heuristic method, heuristic rule). (various references) | |
Russian | эвристический. (various references) | |
Serbo-Croatian | heurističan, istraživački (explorative, exploratory, research). (various references) | |
Spanish | heurístico, heurística (heuristic method, heuristic rule), regla heurística (heuristic method, heuristic rule), método heurístico (heuristic method, heuristic rule). (various references) | |
Swedish | heuristisk problemlösning (heuristic problem solving), heurisktisk beskärning (forward pruning, heuristic pruning, plausible move generation). (various references) | |
Thai | ที่ช่วยค้นหา. (various references) | |
Ukrainian | евристичний. (various references) | |
Vietnamese | để tìm ra (detective), để khám phá. (various references) | |
| Source: compiled by the editor from various translation references. | ||
| Language | Period | Translations |
| Greek | 700 BCE-300 CE | heuretikos. (various references) |
| Source: compiled by the editor from various references. | ||
Derivations | |
Words beginning with "heuristic": heuristically, heuristics. (additional references) | |
| |
"Heuristic" is suggested in spellcheckers for the following: euristic, heiristic, Herastau, heristic, heubristic, heueristic, heuistic, heurestic, heuretic, heurictic, heurisitc, heuristi, heuristivc, heurstic, heurustic, hieuristic, hiuristic, hueristic, huristic, leucistic. (additional references) | |
| Source: compiled by the editor, based on several corpora (additional references). | |
| Words rhyming with "heuristic" (pronounced 'Heu*ris"tic'): Absolutistic, Acatalectic, Acataleptic, Acephalocystic, Acetic, Acherontic, Acroteleutic, Adiaphoristic, Agrestic, Albinistic, Altruistic, Amnestic, Amphiblastic, Amyloplastic, Anacamptic, Anacathartic, Anachronistic, Anaclastic, Anaglyptic, Analectic, Analeptic, Anamnestic, Anapestic, Anaplastic, Anapodeictic, Anastaltic, Anatreptic, Animistic, Annalistic, Antapoplectic, Antarctic, Antephialtic, Antepileptic, Anthelmintic, Antiapoplectic, Anticlastic, Antiephialtic, Antiepileptic, Antigalastic, Antiorgastic, Antiperistaltic, Antiplastic, Antiscorbutic, Antispastic, Antonomastic, Antorgastic, Aoristic, Aortic, Aphlogistic, Aphotic. (additional references) |
Scrabble® Enable2K-Verified Anagrams | |
| Words within the letters "c-e-h-i-i-r-s-t-u" | |
-1 letter: christie. | |
-2 letters: cithers, curites, cushier, eristic, hirsute, icterus, itchier, richest. | |
-3 letters: cherts, chutes, citers, cither, cities, citrus, cruets, cruise, cruset, curets, curies, curite, cuties, eructs, ethics, iciest, itches, rectus, recuts, riches, rictus, ruches, rustic, schuit, steric, suiter, theirs, thrice, trices, truces, tusche, tushie, uretic. | |
-4 letters: cesti, chert, chest, chits, chute, cires, citer, cites, crest. | |
| Words containing the letters "c-e-h-i-i-r-s-t-u" | |
+1 letter: heuristics. | |
+2 letters: eucharistic, spherulitic. | |
+3 letters: euhemeristic, peritrichous. | |
+4 letters: cruiserweight, heuristically, hyperacuities. | |
+5 letters: antirheumatics, churchianities, cruiserweights, peritrichously. | |
| Source: compiled by the editor from various references; see credits. SCRABBLE® is a registered trademark. All intellectual property rights in and to the game are owned in the U.S.A and Canada by Hasbro Inc., and throughout the rest of the world by J.W. Spear & Sons Limited of Maidenhead, Berkshire, England, a subsidiary of Mattel Inc. Mattel and Spear are not affiliated with Hasbro. | |
| 1. Definition 2. Synonyms 3. Crosswords 4. Usage: Commercial | 5. Usage Frequency 6. Expressions 7. Expressions: Internet 8. Translations: Modern | 9. Translations: Ancient 10. Abbreviations 11. Acronyms 12. Derivations | 13. Rhymes 14. Anagrams 15. Bibliography |
Copyright © Philip M. Parker, INSEAD. Terms of Use.
