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,T4T1,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  1761 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
