业界 | 谷歌发布Google Trips:用280年前的算法规划完美行程路线


选自Google Research

机器之心编译 

作者:Bogdan Arsintescu、Sreenivas Gollapudi、Kostas Kollias、Tamas Sarlos、Andrew Tomkins

参与:杜夏德

人们不会知道一个过时的玩意会在何时又重新焕发活力。昨天谷歌推出一款新 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,而且游客这个时间段的停留时间要比其他时间段长。我们不太理解为什么会出现这种情况,但是当我们仔细研究时,才明白这正好是卫兵换班的时间。我们现在也会把这种时间信息编进形成路线选择算法中了。

    来源:https://research.googleblog.com/2016/09/the-280-year-old-algorithm-inside.html

    ©本文由机器之心编译,转载请联系本公众号获得授权。

    ✄————————————————

    加入机器之心(全职记者/实习生):hr@almosthuman.cn

    投稿或寻求报道:editor@almosthuman.cn

    广告&商务合作:bd@almosthuman.cn

    看过本文的人还看过

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注