Two – One Problem

Start Goal
11?22 22?11

Legal Moves:
Rules: • Slide
• 1s’ move right
• 2s’ move left
• Only one move at a time • Hop
• No backing up
Two – One Problem
Trials to solve the problem

Trial One Trial Two

11?22 11?22

112?2 1?122

1?212 ?1122

12?12 Stuck!!!

1221?

122?1

Stuck!!!
Two – One Problem
Five States
 Two – One Problem
Solution Space
H H
?1122 1 1? 2 2 1122 ?
S S

1?1 22 1 1 2? 2
S H H S

?1122 1 2 1?2 1?212 1122 ?

S S S S

1212 ? 12 ?12 ?1212

H
H H H

1 2? 2 1 ?2112 1 2 2 1? 21?12
S H S S H S

1 2 2? 1 ?2121 2 ?11 2 1 2 2 ?1 2112 ? 2?112

S
S

2?121 212 ?1
H H

2 2 1? 1 2?211
S S

2 2? 1 1
 Solution to Problem Solving : Searching
H H
? 1122 11 ? 22 1122 ?
S S
1 ? 122 112 ? 2

S H H S
?1122 121 ? 2 1 ? 212 1122 ?

S S S S
1212 ? 12 ? 12 ? 1212
H H H H
12 ? 21 ? 2112 1221 ? 21 ? 12

S H S S H S
122 ? 1 ? 2121 2 ? 112 122 ? 1 2112 ? 2 ? 112

S S
2 ? 121 212 ? 1

Farmer
H H
Grain Goose 221 ? 1 2 ? 211
Grain

S S Airport
Farmer
Fox Fox 22 ? 11
Goose

Q1 Q2
Farmer
Farmer
Fox Fox Farmer
Fox Goose
Goose Grain Goose
Grain
Grain

Farmer
Farmer
Farmer Fox Fox
Goose Fox
Goose Grain Goose
Grain
Grain
Q4
Q3
Q5

Farmer
Fox Fox
Goose

Hotel
Farmer
Goose Grain
Grain
 Tree and Graph
Terminology
A

B C

D E F G H

•“A” is the “root node”

•“A, B, C …. J” are “nodes” I J
•“B” is a “child” of “A”
•“A” is ancestor of “D”
•“D” is a descendant of “A”
•“D, E, F, G, I, J” are “leaf nodes”
•Arrows represent “edges” or “links”
Examples of Graphs
 Problem Formulation
using Graphs
• The search methods we’ll be dealing with are
defined on trees and graphs

3 3
A B C
2

4
S G
4

3 2
D E F
1 3
 Tree Search
• Graph search is really tree search

3 3
A B C A D
2

B D A E
4

G
S
C E E B B F

3 2 D F B F C E A C G
D E F
1 3
G C G F