Search lesson

Here is my handout.

Proposed solutions

After this lesson last semester I got a question about monotonicity: "If f(A)=10 and f(B)=11, then f is not optimistic, but monotone. How is that possible?"

But f is NOT monotone because f(A) - f(G) > dist(A, G).

Why does monotonicity imply optimistic estimations (admissibility)?
Luger gives this argument in the section on monotonicity:

For any path from a node si to the goal sg we have:

s1 to s2      h(s1) - h(s2) <= cost(s1,s2)
s2 to s3      h(s2) - h(s3) <= cost(s2,s3)
s3 to s4      h(s3) - h(s4) <= cost(s3,s4)
 ....
sg-1 to sg    h(sg-1) - h(sg) <= cost(sg-1,sg)

If you add the columns and use h(sg) = 0

path s1 to sg h(s1) <=cost(s1,sg)

so every estimation is optimistic.

Missionaries and cannibals

Here is a search tree.

The game

Some variations

Last modified: Mon Sep 14 12:49:45 MEST 2009