Heuristics
A client recently asked me what I meant when I refered to “heuristic search.” Heuristic search is performed when “brute force search” (or all-possible-paths-search) is computationally intractable. Essentially, you can think of a heuristic as a “rule of thumb” or an approach to calculate an approximate answer. Here’s a more detailed description…
A heuristic is defined by Meriam Webster’s on line dictionary as follows:
Main Entry: heu·ris·tic
Pronunciation: hyu-’ris-tik
Function: adjective
Etymology: German heuristisch, from New Latin heuristicus, from Greek heuriskein to discover; akin to Old Irish fo-fúair he found
: involving or serving as an aid to learning, discovery, or problem-solving by experimental and especially trial-and-error methods heuristic assumption>; also
: of or relating to exploratory problem-solving techniques that utilize self-educating techniques (as the evaluation of feedback) to improve performance heuristic computer program>
Heuristics are used in the context of high complexity to find good solutions to problems that might be impossible to solve for an exact or the globally optimum solution.
Examples of the use of heuristic search are found in many common optimization problems. In many optimization efforts, computations can take billions of billions of years to find the exact solution even on the fastest computers. This is a case where using heuristics may allow you to find a good solution even if the optimal solution is unknown.
-Stu