千人越大漠问题

liangbch

1.单位定义，将1天的路程定义一个距离单位，则
1)总的距离单位是7，所有要求各段路程的总长度超过7.
2)一个单位路程消耗1/3份食物。

2.方法，使用《实用算法的分析和程序设计》中的方法，主要方法
1) 倒数第1段往返1次，倒数第2段往返2次，以此类推.
2) 倒数第1段起点存放1份食物，倒数第2段起点存放2份食物。


3.计算方法
  1) 若某段距离为s，则往返n次走的总距离为(2n-1)s。
  例：往返1次意味着直接过去，共1段路程。往返2次意味着 "到下一储备点"，“回来”，“再去下一储备点”，共3段路程，往返3次5段路程，以此类推。

  2)若某段距离为s,下面计算往返n次可运过去的食物份数
   前n-1趟，运输食物(n-1)份，消耗食物 (1/3)*2*s*(n-1)  
   第n趟，运输食物1份,  消耗食物 (1/3)*s
   总的运抵食物份数为 n-(2n-1)/3*s
  
  3)确定倒数第n段路长度,s为第n段路长度，则未知数为s的方程为 n-(2n-1)/3*s=n-1,解之的s= 3/(2n-1)

下面的表格给出各段的数据
|倒数第几段段|往返趟数|倒数第i段路的长度|倒数第i段路起点食物份数|倒数第i段路终点食物份数|
|1|1| 3/1  | 1 | 0|
|2|2| 3/3  | 2 | 1|
|3|3| 3/5  | 3 | 2|
|4|4| 3/7  | 4 | 3|
|5|5| 3/9  | 5 | 4|
|6|6| 3/11| 6 | 5|
|7|7| 3/13| 7 | 6|
|8|8| 3/15| 8 | 7|
|9|9| 3/17| 9 | 8|
|10|10|3/19|10 | 9|
|11|11|3/21|11 | 10|
|12|12|3/23|12 | 11|
|13|13|3/25|13 | 12|
|14|14|3/27|14 | 13|
|15|15|3/29|15 | 14|

总共15段路程，总的长度为7.0076个单位，每段路程花的时间都是相同的，3天，总的天数是3×15=45天。

liangbch

六楼的方法“从0站到1站往返40次，80天，1站存放40天食物。”必须要求士兵吃一顿饭，然后饿两天，否则往返40趟无法运抵40份食物。

kastin

zeroieme 发表于 2015-5-7 15:07
前端怎么会饿死呢，所有同时出发，排前面的距离短先到位，就开始传送了。。这样传送流一路延伸。而不是等最 ...

原来是这个意思，不过这样的话避免不了需要考虑两个问题：

1. 供应链长度不足
1000人双手展开排列成一条线（就当是2米长吧），其总长度显然覆盖不了沙漠（7天路程，按照步行30公里/每天的速度的话，2000米远远不够覆盖）。

因此当这条队伍走完最后一人的时候，谁来保证食物传递链不断掉？如果令队伍最后一人来回传送，那么他必须速度比队伍要快好几倍，而且是越来越快（因为随时间推移，队伍越走越远），这样才能保证能始终在饿死人之前赶上队伍最末端，将食物送达。

另外，这种左手传到右手的模式有些滑稽，像是螃蟹走路一般：自己不断横着前进同时得兼顾将左手伸直拿到邻居的送递，然后送往自己右手伸直那端邻居的左手上。如果不想这么麻烦，可以相互靠近点，但须保证不会前脚踩到别人的后脚，然后用双手前后交替传递食物。

2. 不能停止传送
由于队伍是越来越远离出发点的，那么食物传送流就需要保证一定的速度源源不断传递。然而，为了保证食物传送流不停止，队伍中的人需要不停前后递送食物——这种摆手运动如果让机器去做，只要有电力或者汽油，可以保证不劳累不间断工作，但是人就不一样了。我们不能保证每个人的手臂不会酸痛，哪怕他非常饱！

即使我们理想化——只要是有能量，认为人不会疲劳——那么问题又来了，吃饭的时候怎么办？大家不可能不用手吃饭吧？这样一来，食物传送流必然会中断，一旦中断，刚开始还没什么影响，随着时间推移，越是到后面，其影响就会体现出来了。

综上所述，这种方案很难在实际生活中实现。

zeroieme

kastin 发表于 2015-5-7 23:36
原来是这个意思，不过这样的话避免不了需要考虑两个问题：

1. 供应链长度不足

感觉你没见过人家救灾递送物品的场面。踩后脚的问题根本不存在

问题1：注意我一直说用供应链建立补给点而不是直接到终点。

用手传递的效率比人带效率高，因为人走是100多斤的身体带物品一起移动，而用手就省下不少力气。
所以问题2就是个伪命题，你走路都不能连续走，腿都怕酸痛。腿的问题怎么解决手的的问题一样——休息。

ccmmjj

想了一晚我已算出来了，前进基地算法：
1：每人准备122天的食物。
2；前80天每人都在一天的路程处每次储存1天的食物，在此前进基地共每人共储存40天食物，消耗80天食物。
3；第81天每人带3天食物到第一基地，补充后前进到二天路程储存一天食物，返回第一基地补充。再前进到第二基地，储存，返回这样用26天时间，在第二基地储存13天食物，此过程消耗了26天食物。
4；第107天每人带3天食物到第二基地，补充后前进到三天路程储存一天食物，返回第二基地补充。这样用时8天在第三基地储存4天食物。此过程消耗了8天食物。
5；第116天每人带3天食物到第三基地，补充后前进到四天路程储存一天食物，返回第三基地补充。再前进到第四基地补充完整径至终点。这样共消耗食物122天，完成跨越沙漠的任务。

我对此题作了改编，成熟了再贴到难题征解与网友共享。

平常心

liangbch 发表于 2015-5-7 21:53
六楼的方法“从0站到1站往返40次，80天，1站存放40天食物。”必须要求士兵吃一顿饭，然后饿两天，否则往返4 ...

这是一个误会。
我们的方案看似不同，但有许多相似之处。
.单位定义，将1天的路程定义一个距离单位，……一个单位路程消耗1/3份食物。
距离单位的定义相同，只是食物单位有区别。我的“1份”指1天的食物，0站到1站是1天的路程，每人携带3天（3份）食物，往返一次，运送1份食物（这1份，是你定义的1/3份）。

平常心

ccmmjj 发表于 2015-5-8 14:27
想了一晚我已算出来了，前进基地算法：
1：每人准备122天的食物。
2；前80天每人都在一天的路程处每次储 ...

这与我的方案几乎完全一致。只是123天变成了122天。

“4；第107天每人带3天食物到第二基地，补充后前进到三天路程储存……”这里的107天，似乎应为108天。
如果是这样，我们就完全一致了。

ccmmjj

平常心 发表于 2015-5-5 21:34
最后一段路程从3站到7站连续走了4天，在第4站补充了1天的食物。

这个方案未考虑人数多少的影响。

仔细看了，还真是相同的。只是我的数值是计算出来的，是1000人到终点往返搬运的最优结果。我认为没有人在这个条件下能做出更优的结果，换一种思路，不要平均路程搬运也许时间可以缩短。

liangbch

ccmmjj 发表于 2015-5-8 17:04
仔细看了，还真是相同的。只是我的数值是计算出来的，是1000人到终点往返搬运的最优结果。我认为没有 ...

你这个怎么能是最优结果呢？21楼的方案只需要45天，你这个方案需要120多天。

倪举鹏

好像可以整数线性规划  驴子拖萝卜问题