人们不会知道一个过时的玩意会在何时又重新焕发活力。近日谷歌推出一款新 App：Google Trips，它可以帮你在某个陌生的城市度过「完美的一天」。令人惊奇的不是 Google Trips，而是这个 App 中的算法，该算法已经有 280 年的历史了。所以算法工程很有趣，因为它不会真的过时。
事情还得从 1736 年说起，当年 Leonhard Euler，就是那个欧拉，写下了一篇简洁优美的数学论文，论文是关于 Königsberg 小镇和镇上 7 座桥的，如下图：
在这篇论文中，欧拉研究了这么几个问题：是否有可能一次穿过城市的每一座桥？事实证明，对于 Königsberg 来说，不能。为了找到这个答案，欧拉写出了一个理论来表示某块陆地（landmass）和陆地上的桥之间的布局问题，也就是著名的柯尼斯堡七桥问题，他把这个问题称为 Geometriam Situs（即，「Geometry of Place」），这个问题是图论的起源。他把每块陆地（landmass）看成图上的一个「奇点」，每座桥作为一条「边」，就像下面这样：
欧拉发现如果当且仅当连接图上所有奇点的边的条数是偶数时（这样的图被命名为「欧拉回路」），可以一次经过图上所有的边。记住这条定理，下面所说的都和它有关。
我们小组是谷歌研究中的一员，我们对「Geometry of Place」着迷了好一段时间，于是我们开始研究一个与欧拉问题相关的问题：不仅仅是过桥的问题，我们怎么才能在特定的路线中到访更多的地点？我称之为「行程」问题。欧拉没有研究这个问题，但这是一个著名的优化问题，也被称为「定向运动」问题。
虽然欧拉的问题有一个精确有效的解法，但行程问题却没那么简单，想要近似解决都很难！难就难在两个相互冲突的目标：首先，我们要选择著名的景点参观。但是第二，我们挑选的景点应该能用一个完美的路线串联起来，这个路线不要花太多时间；不能到达某个景点时它关门了，等等。这个问题的挑战是找到高效路线，它通常被称为旅行推销员问题（Travelling Salesman Problem，TSP）
旅行行程的算法
幸运的是，现实世界中有一个定理叫做「三角不等式」，也就是说在路线中每多加一个点，并不会缩短路线。满足三角形不等式时，这个 TSP 问题就能使用 Christofides 在 1976 年开发的算法近似解开。这我们的解法中的重要组成部分，它基于欧拉的论文，所以我们在这里给出一个快速四步介绍来展示它的原理：
我们从所有分散的目的地开始，反复连接相邻最近的两个还未连接的目的地。这虽然无法形成一条线路，但是它可以将所有目的地连接成一个最小生成树（minimum spanning tree）图
我们找出这个最小生成树图上所有的拥有奇数连接边（欧拉的证明中边的数量必须是偶数）的目的地，然后仔细的将它们配对。
现在所有的目的地的连接线都是偶数了，于是我们就得出了一幅欧拉回路图，因此我们就画出了一条一次通过所有边的欧拉回路图。
现在我们有了一条很棒的路线，但是在这条线路中，有些点可能要不止经过一次。别担心，我们找到了任意一个需要两次通过的点，只要绕过它就行了，直接从一个地点去下一个地点。
Christofides 给出了一个优雅的证明，最终的线路总是尽可能最短。这里有个 Christofide 算法的例子，位置图上的奇点表示地点，标有成本的边表示两个地点之间的行程时间。
有了这个寻找路径的子路线，我们现在可以开始规划一次不重复地通过所有地点的行程了。每一步，我们都要估算出对用户有利的下一个可能的新目的地，并用 Christofides 算法估算出成本。用户的利益包括一系列自然因素，比如景点的热门度，某一景点与用户在行程中已经到达的景点有什么不同。然后我们选择那个在每一个额外成本上都有最佳效益的新景点（例如，包括在行程中新景点所需的时间）。这里有个例子，是我们的算法用上面的位置图规划出的伦敦行程：
Google Trip 中的行程路线
有了行程路线问题的第一个近似解法后，我们开始和 Google Trip 小组的同事合作，我们意识到我们只是触及了问题的皮毛。比如，即便我们给出了几乎完美的行程路线，任何一个用户都非常合理地说，「太棒了，但是我所有的朋友都会说，我还要去别的景点。还有，我只有上午有时间，但我不想错过你行程单上被安排在下午的景点。而且大笨钟我已经去过两次了。」所以我们并没有一次完成这个线路行程规划问题，也不会叫它「完美的一天」，我们需要一个快速的行程路线动态算法，让用户可以在飞机上修改路线以适应个人需求。因为很多人在旅行时都会遇上信号不好的情况，所以在信号不好的情况下，也要让用户能用上这个 App。
好行程路线来自于群众智慧
虽然这个问题在算法方面的挑战很高，但我们也认识到生成高质量 的行程线路仅仅依赖于我们所理解的许多个可能的停留景点。我们用谷歌的扩展旅行数据库来找出好玩的景点，谷歌的一些关于从任意一个地方到另一地方的系统，我们从这些系统中也获取了大量的数据。但是我们还是不太知道热门的景点有哪些。
为了解决这个问题，我向群众智慧求助。谷歌也用这个办法来估算过高速公路上的堵车点，以及找到餐馆最忙的时间段。这里，我们使用同样技巧来了解普遍的游览次序，让后将感觉不错的编进我们的用户行程路线中。我们将谷歌的景点热门时间的知识与这些景点之间的方向结合起来，想出游客在旅行时喜欢做什么。
未来我们还会用到更多的群众智慧。例如，我们注意到白金汉宫的游览高峰时间大约是在 11:30，而且游客这个时间段的停留时间要比其他时间段长。我们不太理解为什么会出现这种情况，但是当我们仔细研究时，才明白这正好是卫兵换班的时间。我们现在也会把这种时间信息编进形成路线选择算法中了。
