ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 火车运煤问题

火车运煤问题

原创 Linux操作系统 作者:晚秋的枫叶 时间:2013-10-13 12:38:51 0 删除 编辑
转载自 豆瓣:http://www.douban.com/note/270300163/

题目:
  你是山西的一个煤老板,你在矿区开采了有3000吨煤需要运送到市场上去卖,从你的矿区到市场有1000公里,你手里有一列烧煤的火车,这个火车最多只能装1000吨煤,且其能耗比较大——每一公里需要耗一吨煤。请问,作为一个懂编程的煤老板的你,你会怎么运送才能运最多的煤到集市?
  
  看到这个题目后,第一反应是,需要运三次(因为有3000吨煤,并且每次车最多只能装1000吨),前两次将煤运到中途的某个地点并返回,第三次将煤全部运完并送到终点。这样当第三次时会在中途使用前两次运送的煤将车装满,然后走到终点之后肯定还能留一部分。
  于是我有了第一种解法。
  解法一:
  假设矿区为A,市场为B,煤分三次运送。
  第一次运1000吨煤到位置X,并留下返程所需的煤,其余煤全部卸下(假设卸下m吨),并返回。
  第二次运1000吨煤经过X时从第一次卸下的煤中装载m1吨(将车装满)到达Y后留下返回到X处所需的煤。其余煤卸下(假设卸下n吨)。返回到X并装载从X返回到A所需的煤(m2吨)。返回A。
  第三次运1000吨煤,到X时,装载X处剩下的煤(m3吨)这些煤应该正好将车装满。
到达Y处并装载Y处卸下的n吨煤,同样这些没应该改正好将车装满。运送煤直到B,并卸下所有煤(假设为t吨)。

  根据上面的描述我们已经可以知道:
  1000-AX+m1=1000;
  m2=AX;
  1000-AX+m3=1000;
  即m1=m2=m3=AX;
  又因为
  1000-2AX=m;
  所以有:
  1000-2AX=m1+m2+m3;
  1000-2AX=3AX;
  AX=200;
  m1=m2=m3=200; m=600;
  因为:
  1000-2XY=n;
  1000+m3-AY+n=1000;
  所以:
  1000+m3-AX-XY+1000-2XY=1000;
  1000-3XY=0;
  XY=1000/3;
  所以AY=200+1000/3;
  n=1000/3;
  而
  t=1000-YB;
  t=1000-(1000-AY);
  t=AY=533.3。

  在解法一中,我们使用三次运送完所有煤,并算出了最优解。那么如果运送多次呢,是否同样能得到好的解?于是我又尝试了下面的方法。
  解法二:
  因为有3000吨煤,所以一开始我们必须分三批运。但是因为运送过程中煤会消耗,所以我们可以先把所有煤运到到一个中途位置X,使得这时剩下的煤正好为2000吨,然后我们可以改分两批运送,同理我们可以运送到下一个位置Y,使得这时正好还剩下1000吨煤。
然后剩下的1000吨煤我们可以一次运送到终点(假设这时煤还剩下t吨)。
  假设矿区为A,市场为B。
  于是有:
  3000-(2AX)-(2AX)-AX=2000;
  AX=200;
  还有:
  2000-(2XY)-XY=1000;
  XY=1000/3;
  所以
  t=1000-YB;
  t=1000-(1000-AY);
  t=AY=200+1000/3=533.3;
  这时我们发现,解法二虽然看上去,简单粗糙,但却得到了和解法一同样样优秀的解。

个人批注:
这是网上运煤问题分析的不错的一篇文章,第二种方法更为精炼。不过没有给出为什么两个都是最优解的原因,而题目要求的是最优解。
我也给不出具体的证明方法,只是做一个猜想,卡车在最后一次时一定要一次性运送1000吨煤去到终点,就是保证运输过程一定是满载,而次数是否为一次,对于该题的给出的参数,可以使用反证法,来证明多次运输的效果是小于等于一次性的(只要距离在1000以内)。比如,分两批从400米处将1000吨运输到终点,一定不如直接从400米时运输1000吨回终点的方法。(简单来想,因为往返是要耗费煤)同理向前段推,不过这个时候可能是从1000吨变为2000吨,问题就被分割了,每个段是原子不可再分,并且运输是直接的,不经过传递性的,再需要论证这种直接的方式是最佳的。(算法二的思想)

这种求最优解的思想就是将一个过程分为多个不可再分的子过程,每一个子过程都能证明自身最优,并且不同子过程之间不会影响。

而为什么这题是要分割成三次,是因为耗煤的数量、载重量和距离共同决定,这应该是个函数对应关系,解答中没有给出为什么要平均分,为什么是3份,没有证明不平均的更差,也没有证明分4份或者2份的结果。简单的处理方法,就是按照其他两个来分,算出结果作比较,但是真正的证明还是很复杂的。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/29172126/viewspace-774280/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2013-09-12

  • 博文量
    4
  • 访问量
    5143