`

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

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

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

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

image_02

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

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

继续阅读请点击:http://click.aliyun.com/m/9169/
分享到:
评论

相关推荐

    trips协议中文版.pdf

    该协议于1994年在乌拉圭轮谈判中签署,并于1995年生效。 TRIPS协议的主要内容包括: 一、一般规定和基本原则 * 确定了知识产权的定义和范围 * 确定了缔约方的义务和责任 * 确定了与贸易有关的知识产权的保护和...

    trips_协议中文版.doc

    《TRIPS协议中文版》是世界贸易组织(WTO)成员之间签署的一项关于知识产权的国际协议,全称为《与贸易有关的知识产权协议》。该协议旨在制定统一的知识产权保护标准,确保成员国之间的公平贸易,同时考虑各国不同的...

    TRIPS协议视角下司法保护论文.doc

    《TRIPS协议视角下司法保护论文》探讨了世界贸易组织(WTO)的《与贸易有关的知识产权协定》(TRIPS)对成员国知识产权司法保护的影响和挑战。TRIPS协议是国际知识产权保护的重要框架,旨在确保各成员国对知识产权的...

    和贸易有关的知识产权协议(TRIPS)中英文版本.doc

    《与贸易有关的知识产权协议》(TRIPS)是世界贸易组织(WTO)的一项核心协议,旨在协调全球各国的知识产权法律和政策,确保国际间知识产权的保护和执行达到一定标准。该协议涵盖了版权和相关权利、商标、地理标志、...

    转车 换乘 SQL算法

    在SQL的世界里,"转车 换乘 SQL算法"通常指的是解决多表查询和连接问题,特别是涉及路径查找或最短路径计算的场景。在公共交通系统中,乘客可能需要通过多个交通工具(如公交、地铁)来完成旅程,这就涉及到如何高效...

    trips 协议中文版.doc

    该协议于1994年在乌拉圭回合贸易谈判中签订,并于1995年生效。 一般规定和基本原则 TRIPS协议的目的是消除国际贸易中的扭曲和阻碍,确保知识产权的充分和有效保护,并促进合法贸易的发展。该协议的基本原则包括: ...

    TRIPS - A subtree mining algorithm-开源

    TRIPS(Tree-based Pattern Mining using an Iterative Reduction Process in Subtrees)是一种用于挖掘树状数据结构中频繁子树的算法。在数据挖掘领域,树结构数据常见于许多应用,如XML文档、网络日志、语义网络等...

    论文研究-TRIPS-plus条款下平行进口与价格补贴政策协调研究.pdf

    为使发展中国家有效应对TRIPS-plus条款, 本文通过构建多阶段博弈模型, 在Acharyya等[1-2]的基础上将企业创新能力视为内生变量, 分别从发达国家与发展中国家的角度分析TRIPS-plus条款实施前后两国福利水平, 阐述实施...

    论文研究 - 孟加拉国的知识产权保护:对TRIPS的响应程度如何?

    孟加拉国在这方面的努力并非微不足道,因为作为WTO世贸组织成员,孟加拉国迫切需要从2013年7月1日开始使其知识产权制度对TRIPS作出回应,到2021年。在这种环境下,本文力求解决简要介绍了孟加拉国如何实施知识产权...

    TRIPS_与贸易有关的知识产权协定中英文对照.docx

    《TRIPS协定》全称为“与贸易有关的知识产权协定”,是1994年4月15日在摩洛哥马拉喀什签署的世界贸易组织(WTO)成立协议的一部分,附件1C。该协定旨在规范各成员国对知识产权的保护,确保全球贸易的公平性和透明度...

    PyPI 官网下载 | django-trips-0.2.7.tar.gz

    标题中的"PyPI 官网下载 | django-trips-0.2.7.tar.gz"指出这是一个在Python Package Index (PyPI) 上发布的软件包。PyPI是Python开发者分享和分发自己创建的库和模块的主要平台。这个特定的包名为`django-trips-...

    trips 协议中文版汇编.docx

    trips 协议中文版汇编.docx

    An efficient ensemble pruning algorithm using One-Path and Two-Trips searching approach

    一路径两趟搜索算法(OPTT)在修剪速度上非常快,而且在实验中显示出其分类性能与EnPBT算法没有显著差异,从而在修剪有效性和效率之间取得了适当的平衡。该算法通过限制搜索空间来加快修剪过程,同时确保没有对最终...

    TRIPS下知识产权的完善诠释.doc

    TRIPS下知识产权的完善诠释.doc

    SiouxFalls_网络辅助源txt文件.rar

    总结来说,这个压缩包提供的数据和算法是解决SiouxFalls地区交通配流问题的重要工具,通过Frank-Wolfe算法,我们可以从SiouxFalls_trips_1.txt和SiouxFalls_net_1.txt这两个文本文件中获取出行需求和网络结构,进而...

    Taxi_Trips_-_2024_20240408.csv

    Taxi_Trips_-_2024_20240408.csv

    PSA Trips:TRIPS 文件管理和转换工具-开源

    .trips 文件是 PSA-group 汽车日志系统中特有的数据记录格式,它包含了车辆在运行过程中的各种信息,如发动机状态、驾驶行为、故障代码等。这些数据对于诊断车辆问题、优化性能、提高安全性以及进行故障预防具有重要...

Global site tag (gtag.js) - Google Analytics