5. A Search Algorithm & Heuristics

A Search

A Search* computes a cost function $f(n)=g(n)+h(n)$, where:

• $g(n)$ is the cost from the initial state to $n$
• $h(n)$ is the estimated distance of $n$ from the goal state

We choose the state with the lowest value of $f(n)$ when expanding nodes.

Link to original

Admissibility & Optimality

Admissible Heuristic

An admissible heuristic is one that never over-estimates the distance to the goal. The actual distance is always greater than the heuristic value.

Link to original

The key challenge is finding a heuristic which is both admissible and informative, often we relax the constraints of the problem to come up with useful heuristics. Given admissible heuristics, A* will find optimal solutions.

[animate slides 9 to 16]