大数据告诉你，游遍中国需要多久

首先，来看看我国有哪些风景名胜和名山大川。

我们登录一下国家旅游局的网站，查询出中国所有的5A级景区，把这些景区放到地图上，大概长这样：

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

那么，对着地图我们来算算玩完一圈要多久?

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

老师说过：“什么都不懂就神经网络，什么都不会就遗传算法。” 36大数据（http://www.36dsj.com/）

所以我们决定采用遗传算法。而用遗传算法求解的基本思路大概是这样：

一、确定目标和约束条件 36大数据（http://www.36dsj.com/）

根据要求，本题的目标是“找出总游览时间最少的路线”。 36大数据（http://www.36dsj.com/）

而约束条件是游遍所有景点且每个景点只去一次(猜测大家都是不愿走回头路的傲娇宝宝)。

同时，考虑到大家虽然身体棒棒哒，但是游玩也不能太累，我们又增加了一个约束条件：每天花在景点间交通和景点游览的时间总和不能超过12个小时。这样，第一步就算完成了。

二、计算出任意两个景点之间的代价，建立代价矩阵 36大数据（http://www.36dsj.com/）

按照题目条件，代价就是时间。因此，这里我们只考虑交通时间和景点游览时间。

先来看交通时间：

我们先假设放浪不羁的宝宝们选择的是自驾游。

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

再来看景点游览时间：

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

这样，代价矩阵也就建立好了。这个矩阵大概长这样：

三、随机生成若干旅游路线，并通过变异产生新路线，经过数次迭代逼近最优解

要实现这三个步骤，需要写一小段代码：

简而言之，通过以上三步，我们终于计算出了如下的最优线路：

所以，这些花花绿绿的路线是什么意思呢? 36大数据（http://www.36dsj.com/）

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

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

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

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

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

也就是说，无论大家何时想走，从何地出发，都可以遵循这条线路哦。

解决了线路问题，接下来就要计算时间啦。我们先假设想到有些盆友总在路上;而有些盆友平时心系远方，只有节假日才能出去看看;我们进行了这样的分类：

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

同志们，一场说走就走、游遍全国风景名胜名山大川、且毫无遗漏的旅行只要4个月哦。

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

由同一中心城市出发的多次旅行，每次旅行的时间不超过7天。 36大数据（http://www.36dsj.com/）

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

现在的解题思路如下： 36大数据（http://www.36dsj.com/）

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

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

第二步：路线合并。

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

第三步：初始路线生成。

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

第四步：遗传算法优化。

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

假设中心城市为北京，那么最优线路如下所示：

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

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

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

看到这个结果，小科心拔凉拔凉的……世界那么大，必须得看完!所以我们还能怎么省时间呢?

嗯，有句话怎么说来着，金钱买不回时间，可是金钱可以缩短时间啊!于是我们来看看“有钱任性”地走遍中国需要多久?

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

修改一下预设条件，并采用跟之前相同的算法，我们得到了如下的结果：

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

嗯，怪不得人们说：“旅行，是一辈子的事”。

End.