Home (Admissible heuristic)

 Artificial Intelligence 

What is what? Everything you always wanted to know.
  » »
 
   

Admissible heuristic

Artificial Intelligence  Adjusted R  Admon

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.


Admissible Heuristics
How do we choose h(n)?
1) We must underestimate actual cost (E) to avoid premature termination of possible optimal paths to goal.

3.2 What is an admissible heuristic ?
3.3 Describe the A* algorithm?
3.4 Given that h is an admissible heuristic, prove that the A* algorithm is optimal.

A* algorithm (pronounced ``A-star'') an algorithm for heuristic search, using an admissible heuristic function f(n) = g(n) + h(n), where g(n) is the known cost to reach node n from the start, and h(n) is the estimated cost from node n to a goal.

The classic algorithm for finding shortests paths given an admissible heuristic. We'll deal with the notion of admissibility (summary: admissible = optimistic). We show how you can prove properties of A*. We'll also briefly discuss IDA* (iterative deepening A*). ...

(**) This should never happen if you have an monotone ~. However in games we often have inadmissible heuristics.
Source code ...

In addition, an ~ function such as the cost of the minimum spanning tree of the remaining unvisited cities, can be added to the cost so far of a partial tour to increase the amount of prunin.

The restriction to h(n) is that it must always underestimate the cost to reach a goal state from n. Such heuristic measures are called admissible. See Russell and Norvig for proof that A* search with an ~ is complete and optimal.

See also: See also: What is the meaning of Algorithm, Search algorithm, AI, Heuristics, Values?

◄ Adjusted R   Admon ►
 
RSS Mobile