Problem set 1

1. 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).
   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?
2. 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.
   
3. The following version of breadth first search is broken. Draw a state space for which it doesn't work properly. Run the algorithm enough to demonstrate 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 successors back to s
           add successors to open queue
       s ←  next state from open queue