COMP3411 Artificial Intelligence
Session 1, 2016

Week 2/3 Tutorial - Search Strategies

• In what order are the nodes in the state space expanded for each of the following algorithms when searching for a (shortest) path between Arad and Bucharest? Whenever there is a choice of nodes, you should select the one that comes first in alphabetical order. In each case, continue the algorithm until the goal node is expanded.
  1. Breadth First Search, skipping any state that has previously been expanded
  2. Uniform Cost Search, skipping any state that has previously been expanded
  3. Depth First Search, skipping any state that forms a loop (i.e. the same state occurring twice along a single path from root to leaf)
  4. Iterative Deepening (Depth First) Search
  5. Depth First Search again, skipping loops as before, but this time choosing nodes in reverse alphabetical order

• 3.9 The "Missionaries and Cannibals" problem is usually stated as follows: Three missionaries and three cannibals are on one side of the river, along with a boat that can hold one or two 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 place. This problem is famous in Artificial Intelligence because it was the subject of the first paper that approached problem formulation from an analytical viewpoint (Amarel, 1968). (You can even play the puzzle on-line at www.learn4good.com/games/puzzle/boat.htm)
  1. formulate the problem precisely, making only those distinctions necessary to ensure a valid solution, and draw a diagram of the complete state space.
  2. solve the problem optimally using an appropriate search algorithm; is it a good idea to check for repeated states?
  3. why do you think people have a hard time solving this puzzle, given that the state space is so simple?

• 3.13 (2nd Ed.)
  1. Describe a search space in which Iterative Deepening Search performs much worse than Depth-First Search.
  2. Describe a search space in which Breadth-First Search performs much worse than Depth-First Search.
  3. Describe a search space in which Depth-First Search performs much worse than Breadth-First Search.