游遍全国,一个十一假期够吗?

2017-10-20作者:高路拓, 编著编辑:茹鑫

十一长假,我收拾行李正准备回家。学姐忽然出现了。


她兴奋地说:“小团,我决定来一次说走就走的旅行。”


我鼓掌说:“学姐好棒!你要去哪呢?”


她说:“说走就走嘛,不能有特定的目的地,但为了不留下遗憾,我决定要游完全国所有的风景名胜、名山大川,一个不漏。你帮我算算要花几天时间?”


我为难地说:“学姐你这道题好复杂,可我现在要回家了,再晚一点就赶不上火车了。”


学姐真诚地说:“对啊,那你就快点算一下嘛,别误了火车啊。”


既然学姐这么“真诚”,我就勉为其难地在赶火车之前做一个简单的计算吧。


我国有哪些风景名胜和名山大川呢?


我们登录一下国家旅游局的网站,查询出中国所有的5A级景区,假设这些景区就是学姐口中的风景名胜和名山大川,那么把这些景区放到地图上,见图1-18。



图1-18 全国5A级景点分布


可以看到,5A级景区在中国大陆的31个省市自治区都有分布,而最密集的地方有三个:北京市及其附近、江浙沪包邮国以及西安—河南西北部的中原腹地。


学姐看着图说:“很好,那你快算算玩完一圈要多久呢?”


这个问题其实是数学中经典的旅行商问题。在本题的要求下,要想通过遍历所有可能的路线来找出最优解,即使用现在世界上最快的计算机也要好多亿年才能算出来。然而我还急着赶火车呢,所以只能采用近似算法——用什么近似算法呢?


老师说过:“什么都不懂就神经网络,什么都不会就遗传算法。”


所以我决定采用遗传算法。而用遗传算法求解的基本思路如下所述。


第一步:确定目标和约束条件。


根据学姐的要求,本题的目标是“找出总游览时间最少的路线”。


而约束条件是游遍所有景点且每个景点只去一次(我猜测学姐不愿意走回头路)。


同时,考虑到学姐虽然身体很好,但是游玩也不能太累,我们又增加了一个约束条件:每天花在景点间交通和景点游览的时间总和不能超过12个小时。


学姐,我给你留了12个小时用于吃饭睡觉上厕所及其他活动。


这样,第一步就算完成了。


第二步:计算出任意两个景点之间的代价,建立代价矩阵。


在学姐给我的题目中,代价就是时间。因此,这里我们只考虑交通时间和景点游览时间。


先来看交通时间:


由于学姐是突然决定出去旅游的,而国庆期间的机票火车票早已售罄,学姐可采用的交通方式只剩下自驾这一种(正好简化了我的计算)。


如何获取两个景点之间的自驾时间呢?这就要祭出一大神器——百度地图。通过调用百度地图API,我很快地把数据准备好了。


再来看景点游览时间:


我们不妨假设每个景点至少要玩半天;而某些大型的景点,如故宫、九寨沟、张家界等,至少要玩一天。


这样,代价矩阵也就建立好了,见图1-19。



图1-19 代价矩阵


是的,学姐我知道你其实根本就不想看这个矩阵,因此我把图片调低了精度,即使你点开也是看不清楚的。


第三步:随机生成若干旅游路线,并通过变异产生新的路线,经过数次迭代逼近最优解。


第三步是遗传算法的核心。我用Python写了一小段代码来实现。


通过以上三步,我们终于计算出了最优线路,见图1-20。


这个花花绿绿的路线是什么意思呢?


不同的颜色代表我们计算出的不同旅游区域。假如我们从北京出发的话,游览路线将依次经过“红橙黄绿青蓝紫”的区域。


也就是说,先玩北京及北京周边(红)——沿着山西甘肃青海一路向西玩到新疆西藏(红-橙)——云贵川大吃大玩(橙)——海南看海(黄)——两广两湖(黄-绿)——深入中原腹地(绿)——南下闽赣(青)——江浙沪皖(青-蓝)——山东和东三省(紫)——然后回到北京。


当然,游览方向也是可以改变的。北京出发也可以选择“紫蓝青绿黄橙红”路线,即先玩东三省,最后玩内蒙古、山西,再从西路回到北京。


那么,从其他城市出发,是不是也可以采用这条路线呢?



图1-20 游览线路1


当然可以。这是一条闭合的环线,无论从哪个点出发,绕一圈都会回到原点。比如,从上海出发的路线是“蓝紫红橙黄绿青”或“青绿黄橙红紫蓝”,广州出发的路线是“黄绿青蓝紫红橙”或“橙红紫蓝青绿黄”。


学姐,无论你何时想走,从何地出发,都可以遵循这条线路。


学姐十分开心,说:“太好了小团,一会把这张路线图打印给我。对了,游览完这条路线的话,大概几天呢?”


哦,让我算一下:


根据刚才设定的算法,自驾游遍全国201个5A级景区,至少需要1436个小时,然后按照“每天交通和游览时间不超过12个小时”的条件,可折合为120天,也就是4个月。


“学姐,一场说走就走、游遍全国风景名胜名山大川且毫无遗漏的旅行只要4个月。”


学姐却并没一丝一毫的激动,她冷静地说:“小团啊,虽说这个结果挺振奋人心的,但我怎么可能有连续4个月的时间出去玩呢?假如,我每次说走就走,都是在国庆和春节期间,每次也就7天,这样的话,要多少年才能玩完呢?”


