- For alternative uses, see heuristic
In computer science, two fundamental goals are finding algorithms with provably good run times and with provably good, usually optimal, solution quality. A heuristic is an algorithm that gives up 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 quick, but there is no argument this will always be the case.
Often, one can find specially crafted problem instances where the heuristic will in fact produce very bad results or run very slowly; however, these instances might never occur in practise because of their special structure. Therefore, the use of heuristics is very common in real world implementations.
Heuristics in shortest-path problems
For shortest path problems, the term has a much more specific 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* 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. When h(n) is admissible—that is, if h(n) 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 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 (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 efficient for a particular problem. It can be shown that a heuristic h2(n) is better than another heuristic h1(n), if h2(n) dominates h1(n), ie. h1(n) < h2(n) for all n.
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:
- 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 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.
Heuristics in Artificial Intelligence
Many algorithms in artificial intelligence are heuristic in nature, or use heuristic rules. A recent example of this is SpamAssassin which uses a wide variety of heuristic rules to determine whether an email is spam. Any one of the rules used in isolation would often lead to false classification, but when multiple heuristic rules are combined, the solution becomes more robust and trustable. In statistics, this is termed high confidence. When the word heuristic is used in rule-based language processing (stemming), pattern recognition (the features are heuristics) or image processing, it is often used to refer to the rules themselves and practitioners often use the word to mean ad hoc.