Author Topic: 汽车能跑多远?  (Read 34003 times)

fzy

  • Hero Member
  • *****
  • Posts: 520
汽车能跑多远?
« Reply #15 on: 十一月 14, 2004, 11:53:16 am »
Quote from: 万精油
I've been following the discussion of this problem.  Don't like the stage by stage solution. I've been trying to develope a general solution, but failed. Now, I think the current stage by stage solution (by fzy and Warren) may be the best we can do.  I have a minor problem with the stage though. It seems that no matter what, the first storage spot has to be at the half point (i.e. 500 km). At the begining, when you first drive out with 2 barrels (one in the tank of the car, one in the barrel), there's no other place to store the barrel other than the 500 km place (can't be longer or shorter). However, none of your solutions mention the 1/2 point storage place. May be I didn't read it careful enough. I think the best thing to do is to write out the exact procedure of doing the barrel problem.


I did not like the way either, and that is why I waited for so long in the hope of some one can provide a better answer first. But if our solution is indeed the best, the only way to reach it is iteration, because each number depends on the ones before it.

Also in my solution, the 1/2 point plays an important role in calculating the numbers. The whole problem may be reduced to how to reach the 1/2 point (and beyond) in the most efficient way. The way you described (called the all-out way in my earlier post) did not take advantage of storing some fuel in the middle, and most likely will not be optimal. In fact, it uses about 1/2 of the total fuel to reach the 1/2 point. For our way, it is about 43%. So any method that can reach the 1/2 point using less than 43% wil be better than ours. But it cannot be by a lot. It is mathematically not possible to use less than about 40%:

With 2N barrels of fuel, you need 2N-1 trips to carry them anywhere. So it suggests the differential equation of dy/dx = y - 1, where y is fuel consumption and x distance. Solve it and we have y = exp(x) +1. Now we see that y(x - 1/2) is about 60% of y(x).

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
汽车能跑多远?
« Reply #16 on: 十一月 15, 2004, 03:44:13 pm »
You are right. Somehow, I got stuck somewhere. This happens all the time when solving a problem, once stuck in a position, it is very hard to get out of it. Thanks.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
汽车能跑多远?
« Reply #17 on: 十一月 15, 2004, 05:14:57 pm »
I know why I was stuck. I think if you have to do a storage longer than 1/2 point, you can always do it later. e.g. for 5 barrels, the ideal place is 2/3 point, but you can always do a 1/2 storage for the first trip. Then, in the second trip, when you arrive at the 1/2 point, do 3 one way trip of 1/6 to reach the 2/3 trip. It is equivalent to the 2/3 stop. The way I was thinking,  whatever you can do with longer than 1/2 trip, you can always do it with 1/2 point trip first. That's why I was stuck. Now, I feel better. :)

warren

  • Full Member
  • ***
  • Posts: 148
汽车能跑多远?
« Reply #18 on: 十一月 15, 2004, 05:46:25 pm »
You said it. I got this problem about 6 months ago. At first I tried to work out a general way for N barrels of gas, but soon I found I was in a wrong way, the step by step mathod is more effictive, and the calculation is tedious. The original value of N is 100. Since the calculation is complex, I changed the value of N to 10, made the puzzle easier and more interesting.

fzy

  • Hero Member
  • *****
  • Posts: 520
汽车能跑多远?
« Reply #19 on: 十一月 16, 2004, 10:25:13 am »
This is probably over the tolerance of most people for a single problem. But if you are among the minorities, here is a little more spice:

Let's define the 1/2 point efficiency H to be the percentage of fuel you can carry through the 1/2 point. Carry through means the amount of fuel you carry when passing the 1/2 point minus the fuel you carry when you come back by the 1/2 point. I showed earlier that H < 60%. And for our strategy its 1/2 point efficiency for large amount of fuel is the solution of the equation x = exp(-x), or approximately 0.567143. Some other facts about this H: The fuel consumption equation is f = exp(2*H*d), where d is the distance traveled, and f fuel used. The average fuel carried from the start point is (1/H) = 1.7632 barrels; ie if you have 1.7632*N barrels of fuel, you will make N round trips.

Now I am a little more confident about the optimality of the solution, because it involves a nice number.

warren

  • Full Member
  • ***
  • Posts: 148
汽车能跑多远?
« Reply #20 on: 十一月 16, 2004, 12:40:47 pm »
Quote from: fzy
This is probably over the tolerance of most people for a single problem. But if you are among the minorities, here is a little more spice:

Let's define the 1/2 point efficiency H to be the percentage of fuel you can carry through the 1/2 point. Carry through means the amount of fuel you carry when passing the 1/2 point minus the fuel you carry when you come back by the 1/2 point. I showed earlier that H < 60%. And for our strategy its 1/2 point efficiency for large amount of fuel is the solution of the equation x = exp(-x), or approximately 0.567143. Some other facts about this H: The fuel consumption equation is f = exp(2*H*d), where d is the distance traveled, and f fuel used. The average fuel carried from the start point is (1/H) = 1.7632 barrels; ie if you have 1.7632*N barrels of fuel, you will make N round trips.

Now I am a little more confident about the optimality of the solution, because it involves a nice number.


I did not calculate the point efficiency, but I think it is a good view point. Though not proven, I am quite sure this scheme is optimal.