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

#1 DkSnowdon  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 125
  • Joined: 31-October 12

finding the optimal method to a algorithmic problem

Posted 30 November 2012 - 01:48 PM

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

Is This A Good Question/Topic? 0
  • +

Replies To: finding the optimal method to a algorithmic problem

#2 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1138
  • View blog
  • Posts: 7,108
  • Joined: 07-September 06

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.
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10387
  • View blog
  • Posts: 38,440
  • Joined: 27-December 08

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.
Was This Post Helpful? 2
  • +
  • -

#4 ipushmycar  Icon User is offline

  • D.I.C Regular

Reputation: 86
  • View blog
  • Posts: 390
  • Joined: 29-August 10

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.
Was This Post Helpful? 0
  • +
  • -

#5 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1138
  • View blog
  • Posts: 7,108
  • Joined: 07-September 06

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.
Was This Post Helpful? 0
  • +
  • -

#6 DkSnowdon  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 125
  • Joined: 31-October 12

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
Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10387
  • View blog
  • Posts: 38,440
  • Joined: 27-December 08

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.
Was This Post Helpful? 0
  • +
  • -

#8 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 770
  • Joined: 27-June 09

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.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1