Solving Problems by Searching Notes | EduRev

: Solving Problems by Searching Notes | EduRev

 Page 1


1
Solving Problems by 
Searching
Page 2


1
Solving Problems by 
Searching
2
Terminology
• State
• State Space
• Initial State
• Goal Test
• Action
• Step Cost
• Path Cost 
• State Change Function
• State-Space Search
Page 3


1
Solving Problems by 
Searching
2
Terminology
• State
• State Space
• Initial State
• Goal Test
• Action
• Step Cost
• Path Cost 
• State Change Function
• State-Space Search
3
Formal State-Space Model
Problem = (S, s, A, f, g, c)
S = state space
s = initial state
A = set of actions
f = state change function    f: S x A -> S
g = goal test function          g: S -> {true,false}
c = cost function                 c: S x A x S -> R
x y
a
• How do we define a solution?
• How about an optimal solution?
Page 4


1
Solving Problems by 
Searching
2
Terminology
• State
• State Space
• Initial State
• Goal Test
• Action
• Step Cost
• Path Cost 
• State Change Function
• State-Space Search
3
Formal State-Space Model
Problem = (S, s, A, f, g, c)
S = state space
s = initial state
A = set of actions
f = state change function    f: S x A -> S
g = goal test function          g: S -> {true,false}
c = cost function                 c: S x A x S -> R
x y
a
• How do we define a solution?
• How about an optimal solution?
4
3 Coins Problem
A Very Small State Space Problem
• There are 3 (distinct) coins:  coin1, coin2, coin3. 
• The initial state is                      H       H        T
• The legal operations are to turn over exactly one coin.
– 1 (flip coin1), 2 (flip coin2), 3 (flip coin3)
• There are two goal states:         H       H        H
T        T        T
What are S, s, A, f, g, c ? 
Page 5


1
Solving Problems by 
Searching
2
Terminology
• State
• State Space
• Initial State
• Goal Test
• Action
• Step Cost
• Path Cost 
• State Change Function
• State-Space Search
3
Formal State-Space Model
Problem = (S, s, A, f, g, c)
S = state space
s = initial state
A = set of actions
f = state change function    f: S x A -> S
g = goal test function          g: S -> {true,false}
c = cost function                 c: S x A x S -> R
x y
a
• How do we define a solution?
• How about an optimal solution?
4
3 Coins Problem
A Very Small State Space Problem
• There are 3 (distinct) coins:  coin1, coin2, coin3. 
• The initial state is                      H       H        T
• The legal operations are to turn over exactly one coin.
– 1 (flip coin1), 2 (flip coin2), 3 (flip coin3)
• There are two goal states:         H       H        H
T        T        T
What are S, s, A, f, g, c ? 
5
State-Space Graph
HTT
TTT
THH
HHH
HHT THT
TTH
HTH
1
2
1
3
1
2
1
3
3
3
2
2
• What are some solutions?
• What if the problem is changed to allow only 3 actions?
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!