PSet 1: basic search - SI420 Artificial Intelligence

(videos up to and including BFS)

In the missionaries and cannibals problem, there is a group of three missionaries and three cannibals who want to cross a river. Their boat only holds two people, and they can’t ever let the cannibals outnumber the missionaries in one place (presumably because the cannibals will eat the outnumbered missionaries). The boat cannot cross on its own without at least one passenger. The goal is for all of them to reach the other side.
1. List the operators for this problem.
2. Draw a diagram of the state space to a depth of four.
3. Given that the state space is so small, why is this problem hard for people?
4. Give the full sequence of states that reaches the goal state.
In the graph below, run breadth first search with J as the start state and B as the goal. Show the search tree, and show the evolution of the State variable, the open and the closed containers.
The following version of breadth first search is broken. Draw a state space (use same format of open/closed container evoluation in the prior question), but one for which it doesn’t work properly. Run the algorithm enough to demonstrate the problem. Then write one sentence clearly describing the problem. Hint: it isn’t a correctness issue, but an efficiency issue.
```
BreadthFirstSearch(StartState s)
  while (isNotGoal(s))
    add s to closed
    generate successors to s
    For each successor not in closed
        point successor back to s
        add successor to open queue
    s ←  next state from open queue
```