Transcript PPT

Search Modeling
Practice Problems
M. Reza Zakerinasab
[email protected]
Please include [CPSC433] in the subject line of any emails regarding
this course.
Slides originally created by Andrew M Kuipers.
CPSC 433 Artificial Intelligence
What we need?
• Facts & States
• Search Modeling Paradigm
• Set based Search Modeling
– Extension Rules
• And-tree Search Modeling
– Erw((pr, ?), (pr, yes))
– Div function
• Or-tree Search Modeling
– Erw ((pr, ?), (pr, yes)) & Erw ((pr, ?), (pr, no))
– Altern function
CPSC 433 Artificial Intelligence
8 Puzzle
3
1
7
6
2
4
8
5
1
2
3
4
5
6
7
8
• Classic “Sliding Boxes” puzzle
– Re-arrange numbered tiles so that numbers
are sequentially ordered (left-to-right) in box
– Can only move tiles into the empty space
from horizontally or vertically adjacent
spaces
CPSC 433 Artificial Intelligence
Water Jugs
• Goal: get exactly 2L into
the 4L jug
3L
4L
• Allowable Actions:
– Fill either jug completely
– Empty either jug onto the
ground
– Empty one jug into the
other
– Top off one jug from the
other
CPSC 433 Artificial Intelligence
Missionaries and Cannibals
• There are N (where N  1) missionaries and N cannibals
on the left bank of a river
• They have a rowboat with them, which can carry a
maximum of two people, and needs at least one person
to row across the river
• If there are one or more missionaries on a river bank,
there cannot be more cannibals than missionaries on
that bank
• How can all missionaries and cannibals be transported
across the river?
CPSC 433 Artificial Intelligence