Breakth-frist
Cheapest-first
Depth-first
Greedy best-first search
A* algorithm
f = g + h
g(path) = path cost
h(path) = h(s) = estimated distance to goal
A* finds lowest cost path is:
h(s) < true cost
Sliding blocks puzzle (15puzzle)
h1 = #misplaced blocks
h2 = sum(distances of blocks)
a block can move A -> B
if (A adjacent to B)
and (B is blank)
h2 h1
h = max(h1, h2)
Problem-solving works when:
-fully observable
-known
-discrete
-deterministic
-static
