|||
骆驼运香蕉问题(140714)
闵应骅
计算机科学要研究算法,有过程的问题、优化的问题、复杂性的问题等等。这些问题常常可以用很通俗的语言表达出来,而其含义却很深远。譬如,货郎担问题、八皇后问题、邦占廷将军问题都是这样。北大毕业的才子洪加威(1936-,现在美国,参见http://blog.sina.com.cn/s/blog_45de2bb30101hebn.html)在国际会议上提出三个中国人问题,以祖父、父亲、儿子三个中国人在迷宫里怎样机智地确定有没有回路的形象比喻,首次在世界上提出关于决定性空间完全性问题。所以,不要认为这些通俗的说法不起眼,可能恰恰是说明了问题的本质。
上周美国天普大学吴杰教授访问中科院计算所,点名要见我。我与他的联系已经30年了。上世纪80年代,承他邀请,我访问过他的大学,并在他家面临着湖的院子里为我举办了家庭派对。此后,我们联系很多。他是龙星计划创始人之一,第一批龙星计划特邀教授来华讲课。这次,他来做了一个报告,其中提到了一个骆驼运香蕉的问题。banana-eating camel problem在百度里被自动翻译成“香蕉吃骆驼的问题”,可笑不可笑!自动翻译真不可信。至少也应该翻成“吃着香蕉的骆驼”吧!但这问题还是很有意思,听说外企招聘面试的时候还提过这样的问题。特转述如下。
想当初,一个沙漠地区的农民收获了3000香蕉,要送到1000英里以外的市场去卖。他只有一头骆驼,这骆驼一次最多驼1000个香蕉,而且每走1英里就要吃掉1个香蕉。那么,他最多能送多少香蕉到市场呢?很显然,如果一直走下去,到终点,香蕉也就吃光了,一个也不剩。所以,需要在路中间停下,存一些香蕉,下次来补上已经吃掉的。
这问题的解如下图所示,是这样的:骆驼首先驼1000香蕉出发,走了200英里,撂下600香蕉往回走。再取1000香蕉出发,到了Store1,检起200香蕉继续走,到533英里处,撂下333香蕉往回走,到200英里处,再检200香蕉回到原地。再取1000香蕉出发,在200英里处检起200香蕉往前走,到533英里处,再检起那333香蕉往前走。这时,它还有1000香蕉。再走467英里到了市场,还剩1000-467=533香蕉。所以,骆驼最多只能送533香蕉到市场。
你能证明这是最优解吗?200和1000/3这两个数是怎么出来的?想一想,也许有点意思。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-27 07:44
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社