千人越大漠问题

平常心

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

若穿越沙漠共需n天路程，千人整体通过实际需要天数由下式计算：3*(1+(3n-3-1)/2)(天)

平常心

liangbch 发表于 2015-5-8 18:15
你这个怎么能是最优结果呢？21楼的方案只需要45天，你这个方案需要120多天。

123天确实不是最优方案。

从整体穿越的情况来看，你给出的方案是理想的最优方案。
不过，人穿越沙漠问题与汽车运输穿越问题有点不同，汽车每时每刻都在耗油；人的饮食一般按日计算，或者一日三餐、二餐。所以我觉得，应该参照你的方法给出一个近似的最优方案。

平常心

zeroieme 发表于 2015-5-8 09:05
感觉你没见过人家救灾递送物品的场面。踩后脚的问题根本不存在

问题1：注意我一直说用供应链建立补给 ...

您的想法有一点道理，应该完善。
“用手传递的效率比人带效率高……”这个问题大概不存在这样的方式。一天的路程，也许是50——199 ㎞，若每人之间的距离是1m,1000人只有1㎞。

利用人数肯定有较好的方案。可以讨论。

ccmmjj

liangbch 发表于 2015-5-8 18:15
你这个怎么能是最优结果呢？21楼的方案只需要45天，你这个方案需要120多天。

是我太草率了。我昨晚又仔细的一想，这个问题不那么简单。前晚只是想提出一个过沙漠的方案，没在考虑到其他可能性。最优结果，有一个极限，我正试着去找它，不知老兄有没有现成的答案？

KeyTo9_Fans

我们首先考虑终点没有充足食物（和水）的情况。

我们假设$1$人行军$1$单位长度需要消耗$1$份食物，行军速度是每$3$天行走$1$单位长度。

#####

$1$人过大漠问题：

liangbch在9楼已经给出了答案：

pan.baidu.com/s/1ntA8HuD
第$5$页例$1$。

他的结论是：

穿越长度为$1$的大漠需要$3$天时间；
穿越长度为$1+1/3$的大漠需要$6$天时间；
穿越长度为$1+1/3+1/5$的大漠需要$9$天时间；
穿越长度为$1+1/3+1/5+1/7$的大漠需要$12$天时间；
……
依次类推，得到以下结果：

穿越长度为$7/3$的大漠，需要$44.7790808...$天。

$2$人过大漠问题：

与$1$人过大漠不同，$2$人可以分头行动。

例如，$2$人穿越长度为$5/4$的大漠，可以采取以下方案：

$2$人各携带$1$份食物出发；
行至$1/8$处时，$2$人各剩$7/8$份食物，$1$人放下$5/8$份食物，并把$1/8$份食物补给另$1$人后，自己剩余$1/8$份食物折返，另$1$人则补满了食物继续前行；
$1$人返回起点已无食物，于是再携带$1$份食物出发，另$1$人行至$1/4$处剩余$7/8$份食物，放下$3/4$份食物后，自己剩余$1/8$份食物折返；
$2$人在$1/8$处相遇，$1$人剩$7/8$份食物，另$1$人已无食物，于是拿起此处的$5/8$份食物，$2$人一共剩余$3/2$份食物一起前行；
$2$人行至$1/4$处，一共剩余$5/4$份食物，于是拿起此处的$3/4$份食物，$2$人一共剩余$2$份食物继续前行；
最终$2$人顺利到达$5/4$处的终点。

综上所述，$2$人一共消耗了$3$份食物，穿越了长度为$1+1/4$的大漠，行走的路线如下：



为了在某处放置$3$份食物，可以采取以下方案：

$2$人各携带$1$份食物出发；
行至$1/6$处时，$2$人一共剩余$5/3$份食物，$2$人一共放下$4/3$份食物后，一共剩余$1/3$份食物一起折返；
$2$人返回起点已无食物，于是再各携带$1$份食物出发；
行至$1/6$处时，$2$人一共剩余$5/3$份食物，$2$人把全部食物放下后，$1/6$处就有了$3$份食物；

由于$2$人一共消耗$3$份食物，可以穿越长度为$1+1/4$的大漠，
综上所述，$2$人一共消耗了$4$份食物，穿越了长度为$1+1/4+1/6$的大漠。

为了在某处放置$4$份食物，可以采取以下路线：



上述路线在起点处一共拿走了$5$份食物，在$1/8$处一共放置了$4$份食物。

由于$2$人一共消耗$4$份食物，可以穿越长度为$1+1/4+1/6$的大漠，
综上所述，$2$人一共消耗了$5$份食物，穿越了长度为$1+1/4+1/6+1/8$的大漠。

综上所述，我们有以下结论：
$2$人穿越长度为$1$的大漠一共需要消耗$2$份食物；
$2$人穿越长度为$1+1/4$的大漠一共需要消耗$3$份食物；
$2$人穿越长度为$1+1/4+1/6$的大漠一共需要消耗$4$份食物；
$2$人穿越长度为$1+1/4+1/6+1/8$的大漠一共需要消耗$5$份食物；

