# finding the optimal method to a algorithmic problem

Page 1 of 1

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

### #1 dsnowdon

• D.I.C Head

Reputation: 0
• Posts: 219
• Joined: 18-January 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

• #include "soul.h"

Reputation: 1285
• Posts: 7,566
• 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

• Games, Graphs, and Auctions

Reputation: 11227
• Posts: 42,258
• 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

• D.I.C Regular

Reputation: 86
• 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

• #include "soul.h"

Reputation: 1285
• Posts: 7,566
• 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 dsnowdon

• D.I.C Head

Reputation: 0
• Posts: 219
• Joined: 18-January 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

• Games, Graphs, and Auctions

Reputation: 11227
• Posts: 42,258
• 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

• D.I.C Addict

Reputation: 376
• Posts: 815
• 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

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }