Heuristic

Heuristic is the art and science of discovery. The word comes from the same Greek root as "eureka", meaning "to find". A heuristic for a given problem is a way of directing your attention fruitfully to a solution. It is different from an algorithm in that it merely serves as a rule of thumb or guideline, as opposed to an invariant procedure. Heuristics may not always achieve the desired outcome, but can be extremely valuable to problem-solving processes. Good heuristics can dramatically reduce the time required to solve a problem by eliminating the need to consider unlikely possibilities or irrelevant states.

The mathematician George Polya popularised heuristics in the twentieth century in his book How to Solve It. He was motivated by his experiences in Mathematics education where students are taught mathematical proofs ,without learning techniques to formulate proofs themselves. 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 give results very quickly.

In psychology, heuristics are simple, efficient rules of thumb that people use to make decisions, typically when facing complex problems or incomplete information. These rules work well under most circumstances, but in certain cases lead to systematic cognitive biases.

For instance, people may tend to perceive more expensive beers as tasting better than inexpensive ones. This finding holds even when prices and brands are switched; putting the high price on the normally relatively inexpensive brand is enough to lead experimental subjects to perceive that beer as tasting better than the beer that is normally relatively expensive. You might call this bias the "price infers quality" bias.

Much of the work of discovering heuristics in human decision makers was ignited by Amos Tversky and Daniel Kahneman, whom shared an important influence on behavioral finance. Another example of a heuristic is the availability heuristic.

In computer science, a heuristic is a technique 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.

A 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.

Table of contents

1 Effect of heuristics on computational performance
2 Finding heuristics
3 External links
4 Further reading

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:

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.

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.

External links

http://greenlightwiki.com/heuristic A wiki devoted to heuristics.