For generic article about heuristics, see
Heuristic.
In computer science, besides the common use as "rule
of thumb" (see heuristic), the term heuristic has two well-defined technical
meanings. It can either be any algorithm that gives up finding the optimal solution for an improvement in run time or it can be a
function that estimates the cost of the cheapest path from one node to another.
Heuristic algorithms
Two fundamental goals in computer science are finding algorithms with provably good run times and with provably good or optimal solution quality. A heuristic is an
algorithm that abandons one or both of these goals; for example, it usually finds pretty good solutions, but there is no proof
the solutions could not get arbitrarily bad; or it usually runs reasonably quickly, but there is no argument that this will
always be the case.
For instance, say you are packing odd-shaped items into a box. Finding a perfect
solution is a hard problem: there is essentially no way to do it without trying every possible way of packing them. What most
people do, then, is "put the largest items in first, then fit the smaller items into the spaces left around them." This will not
necessarily be perfect packing, but it will usually give a packing that is pretty good. It is an example of a heuristic
solution.
Pearl (1984), states that heuristic methods are based upon intelligent search strategies for computer problem solving, using
several alternative approaches.
Often, one can find specially crafted problem instances where the heuristic will in fact produce very bad results or run very
slowly; however, such pathological instances might never occur in practice
because of their special structure. Therefore, the use of heuristics is very common in real world implementations. For many
practical problems, a heuristic algorithm may be the only way to get good solutions in a reasonable amount of time.
There is a class of general heuristic strategies called metaheuristics, which often use
randomized search for example. They can be applied to a wide range of problems, but good performance is never guaranteed.
The following (from Zanakis and Evans in course text)
Disadvantages
1. Not as general as algorithms
2. May result in poor solutions
3. Sequential choices may fail to anticipate consequences of choices
Heuristics in shortest-path problems
For shortest path problems, the term has a different meaning. Here, a
heuristic is a function, h(n)
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* search will
expand nodes that have the lowest value for g(n) + h(n), where
g(n) is the (exact) cost of the path from the initial state to the current node. If
h(n) is admissible—that is, if h(n)
never overestimates the costs of reaching the goal—, then A* will always find an optimal solution.
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 b choices at each node and a depth of
d at the goal node, a naive searching algorithm would have to potentially search around
bd nodes before finding a solution. Heuristics improve the efficiency of
search algorithms by reducing the branching factor from b to a lower constant b', using a cutoff mechanism. The branching
factor can be used for defining a partial order on the heuristics, such that
h1(n) < h2(n) if h1(n) has a lower branch factor than h2(n) for a given node n of the search tree.
Heuristics giving lower branching factors at every node in the search tree are preferred for the resolution of a particular
problem, as they are more computationally efficient.
Finding heuristics
The problem of finding an admissible heuristic with a low branching factor for common search tasks has been extensively
researched in the artificial intelligence community. Several common techniques
are used:
- 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 independently of
moving the other tiles.
- Given a set of admissible heuristic functions h1(n),h2(n),...,hi(n), the
function h(n) =
max{h1(n),h2(n),...,hi(n)} is an
admissible heuristic that dominates all of them.
Using these techniques a program called ABSOLVER was written (1993) 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.
Trivia
The movie and book 2001: A Space Odyssey portrays the HAL-9000 computer
which stands for "Heuristic ALgorithmic computer".
See also
References
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
