if anyone has heard of the river crossing problem

four people cross a river, they have to cross two at a time and need a touch to cross, this means one person come back each time to give the torch to the next 2 people to cross. when two people cross they need to travel at the speed of the slowest person.

assume the times of the people are T1,T2,T3 & T4

for example if T1 & T2 Cross

Initial State

T1,T2,T3,T4 ||

new state

T3,T4||T1,T2

and this took the time of T2

is there a method to prove what the optimal state is except from brute force.

any help is appreciated

Dale

## 7 Replies - 1858 Views - Last Post: 30 November 2012 - 02:34 PM

### #1

# finding the optimal method to a algorithmic problem

Posted 30 November 2012 - 01:48 PM

##
**Replies To:** finding the optimal method to a algorithmic problem

### #2

## Re: finding the optimal method to a algorithmic problem

Posted 30 November 2012 - 02:07 PM

In this case a greedy approach should always (at least that I have been able to come up with) return the quickest time to get all 4 people across the river. Basically greedy algorithms do whatever is the best decision for them at the time (not worrying about the future, only the present). There are also dynamic programming algorithms (though those are generally slower they can find better/best solutions -- assuming they are given enough time and memory to complete).

I have an example that shows how this would work, but I feel (since this sounds like homework) you should try it yourself first.

Hopefully that makes sense.

I have an example that shows how this would work, but I feel (since this sounds like homework) you should try it yourself first.

Hopefully that makes sense.

### #3

## Re: finding the optimal method to a algorithmic problem

Posted 30 November 2012 - 02:09 PM

Moved to Computer Science.

You could show this through induction. If we have: T1 > T2 > T3 > T4, then what is the optimal choice? Look at the limiting factors here.

You could show this through induction. If we have: T1 > T2 > T3 > T4, then what is the optimal choice? Look at the limiting factors here.

### #4

## Re: finding the optimal method to a algorithmic problem

Posted 30 November 2012 - 02:11 PM

I agree induction would be the way to go.

### #5

## Re: finding the optimal method to a algorithmic problem

Posted 30 November 2012 - 02:14 PM

Oh, we are talking proofs... alright, then my post isn't as useful (like at all). However there is always the power of logic.

### #6

## Re: finding the optimal method to a algorithmic problem

Posted 30 November 2012 - 02:18 PM

it goes this way

T1 is < or equal to T2 is < or equal to T3 is < or equal to T4

and is there away to show this without induction as am dont think induction is what my lecture in looking for although i could be wrong

thanks

dale

T1 is < or equal to T2 is < or equal to T3 is < or equal to T4

and is there away to show this without induction as am dont think induction is what my lecture in looking for although i could be wrong

thanks

dale

### #7

## Re: finding the optimal method to a algorithmic problem

Posted 30 November 2012 - 02:25 PM

You could do proof by algorithm, and approach it as BetaWar showed. Or proof by contradiction. Suppose the known optimal solution (in terms of your variables) isn't optimal, then show this cannot be the case.

### #8

## Re: finding the optimal method to a algorithmic problem

Posted 30 November 2012 - 02:34 PM

The general principle is that you want to send two really slow people accross at the same time and have a faster person waiting to return the torch. That way, the sluggishness of one of the individuals does not completely slow the progress of the task. For example, find the optimal solution for these individuals

T1=1 second, T2 = 2 s, T3 = 49 s, T4 = 50 s

When you have that maneuver figured out, you can repeatedly apply it for bigger groups. Use some math to determine when you should do this and when it is better to just use the fastest member as an escort.

T1=1 second, T2 = 2 s, T3 = 49 s, T4 = 50 s

When you have that maneuver figured out, you can repeatedly apply it for bigger groups. Use some math to determine when you should do this and when it is better to just use the fastest member as an escort.

Page 1 of 1