CSCI 4511W Midterm: CS 4511 UMN Midterm 1 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 missionaries and cannibals problem. 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. Explain why your heuristics is admissible: 15 points. Be precise and explain what you will use for g(n) and for h(n): 15 points. Answer these questions brie y but precisely: would using a pattern database be a reasonable heuristics for solving. Explain why (or why not: how would simulated annealing work if the temperature t is always. Xed at 0: explain brie y how a ridge in the search space may appear to be a local maximum to a hill-climbing algorithm. Turn to the next page for more questions: 10 points.
