飞机加油的最佳策略设计

KeyTo9_Fans

背景描述：

数轴的$0$点是飞机场，可容纳任意多架飞机。

飞机的油箱容量是$1$，装满油可以飞行$1$个单位距离。

所有飞机的飞行速度是一样的，每个单位时间飞行$1$个单位距离。

除了飞机场，飞机不能在任何地方停留，但可以在任何地方转向。

当两架飞机位于同一地点的时候，其中一架飞机可以把一部分油加给另一架飞机。

飞机一旦把油用尽就会坠毁，除非把油用尽的时候刚好到达飞机场或者有另一架飞机为他加油。

飞机的起飞、降落、加油、转向动作都是一瞬间完成的，只有飞行是需要时间的。

任务描述：

任务$1$：远航任务
--------------------
该任务有$2$个版本。

任务$1.1$：最多使用$n$程油，令$1$架飞机飞到尽可能远的地方并坠毁。

任务$1.2$：最多出动$m$架飞机（$m=1,2,3,...$），在其余的$(m-1)$架辅助飞机都不坠毁的前提下，令$1$架飞机飞到尽可能远的地方并坠毁。
--------------------

任务$2$：返航任务
--------------------
该任务也有$2$个版本。

任务$2.1$：最多使用$n$程油，令$1$架飞机飞到尽可能远的地方并安全返航。

任务$2.2$：最多出动$m$架飞机（$m=1,2,3,...$），所有的飞机都不得坠毁，令$1$架飞机飞到尽可能远的地方并安全返航。
--------------------

任务$3$：环球飞行任务
--------------------
所有的飞机都不得坠毁，令$1$架飞机环球飞行$1$圈后回到出发点。
--------------------

由于微软按照任务$3$的设定出了一道面试题：

http://blog.csdn.net/miracle_ma/article/details/42109457

因此该问题被广泛传播。

但是环球飞行任务可以通过任务$1$解决，做法如下：

假设绕地球飞行一圈需要$s$程油，那么我们只需令$1$架飞机远航至$(s+1)/2$程即可。

只要反向出动相同架次的辅助飞机，使用对称的操作即可把远航至$(s+1)/2$程的那架飞机从反方向救回。

因此只需讨论任务$1$和任务$2$即可。

摆擂目的：

飞机加油问题虽然与汽车跑路问题相似，但两者的难度并不是同一个档次的，前者至今仍未得到精确解。

这类问题有清晰的背景和简单的假设，易理解，可视，可操作，具有趣味性。

希望通过摆擂攻擂的方式，收集到大量案例的精确解，找到精确解的一般规律，从而彻底解决飞机加油问题。

同时也希望这类问题最终都能做成解谜类游戏，通过破解谜题让人感受到数学的魅力。

攻擂规则：

所有看过此贴的人都可以参与。

下载这个附件，解压后就可以玩这个游戏了：

p0.zip (16.2 KB, 下载次数: 24)

2017-12-10 22:37 上传

点击文件名下载附件

操作说明：

----------------------------------------
左上角为操作按钮：

“·”：在飞机场中增加一架飞机
“↑”：为飞机场中选中的飞机加油
“>”：所有飞机飞行一段距离
“つ”：选中的飞机掉头
“＋”：浅蓝色的飞机为黄色的飞机加油
“-><-”：所有飞机飞行一段距离，直到选中的飞机相遇

“←”：撤销一步操作
“→”：重做（反撤销）一步操作
“|←”：撤销全部操作（回到最初状态）
“→|”：重做全部操作（回到最终状态）

“>”：播放全部操作
“||”：暂停播放
“>||”：在暂停状态下，按下时播放，松开时暂停
“■”：停止播放，回到最终状态

“▓←”：把当前操作序列记录到record.txt里
“▓→”：从record.txt里读取操作序列

右上角为参数输入区：

