Uninformed Search

Informed Search with Heuristics

Tree vs Graph Search

Admissible vs Consistent

Example: 8 Puzzle Search Problem

States:

• Start is in a circle with empty space in center
• goal state is numbers in order

How many: 9!

• (9 boxes and each one can be fit in 9 ways)

Actions

• NSEW

How many successors from the start state:

• 4 because thats the farthest number of tile spaces we can move away from a start tile

Costs / What is an admissible heuristic?:

• How far is each tile state from the goal state?
• Number of tiles misplaced → h(start) = 8