Crossing the Bridge
Four people want to get to the other side of a river by crossing a narrow bridge. A maximum of two people may cross at a time. It is nighttime, so someone must carry the single flashlight during each crossing. One of them takes 1 minute to cross the bridge, another takes 2 minutes, another takes 5 minutes, and the last takes 10 minutes to cross. Call them persons 1, 2, 5, and 10, respectively. If two people cross the bridge together, they must walk at the pace of the slower one. So, if persons 5 and 10 cross together, they take 10 minutes to get to the other side. (If person 5 crosses by himself, it takes 5 minutes.) How long does it take all four people to get to the other side? Of course, it depends on how they do it. From the initial state (1, 2, 5, and 10 on the same side with the flashlight) there are ten possible crossing actions: 1 crosses alone, 2 crosses alone, 5 crosses alone, 10 crosses alone, 1 and 2 cross, 1 and 5 cross, 1 and 10 cross, 2 and 5 cross, 2 and 10 cross, or 5 and 10 cross. (If two people cross, it doesn't matter which one holds the flashlight.)
Here is an example solution:
1 and 10 go across 10 minutes 1 goes back with light 1 minute 1 and 5 go across 5 minutes 1 goes back with light 1 minute 1 and 2 go across 2 minutes Total 19 minutesFor this problem, 19 minutes is a solution, but is not the fastest one. They could cross the bridge in 17 minutes total (you might want to verify this by hand). For breadth-first search, depth-first search, and depth-first-iterative-deepening search, we're going to assume that the goal is to complete the task in N minutes or less. Any solution that satisfies this is an acceptable goal solution.
For this problem, you must implement the solutions to the Crossing the Bridge problem using
Your functions should be able to handle people crossing the bridge with different costs, not just 1, 2, 5, and 10. For example, an instance of this problem with costs '(1, 3, 7, 12) and a total time of 21 could be given as the two arguments to your functions. (The 2nd argument means that 21 minutes or less is an acceptable solution.)
For each of the search routines, avoid returning to states that have already been visited on the current solution path i.e., there should be no repeated states in a solution.) Also, for BFS, DFS, and DFIDS, don't expand a node if its path cost is already over the chosen time limit. You will have to keep track of the total minutes taken.
Your programs will be called as such (the number of people might change):
(BFSCrossing '(1 2 5 10) 16) (the last argument is the goal time of N minutes)
(DFSCrossing '(1 4 6 10) 20)
(DFIDSCrossing '(2 3 5 7) 18)
The output of your programs should look like this (shown for formatting purposes, not an actual answer):
>(BFSCrossing '(1 2 5 10) 19) returns (19 (1 10) (1) (1 5) (1) (1 2))The interpretation is
The way to approach this problem is to consider the state space, operators, goal test and path costs:
State space: One way to think about this is that any of the four people could be at one side of the bridge, while the rest are at the other side. There are thus 2^4 = 16 distinct states. This is equal to the number of ways to choose people to be on one side of the bridge: (C(4,0) + C(4,1) + C(4,2) + C(4,3) + C(4,4) = 16).
Possible operators: The possible operators are all the ways to have one or two people go from one side of the bridge to the other. Taking any action will move the state from one to another of the above states.
Goal test: Has everyone crossed to the other side of the bridge?
Initial state: All people are on one side of the river.
Path cost: The cost of an operator is how long it takes for the slowest person traveling to cross the bridge.
The TA may run the program with several different numbers of people and crossing costs. Remember that some approaches may not find a solution (also, some problems don't have solutions.)
You will receive a 0 if it looks like you just did not spend much time on it. But generally, the grading breakdown is as follows:
What to Submit
Submit everything electronically. In all files include your name and SID.