Heuristic

Heuristic is the art and science of discovery and invention.

Here are sSome commonplace heuristics, all from How to Solve It:

• If you are having difficulty understanding a problem, try drawing a picture.
• If you can't find a solution, try assuming that you have a solution and seeing what you can derive from that ("working backward").
• If the problem is abstract, try examining a concrete example.
• Try solving a more general problem first (the "inventor's paradox": the more ambitious plan may have more chances of success).

A particular technique of directing your attention toward discovery is a heuristic, two or more of these are heuristics, and the adjective for "pertaining to how something is discovered" is heuristic.

(http://en.wikipedia.org/wiki/Heuristic)

In computer science, the term heuristic has two well-defined technical meanings, as in:

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 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 quickly, but there is no argument that this will always be the case.

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.

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 in a single step.

• Given a set of admissible heuristic functions h₁(n),h₂(n),...,h_i(n), the function h(n) = max{h₁(n),h₂(n),...,h_i(n)} is an admissible heuristic that dominates all of them.

(http://en.wikipedia.org/wiki/Heuristic_%28computer_science%29)