What is A* algorithm (requirements)?

Jump to bottom

Cameron W edited this page Jun 8, 2017 · 2 revisions

What is A* algorithm (requirements)?

If algorithm A is used with an evaluation function in which h(n) is less than or equal to the cost of the minimal path from n to the goal, the resulting search algorithm is A*.’
The admissibility property of a heuristic means that the cost to reach the goal is never overestimated (i.e. it's optimistic).

Algorithm A: Consider the evaluation function f(n) = g(n) + h(n), where

N is any state encountered in the search
g(n) is the cost of n from the start state
h(n) is the heuristic estimate of the cost of going from n to a goal A*:
If algorithm A is used with an evaluation function in which h(n) is less than or equal to the cost of the minimal path from n to the goal, the resulting search algorithm is called algorithm A*