CSCI 4511W Midterm: CS 4511 UMN Midterm 1key 04
Document Summary
75 minutes == 75 points open book and notes: 15 points. Propose an admissible (and not trivial, i. e. h(n) = 0 is not a valid answer) heuristic for the. Assume there is one boat which can carry a maximum of 2 people, and that in the initial state the same number of missionaries and cannibals are on one side of the river. To come up with a heuristic we can try to solve a relaxed problem. If we do not take into account the possibility of cannibals eating missionaries, we can compute how many trips are needed to take everyone across. The boat takes two people, but after each trip across the boat has to come back to the starting side and so at least one person must paddle back. This will give us the following heuristic; h1(n) = (n umberof p eopleoninitialside) 1.
