讯享网

 <p id="34V26V3T">时隔近70年，那个用来解决最短路径问题的经典算法——Dijkstra，现在有了新突破：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1102%2Fa9j00smasqd00ard000np00dcp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p id="34V26V41">什么意思？</p><p id="34V26V43">这就意味着不论它面对多复杂的图结构，即便在最坏情况下都能达到理论上的最优性能！</p><p id="34V26V45">而且这还是学术界首次将这一概念应用于任何序列算法。</p><p id="34V26V47">对于Dijkstra算法，想必很多人肯定不会陌生，毕竟它是每个计算机本科生必学的内容。</p><p id="34V26V49">而且从它诞生至今，已经在广泛地应用于我们的日常生活中，例如在谷歌地图、苹果地图，Dijkstra算法就被用来计算从用户当前位置到目的地的最优路线。</p><p id="34V26V4B">在计算机网络中，被广泛应用于路由协议中；例如开放最短路径优先（OSPF）协议就是基于Dijkstra算法来计算网络中数据包的最优传输路径。</p><p id="34V26V4D">再如通信网络设计、机器人路径规划和物流运输优化等领域，也是处处都有它的身影。</p><p id="34V26V4F">（相关教程可参考：https://www.youtube.com/watch?v=EFg3u_E6eHU）</p><p id="34V26V4H">而这项集结了苏黎世联邦理工、CMU、普林斯顿等顶尖高校科研人员之力的研究，一举让这个经典算法达到了前所未有的高度。</p><p id="34V26V4J">哥伦比亚大学计算机科学家Tim Roughgarden在看完论文后直呼：</p><p id="34V26V4L">据悉，这篇论文已经斩获下周即将举办的理论计算机顶会FOCS 2024（计算机科学基础研讨会）的**论文。</p><p id="34V26V4N">一言蔽之，现在的Dijkstra算法，已经被证明是解决单源最短路径问题的“近乎理想”的方法。</p><p id="34V26V4P">那么这项研究又是如何证明和优化的呢？</p><p id="34V26V4R">首先，我们先通过一个例子，简单回顾一下Dijkstra算法。</p><p id="34V26V4T">如下图所示，Dijkstra算法寻找最短路径的方法，大致可以分为四步：</p><p id="34V26V4V">最终，Dijkstra算法可以快速找到网络中从起始点到其他所有节点的最短路径。</p><p id="34V26V51">在最初的Dijkstra算法论文中使用到了一个简单且关键的数据结构——堆（Heap），而这就为后来的计算机科学家们留下了改进的余地。</p><p id="34V26V53">例如1984年，两位计算机科学家设计了一种巧妙的堆数据结构，使得Dijkstra算法在解决单源最短路径问题所需的时间上达到了理论极限或“下限”。</p><p id="34V26V55">从某种特定意义上说，这个版本的Dijkstra算法已经可以说是最好的，也是近40年来的一种“标准”。</p><p id="34V26V57">而这次的最新论文，研究人员的突破口依旧是这个堆数据结构。</p><p id="34V26V59">因为他们发现，像Fibonacci堆等常用的数据结构虽然在理论上具有较好的最坏情况时间复杂度（Worst-case time complexity），但在很多情况下未能充分利用图的局部结构特性。</p><p id="34V26V5B">这就导致在处理某些类型的图时，仍然需要高昂的计算代价。</p><p id="34V26V5D">但如果在1984年设计的堆基础上加入对最近插入项快速访问的能力，就可以显著提升算法的效率。</p><p id="34V26V5F">为此，研究人员提出了一种全新的堆数据结构——具备特殊的 “工作集属性”（Working Set Property） 。</p><p id="34V26V5H">所谓 “工作集属性” ，指的是堆能够充分利用操作的局部性，从而优先处理最近插入的元素，降低提取最小元素的成本。</p><p id="34V26V5J">这个概念类似于我们在管理待办事项时，会优先处理那些刚刚添加的紧急任务，从而更高效地完成工作。</p><p id="34V26V5L">若是用公式化的表述，就如下图所示。</p><p id="34V26V5N">对于在堆中插入并随后被提取的任意元素x，其工作集Wx包括了在x**入后、在x被提取前插入的所有元素，以及x本身。</p><p id="34V26V5P">借助这种“工作集属性”，新设计的堆数据结构能够显著提升Dijkstra算法的整体性能，尤其是在具有局部性特征的图上。</p><p id="34V26V5R">也成功使Dijkstra算法具备了普遍最优性，不仅在最坏情况下具有最优性，还能在任何图结构上表现出色。</p><p id="34V26V5T">不仅如此，这项工作还提供了精确的复杂度分析。</p><p id="34V26V5V">例如，作者证明了Dijkstra算法在具有工作集属性的堆上的比较次数是O(OPTQ(G)+n+max⁡w∈WG∣FG,w∣)。</p><p id="34V26V61">其中，OPTQ(G)是解决距离排序问题的最优算法所需的比较次数，n是顶点数，∣FG,w∣是前向边的数量。</p><p id="34V26V63">这也为算法的性能提供了更精确的界限。</p><p id="34V26V65">总而言之，这些成果不仅推动了图算法的研究，也为实际应用中的算法设计提供了新的视角和工具。</p><p id="34V26V67">关于Dijkstra算法诞生的故事，其实是始于一次意外的灵感。</p><p id="34V26V69">1956年，年仅26岁的荷兰计算机科学家Edsger Dijkstra当时正试图为一台新型计算机ARMAC编写一个程序，来展示它的计算能力。</p><p id="34V26V6B">有一天，他和未婚妻在阿姆斯特丹购物时走进了一家咖啡馆，正是在休息的片刻中，Dijkstra突然有了灵感，想出了一个计算最短路径的算法。</p><p id="34V26V6D">在没有纸和笔的情况下，他花了大约20分钟在脑海中推演出了这个算法的细节。</p><p id="34V26V6F">正如他在晚年一次采访中所说的那样：</p><p id="34V26V6H">也正是这种简洁和优雅，使得Dijkstra算法在随后的几十年里成为计算机科学领域的经典。</p><p id="34V26V6J">Edsger Dijkstra可以说是一位极具影响力的计算机科学家，他不仅以其最短路径算法闻名，还对计算机科学的许多基础领域做出了开创性的贡献。</p><p id="34V26V6L">Dijkstra出生于1930年，父亲是一位化学家，母亲是一位出色的数学家。</p><p id="34V26V6N">1951 年，Dijkstra在父亲的建议下前往剑桥参加了一门为期三周的编程课程，这次经历改变了他的职业轨迹。</p><p id="34V26V6P">在此期间，他遇到了著名的数学家和计算机科学家Adriaan van Wijngaarden，并由此获得了在阿姆斯特丹数学中心（Mathematical Centre）的工作机会。</p><p id="34V26V6R">Dijkstra是荷兰首位以“程序员”身份被雇佣的人，1956年完成学业后，他继续在数学中心工作，并于1959年发表了他的著名论文A Note on Two Problems in Connexion with Graphs。</p><p id="34V26V6T">这篇论文介绍了他提出的最短路径算法，后来成为了计算机科学中引用次数最多的论文之一。</p><p id="34V26V6V">尽管Dijkstra的算法十分优雅，但当时几乎没有计算机科学期刊，发表过程十分困难，最终他选择将其发表于新创刊Numerische Mathematik上。</p><p id="34V26V71">Dijkstra在职业生涯中赢得了极高的声誉，并于1972年获得计算机科学领域最负盛名的图灵奖。</p><p id="34V26V73">他不仅在编程语言、操作系统和并发控制等领域做出了许多基础性贡献，还以其对编程方法学的深入思考而著称。</p><p id="34V26V75">他强调程序的正确性，认为程序应该从一开始就正确地设计，而不是通过调试来达到正确。</p><p id="34V26V77">不过与此同时，Dijkstra的性格也非常独特，他既被赞赏也被批评，是一位充满争议的人物。</p><p id="34V26V79">他对于计算机科学的教育和研究有着强烈的观点，常常发表极具挑战性的言论。</p><p id="34V26V7B">例如，他反对使用goto语句，并在1968年发表了著名的文章Go To Statement Considered Harmful，这篇文章引发了广泛的争议，但最终他的观点得到了普遍认可。</p><p id="34V26V7D">Dijkstra算法不仅可以计算从起始点到一个目的地的最短路径，还可以给出从起始点到所有其他节点的排序，这正是单源最短路径问题的解决方案。</p><p id="34V26V7F">文章转载:[aim.share.shareinglight.com）</p><p id="34V26V7H">它的核心思想是不断探索当前距离最短的路径，更新每个节点的最短距离，直到所有节点的距离都确定下来。</p><p id="34V26V7J">文章转载:[aim.share.lhcyxx.com）</p><p id="34V26V7L">这种算法的简洁性和高效性使得它成为经典的路径规划工具。</p><p id="34V26V7N">文章转载:[aim.share.kapin.net）</p><p id="34V26V7P">麻省理工学院的计算机科学家Erik Demaine曾评论道：</p><p id="34V26V7R">文章转载:[aim.share.boxchat.net）</p><p id="34V26V7T">但算法的成功不仅归功于其核心思想，还离不开数据结构的选择，在几十年的发展中，研究人员不断改进堆数据结构，使得算法的整体性能不断提升。</p><p id="34V26V7V">文章转载:[aim.share.gemmglam.com）</p><p id="34V26V81">而这一次，改良堆数据结构，可以说是再次立功了。</p><p id="34V26V83">文章转载:[aim.share.1awnings.com）</p><p id="34V26V85">论文地址：https://arxiv.org/abs/2311.11793</p><p id="34V26V87">文章转载:[aim.share.jerabski.com）</p><p id="34V26V89">参考链接：[1]https://www.quantamagazine.org/computer-scientists-establish-the-best-way-to-traverse-a-graph-/[2]https://inference-review.com/article/the-man-who-carried-computer-science-on-his-shoulders</p><p id="34V26V8B">文章转载:[aim.share.7oria.net）</p>