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

warren

  • Full Member
  • ***
  • Posts: 148
汽车能跑多远?
« on: 十一月 01, 2004, 06:14:21 pm »
假设有一辆车,它的油箱恰好和一个油桶一样大,而且车上恰好可以运载一个
桶。假设一桶油可以让车开一千公里。现在在起点有10桶油。问,这车最远能
离开起点多远? 如果有N桶油,汽车能跑多远?

fzy

  • Hero Member
  • *****
  • Posts: 520
汽车能跑多远?
« Reply #1 on: 十一月 02, 2004, 09:46:59 am »
It depends on whether the truck can carry an empty barrel in addition to a barrel of gas. This will determine whether it can store more than one barrel at any given place. If yes, the result is

(2 + 2/3 + 2/5 + 2/7 + 2/9) * 1000 = 3574 km

If no, the best I got so far is (3 + 5/12) * 1000 = 3416 km

warren

  • Full Member
  • ***
  • Posts: 148
汽车能跑多远?
« Reply #2 on: 十一月 02, 2004, 12:22:23 pm »
Quote from: fzy
It depends on whether the truck can carry an empty barrel in addition to a barrel of gas. This will determine whether it can store more than one barrel at any given place. If yes, the result is

(2 + 2/3 + 2/5 + 2/7 + 2/9) * 1000 = 3574 km

If no, the best I got so far is (3 + 5/12) * 1000 = 3416 km


If the truck can carry an empty barrel in addition to a barrel of gas,
this puzzle is not difficult, and I think your answer is right. I am interested
in the case when only one barrel can be carried. The difficulty is that
at most one barrel of gas can be stored at one place, this makes the
calculation complex.

sean

  • Jr. Member
  • **
  • Posts: 86
汽车能跑多远?
« Reply #3 on: 十一月 02, 2004, 12:40:14 pm »
I think it would be harder to obtain a tight upper bound than a tight lower bound for this kind of problem; if one can show his result is optimal, that would be really good. I am more interested in this, but do not know how.

There is a bicycle problem posted below.  I think  the problem has been considered solved, but there is no optimality proof either.  

Has anyone tried this direction?

warren

  • Full Member
  • ***
  • Posts: 148
汽车能跑多远?
« Reply #4 on: 十一月 04, 2004, 04:04:18 pm »
这个问题发了三天了,不知有几人在考虑。这里对比较小的 N 说说我的方法。

设起点有 N 桶油(N 不一定是整数)。
1) 0〈 N 〈= 2, 汽车在起点带上全部油出发,能行驶1000N公里。
2) 2〈 N 〈= 4,记 R=N-2,第一次汽车带油R桶,行驶1000R/3公里到A点,存R/3桶油在A点,返回。 第二次汽车带油2桶,到A点加油R/3桶,能继续行驶2000公里。共行驶(2+(N-2)/3)*1000公里。
3) 4〈 N 〈= 5+2/3,记 R=N-4,第一次汽车带油R桶,行驶1000R/5公里到A点,存3R/5桶油在A点,返回。 第二次汽车带油2桶,到A点加油R/5桶,继续行驶2000/3公里到B点,存油2/3桶,返回A点,加油R/5桶,返回起点。第三次汽车带油2桶,到A点加油R/5桶,继续行驶2000/3公里到B点,加油2/3桶,继续行驶2000公里。共行驶(2+2/3+(N-4)/5)*1000公里。当N=5+2/3时,行驶距离是 3000 公里。

fzy

  • Hero Member
  • *****
  • Posts: 520
汽车能跑多远?
« Reply #5 on: 十一月 05, 2004, 10:04:55 am »
I got some messy numbers and really do not want to put it up yet

fzy

  • Hero Member
  • *****
  • Posts: 520
汽车能跑多远?
« Reply #6 on: 十一月 09, 2004, 01:04:02 pm »
There seem to be a sequence of optimal storage point on the route, and a corresponding sequence of maximal amount of gasoline you can have without using the next storage point, and a sequence of maximal distance you can travel with it. Let's call the sequeces X1, X2, X3, ..., Y1, Y2, Y3, ..., and Z1, Z2, Z3, .... Here is what I got so far:

X1 = 2 away from the final destination. (Lets omit all the 000.)
Y1 = 4 barrels
Z1 = 2 + 2/3

X2 = 2/3 from X1
Y2 = 5 + 2/3
Z2 = 3

X3 = 1/3 from X2
Y3 = 7 + 8/15
Z3 = 3 + 4/15

X4 = 4/15 from X3
Y4 = 9 + 1/3
Z4 = 3 + 7/15

X5 = 1/5 from X4
Y5 = 11 + 1/105
Z5 = 3 + 13/21

X6 = 16/105 from X5
Y6 = 12 + 91/105
Z6 = 3 + 16/21

The answer from my sequences to the original problem is between z4 and z5. (z4 + 2/33 = 3 +87/165 to be precise.)

warren

  • Full Member
  • ***
  • Posts: 148
汽车能跑多远?
« Reply #7 on: 十一月 09, 2004, 01:21:06 pm »
Good job! I believe this is optimal. For N=10, the farest place the truck can reach is (3+29/55)*1000=3527km.

warren

  • Full Member
  • ***
  • Posts: 148
