KeyTo9_Fans 发表于 2009-12-19 02:42:30

飞机加油的最佳策略设计

背景描述:

数轴的$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$即可。

摆擂目的:

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

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

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

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

攻擂规则:

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

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





操作说明:

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

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

“←”:撤销一步操作
“→”:重做(反撤销)一步操作
“|←”:撤销全部操作(回到最初状态)
“→|”:重做全部操作(回到最终状态)

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

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

右上角为参数输入区:

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

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

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

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

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

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

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

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

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

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

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

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

任务$1.1$的战绩榜
用户名日期总用油量远航距离所在楼层
mokey.liu2008-01-0411百度数学吧
mokey.liu2008-01-0421+1/3百度数学吧
mokey.liu2008-01-0431+1/2百度数学吧
mokey.liu2008-01-0441+11/18百度数学吧
mokey.liu2008-01-0451+32/45百度数学吧
KeyTo9のFans2008-01-2151+146/205百度数学吧
mokey.liu2008-01-0461+7/9百度数学吧
mokey.liu2008-01-0471+5/6百度数学吧
mokey.liu2008-01-0481+8/9百度数学吧
mokey.liu2008-01-0491+59/63百度数学吧
mokey.liu2008-01-04101+35/36百度数学吧
KeyTo9のFans2008-01-04101+184/189百度数学吧
cts2452005-07-2410+20/27211#
KeyTo9_Fans2009-12-1910+7/1221#
KeyTo9_Fans2017-12-1010+29/50213#
mokey.liu2008-01-04112+1/180百度数学吧
KeyTo9のFans2008-01-04112+1/108百度数学吧
KeyTo9のFans2008-01-1040+29/752+1/2思维定势吧


任务$1.2$的战绩榜
用户名日期出动飞机数远航距离总用油量所在楼层
活着才是真精彩2007-12-1631+11/184思维定势吧
59.57.133.2432007-12-1941+23/306思维定势吧
KeyTo9のFans2008-05-0741+317/4106思维定势吧
KeyTo9のFans2007-12-1951+19/218+10/21思维定势吧
KeyTo9のFans2007-12-266211+5/1411#


任务$2.1$的战绩榜
用户名日期总用油量返航距离所在楼层
胡亚峰,胡爱军,王煜航,张贤达2006-07-0122/3爱学术
戚晨皓,翟建锋,邹建宇2006-07-0122/3爱学术
戚晨皓,翟建锋,邹建宇2006-07-0135/6爱学术
戚晨皓,翟建锋,邹建宇2006-07-01411/12爱学术
戚晨皓,翟建锋,邹建宇2006-07-0151爱学术
戚晨皓,翟建锋,邹建宇2006-07-0161+1/18爱学术
戚晨皓,翟建锋,邹建宇2006-07-0171+1/10爱学术
戚晨皓,翟建锋,邹建宇2006-07-0181+29/180爱学术
戚晨皓,翟建锋,邹建宇2006-07-0191+19/90爱学术
胡亚峰,胡爱军,王煜航,张贤达2006-07-01181+1/3爱学术
戚晨皓,翟建锋,邹建宇2006-07-01181+1/3爱学术
胡亚峰,胡爱军,王煜航,张贤达2006-07-01541+2/3爱学术
戚晨皓,翟建锋,邹建宇2006-07-01541+2/3爱学术
胡亚峰,胡爱军,王煜航,张贤达2006-07-011622爱学术
戚晨皓,翟建锋,邹建宇2006-07-011622爱学术
mokey.liu2008-01-04712百度数学吧


任务$2.2$的战绩榜
用户名日期出动飞机数返航距离总用油量所在楼层


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

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

数学星空 发表于 2009-12-19 08:23:46

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

gxqcn 发表于 2009-12-20 20:25:13

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

无心人 发表于 2009-12-21 08:36:44

细想起来
很麻烦

shshsh_0510 发表于 2009-12-21 17:08:49

问题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驾
乱七八糟,不知错了没:lol

mathe 发表于 2009-12-21 18:00:27

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

KeyTo9_Fans 发表于 2009-12-22 01:41:19

5#说的是这个方案吗?



貌似一共出动14架,每架1箱油就可以了。

为什么是20架呢?

和上述方案有什么差别?

shshsh_0510 发表于 2009-12-22 09:45:12

7# KeyTo9_Fans

哦,我就是想这个意思,只不过总是算错:)
你这个图有意思,咋画的

KeyTo9_Fans 发表于 2009-12-22 17:29:35

没有在操作平台上跑一遍吗?如果跑通了就不大可能出错了。

拿gif工具一帧一帧画的。

除了第一帧,后面的直接复制粘贴,然后做点小改动。

共有116帧,做了两个小时。

不过这样做效率太低了。

所以我考虑在1楼的操作平台里添加一个功能,自动生成gif动画。

geslon 发表于 2010-1-3 11:37:48

哦,一开始觉得很简单,轻易得出共需8架飞机8个油的结论。后来发现不对了。
关键是飞机一经起飞,就必须在天上飞,不停耗油。需要把握好时间呢。
页: [1] 2
查看完整版本: 飞机加油的最佳策略设计