A* Search

Question 1

Heuristic

Answer 1

Approximate cost to goal

Question 2

A* Priority Function

Answer 2

f(n) = h(n) + g(n)
(estimate of “cheapest” solution)

Question 3

Admissibilty

Answer 3

Heuristic is admissible if it never overestimates. (never greater then true cost)

Question 4

Consistency

Answer 4

Always returns the same value for the same input. Consistent heuristic is always admissible but not all admissible heuristics are consistent.

Question 5

A* Properities

Answer 5

(C* is path of cost of optimal solution)
- expands all nodes f(n)<C*
- may expand some nodes f(n) = C*
- will not expand any nodes f(n)>C*
- is complete if all step costs finite and branching factor finite
- is optimally efficient among algorithms that expand all nodes f(n)<C*