CSCE 420 Lecture 5

« previous | Tuesday, January 29, 2013 | next »

Informed Search Algorithms

Until today we've been talking about uninformed search algorithms (DFS, BFS, UC, ID)

• Even though ID has the best-case time and space complexity, it's still exponential

Heuristic search: "use knowledge" (Best-first, A*), but what is knowledge?

• heuristic for navigation: estimated distance to goal $h(n)$ could be straight-line distance
• heuristic also represents estimate of problem difficulty

Best First Search

Use Uniform cost, but priority queue will be sorted on $h(n)$, the estimated cost remaining from $n$ to goal, instead of $g(n)$, the total path cost from root to $n$.

Limitation: you can be led astray by inaccuracy of $h(n)$.

Space complexity is $O(b^{m})$

A* Search

Same as Best First Search, but keep priority queue sorted on a new score $f(n)=h(n)+g(n)$, which represents the estimated path cost from root to goal, passing through $n$.

Theorem

A* is optimal if $h(n)$ is admissible.

$h(n)$ is admissible if it never overestimates the true distance to the goal: $h(n)\leq h^{*}(n)$, where $h^{*}(n)$ is the true path cost from $n$ to goal.

Straight-line distance is admissible:

• best case: $h^{*}(n)={\text{path cost}}$
• trivial case: $h_{0}(n)=0$

Why is A* optimal?

Proof. Assume some node $n'$ exists that has a better solution than $n$.

Like in UC, $f(n)$ increases monotonically (guaranteed by admissibility).

At the point $n$ would have been dequeued, some nodes in the path from root to $n'$ would have already been in the queue with shorter distances/costs.

Lemma

A* explores nodes in state space in order of increasing total path cost