为飞机场中选中的飞机加油时，该区变蓝，输入加油量，单位为$1$。
浅蓝色的飞机为黄色的飞机加油时，该区变黄，输入加油量，单位为$1$。
让所有飞机飞行一段距离时，该区变绿，输入前行距离，单位为$1$。
其余时候该区为灰色，表示不需要输入参数。

小红点表示飞机，用鼠标左键点击会变颜色，表示选中。
再次点击时，颜色还原，表示取消选中。
点击鼠标右键为取消所有选中。
暗蓝色点表示在飞机场中停留的飞机，转向即可改变停留/出发状态。

标尺中的$1$可以随时拖动，缩放单位$1$在屏幕上的比例。
----------------------------------------

该操作平台有待改进，其中最大的问题是浮点运算的误差。

除此之外，可能还有其它的缺陷，甚至是bug，用多了自然就会发觉。欢迎提供反馈意见和建议。

为了方便交流，操作记录采用统一的格式书写，记录在record.txt里。

record.txt的内容既可以通过操作平台写入，也可以用其它方法写入。

只要在操作平台里成功读入并正常运作，都认为是合法的方案。

只要出现如下所示的提示消息，都认为任务成功完成。

+—————————————————————————+
|所有辅助飞机安全返回　　　　　　　　　　　  ＿□×|
+—————————————————————————+
|出动6架辅助飞机　　　　　　　　　　　　　　　　|
|使用10.58333333333333200个单位距离的油量　　  |
|最远飞行距离达到2.00000000000000040个单位距离|
+—————————————————————————+
|　　　　　　　　　　　　确定　　　　　　　　　  |
+—————————————————————————+

一旦成功完成任务，其战绩就可以与战绩榜中的记录对比。

只要新的战绩优于战绩榜中的记录，都可以添加到战绩榜里。

任务$1.1$的战绩榜

用户名	日期	总用油量	远航距离	所在楼层
mokey.liu	2008-01-04	1	1	百度数学吧
mokey.liu	2008-01-04	2	1+1/3	百度数学吧
mokey.liu	2008-01-04	3	1+1/2	百度数学吧
mokey.liu	2008-01-04	4	1+11/18	百度数学吧
mokey.liu	2008-01-04	5	1+32/45	百度数学吧
KeyTo9のFans	2008-01-21	5	1+146/205	百度数学吧
mokey.liu	2008-01-04	6	1+7/9	百度数学吧
mokey.liu	2008-01-04	7	1+5/6	百度数学吧
mokey.liu	2008-01-04	8	1+8/9	百度数学吧
mokey.liu	2008-01-04	9	1+59/63	百度数学吧
mokey.liu	2008-01-04	10	1+35/36	百度数学吧
KeyTo9のFans	2008-01-04	10	1+184/189	百度数学吧
cts245	2005-07-24	10+20/27	2	11#
KeyTo9_Fans	2009-12-19	10+7/12	2	1#
KeyTo9_Fans	2017-12-10	10+29/50	2	13#
mokey.liu	2008-01-04	11	2+1/180	百度数学吧
KeyTo9のFans	2008-01-04	11	2+1/108	百度数学吧
KeyTo9のFans	2008-01-10	40+29/75	2+1/2	思维定势吧

任务$1.2$的战绩榜

用户名	日期	出动飞机数	远航距离	总用油量	所在楼层
活着才是真精彩	2007-12-16	3	1+11/18	4	思维定势吧
59.57.133.243	2007-12-19	4	1+23/30	6	思维定势吧
KeyTo9のFans	2008-05-07	4	1+317/410	6	思维定势吧
KeyTo9のFans	2007-12-19	5	1+19/21	8+10/21	思维定势吧
KeyTo9のFans	2007-12-26	6	2	11+5/14	11#

任务$2.1$的战绩榜

