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)\le 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^{\prime }$ 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^{\prime }$ 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