This homework is a continuation of the work you’ve done in HOMEWORK #1. It consists of two parts:
I. (8 points)6 missionaries and 6 cannibals should cross a river. The capacity of the boat is 5. You must list the shortestsequence of crossings which does the job.
II. (2 points)4 missionaries and 4 cannibals should cross a river. The capacity of the boat is 3. This time, you must calculate the numberof shortest sequence of crossings (viz. the number of shallowest goals).
(As was the case with HW #1, there is a paper relevant to this assignment and it may be very useful to take a look at it: https://dl.acm.org/citation.cfm?id=144106)
HINT: Earlier you’ve most probably used xMyCbas a state representation, where x is the number of missionaries
(M) on the west bank, y is the number of cannibals (C) on the west bank, and b is 1 if the boat is on the west bank (and 0, if it is on the east bank). This representation is still good but notice that now the welfare of the passengers in the boat is also crucial. (This you didn’t have to worry about when the capacity of the boat was 2.)
Your program must use the A* searchstrategy to solve part (I).(Just implement, in a straightforward manner, the pseudocode given in Winston, Chapter 5.) It is your responsibility to design an admissible heuristic h(n), where n is a node in the state space. In the beginning of your program, you should have a block comment where you explain clearly which h(n) you are using and why you think it is admissible.
You must check for repeatedstates. It is entirely up to you to add a dynamic programming component to your program. (In other words, you won’t lose points if you don’t have such a component.)
What should be the output of your program?
A sequence of crossings will do the job for part (I).For instance, in the classical version of the problem (start state = 3M3C1 and boat capacity = 2) the program might produce a sequence which begins:
. . .
For part (II), a number is required and you can use any search strategy.(But do not forget to clearly state---again in a block comment---what strategy it is.)
Your program should have a simple control for ‘single stepping’ (tracing your code) so that you and the TAs can inspect the intermediate stages of the problem-solving process in an incremental fashion. Needless to say, this is also useful for debugging your program during the development stage.
GENERAL REMARKS (THESE ARE APPLICABLE TO ALL HOMEWORK ASSIGNMENTS)
• IF YOU ARE REQUESTED TO SUBMIT A HARDCOPY AT ANY TIME IN THIS COURSE, MAKE SURE THAT WHAT YOU SUBMIT IS CLEAN AND FULLY MACHINE-GENERATED. IF THERE IS A HANDWRITTEN ADDITION OR CORRECTION ON A PRINTOUT, YOU’LL DEFINITELY LOSE POINTS.
• Late submissions will first have 2 points deducted categorically. Then they’ll have 2 points deducted for every late day. (A new day begins at 12:01 midnight.)