依次类推：
$2$人穿越长度为$1+1/4+1/6+1/8+1/10$的大漠一共需要消耗$6$份食物；
$2$人穿越长度为$1+1/4+1/6+1/8+1/10+1/12$的大漠一共需要消耗$7$份食物；
……

于是$2$人穿越长度为$7/3$的大漠，一共需要消耗$22.937550...$份食物。
由于$2$人每$3$天消耗$2$份食物，所以对应的天数是$34.406325...$天。

$3$人过大漠问题：

通过以下路线，$3$人一共消耗$4$份食物，可以穿越长度为$1+1/5$的大漠。



通过以下路线，$3$人一共消耗$5$份食物，可以在$1/7$处一共放下$4$份食物。



于是$3$人一共消耗$5$份食物，可以穿越长度为$1+1/5+1/7$的大漠。

依次类推：
$3$人一共消耗$6$份食物，可以穿越长度为$1+1/5+1/7+1/9$的大漠；
$3$人一共消耗$7$份食物，可以穿越长度为$1+1/5+1/7+1/9+1/11$的大漠；
$3$人一共消耗$8$份食物，可以穿越长度为$1+1/5+1/7+1/9+1/11+1/13$的大漠；
$3$人一共消耗$9$份食物，可以穿越长度为$1+1/5+1/7+1/9+1/11+1/13+1/15$的大漠；
……

于是$3$人穿越长度为$7/3$的大漠，一共需要消耗$30.073099...$份食物。
由于$3$人每$3$天消耗$3$份食物，所以对应的天数是$30.073099...$天。

千人过大漠问题：

依次类推，千人过大漠的结论如下：
$1000$人一共消耗$1000$份食物，可以穿越长度为$1$的大漠；
$1000$人一共消耗$1001$份食物，可以穿越长度为$1+1/1002$的大漠；
$1000$人一共消耗$1002$份食物，可以穿越长度为$1+1/1002+1/1004$的大漠；
$1000$人一共消耗$1003$份食物，可以穿越长度为$1+1/1002+1/1004+1/1006$的大漠；
$1000$人一共消耗$1004$份食物，可以穿越长度为$1+1/1002+1/1004+1/1006+1/1008$的大漠；
……

于是$1000$人穿越长度为$7/3$的大漠，一共需要消耗$7703.655...$份食物。
由于$1000$人每$3$天消耗$1000$份食物，所以对应的天数是$23.110965...$天。

$+\infty$人过大漠问题：

依次类推，$+\infty$人过大漠的结论如下：
$+\infty$人各消耗$1+t$份食物，可以穿越长度为$1+\int_{x=0}^{t}1/(1+2x) dx$的大漠；

于是$+\infty$人穿越长度为$7/3$的大漠，每人需要消耗$7.695958...$份食物。
由于每人每$3$天消耗$1$份食物，所以对应的天数是$23.087874...$天。

#####

以上是终点没有充足食物的情况下，任意多个人过大漠的一套方案。

这套方案还能继续优化吗？

如果终点有充足的食物，那么当一部分人到达终点后，可以把终点的食物往回运，补给后面的人。

这样能缩短所有人都通过大漠所需的时间吗？

王守恩

千人越大漠趣题

