In Java

1 Introduction Students can work in groups of 2-3 students. The assignment is composed of two consecutive parts. The first part is to development a program. Whereas in the second part an oral presentation will be prepared and presented. 2 Problem description: A group of K persons (K > 1) want to cross a bridge from East to West during the night. The persons that are crossing the bridge must use a flashlight. There is only one flashlight. The bridge is very narrow and allows two persons to cross it at the same time at most. Two persons go from east to west and one person returns with the flashlight from west to east. If the two persons are crossing the bridge together, they are crossing it at the speed of the slower one. These people are trying to cross the bridge as quickly as possible. Use 3 search strategies (UCS, IDS and A*) to find the best order for these persons to cross the bridge. Input file: 1) C, number of test cases 2) For each test case: a. K number of people b. A list of K numbers, showing the time required by each person to pass to the other side. Output: Your program should printout the following information for each search strategy: 1) Sequence of trips taken by the group along with direction of each trip for each strategy (solution) 2) Total time required to have all K people crossing using each strategy (solution cost). 3) Total number of generated nodes (Search time) for each strategy 4) Maximum number of nodes concurrently stored in the system (Space requirement) for each strategy. 3 What to submit A report containing problem description, problem formulation and experimental results (minimum of 5 samples). 4 Example: Input: 1 3 3.2.5 Description: There is one test case, C=1 There are three people, K=3. The first person (a) needs 3 (time units) to pass to from one side to the other The second person (b) needs 2 time units The third person (c) needs 5 time units Output: Test case #1: UCS Solution 1. (ab) move to the west side 2. (b) returns with the flashlight 3.(1.c) move to the west side Solution Cost 10 Search Cost 14 Space Requirement 9 1 Introduction Students can work in groups of 2-3 students. The assignment is composed of two consecutive parts. The first part is to development a program. Whereas in the second part an oral presentation will be prepared and presented. 2 Problem description: A group of K persons (K > 1) want to cross a bridge from East to West during the night. The persons that are crossing the bridge must use a flashlight. There is only one flashlight. The bridge is very narrow and allows two persons to cross it at the same time at most. Two persons go from east to west and one person returns with the flashlight from west to east. If the two persons are crossing the bridge together, they are crossing it at the speed of the slower one. These people are trying to cross the bridge as quickly as possible. Use 3 search strategies (UCS, IDS and A*) to find the best order for these persons to cross the bridge. Input file: 1) C, number of test cases 2) For each test case: a. K number of people b. A list of K numbers, showing the time required by each person to pass to the other side. Output: Your program should printout the following information for each search strategy: 1) Sequence of trips taken by the group along with direction of each trip for each strategy (solution) 2) Total time required to have all K people crossing using each strategy (solution cost). 3) Total number of generated nodes (Search time) for each strategy 4) Maximum number of nodes concurrently stored in the system (Space requirement) for each strategy. 3 What to submit A report containing problem description, problem formulation and experimental results (minimum of 5 samples). 4 Example: Input: 1 3 3.2.5 Description: There is one test case, C=1 There are three people, K=3. The first person (a) needs 3 (time units) to pass to from one side to the other The second person (b) needs 2 time units The third person (c) needs 5 time units Output: Test case #1: UCS Solution 1. (ab) move to the west side 2. (b) returns with the flashlight 3.(1.c) move to the west side Solution Cost 10 Search Cost 14 Space Requirement 9