用户名	日期	总用油量	返航距离	所在楼层
胡亚峰，胡爱军，王煜航，张贤达	2006-07-01	2	2/3	爱学术
戚晨皓，翟建锋，邹建宇	2006-07-01	2	2/3	爱学术
戚晨皓，翟建锋，邹建宇	2006-07-01	3	5/6	爱学术
戚晨皓，翟建锋，邹建宇	2006-07-01	4	11/12	爱学术
戚晨皓，翟建锋，邹建宇	2006-07-01	5	1	爱学术
戚晨皓，翟建锋，邹建宇	2006-07-01	6	1+1/18	爱学术
戚晨皓，翟建锋，邹建宇	2006-07-01	7	1+1/10	爱学术
戚晨皓，翟建锋，邹建宇	2006-07-01	8	1+29/180	爱学术
戚晨皓，翟建锋，邹建宇	2006-07-01	9	1+19/90	爱学术
胡亚峰，胡爱军，王煜航，张贤达	2006-07-01	18	1+1/3	爱学术
戚晨皓，翟建锋，邹建宇	2006-07-01	18	1+1/3	爱学术
胡亚峰，胡爱军，王煜航，张贤达	2006-07-01	54	1+2/3	爱学术
戚晨皓，翟建锋，邹建宇	2006-07-01	54	1+2/3	爱学术
胡亚峰，胡爱军，王煜航，张贤达	2006-07-01	162	2	爱学术
戚晨皓，翟建锋，邹建宇	2006-07-01	162	2	爱学术
mokey.liu	2008-01-04	71	2	百度数学吧

任务$2.2$的战绩榜

用户名

日期

出动飞机数

返航距离

总用油量

所在楼层

由于任务$3$可以通过任务$1$解决，因此任务$3$无需另设战绩榜。

欢迎大家参与，争取早日解决飞机加油问题。

数学星空

呵,KeyTo9_Fans在编程方面的确有更深的研究嘛,你这种做法值得大家学习哟,可以让更多的人参与游戏又增长了数学知识...

gxqcn

估计这类问题可能需要不断编程、不断修正数学模型才能逼近最优解， 有些难度，适合作为一个长期的擂台节目。

无心人

细想起来 很麻烦

shshsh_0510

问题1： 考虑两驾，一驾可以在1/3处将另一驾加满，然后自己安全返回，于是 任务需要轰炸机在坐标1是满油的，此时需要另一个在坐标1将他加满 即在坐标1有两驾2/3油 这两驾是在坐标2/3处被另两驾加满的于是，需要4驾在坐标2/3处2/3油 8驾在坐标1/3处2/3油 另外，还需接回坐标1处空油的一驾，即需要坐标1处2/3油的一驾，共同返回坐标2/3，这需要4驾 然后需要接回坐标2/3处的2驾空油的，这需要另外的坐标2/3处2驾2/3油，即4驾0处满油 然后，需要接回坐标1/3处的4驾空油的，这是额外4驾 总共：8+4+4+4=20驾 乱七八糟，不知错了没

mathe

不需要所有飞机同时起飞的。可以部分飞机迟一些起飞，去接其他没有油的飞机，问题复杂在这里

KeyTo9_Fans

5#说的是这个方案吗？ 貌似一共出动14架，每架1箱油就可以了。 为什么是20架呢？ 和上述方案有什么差别？

shshsh_0510

7# KeyTo9_Fans 哦，我就是想这个意思，只不过总是算错 你这个图有意思，咋画的

KeyTo9_Fans

没有在操作平台上跑一遍吗？如果跑通了就不大可能出错了。 拿gif工具一帧一帧画的。 除了第一帧，后面的直接复制粘贴，然后做点小改动。 共有116帧，做了两个小时。 不过这样做效率太低了。 所以我考虑在1楼的操作平台里添加一个功能，自动生成gif动画。

geslon

哦，一开始觉得很简单，轻易得出共需8架飞机8个油的结论。后来发现不对了。 关键是飞机一经起飞，就必须在天上飞，不停耗油。需要把握好时间呢。