Google Trips与七桥问题算法

[dropcap]9[/dropcap]月12日,Google发布了Google Trips,接着Google research也发布了一篇文章《The 280-Year-Old Algorithm Inside Google Trips》,我看到国内几个网站也转载了,但没有进一步分析。现在我尝试以通俗的语言解释一下Google Trips中与7桥问题相关的一个路径规划算法。

Google Trips,顾名思义,帮你规划旅程的。其中一个算法源自于280年前的“七桥算法(Seven Bridges of Königsberg)”。

1736年,Leonhard Euler(说欧拉估计大家都知道)解决了七桥问题:不可能一次性不重复地走遍下图中7座桥。
konigsberg_bridges
他还进行了推论:[highlight]如果所有结点都拥有偶数线,就存在一次性不重复地走完的路线。[/highlight]下图中ABCD就是结点,结点之间为连线,如图中A结点连线数目为5,为奇数,而D结点连线是3,为奇数。
seven
我们可以把ABCD想象成目的地,而连线看做是目的地之间的路线。Google Trips工程师们的问题是:如何一次性尽可能多地游览景点?这个问题和欧拉问题不同之处在于,它需要解决两个冲突:首先是[highlight] 我们需要选择想要参观哪些景点 ;其次我们有一些决策原则,如不能花太多时间,不要在到景点发现关门了等等。[/highlight]

有个类似的问题被称为Travelling Salesman Problem (TSP),给定若干城市和城市两两之间的距离,有没有最短路径能够不重复地经过所有城市并回到出发的城市?大家注意这里有距离信息,我们都知道三角形两边之和大于第三边,再结合Christofides算法就能解决TSP问题。

这里有必要详细描述一下Christofides算法,根据三角形两边之和大于第三边定律,三个顶点u, v和x, 一定是w(uv) + w(vx) ≥ w(ux)。

[pullquote-left]“设G = (V,w),其中G表示包含若干顶点的图形,V表示顶点,w函数为G图形中连线的权重。”[/pullquote-left]

该算法具体步骤如下:
1. 创建G的最小生成树(minimum spanning tree)T。
2. 设O为T中含奇数度(也就是奇数连线)的顶点集。根据握手定理,O有偶数顶点。
3. 找到O中最小权重M。
4. 结合M和T生成H,H中每个顶点有偶数度。
5. 在H中生成Eulerian circuit ,其实就是我们之前提到的七桥问题的推论。
6. 对步骤5中重复的顶点去掉,生成Hamiltonian path

看起来很复杂的样子,没事,我们只要知道个大概就行,接下来看看Google怎么做的。
1. 将距离近的两点相连,这就创建了最小生成树。
2. 找到奇数连线的节点,将它们配对,此时所有节点都有偶数连线,所以我们创建了Eulerian Graph。
3. 对步骤2中的路线进行修正,有重复节点的话直接略过。

GIF

123%e4%b8%83%e6%a1%a5png

4567%e4%b8%83%e6%a1%a5png

这篇文章还给了一个例子,不过我觉得它例子中的算法是错误的。我已经在原文和推特上留言,还有quora上提问,没人回复我。等回复了我再更新此文。

发表评论

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