CS2109S: We discussed the Missionaries and Cannibals problem, which is a classic river-crossing logic puzzle: Introduction to AI and Machine Learning Assignment, NUS, Singapore

Missionaries and Cannibals

We discussed the Missionaries and Cannibals problem, which is a classic river-crossing logic puzzle. It is not difficult to solve this problem by hand when we have 3 Missionaries and 3 Cannibals. However, the solution becomes less obvious when we generalize the problem to m Missionaries and c Cannibals where m and c are some positive integers. To solve this problem, we will implement both BreadthFirst Search and Depth-First Search. In the process, we hope that you will conceptually learn the differences in performance between these two search strategies.

The Missionaries and Cannibals problem is usually stated as follows: 3 missionaries and 3 cannibals are on one side of a river, along with a boat that can hold 1 or 2 people. Find a way to get everyone to the other side, without ever leaving a group of missionaries in one place outnumbered by the cannibals in that same place. You can try it online to test your understanding of the problem. The following is an example of how to help 2 Missionaries and 2 Cannibals cross the river.

Breadth-First Search and Depth-First Search

For this problem, all actions have the same cost (number of steps). BFS is an appropriate strategy to search all possible states. It first expands the root node, and then all the successors of the root node, and their successors. However, a BFS-based tree search algorithm will encounter a large number of repeated states in the tree and waste a lot of time in searching redundant nodes. On the other hand, the BFS-based graph search algorithm will check for redundant paths to avoid visiting states more than once. To see the connection between tree search and graph search, you are tasked to implement both BFS tree search and BFS graph search.

DFS is another commonly seen algorithm in solving AI problems. It always expands the deepest node in the frontier first. DFS proceeds directly to the deepest level of the search tree. The search then “backs up” to the previous node that has unexpanded successors. Your task is to implement both DFS tree search and DFS graph search. You will observe that a DFS-based tree search is susceptible to getting stuck in a looped path. In the context of this problem, it could mean keeping 2 Missionaries on the boat, rowing back and forth until exhaustion.