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!