Amy, Jim, John, and Kelly are standing on the east bank of a river and wish to cross to the west side using a canoe. The canoe can hold at most two people at a time. Amy, being the most athletic, can row across the river in 1 minute. Jim, John, and Kelly would take 3, 6, and 9 minutes, respectively. If two people are in the canoe, the slower person dictates the crossing time. The objective is for all four people to be on the other side of the river in the shortest time possible. STUDENTS MUST ANSWER ALL 5 PARTS (a,b,c.d.e) OF THIS ASSIGNMENT (o) Define the criterion for evaluating the alternatives sequences of moves (remember, the canoe is the only mode of transportation, and it cannot be shuttled empty). (b) What is the shortest time for moving all four people to the other side of the river? SOLUTION GUIDELINE AND DETAILED DESCRIPTION The problem is a puzzle type. First step must be selecting suitable variables to symbolize and represent each object of the problem to represent the initial state of the puzzle. One can use A: for Amy. Mi for Jim, N:for John, K: for Kelly. C for Canoe, & Vertical Bar | for the river. All these six items can be put in a 6-tuple contained in a pair of square brackets, like [AMNKC] to show that all four persons and the canoe are on the West/left side of the river. The symbols will keep on moving from left to right as people move across the river; and finally must halt at the state [AMNKC] to show that everybody is on the East bank or right side of the river. Actually person/s move to and fro across the river. You must enumerate all the possible moves that can be applied in the puzzle solution with suitable symbols to best describe the actions and effects of the move on the current state to generate the next state as puzzle space leads to the solution. In fact puzzle space is a graph of node to represent puzzle states and arcs or edges to represent moves. Since states should be such generated therefore, same state from the root or start state should not be repeated, i.e., loops must be avoided. Effectively, all moves can be list as given in the following: =>AM3,=>AN6,=>AK9,=>MN6,=>NK9 to show the respective pairs going from West/left to East/right taking the number of minutes as shown on the right end of the move symbol. 3AMA1,=>M3,=>N6, =>K9 for moving canoe back to East bank. The graph is going to be a big tree each node having 6,4,3, or 2 sub-branches shown by arrows emitting downwards from current state to next state. AMNKCII NKS AM3 ANG >>AKS >MINH =>MKS FARMNC INKAMCI IMRANCI [MNI AKCI ANMKC] IAMINKCI M3 KS N6c KS CAMICKO LAMKCINI LAMINCINO ANKCIMI The graph/tree shown is only partially populated just for the sake of students' help. ANG AKC ONKS KIAMNC (AIMNKCINIAMKC (c)They have to build a complete tree with some Graphics tool. Each path from root downwards the terminal node/state would at least contain five arrows each with suitable move symbols. =MNG =>MIKS =>NKY KAMNC MANKC) IN AMKC (d) Students must label the terminal node with suitably calculated time to be spent from the start state to each terminal state node by adding up all the time numbers on the moves/arrows. 45 Minutes: (AMNKCI] =>MK9 TAN|MKC) K9CE (ANKC|M] =>NK9 ANMKC K9AKO ||ANMKC] (e) Students must also list all the possible sequences of moves with respective times involved and in the end give all possible move sequences which correspond to minimum (optimal) time. HINT: one such sequence of move could be
