HW #3
Provide answers to the following questions. Your answers should be thoughtful, clearly stated, and grammatically correct. Submit your answers through blackboard in .txt, .pdf, .odt, or .doc(x) format.
- THE FARMER PROBLEM*
Consider the following problem:A farmer with his wolf, goat and cabbage comes to the edge of a river he wishes to cross. There is a boat at the river's edge, but, of course, only the farmer can row. The boat also can carry only two things (including the rower) at a time. If the wolf is ever left alone with the goat, the wolf will eat the goat; similarly, if the goat is left alone with the cabbage, the goat will eat the cabbage. Devise a sequence of crossings of the river so that all four characters arrive on the other side with as few crossings as possible.
- Formulate this as a search problem of the type described in Chapter 3 of our textbook.
- How many states would this problem have if we didn't need to worry about characters eating each other?
- How many states does the problem have, given that we can't allow characters to eat each other?
- Draw a graph representation of this problem. Indicate the start and goal states in your graph. (Please submit something neat. You will probably want to use a diagramming program, or plan on creating a rough draft first.)
- Figure 3.7 presents two general search algorithms, TREE-SEARCH and GRAPH-SEARCH. Is one of these more appropriate for this problem than the other? Justify your answer.
- Find a solution to the problem by inspecting your graph. You can either list the actions, or mark the solution on your graph.
- THE FISHERMAN PROBLEM
This version of the problem is the same as the previous version, except that the farmer has been replaced by a fisherman. The fisherman catches a single fish every time he crosses the river. There is no limit to the number of fish that he can accumulate. The goal for this version of the problem is for the fisherman to get all characters safely across the river and accumulate at least 25 fish for his hungry family using as few crossings as possible.
- How many states would there be in a reasonable formulation of this problem?
- Which general approach is more appropriate for this version of the problem: TREE-SEARCH or GRAPH-SEARCH. Justify your answer.
-
Comment on the appropriateness of each of the following approaches
to this problem in terms of completeness, optimality, time complexity
and space complexity.
- Depth First Search
- Breadth First Search
- Iterative Deepening Search
- Uniform Cost Search
- Which of these is the best choice for this problem? Justify your answer.
- THE GREEDY FISHERMAN PROBLEM
This problem is the same as the fisherman problem, except that the goal is for the fisherman to get all characters safely across the river and accumulate at least 50 Fish.
- How would you characterize the difficulty of this problem relative to the difficulty of the 25-fish version?