Admissible heuristic

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 cost of reaching the goal.[1] An admissible heuristic is also known as an optimistic heuristic.

Contents

Search Algorithm

An admissible heuristic is used to estimate the cost of reaching the goal state in an informed search algorithm. In order for a heuristic to be admissible to the search problem, the estimated cost must always be lower than or equal to the actual cost of reaching the goal state. The search algorithm uses the admissible heuristic to find an estimated optimal path to the goal state from the current node. For example, in A* search the evaluation function (where n is the current node) is:

f(n) = g(n) + h(n)

where

f(n) = the evaluation function.
g(n) = the cost from the start node to the current node
h(n) = estimated cost from current node to goal.

h(n) is calculated using the heuristic function. With a non-admissible heuristic, the A* algorithm could overlook the optimal solution to a search problem due to an overestimation in f(n).

Formulation

n is a node
h is a heuristic
h(n) is cost indicated by h to reach a goal from n
C(n) is the actual cost to reach a goal from n
h is admissible if
\forall n, h(n) \leq C(n)

Construction

An admissible heuristic can be derived from a relaxed version of the problem, or by information from pattern databases that store exact solutions to subproblems of the problem, or by using inductive learning methods.

Examples

Two different examples of admissible heuristics apply to the fifteen puzzle problem:


The Hamming distance is the total number of misplaced tiles. It is clear that this heuristic is admissible since the total number of moves to order the tiles correctly is at least the number of misplaced tiles (each tile not in place must be moved at least once). The cost (number of moves) to the goal (an ordered puzzle) is at least the Hamming distance of the puzzle.


The Manhattan distance of a puzzle is defined as:

h(n) = distance(tile,correctposition)
alltiles

The Manhattan distance is an admissible heuristic because every tile will have to be moved at least the amount of spots in between itself and its correct position. Consider the puzzle below:

43 61 30 81
72 123 93 144
153 132 14 54
24 101 111

The subscripts show the Manhattan distance for each tile. The total Manhattan distance for the shown puzzle is:

h(n) = 3 + 1 + 0 + 1 + 2 + 3 + 3 + 4 + 3 + 2 + 4 + 4 + 4 + 1 + 1 = 36

Notes

While all consistent heuristics are admissible, not all admissible heuristics are consistent.

For tree search problems, if an admissible heuristic is used, the A* search algorithm will never return a suboptimal goal node.

References

  1. ^ Russell, S.J.; Norvig, P. (2002). Artificial Intelligence: A Modern Approach. Prentice Hall. ISBN 0-13-790395-2. 

See also



Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • 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… …   Wikipedia

  • admissible — adjective a) capable or deserving to be admitted, accepted or allowed; allowable, permissible, acceptable b) Describing a heuristic that never overestimates the cost of reaching a goal …   Wiktionary

  • 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

  • A* search algorithm — In computer science, A* (pronounced A star ) is a best first, graph search algorithm that finds the least cost path from a given initial node to one goal node (out of one or more possible goals). It uses a distance plus cost heuristic function… …   Wikipedia

  • Bidirectional search — is a graph search algorithm that runs two simultaneous searches: one forward from the initial state, and one backward from the goal, and stopping when the two meet in the middle. The reason for this approach is that each of the two searches has… …   Wikipedia

  • Admissibility — may refer to: * Admissible evidence, evidence which may be introduced in a court of law. * Admissible decision rule, in decision theory, a rule which is never dominated. * Admissible rule, in logic, a type of rule of inference. * Admissible… …   Wikipedia

  • Fifteen puzzle — A solved 15 puzzle The 15 puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and many others) is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle also… …   Wikipedia

  • Cost overrun — A cost overrun, also known as a cost increase or budget overrun, is an unexpected cost incurred in excess of a budgeted amount due to an under estimation of the actual cost during budgeting. Cost overrun should be distinguished from cost… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

Share the article and excerpts

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