More Heuristic Search

A^* gives us a shortest path without searching all states.
So should we use A^*? Consider the following.

---

Finding an A^* algorithm is easy

The logic of the A^* reasoning means that:
If you just set h(n) = 0 for all n, then you have an admissible algorithm that will guarantee to find shortest path!

Q. So finding an A^* algorithm is easy?

A. Yes. Exactly! You have just defined breadth-first search. f(n) = g(n) + 0.
Breadth-first is an A^* algorithm. Problem is it takes too long.

The trick is to find a non-zero h(n) that will prune the search, but that is still always an underestimate.

The states searched by any A^* algorithm will be a subset of the states searched by breadth-first.

Example

N-puzzle.
Examples of A^* algorithms:

1. h(n) = 0
2. h(n) = no. of pieces out of place (will need this no. of moves or more)

Shows that it may not be hard to find a non-zero h(n) that is still always optimistic. Then you have an algorithm guaranteed to find optimal path (eventually).
Obviously some h(n)'s are better (weed more states) than others.

---

4.3.3 Informedness

When is one heuristic better than another?

Imagine we have two A^* heuristics.
h₁(n) ≤ h^*(n) for all n.
h₂(n) ≤ h^*(n) for all n.

If h1(n) ≤ h2(n) for all n, we say that heuristic h2 is more informed (i.e. better) than h1

But still need h₂(n) ≤ h^*(n) for all n.

---

Example

With 8-puzzle, where h₁ = 0 (breadth-first), h₂ = no. of tiles out of place:

h₁(n) ≤ h₂(n) ≤ h^*(n) for all n

h₂ is more informed (better) than h₁

h₂ searches only a subset of the states searched by h₁
Image courtesy of Ralph Morelli.
See Luger Fig 4.18
h₁ searches all states shown. h₂ searches shaded area.

Exercise - Prove this.

One can imagine a sequence of search spaces, each smaller than the previous one, converging on the optimal solution.

---

4.5 Complexity issues

The heuristic prunes the state space.
But the heuristic itself may take a non-trivial time to compute, if it is complex.
Time to compute heuristic for every state may waste all the time saved by pruning the space. There is a trade-off.

Luger Fig 4.28
"Control strategy cost" = Cost of calculating heuristic.
"Rule application cost" = Number of states searched.

LHS - Simple heuristic. Quick to calculate heuristic. But doesn't prune much - huge space to search.
RHS - Good heuristic. Cuts space. But calculating heuristic takes time.
Trade-off - Find middle point where computational cost of problem solving is lowest.

---

Beam search

Beam search: Reduce the space to be searched in best-first search.
We do this by keeping a fixed size OPEN list.
Only keep the n most promising (according to heuristic) unvisited states on OPEN.

ancientbrain.com      w2mind.org      humphrysfamilytree.com

On the Internet since 1987.      New 250 G VPS server.

Note: Links on this site to user-generated content like Wikipedia are highlighted in red as possibly unreliable. My view is that such links are highly useful but flawed.