【算法揭秘】Google Trips中存在了280年的古老算法揭秘

算法工程比较有意思的地方在于它永远不过时，不知道什么时候比较古老但是比较有用的算法可能会在我们的设计中体现，昨天，google发布了它的google trips, 一个新的app帮助你创建你在城市中的非常不错的行程。而这个算法确实在280年之前就已经被论证过的。

1736年，欧拉发表了著名的有关柯尼斯堡的七座桥的著名论文，七座桥问题，如下：
image_01

在这篇论文中，欧拉研究了以下问题：能否旅行者所有桥只走一次就能够逛遍整所城市（大陆被七座桥隔开）？最后论文给出了结果，对于柯尼斯堡这个城市来说来说，不能。为了证明，欧拉提出了一种所谓的位置几何学的概念也就是后来发展出来的图论。论文中，所有的城市的大陆部分被桥分割称之为节点，而跨越大陆的桥则被称为边。如下图：

image_02

欧拉发现存在这种路径的充要条件是所有的节点都必须有偶数的边。只有在这种条件下，才存在一个穿越所有大陆连接，所有的桥只走一次；基于以上的发现，我们将它应用在了了google trips当中。

我们团队关于这种位置几何学的理论研究过了一阵子，后来我们的研究方向是根据欧拉的理论我们能否让旅行者尽可能的走边所有的地方，这种问题就是现在的“行程规划”问题。有关这种问题，欧拉没有研究过，但是基于欧拉的灵感，我们把它称为定向工程问题。

继续阅读请点击：http://click.aliyun.com/m/9169/