学姐的深思熟虑非常现实。然而,要在算法中实现却比较难。


好吧,那让我们再算一下。


如果我们把“从中心城市出发——游览至少一个景点——回到中心城市”视为一次旅行,那么根据学姐的最新要求,本题的约束条件将变为:


由同一中心城市出发的多次旅行,每次旅行的时间不超过7天。


虽然遗传算法对解决这个问题依然适用,却是比较低效的。为了更快地逼近最优解,我需要借鉴梯度下降法写一段小程序,放在遗传算法之前。


现在的解题思路如下所述。


第一步:生成最低效路线。


假设每次旅行只去一个景点,也就是我们需要201次旅行。这样显然是非常低效的,但同时可以帮我们去掉一些在现行约束条件下无法到达的景点。


第二步:路线合并。


随机选择一个景点,合并入其他的路线里,将旅行次数减少为200次。通过遍历,找出总时间最少的合并方案。


第三步:初始路线生成。


依此类推,将所有可能被合并的路线都合并掉。若某个方案的总时间已达到7天,不能再放进新的景点。


第四步:遗传算法优化。


将初始路线放进刚才的遗传算法里优化,得到最终结果。


假设中心城市为北京,那么最优线路见图1-21。


我们悲伤地发现,无论如何安排,想要从北京出发,七天以内自驾玩完新疆西藏的11个景点是不可能的了(注意:我们不鼓励超速驾驶和夜间驾驶)。


那么,去掉这11个景点后,学姐需要花费多少个长假,才能游遍其他所有的景点呢?


从北京出发,自驾玩完除新疆西藏以外的190个5A级景点,假如仅限每年国庆和春节出游的话,最少需要3958小时,按“每天交通和游览时间不超过12个小时”,折合下来需要:23.5年。



图1-21 游览线路2


学姐,请你慢慢努力吧,23.5年之后请告诉我你旅行胜利的消息。


我转身就要出门赶火车,但学姐拉住了我:


“自古美人如名将,不许人间见白头。杨过都等到小龙女了,我却还没遍历过我的‘男朋友’(咦,学姐你不是要去景区吗)。小团,你再算一下,要是我坐飞机、动车呢?不差钱!”


我好像明白了什么。


但我马上就要误火车了,算了,就勉为其难地简单回答一下吧。


首先,我从网上找到了省会城市之间的航班和高铁信息,然后综合考虑自驾、飞机、高铁三种交通方式,算出了任意两个景点间的最小交通时间。


学姐说:“这样不够科学吧?为什么只找省会,很多地级市之间也有飞机呀。还有普通动车你也没考虑。”


我假装没听见。


简言之,修改一下预设条件,并采用跟之前相同的算法,我们得到了如下的结果,见图1-22。



图1-22 游览线路3


假如学姐综合采用自驾、飞机、高铁等交通方式,仅限每年国庆和春节出游,不计成本,游遍全国所有5A级景区,至少也需要2597个小时,按“每天交通和游览时间不超过12个小时”的条件的话,总花费时间折合为:15.5年。


算完这个数字,我来不及管学姐了,夺门而出,一路狂奔,抢到一辆出租车,赶到了火车站,前脚踩上火车,后脚车门关闭。我深吸了一口气,决定给学姐发一条消息:


“学姐,说走就走的旅行,其实并不适合你。”


短暂的任性带来的往往是持久的悔恨,旅行并不是忽发奇想,不要着急。人们说:旅行,是一辈子的事。


我觉得这句话很有道理。


不是因为旅行这件事值得花一生去做,而是因为你没有那么多的假期。


更多干货内容关注微信公众号“书问”


内容来源:书问

作者城市数据团
出版清华大学出版社
定价69元
书籍比价

分享到

扫描二维码 ×

电子纸书

今個假期遊廣州(2012-2013最新版)

黃照康SUNNY
圓方出版社(香港)有限公司[2011] ¥26

两年假期(中文导读英文版)

儒勒·凡尔纳,王勋,纪飞 著
清华大学出版社[2009] ¥13

一个梦一个家

中共沈阳市和平区委员会, 组编
辽宁人民出版社[2016] ¥15

给你一家微企,你能赚钱吗?——创业策划

肖胜平
清华大学出版社[2014] ¥16

难道我们又要搬家吗?

李海生
清华大学出版社[2014] ¥5

雷电科学史话——你真的知道它有多危险吗

[比]克里斯汀·布克纽、王雪颖
清华大学出版社[2010] ¥6

从明天起,做一个幸福的人 : 海子经典诗选

海子
广东人民出版[2019] ¥20

一个新闻人议政实录(南振中文集)

南振中, 著
清华大学出版社[2018] ¥76

你要无可替代:一个HRD的21天进阶之旅

大白兔77赵颖 编著
北京时代华文书局[2018] ¥21

一个政治家的肖像:约瑟夫·富歇传

斯蒂芬.茨威格[奥]
万卷出版社[2015] ¥10

出版业领先的TMT平台

使用社交账号直接登陆

Copyright © 2019 BookAsk 书问   |   京ICP证160134号


注册书问

一键登录

Copyright © 2019 BookAsk 书问   |   京ICP证160134号