Page 1 1 Chapters 3-5 Problem Solving using Search Chapters 3-5 Problem Solving using Search CSEP 573 © CSE AI Faculty “First, they do an on-line search” 2 Example: The 8-puzzle Example: The 8-puzzle 1 2 3 6 7 5 8 4 1 2 3 8 7 5 4 6 Page 2 1 Chapters 3-5 Problem Solving using Search Chapters 3-5 Problem Solving using Search CSEP 573 © CSE AI Faculty “First, they do an on-line search” 2 Example: The 8-puzzle Example: The 8-puzzle 1 2 3 6 7 5 8 4 1 2 3 8 7 5 4 6 2 3 Example: Route Planning Example: Route Planning start end 4 Example: N Queens Example: N Queens 4 Queens Page 3 1 Chapters 3-5 Problem Solving using Search Chapters 3-5 Problem Solving using Search CSEP 573 © CSE AI Faculty “First, they do an on-line search” 2 Example: The 8-puzzle Example: The 8-puzzle 1 2 3 6 7 5 8 4 1 2 3 8 7 5 4 6 2 3 Example: Route Planning Example: Route Planning start end 4 Example: N Queens Example: N Queens 4 Queens 3 5 Example: N Queens Example: N Queens 4 Queens 6 State-Space Search Problems State-Space Search Problems General problem: Given a start state, find a path to a goal state • Can test if a state is a goal • Given a state, can generate its successor states Variants: • Find any path vs. a least-cost path • Goal is completely specified, task is just to find the path – Route planning • Path doesn’t matter, only finding the goal state – 8 puzzle, N queens Page 4 1 Chapters 3-5 Problem Solving using Search Chapters 3-5 Problem Solving using Search CSEP 573 © CSE AI Faculty “First, they do an on-line search” 2 Example: The 8-puzzle Example: The 8-puzzle 1 2 3 6 7 5 8 4 1 2 3 8 7 5 4 6 2 3 Example: Route Planning Example: Route Planning start end 4 Example: N Queens Example: N Queens 4 Queens 3 5 Example: N Queens Example: N Queens 4 Queens 6 State-Space Search Problems State-Space Search Problems General problem: Given a start state, find a path to a goal state • Can test if a state is a goal • Given a state, can generate its successor states Variants: • Find any path vs. a least-cost path • Goal is completely specified, task is just to find the path – Route planning • Path doesn’t matter, only finding the goal state – 8 puzzle, N queens 4 7 Tree Representation of 8-Puzzle Problem Space Tree Representation of 8-Puzzle Problem Space 8 fringe (= frontier in the textbook) is the set of all leaf nodes available for expansion Page 5 1 Chapters 3-5 Problem Solving using Search Chapters 3-5 Problem Solving using Search CSEP 573 © CSE AI Faculty “First, they do an on-line search” 2 Example: The 8-puzzle Example: The 8-puzzle 1 2 3 6 7 5 8 4 1 2 3 8 7 5 4 6 2 3 Example: Route Planning Example: Route Planning start end 4 Example: N Queens Example: N Queens 4 Queens 3 5 Example: N Queens Example: N Queens 4 Queens 6 State-Space Search Problems State-Space Search Problems General problem: Given a start state, find a path to a goal state • Can test if a state is a goal • Given a state, can generate its successor states Variants: • Find any path vs. a least-cost path • Goal is completely specified, task is just to find the path – Route planning • Path doesn’t matter, only finding the goal state – 8 puzzle, N queens 4 7 Tree Representation of 8-Puzzle Problem Space Tree Representation of 8-Puzzle Problem Space 8 fringe (= frontier in the textbook) is the set of all leaf nodes available for expansion 5 9 10 action = Right childrenRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!