汽车能跑多远?
« Reply #8 on: 十一月 09, 2004, 02:29:03 pm »
fzy的计算结果与我的计算结果一致,我认为这是最优解.关键是计算出数列 2,2/3,1/3,4/15,1/5,16/105,..., 它们分别是
终点,第一个存油点,第二个存油点,第三个存油点,...,起点之间的距离.从这些存油点出发到终点所需油量分别是 2,2+3*2/3,2+3*2/3+5*1/3,2+3*2/3+5*1/3+7*4/15,2+3*2/3+5*1/3+7*4/15+9*1/5,2+3*2/3+5*1/3+7*4/15+9*1/5+11*16/105,...,
计算出来就是2,4,5+2/3,7+8/15,9+1/3,11+1/105,.... 对于N=10,9+1/3<N<11+1/105,
离起点最近的存油点距离是(N-(9+1/3))/11=2/33, 其他各存油点之间的距离分别是1/5,4/15,1/3,2/3. 有兴趣的网友可以考虑详细的过程.

sean

  • Jr. Member
  • **
  • Posts: 86
汽车能跑多远?
« Reply #9 on: 十一月 09, 2004, 07:26:01 pm »
Quote from: warren
Good job! I believe this is optimal. For N=10, the farest place the truck can reach is (3+29/55)*1000=3527km.


How do you show it is optimal?

warren

  • Full Member
  • ***
  • Posts: 148
汽车能跑多远?
« Reply #10 on: 十一月 09, 2004, 08:23:14 pm »
Quote from: sean
Quote from: warren
Good job! I believe this is optimal. For N=10, the farest place the truck can reach is (3+29/55)*1000=3527km.


How do you show it is optimal?


只是"believe", 要严格证明很繁琐,我没时间去证.也许fzy有最优性证明.

fzy

  • Hero Member
  • *****
  • Posts: 520
汽车能跑多远?
« Reply #11 on: 十一月 10, 2004, 02:04:32 pm »
The way I got my strategy is iterative and incremental. I believe it is locally optimal, which means small tweaks will not improve the result. But I cannot rule out that some dramatically different strategies may have better results, in particular for larger amount of fuel. This is my way:

1. We assume that a sequence of optimal storage points exist and their relative positions will not change. There is one criteria: When the truck leaves a storage point for the last time, it should have a full tank and a full barrel.

2. When a truck starts between Storage Point N (SP(N)) and SP(N+1), it will make N round trips back to the start point, first time to SP(N), then SP(N-1), and so on. Each time one full barrel of fuel is stored, except at SP(1), where 1/3 barrel is stored.

3. For one round trip to an SP that is less than 1/2 unit (we assume one barrel of fuel can go 1 unit) away, we carry 1 + 2d barrels (d the distance). Other wise we carry 2 barrels.

4. If we start near SP(N) and (2N+1)d < 1 + 2d, we carry (2N+1)d and store (2N-1)d for the first trip. And this is how I got the answer for the original problem.

5. The value of the distance between SP(N) and SP(N+1) is the largest number such that the above is possible. It turns out the only trip we need to worry about is the first one over 1/2.

As examples, I show here how I got SP(4) and SP(5). We already knew that SP(1) = 2, SP(2) = 2/3, and SP(3) = 1/3. (From now on we make no difference between an SP and its distance from the previous one.)

For SP(4) the first trip exceeding 1/2 is the second one. Let SP(4) = x. During this trip the fuel amounts added and dumped are (2 - 1 + (1 - 3x)). Here 1 dumped at SP(2) and (1 - 3x) added at SP(3) so that 3x left for the 3 future passes. The distance traveled is 2(SP(3) + x). Solve the equation and we get x = 4/15.

For SP(5) the first trip exceeding 1/2 is the third one. (If you solve for the second trip you will not get a solution.) Let SP(5) = x. The fuel amounts added and dumped are (2 - 1 + 1/5 + (1 - 3x)). Here 1/5  barrel is added at SP(3) from the previous calculation. The distance traveled is 2(SP(4) + SP(3) + x). Solve the equation and we get x = 1/5.

Another strategy that might look attractive for large amount of fuel is to go all out: Carry as much fuel as possible on each trip, use about half of it and store the other half at the 1/2 point. But since the SP sequece is decreasing and the fuel consumption graph is concave, we can see that the first strategy is always better than the second one.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
汽车能跑多远?
« Reply #12 on: 十一月 12, 2004, 04:11:13 pm »
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.

warren

  • Full Member
  • ***
  • Posts: 148
汽车能跑多远?
« Reply #13 on: 十一月 12, 2004, 08:18:13 pm »
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.


The first storage point needs not be at 500km. For example, when N=5,
as shown in my previous poster(the 5th floor), the first storage point is
1000/5=200km away from the start point, and it is easy to show that this
 plan is optimal.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
汽车能跑多远?
« Reply #14 on: 十一月 12, 2004, 09:56:13 pm »
Yes, I can see that, just like when you have 3 barrel, the first storage place is 1/3, this is because you want to reduce the round trips, thus, make the number of barrels to be even. When you have even number of barrels, anything shorter than 1/2 point will make more trips. You may be able to have shorter storage place later when you have an empty barrel, but the first time, you have to do a 1/2 point stop, I think.