Admissible heuristic

From Wikipedia, the free encyclopedia

This article does not cite any references or sources. (June 2007)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

In computer science, a heuristic 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. An admissible heuristic is also known as an optimistic heuristic.

[edit] Formulation

n

is a node

h

is a heuristic

h (n)

is cost indicated by

h

to reach a goal from

n

h * (n)

is the actual cost to reach a goal from n

h

is admissible if

$\forall n, h(n) \leq h^*(n)$

[edit] 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.