我们把沙漠分成七段，起点为大本营，终点为目的地，中间依次为6#营地、5#营地、4#营地、3#营地、2#营地、1#营地。
第1天。大本营：1000人前进，带干粮3000份，到达6#营地。
第2天。6#营地：1000人返回，带干粮1000份，6#营地库存1000份。
第3天。大本营：1000人前进，带干粮3000份，到达6#营地。
第4天。6#营地：1000人返回，带干粮1000份，6#营地库存2000份。
第5天。大本营：1000人前进，带干粮3000份，到达6#营地。
第6天。6#营地：1000人返回，带干粮1000份，6#营地库存3000份。
第7天。大本营：1000人前进，带干粮3000份，到达6#营地。
… …
第73天。大本营：1000人前进，带干粮3000份，到达6#营地。
第74天。6#营地：1000人返回，带干粮1000份，6#营地库存37000份。
第75天。大本营：1000人前进，带干粮3000份，到达6#营地。
第76天。6#营地：1000人返回，带干粮1000份，6#营地库存38000份。
第77天。大本营：1000人前进，带干粮3000份，到达6#营地。
第78天。6#营地：1000人返回，带干粮1000份，6#营地库存39000份。
第79天。大本营：1000人前进，带干粮3000份，到达6#营地。
第80天。6#营地：1000人返回，带干粮1000份，6#营地库存40000份。
第81天。大本营：1000人前进，带干粮3000份，到达6#营地。
注1：至此大本营共输出干粮123000份，6#营地库存干粮共42000份。
第82天。6#营地：1000人前进，带干粮3000份，到达5#营地。
第83天。5#营地：1000人返回，带干粮1000份，5#营地库存1000份。
第84天。6#营地：1000人前进，带干粮3000份，到达5#营地。
第85天。5#营地：1000人返回，带干粮1000份，5#营地库存2000份。
第86天。6#营地：1000人前进，带干粮3000份，到达5#营地。
第87天。5#营地：1000人返回，带干粮1000份，5#营地库存3000份。
第88天。6#营地：1000人前进，带干粮3000份，到达5#营地。
… …
第100天。6#营地：1000人前进，带干粮3000份，到达5#营地。
第101天。5#营地：1000人返回，带干粮1000份，5#营地库存10000份。
第102天。6#营地：1000人前进，带干粮3000份，到达5#营地。
第103天。5#营地：1000人返回，带干粮1000份，5#营地库存11000份。
第104天。6#营地：1000人前进，带干粮3000份，到达5#营地。
第105天。5#营地：1000人返回，带干粮1000份，5#营地库存12000份。
第106天。6#营地：1000人前进，带干粮3000份，到达5#营地。
第107天。5#营地：1000人返回，带干粮1000份，5#营地库存13000份。
第108天。6#营地：1000人前进，带干粮3000份，到达5#营地。
注2：至此6#营地共输出干粮42000份，5#营地库存干粮共15000份。
第109天。5#营地：1000人前进，带干粮3000份，到达4#营地。
第110天。4#营地：1000人返回，带干粮1000份，4#营地库存1000份。
第111天。5#营地：1000人前进，带干粮3000份，到达4#营地。
第112天。4#营地：1000人返回，带干粮1000份，4#营地库存2000份。
第113天。5#营地：1000人前进，带干粮3000份，到达4#营地。
第114天。4#营地：1000人返回，带干粮1000份，4#营地库存3000份。
第115天。5#营地：1000人前进，带干粮3000份，到达4#营地。
第116天。4#营地：1000人返回，带干粮1000份，4#营地库存4000份。
第117天。5#营地：1000人前进，带干粮3000份，到达4#营地。
注3：至此5#营地共输出干粮15000份，4#营地库存干粮共6000份。
第118天。4#营地：1000人前进，带干粮3000份，到达3#营地。
第119天。3#营地：1000人返回，带干粮1000份，3#营地库存1000份。
第120天。4#营地：1000人前进，带干粮3000份，到达3#营地。
注4：至此4#营地共输出干粮6000份，3#营地库存干粮共3000份。
第121天。3#营地：1000人前进，带干粮3000份，到达2#营地。
第122天。2#营地：1000人前进，带干粮2000份，到达1#营地。
第123天。1#营地：1000人前进，带干粮1000份，到达目的地。

朋友！123天到达目的地，你有小于123天的方法？请你告诉我！少1天也行！

aimisiyou

感觉2人和1000人分析的情况不相同。打个不恰当的比方（没仔细分析），比如1000人每人携带3天的食物出发，行至0.5天的路程处时，800人返回，200人带3天的食物继续前，该处留存一部分食物，200人行至某处时，一部分人返回，另一部分人继续携带3天的食物继续往前赶，该处同样留一部分食物…第一波返回的800人携带3天的食物再次出发，行至0.5天路程处时，600人返回，200人携带3天的食物出发，该处留存一部分食物…最后的情形是，从起点返回的人携带3天的食物出发，沿路收集预留食物直到终点。类似并行运行，如果可行的话，时间应该可以缩短些。

aimisiyou

aimisiyou 发表于 2017-2-13 22:07
感觉2人和1000人分析的情况不相同。打个不恰当的比方（没仔细分析），比如1000人每人携带3天的食物出发，行 ...

看来尽快送一批人先过去的思路不对！如将天数7改为4，则方案有如下：方案1：1000人带三天食物行至1天路程处，放下1000份食物，全部返回，再次携带三天食物出发，行至1天路程处时所剩食物2000份，加上上次预留的1000份，刚好够1000人三天的路程，所以总时间为6天；方案2：1000人带三天食物行至1天路程处，500人返回，500人继续前行，刚好500人到达终点，500人回到起点，再出发500人，返回250人，再出发250人返回125人，再出发250人返回63人，（中转站处留一份食物），再出发63人返回31人，再出发31人返回16人（中转站处留一份食物）……对比总时间还是方案1最短！

王守恩

aimisiyou 发表于 2017-2-14 15:12
看来尽快送一批人先过去的思路不对！如将天数7改为4，则方案有如下：方案1：1000人带三天食物行至1天路程 ...

尽快送一批人先过去的思路肯定不是最佳方案。

aimisiyou

KeyTo9_Fans 发表于 2015-5-30 18:29
我们首先考虑终点没有充足食物（和水）的情况。

我们假设$1$人行军$1$单位长度需要消耗$1$份食物，行军 ...

\(2\)人穿越长度为\(1+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{9}\)路程需要消耗多少食物？总耗时多少天？