文档章节

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

云栖运营小编
 云栖运营小编
发布于 2017/01/10 15:31
字数 739
阅读 2
收藏 0

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

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

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

image_02

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

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

欧拉的解是完美的并且非常的正确,可是有关行程规划确实比较头痛,因为它不存在完美的解决方案,只能找到尽可能接近完美的解决方式。主要在于,有两个维度是有矛盾的地方:比如说要参观比较好的景点,但是时间的安排上确需要最节省;其次还需要考虑去的景点不要关门,要考虑到关门时间;甚至比如不要逛太多的博物馆(没人会喜欢连续的玩博物馆)。如此增加如此多的约束的问题都被归结为“旅行商”问题。

本文转载自:http://click.aliyun.com/m/9169/

云栖运营小编
粉丝 7
博文 98
码字总数 52676
作品 0
朝阳
运营/编辑
私信 提问
Google Trips更省流量的同时,大数据“窃取”隐私成双刃剑

  Google Maps一直以准确、便利著称,是人们外出旅行不可缺少的帮手。但人们在使用过程中也发现了它的不少缺点和不便之处,如路线规划不简便、离线信息不准确等。现在Google为出国旅行的人...

大数据头条
2018/01/03
0
0
楼层的 SVG 编辑器 - trips-editor

楼层的空间拓扑关系是我们算法的关键输入之一,但很难生成或提取。在许多情况下,我们只能得到平面图的位图图像。有一些复杂的工具,如Microsoft Visio或Inkscape,可以加载图像文件并根据图...

匿名
05/16
515
0
若可以只教++部分, 不教C部分, 那C++会是很好的教学语言

专栏 | 九章算法 网址 | www.jiuzhang.com 01 关于C和C++ 如果我们可以只教++部分不教C部分,那C++会是很好的教学语言。 C++在编程语言的历史上有一定地位,就像卡里古拉在罗马帝国历史上有他...

2017/12/25
0
0
Google面试题 | 循环字符串里面的独立子串

专栏 | 九章算法 网址 | www.jiuzhang.com 题目描述 假设s是一个无限循环的字符串”abcdefghijklmnopqrstuvwxyz”,s就是一个”...zabcdefghijklmnopqrstuvwxyza...”这样的字符串,现在给你...

九章算法
2017/11/09
0
0
周末了放松一下 | 程序员才看得懂的笑话

专栏 | 九章算法 网址 | www.jiuzhang.com Reddit的幽默社区的程序员们卯足了力气要想出他们能想到的最好笑的编程妙语,规则只有一条:笑话必须是严格的开发人员的俏皮话。 Hi,我想听个TCP...

九章算法
2017/12/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

PostgreSQL 11.3 locking

rudi
今天
5
0
Mybatis Plus sql注入器

一、继承AbstractMethod /** * @author beth * @data 2019-10-23 20:39 */public class DeleteAllMethod extends AbstractMethod { @Override public MappedStatement injectMap......

一个yuanbeth
今天
10
1
一次写shell脚本的经历记录——特殊字符惹的祸

本文首发于微信公众号“我的小碗汤”,扫码文末二维码即可关注,欢迎一起交流! redis在容器化的过程中,涉及到纵向扩pod实例cpu、内存以及redis实例的maxmemory值,statefulset管理的pod需要...

码农实战
今天
4
0
为什么阿里巴巴Java开发手册中不建议在循环体中使用+进行字符串拼接?

之前在阅读《阿里巴巴Java开发手册》时,发现有一条是关于循环体中字符串拼接的建议,具体内容如下: 那么我们首先来用例子来看看在循环体中用 + 或者用 StringBuilder 进行字符串拼接的效率...

武培轩
今天
8
0
队列-链式(c/c++实现)

队列是在线性表功能稍作修改形成的,在生活中排队是不能插队的吧,先排队先得到对待,慢来得排在最后面,这样来就形成了”先进先出“的队列。作用就是通过伟大的程序员来实现算法解决现实生活...

白客C
今天
81
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部