Heuristic function

Heuristic function

A heuristic function or simply a heuristic is a function that ranks alternatives in various search algorithms at each branching step basing on an available information in order to make a decision which branch is to be followed during a search.

hortest paths

For example, for shortest path problems, 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 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_1(n) < h_2(n) if h_1(n) has a lower branch factor than h_2(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 h_1(n), h_2(n), ..., h_i(n), the function h(n) = max{h_1(n), h_2(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.

ee also

* Heuristic algorithm
* Artificial intelligence
* Consistent heuristic
* Expert system
* Heuristic evaluation
* Inference engine
* Inquiry
* Problem solving

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Heuristic algorithm — In computer science, a heuristic algorithm or simply a heuristic is an algorithm that ignores whether the solution to the problem can be proven to be correct, but which usually produces a good solution or solves a simpler problem that contains or …   Wikipedia

  • Heuristic (disambiguation) — A heuristic is a method for helping in solving of a problem, commonly informal. The term may also have the following technical meanings.*Heuristic algorithm *Heuristic evaluation is an expert based usability evaluation method. *Heuristic function …   Wikipedia

  • Heuristic analysis — is a method employed by many computer antivirus programs designed to detect previously unknown computer viruses, as well as new variants of viruses already in the wild.Heuristic analysis is an expert based analysis that determines the… …   Wikipedia

  • Admissible heuristic — In computer science, specifically in algorithms related to Pathfinding, a heuristic function is said to be admissible if it is no more than the lowest cost path to the goal. In other words, a heuristic is admissible if it never overestimates the… …   Wikipedia

  • Consistent heuristic — In computer science, a consistent (or monotone) heuristic function is a strategy for search that approaches the solution in an incremental way without taking any step back. Formally, for every node N and every successor P of N generated by any… …   Wikipedia

  • Evaluation function — An evaluation function, also known as a heuristic evaluation function or static evaluation function, is a function used by game playing programs to estimate the value or goodness of a position in the minimax and related algorithms. The evaluation …   Wikipedia

  • Monotonic function — Monotonicity redirects here. For information on monotonicity as it pertains to voting systems, see monotonicity criterion. Monotonic redirects here. For other uses, see Monotone (disambiguation). Figure 1. A monotonically increasing function (it… …   Wikipedia

  • Espresso heuristic logic minimizer — The Espresso logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital electronic gate circuits.[1] Espresso was developed at IBM by Robert Brayton. Rudell later published the …   Wikipedia

  • Dirac delta function — Schematic representation of the Dirac delta function by a line surmounted by an arrow. The height of the arrow is usually used to specify the value of any multiplicative constant, which will give the area under the function. The other convention… …   Wikipedia

  • Hash function — A hash function is any well defined procedure or mathematical function for turning some kind of data into a relatively small integer, that may serve as an index into an array. The values returned by a hash function are called hash values, hash… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”