In computer science, besides the common use as "rule of thumb" (see heuristic), the term heuristic has two well-defined technical meanings. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... A rule of thumb is an easily learned and easily applied procedure for approximately calculating or recalling some value, or for making some determination. ... Heuristic is the art and science of discovery and invention. ...

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. Flowcharts are often used to graphically represent algorithms. ... In mathematics, a proof is a demonstration that, assuming certain axioms, some statement is necessarily true. ... In computer science, runtime describes the operation of a computer program, the duration of its execution, from beginning to termination (compare compile time). ... It has been suggested that Loop optimization be merged into this article or section. ... Dissolving table salt in water In chemistry, a solution is a homogeneous mixture composed of one or more substances, known as solutes, dissolved in another substance, known as a solvent. ...

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 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. A metaheuristic is a heuristic method for solving a very general class of computational problems by combining user given black-box procedures — usually heuristics themselves — in a hopefully efficient way. ...

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. In graph theory, the single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized. ... Partial plot of a function f. ... Tree search algorithms are specialized versions of graph search algorithms, which take the properties of trees into account. ... Look up path in Wiktionary, the free dictionary. ... It has been suggested that this article or section be merged into Goal (management). ... Informed search algorithms are basically algorithms that solve problems using infomation that is not necessarily provided by the problem definition. ... The greedy best-first search method expands the state that is closest to the goal based on the heuristic. ... The A* search algorithm (pronounced A star) is a graph search algorithm that finds a path from a given initial node to a given goal node (or one passing a given goal test). ... In mathematics, the term optimization refers to the study of problems that have the form Given: a function f : A R from some set A to the real numbers Sought: an element x0 in A such that f(x0) ≤ f(x) for all x in A (minimization) or such that...

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. A solved 15-puzzle The n-puzzle is known in various versions, including the 8 puzzle, the 15 puzzle, and with various names. ... Taxicab geometry, considered by Hermann Minkowski in the 19th century, is a form of geometry in which the usual metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the (absolute) differences of their coordinates. ...

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 b^d 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 h₁(n) < h₂(n) if h₁(n) has a lower branch factor than h₂(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. i love algotheorms In computing, tree data structures, and game theory, the branching factor is the number of children of each node. ... In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ...

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: // Hondas intelligent humanoid robot AI redirects here. ...

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

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. A solved 15-puzzle The n-puzzle is known in various versions, including the 8 puzzle, the 15 puzzle, and with various names. ... Variations of Rubiks Cubes (from left to right: Rubiks Revenge, Rubiks Cube, Professors Cube, & Pocket Cube) Rubiks Cube or Rubix Cube is a mechanical puzzle invented in 1974 by the Hungarian sculptor and professor of architecture Ernő Rubik. ...

See also

• Artificial intelligence
• Expert system
• Heuristic evaluation
• Inference engine
• Inquiry
• Problem solving