Solving the Missionaries and Cannibals River Crossing Problem
Consider the classic problem of three missionaries and three cannibals needing to cross a river using a canoe that can hold up to two people. The challenge is to transport everyone safely without leaving more cannibals than missionaries on either side of the river. Learn about search problem formulation, initial and goal states, and the successor function for this intriguing problem representation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Consider this problem Three missionaries and three cannibals Want to cross a river using one canoe. Canoe can hold up to two people. Can never be more cannibals than missionaries on either side of the river. Aim: To get all safely across the river without any missionaries being eaten.
Why am I teaching you search? Gives us a chance to: design a non-trivial problem talk about (use) the first two ADTs build one or two domain specific data types (classes) really apply the complexity operations we introduced with searching/sorting
Search Problem Formulation A problem is defined by four items: 1. initial state 2. successor function (which actually defines all reachable states) 3. goal test 4. path cost (additive) e.g., sum of distances, # of actions executed, etc. C(x,a,y) is the step cost, assumed to be 0
Consider this problem Three missionaries and three cannibals Want to cross a river using one canoe. Canoe can hold up to two people. Can never be more cannibals than missionaries on either side of the river. States?? Actions?? Goal test?? Path cost??
Problem Representation : Cannibals and Missionaries Initial State We can show number of cannibals, missionaries and canoes on each side of the river. Start state is therefore: [3,3,1,0,0,0]
Problem Representation : Cannibals and Missionaries Initial State However, since the system is closed, we only need to represent one side of the river, as we can deduce the other side. We will represent the starting side of the river, and omit the ending side. So start state is: [3,3,1]
Problem Representation : Cannibals and Missionaries Goal State(s) [0,0,0] TECHNICALLY also [0,0,1]
Problem Representation : Cannibals and Missionaries Successor Function (3 actions) 1. Move one missionary. 2. Move one cannibal. 3. Move one missionary and one cannibal.
Problem Representation : Cannibals and Missionaries Successor Function To be a little more mathematical/computer like, we want to represent this in a true successor function format S(state) state 1. Move one cannibal across the river. S([x,y,1]) [x-1,y,0] S([x,y,0]) [x+1,y,1] [Note, this is a slight simplification. We also require, 0 x, y, [x+1 or x-1] 3]
Problem Representation : Cannibals and Missionaries Successor Function S([x,y,0]) [x+1,y,1] //1 missionary S([x,y,1]) [x-1,y,0] S([x,y,0]) [x,y+1,1] //1 cannibal S([x,y,1]) [x,y-1,0] S([x,y,0]) [x+1,y+1,1] // 1 of each S([x,y,1]) [x-1,y-1,0]
Problem Representation : Cannibals and Missionaries Path Cost One unit per trip across the river.
Solution What is the Solution? How did you arrive at that solution?
Travelling in Romania Suppose you travelling in Romania Currently you are in Arad Your flight leaves Bucharest tomorrow morning so you need to get to the airport
You Try It https://replit.com/@CSED5320-F22/Arad-To- Bucharest#main.py Once the page loads press the run button towards the top of the page. Be patient. It takes 3-4 seconds to fully load. Record your process on scratch paper
Solution What Solution(s) did you find? How did you arrive at that solution(s)?
Implementation: General Tree Search
Implementation: General Tree Search
Uninformed Search Strategies Uninformed strategies use only information available in the problem definition Breadth-first search Uniform-cost search Depth-first search Depth-limited search Iterative deepening search
Uninformed Search Strategies Uninformed strategies use only information available in the problem definition Breadth-first search Uniform-cost search Depth-first search Depth-limited search Iterative deepening search
Breadth-First Search Expanding shallowest unexpanded node Implementation fringe is a FIFO queue, i.e., new successors go at end
Breadth-First Search Expanding shallowest unexpanded node Implementation fringe is a FIFO queue, i.e., new successors go at end
Breadth-First Search Expanding shallowest unexpanded node Implementation fringe is a FIFO queue, i.e., new successors go at end
Breadth-First Search Expanding shallowest unexpanded node Implementation fringe is a FIFO queue, i.e., new successors go at end
Depth-First Search Expand deepest unexpanded node Implementation: fringe = LIFO queue, I.e., put successors at front
Depth-First Search Expand deepest unexpanded node Implementation: fringe = LIFO queue, I.e., put successors at front
Depth-First Search Expand deepest unexpanded node Implementation: fringe = LIFO queue, I.e., put successors at front
Depth-First Search Expand deepest unexpanded node Implementation: fringe = LIFO queue, I.e., put successors at front
Depth-First Search Expand deepest unexpanded node Implementation: fringe = LIFO queue, I.e., put successors at front
Depth-First Search Expand deepest unexpanded node Implementation: fringe = LIFO queue, I.e., put successors at front
Depth-First Search Expand deepest unexpanded node Implementation: fringe = LIFO queue, I.e., put successors at front
Depth-First Search Expand deepest unexpanded node Implementation: fringe = LIFO queue, I.e., put successors at front
Depth-First Search Expand deepest unexpanded node Implementation: fringe = LIFO queue, I.e., put successors at front
Depth-First Search Expand deepest unexpanded node Implementation: fringe = LIFO queue, I.e., put successors at front
Depth-First Search Expand deepest unexpanded node Implementation: fringe = LIFO queue, I.e., put successors at front
Depth-First Search Expand deepest unexpanded node Implementation: fringe = LIFO queue, I.e., put successors at front
Search Strategies A strategy is defined by picking the order of node expansion Strategies are evaluated along the following dimensions: completeness does it always find a solution if one exists? time complexity number of nodes generated/expanded space complexity maximum number of nodes in memory optimality does it always find a least-cost solution
Search Strategies Time and space complexity are measured in terms of b maximum branching factor of the search tree d depth of the least-cost solution m maximum depth of the state space (may be infinite)
Properties of Breadth-First Search Complete??
Properties of Breadth-First Search Complete?? Yes (if b is finite) Time??
Properties of Breadth-First Search Complete?? Yes (if b is finite) Time?? 1 + b + b2 + b3+ + bd + b(bd 1) = O( bd+1 ), ie, exp. in d Space??
Properties of Breadth-First Search Complete?? Yes (if b is finite) Time?? 1 + b + b2 + b3+ + bd + b(bd 1) = O( bd+1 ), ie, exp. in d Space?? O( bd+1 ) (keep every node in memory) Optimal??
Properties of Breadth-First Search Complete?? Yes (if b is finite) Time?? 1 + b + b2 + b3+ + bd + b(bd 1) = O( bd+1 ), ie, exp. in d Space?? O( bd+1 ) (keep every node in memory) Optimal?? Yes (if cost = 1 per step); not optimal in general Space is the big problem: can easily generate nodes at 10MB/sec, so 24hours = 860GB.
Properties of Depth-first Search Complete??
Properties of Depth-first Search Complete?? No: fails in infinite-depth spaces, spaces with loops Modify to avoid repeated states along path complete in finite spaces Time??
Properties of Depth-first Search Complete?? No: fails in infinite-depth spaces, spaces with loops Modify to avoid repeated states along path complete in finite spaces Time?? O(bm): terrible if m is much larger than d but if solutions are dense, may be much faster than breadth-first Space??
Properties of Depth-first Search Complete?? No: fails in infinite-depth spaces, spaces with loops Modify to avoid repeated states along path complete in finite spaces Time?? O(bm): terrible if m is much larger than d but if solutions are dense, may be much faster than breadth-first Space?? O(bm), i.e., linear space! Optimal??
