最少换乘、最少用时......导航一秒帮你规划路线是怎么做到的？
2020/11/2 17:00:00 中国科普博览

    

     你现在在徐家汇，你想坐地铁去南京东路外滩。你习惯性地拿出手机导航，地图APP在0.1秒内为你找出了各种方案，有最短距离的，最省时间的，最少换乘的，请问它是怎么做到的？

     其实在250年前，人们就已经思考这个问题了。在俄罗斯柯尼斯堡，有一条河叫普莱格尔河，河上有两座湖心岛，七座桥把岛和两岸连在一起。有人突发奇想能不能把这七座桥从头到尾走一遍，并且不重复。试试吧，你肯定做不到。这就是历史上著名的七桥问题。 数学家欧拉证明确实不行。上岛下岛，有进必有出。也就是说每个点都要连接偶数线，才能保证不重复经过。我们可以数一数，两座湖心岛和两岸连接的线段数分别是5 3 3，全部是奇数，所以这个问题不可能有解。 1736年，欧拉发表了《一笔画定理》，一个图形要能一笔画完成必须符合两个条件：第一，图形是封闭联通的；第二，所有的交叉点都是偶数条线路，或者奇数条线路的点最多不超过2个。 七桥问题和坐地铁有什么关系呢？这要从七桥问题发展出的图论学科说起了。凡是构成网络的结构问题，都可以用图论解决。我们的地铁系统就是非常典型的网络结构图，我们最开始的问题也可以用图论中的最短路径算法——狄克斯特拉算法来解答。首先数一下你只坐一站能到达哪些站，再数一下经过两站路能到达哪些站，以此类推，直到数到你的目标地铁站，这时就得出了一条最短路径。这个算法虽然简单，但一旦地铁节点过多，靠人工就算不出来了，只能靠电脑计算。 图论在生活中有非常广泛的应用。比如有人网上冲浪通过相关用户推荐，抓到了伴侣出轨的对象。当然图论还可以应用在更加严肃正经的场合，比如在竞技体育中，图论可以轻松处理循环赛的结果；还可以辅助规划城市公共服务设施，比如医院、学校、消防局等等，如何分布建设才能以最低的成本满足最大的需要，这些都可以用图论的方法解决。

     出品：科普中国

     制作：科影纪监制：中国科学院计算机网络信息中心(本文中标明来源的图片已获得授权)

     文章仅代表作者观点，不代表中国科普博览立场本文来源于”中国科普博览“公众号(kepubolan)，转载请注明公众号出处

    

    

    

    

    

    

    

    转载注明出处 未经授权不得转载转载授权、合作、投稿事宜，联系webmaster@kepu.net.cn

     中国科普博览是中科院科普云平台，由中科院计算机网络信息中心主办，依托中科院高端科学资源，致力于传播前沿科学知识，提供趣味科教服务。

    点这里告诉我你在看

    

    http://weixin.100md.com
返回 中国科普博览 返回首页 返回百拇医药