Counter Example for Greedy Algorithm
William Koch
Ranch Hand
Posts: 76
posted 3 years ago
There is only enough room for one person in the pool at a time but during this race unlimited people can bike and run at the same time. We want the race to be completed as early as possible. The order is Swim, Bike, Run. You have records that let you calculate approximate times for each person for each event.
My greedy strategy would to have the slowest swimmer go in the pool first, followed by the next fastest, and so on so the fastest swimmer would go last. You also know their run and bike times though, so I am having trouble coming up with a counter example that proves this strategy won't work. Can anyone provide me with one. Your example can have any number of racers involved in it.
My greedy strategy would to have the slowest swimmer go in the pool first, followed by the next fastest, and so on so the fastest swimmer would go last. You also know their run and bike times though, so I am having trouble coming up with a counter example that proves this strategy won't work. Can anyone provide me with one. Your example can have any number of racers involved in it.
posted 3 years ago
Me too, and mainly because you haven't described the problem very well. The fact is that you are looking for the best triathlon time with the same person doing all three sports (I assumed this was some sort of "team" problem). You also haven't said what exactly this business of the pool only being able to take "one person at a time" is, and how it affects the rules of the race. My first thought is that it simply makes swimming time irrelevant; but I could well be wrong.
Winston
William Koch wrote:I am having trouble coming up with a counter example that proves this strategy won't work.
Me too, and mainly because you haven't described the problem very well. The fact is that you are looking for the best triathlon time with the same person doing all three sports (I assumed this was some sort of "team" problem). You also haven't said what exactly this business of the pool only being able to take "one person at a time" is, and how it affects the rules of the race. My first thought is that it simply makes swimming time irrelevant; but I could well be wrong.
Winston
"Leadership is nature's way of removing morons from the productive flow"  Dogbert
Articles by Winston can be found here
Ivan Jozsef Balazs
Rancher
Posts: 992
5
William Koch
Ranch Hand
Posts: 76
posted 3 years ago
Ah. Total time. OK, now it makes sense....
Winston
Ivan Jozsef Balazs wrote:My conjecture is the problem is to organize the competition in the least total time with the only restriction: the swimming pool (or its timing machine) is restricted to be used by at most 1 swimmer at a time.
Ah. Total time. OK, now it makes sense....
Winston
"Leadership is nature's way of removing morons from the productive flow"  Dogbert
Articles by Winston can be found here
posted 3 years ago
Well, I think my first cut would be to rank them by the difference in the amount of time it takes them to swim from the time it takes them to complete the cycling and running, ie, rank them by x where x = (c + r)  s, and then have them enter the pool in descending order of x.
That ensures that the overall time will be close to sum(s) (which is a constant) + min(x). The only thing I'm not sure about (because I haven't really thought it through ) is whether the final competitors can be shuffled around if there is a gap between values of x which is greater than one of the swimmer's times. I'm pretty sure they should be  but exactly how you go about it I'm not sure.
HIH
Winston
William Koch wrote:correct but you also need to assume you know everyones estimated times for all three events. So how do you organize it so the entire event takes the least amount of time?
Well, I think my first cut would be to rank them by the difference in the amount of time it takes them to swim from the time it takes them to complete the cycling and running, ie, rank them by x where x = (c + r)  s, and then have them enter the pool in descending order of x.
That ensures that the overall time will be close to sum(s) (which is a constant) + min(x). The only thing I'm not sure about (because I haven't really thought it through ) is whether the final competitors can be shuffled around if there is a gap between values of x which is greater than one of the swimmer's times. I'm pretty sure they should be  but exactly how you go about it I'm not sure.
HIH
Winston
"Leadership is nature's way of removing morons from the productive flow"  Dogbert
Articles by Winston can be found here
Ivan Jozsef Balazs
Rancher
Posts: 992
5
posted 3 years ago
Let us presume the first competitor swims in 2 hours and bikes+runs in hour, whereas the second swims in 1 hour, and bikes+runs in 2 hours.
If the slower swimmer, that is, number 1 begins swimming, (s)he finises at time unit 2, goes on (b+r)ing until 3 hour.
Number 2, having waited for number 1 to finish swimming, starts at hour 2, swims until hour 3, and finishes at hour 5.
However if number 2 starts, (s)he finishes at 3 hour, number 1 waits until 1 hour, and starts then and finishes at 4.
The point is that in this case not the swimming time counts but the combined time for biking and running.
If the slower swimmer, that is, number 1 begins swimming, (s)he finises at time unit 2, goes on (b+r)ing until 3 hour.
Number 2, having waited for number 1 to finish swimming, starts at hour 2, swims until hour 3, and finishes at hour 5.
However if number 2 starts, (s)he finishes at 3 hour, number 1 waits until 1 hour, and starts then and finishes at 4.
The point is that in this case not the swimming time counts but the combined time for biking and running.
Gravity is a harsh mistress. But this tiny ad is pretty easy to deal with:
the new thread boost feature: great for the advertiser and smooth for the coderanch user
https://coderanch.com/t/674455/ThreadBoostfeature
