Chapters 3-5 - Problem Solving using Search Notes | EduRev

Created by: Himanshu Sahney

: Chapters 3-5 - Problem Solving using Search Notes | EduRev

 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
children
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!