Scribd
Upload
163 views4 pages

Missionaries & Cannibals BFS & DFS

The document describes the Missionaries and Cannibals problem and provides instructions to solve it using breadth-first search (BFS) and depth-first search (DFS). The problem involves getting 3 missionaries and 3 cannibals across a river using a boat that holds at most 2 people, without cannibals ever outnumbering missionaries. States are represented as triples (m c b) and the legal operators to move between states are defined. The tasks are to: 1) Draw a state transition diagram. 2) Implement BFS and DFS to find the solution, showing the open/closed lists at each iteration.

Uploaded by

tay keith
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
163 views4 pages

Missionaries & Cannibals BFS & DFS

The document describes the Missionaries and Cannibals problem and provides instructions to solve it using breadth-first search (BFS) and depth-first search (DFS). The problem involves getting 3 missionaries and 3 cannibals across a river using a boat that holds at most 2 people, without cannibals ever outnumbering missionaries. States are represented as triples (m c b) and the legal operators to move between states are defined. The tasks are to: 1) Draw a state transition diagram. 2) Implement BFS and DFS to find the solution, showing the open/closed lists at each iteration.

Uploaded by

tay keith
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

CS 3600 – Introduction to Intelligent Systems

1. Missionaries and Cannibals.

Missionaries and Cannibals is a problem in which 3 missionaries and 3 cannibals want to


cross from the left bank of a river to the right bank of the river. There is a boat on the left
bank, but it only carries at most two people at a time (and can never cross with zero
people). If cannibals ever outnumber missionaries on either bank, the cannibals will eat
the missionaries.

A state can be represented by a triple, (m c b), where m is the number of missionaries on


the left, c is the number of cannibals on the left, and b indicates whether the boat is on the
left bank or right bank. For example, the initial state is (3 3 L) and the goal state is
(0 0 R).

Operators are:
• MM: 2 missionaries cross the river
• CC: 2 cannibals cross the river
• MC: 1 missionary and 1 cannibal cross the river
• M: 1 missionary crosses the river
• C: 1 cannibal crosses the river

Draw a diagram showing all the legal states and transitions from states corresponding to
all legal operations. See Figure 3.3 in Russell & Norvig (p. 65) for an example of what
your diagram should look like.
2. Answer the following question.

Hint: think about branching factor of states near the initial state and goal state, as
compared to the branching factor of states in the “middle” of the state space.

3. Breadth-first search

Solve the Missionaries and Cannibals problem by implementing the BFS algorithm given
in class. Implement the BFS algorithm to show the open list and closed list at every
iteration of the algorithm until the goal is visited. Use the format below. I have given the
first two iterations.

open: 33L
closed: nil

open: 31R, 22R, 32R


closed: 33L

open: 22R, 32R, 32L


closed: 31R, 33L
open: 32R, 32L, 32L
closed: 22R, 31R, 33L

open: 32L, 32L


closed: 32R, 22R, 31R, 33L

open: 32L, 30R


closed: 32L, 32R, 22R, 31R, 33L

open: 30R
closed: 32L, 32R, 22R, 31R, 33L

open: 31L
closed: 30R, 32L, 32R, 22R, 31R, 33L

open: 11R
closed: 31L, 30R, 32L, 32R, 22R, 31R, 33L

open: 22L
closed: 11R, 31L, 30R, 32L, 32R, 22R, 31R, 33L

open: 02R
closed: 22L, 30R, 11R, 31L, 30R, 32L, 32R, 22R, 31R, 33L

open: 03L
closed: 02R, 22L, 30R, 11R, 31L, 30R, 32L, 32R, 22R, 31R, 33L

open: 03L
closed: 11R, 02R, 22L, 30R, 11R, 31L, 30R, 32L, 32R, 22R, 31R, 33L

open: 01R
closed: 03L, 11R, 02R, 22L, 30R, 11R, 31L, 30R, 32L, 32R, 22R, 31R, 33L

open: 11L, 02L


closed: 01R, 03L, 11R, 02R, 22L, 30R, 11R, 31L, 30R, 32L, 32R, 22R, 31R, 33L

open: 02L, 00R, 01R


closed: 11L, 01R, 03L, 11R, 02R, 22L, 30R, 11R, 31L, 30R, 32L, 32R, 22R, 31R, 33L

open: 00R, 01R, 00R,


closed: 02L, 11L, 01R, 03L, 11R, 02R, 22L, 30R, 11R, 31L, 30R, 32L, 32R, 22R, 31R,
33L

Solution: CC, C, CC, C, MM, MC, MM, C, CC, M, MC


3. Depth-first search

Same as problem 2, but use the DFS algorithm given in class.

open: 33L
closed: nil

open: 31R, 22R, 32R


closed: 33L

open: 32L, 22R, 32R


closed: 31R, 33L

open: 30R, 22R, 32R


closed: 32L, 31R, 33L

open: 31L, 22R, 32R


closed: 30R, 32L, 31R, 33L

open: 11R, 30R, 22R, 32R


closed: 31L, 30R, 32L, 31R, 33L

open: 22L, 30R, 22R, 32R


closed: 11R, 31L, 30R, 32L, 31R, 33L

open: 02R, 30R, 22R, 32R


closed: 22L, 11R, 31L, 30R, 32L, 31R, 33L

open: 03L, 30R, 22R, 32R


closed: 02R, 22L, 11R, 31L, 30R, 32L, 31R, 33L

open: 01R, 30R, 22R, 32R


closed: 03L, 02R, 22L, 11R, 31L, 30R, 32L, 31R, 33L

open: 11L, 02L, 30R, 22R, 32R


closed: 01R, 03L, 02R, 22L, 11R, 31L, 30R, 32L, 31R, 33L

open: 00R, 01R, 02L, 30R, 22R, 32R


closed: 11L, 01R, 03L, 02R, 22L, 11R, 31L, 30R, 32L, 31R, 33L

Solution: CC, C, CC, C, MM, MC, MM, C, CC, M, MC

You might also like