千人越大漠问题

kastin

千人越大漠问题
1000人的部队行军要穿越7天路程的沙漠，而每个人最多只带得了3天的干粮（包括水）。问将军如何安排一套方案，使得能花费尽可能少的时间完成任务？

注：1. 沙漠天气一直晴朗无风沙，不会发生迷路；2. 行军途中不会出现敌袭；3. 出发地有足够的粮食储备。

这个问题是几年前在网上看到的，觉得与“狼羊过桥”问题有点类似，当然题目里面的数据是可以改的，比如“人数”，“路程天数”，“每人最多能带的补给”，因此很想知道这类问题有何巧妙或者系统的解法？

补充内容 (2015-5-8 11:29):
- 按照常识，7天行军路程远远大于单个人体长，故单人可看作质点（但若一字排开，则队伍不能视为质点）。
- 原题未说明终点是否有充足食物（和水），故本题可以考虑两种情况（显然终点有食物的情形所需时间更短）。

282842712474

假设中的军队能不能挨饿，比如挨一天饿？

liangbch

信息学竞赛题目中有类似的题型。类似的题目有，油罐车拉油问题。等我回去找找相应的资料。

zeroieme

跟油罐车最大的区别是人不能连续24小时*7天走路，也不用连续24小时不停吃饭

平常心

问题可以解决，但最佳方案需要认真思考。另外题目可以说得再清楚一些，比如到达终点的人是否可以返回运送食物。
1000人一次通过是不可能的。可以先运送食物（干粮、水）放在途中，比如每人先走1天的路程，放下1天的食物即返回。如此反复多次、逐步向前推进，最终全部通过沙漠。

平常心

先考虑全部通过，这是一个与人数无关的方案。
→
0——1——2——3——4——5——6——7
将全程分为7段（如上图），0站为起点，每段为1天的路程。
从0站到1站往返40次，80天，1站存放40天食物。
再从0站出发到1站补充1天食物，1天（累计81天）。然后在1站2站之间往返13次，26天（累计107天），在2站存放13天食物。又从1站出发，到2站补充1天食物，1天（累计108天）。
继续从2站到3站往返4次，3站存放4天食物，8天（累计116天）。下次从2站到3站后，补充1天食物，1天（累计117天）。
3站到4站往返1次，放下1天食物，2天（累计119天）。
最后从3站出发，到4站补充1天食物，继续前进直到终点7站，4天（累计123天）。

liangbch

楼上的方案明显不是最优的。最后一段路程可以是3天的路程，不用考虑带备用的食物。

平常心

liangbch 发表于 2015-5-5 19:17
楼上的方案明显不是最优的。最后一段路程可以是3天的路程，不用考虑带备用的食物。

最后一段路程从3站到7站连续走了4天，在第4站补充了1天的食物。

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

liangbch

liangbch 发表于 2015-5-5 12:02
信息学竞赛题目中有类似的题型。类似的题目有，油罐车拉油问题。等我回去找找相应的资料。

请参阅《实用算法的分析和程序设计》第5页【例1】贮油点，百度云盘 http://pan.baidu.com/s/1ntA8HuD

zeroieme

人数多了可以考虑蚂蚁搬家式的传递物资。上千人平均分布在路上，就10分钟路程（24小时*7天）。所以不能再以天为单位计算，还有保留休息时间。