https://www.qbitai.com/2024/10/212282.html 十三 本科经典演算法Dijkstra，证明是普遍最优了：最坏情况性能也最优！ FOCS'24最佳论文 时隔近 70年 ，那个用来解决 最短路径问题 的经典演算法── Dijkstra ，现在有了新 突破： 被证明具有普遍最优性（Universal Optimality）。 什麽意思？ 这意味着不论它面对多复杂的图结构，即便在 最坏情况下都能达到理论上的最优性能！ 而这还是学术界 首次 将此概念应用於任何序列演算法。 。 对於Dijkstra演算法，想必很多人肯定不会陌生，毕竟它是每个电脑 本科生必学 的内容 。 而且从它诞生至今，已经在广泛地应用於我们的日常生活中，例如在 谷歌地图 、 苹果 地图 ，Dijkstra演算法就被用来计算从用户当前位置到目的地的最优路线。 在电脑网路中，被广泛应用於 路由协定 中；例如开放最短路径优先（OSPF）协定就是基 於Dijkstra演算法来计算网路中资料包的最优传输路径。 再如 通讯网路设计 、 机器人路径规划 和 物流运输优化 等领域，也是处处都有它的身 影。 （相关教学可参考：https://www.youtube.com/watch?v=EFg3u_E6eHU） 而这项集结了苏黎世联邦理工、CMU、普林斯顿等顶尖高校科研人员之力的研究，一举让 这个经典演算法达到了前所未有的高度。 哥伦比亚大学电脑科学家Tim Roughgarden看完论文後直呼： 这也太神奇了，我无法想像还有比这更吸引人的研究。 据悉，这篇论文已经斩获下周即将举办的 理论计算机顶会FOCS 2024 （计算机科学基础 研讨会）的 最佳论文 。 一言蔽之，现在的Dijkstra演算法，已经被证明是解决单源最短路径问题的「近乎理想」 的方法。 那麽这项研究又是如何证明和优化的呢？ 70年经典演算法新突破 首先，我们先透过一个例子，简单回顾一下Dijkstra演算法。 如下图所示，Dijkstra演算法寻找最短路径的方法，大致可以分为四个步骤： 从起点出发 ：选择起点A。计算从A到邻近点的距离，例如到B的距离为1，到C的距离 为5。选择较短的路径，即先前往B。 继续探索 ：从新的点（B）继续找出邻近点的距离，并将这些距离加上从A到B的距离 。例如，从A到B的距离是1，B到D的距离是1，因此A到D的总距离为2（1 + 1 = 2）。更新 已知的最短路径。 记录新的最短路径 ：在探索过程中发现较短的路径时，更新记录。例如，A到C的原 始距离是5，但经过B和D的路径到C的总距离是3（1 + 1 + 1 = 3），比原来的距离短，因 此更新A到C的距离为3 。 重复步骤，直到覆盖所有点 ：演算法继续遍历，直到所有节点的最短路径都被确定 。每次优先选择距离最短的路径进行下一步计算，逐步优化到每个点的最短路径。 最终，Dijkstra演算法可以快速找到网路中从起始点到其他所有节点的最短路径。 在最初的Dijkstra演算法论文中使用到了一个简单且关键的数据结构—— 堆（Heap） ， 而这就为後来的计算机科学家们留下了改进的余地。 例如1984年，两位电脑科学家设计了一个巧妙的堆资料结构，使得Dijkstra演算法在解决 单源最短路径问题所需的时间上达到了理论极限或「下限」。 从某种特定意义上来说，这个版本的Dijkstra演算法已经可以说是最好的，也是近40年来 的一种「标准」。 而这次的最新论文，研究人员的 突破口 依旧是这个堆资料结构。 因为他们发现，像Fibonacci堆等常用的资料结构虽然在理论上具有较好的最坏情况时间 复杂度（Worst-case time complexity），但在许多情况下未能充分利用图的局部结构特 性。 这就导致在处理某些类型的图表时，仍然需要高昂的计算代价。 但如果在1984年设计的堆基础上加入对最近插入项快速访问的能力，就可以显着提升算法 的效率。 为此，研究人员提出了一种全新的堆叠资料结构－具备特殊的 「工作集属性」（ Working Set Property） 。 所谓「工作集属性」 ，指的是堆能够充分利用操作的局部性，从而优先处理最近插入的 元素，降低提取最小元素的成本。 这个概念类似於我们在管理待办事项时，会优先处理那些刚刚新增的紧急任务，更有效率 地完成工作。 若是用公式化的表述，就如下图所示。 对於在堆中插入并随後被提取的任意元素x，其工作集Wx包括了在x被插入後、在x被提取 前插入的所有元素，以及x本身。 https://www.qbitai.com/wp-content/uploads/replace/ce6d76e44dba4992e6de32fe97ecb42c.png 借助这种“工作集属性”，新设计的堆数据结构能够显着提升Dijkstra算法的整体性能， 尤其是在具有局部性特徵的图上。 也成功地让Dijkstra演算法具备了普遍最优性，不仅在最坏情况下具有最优性，还能在任 何图结构上表现出色。 不仅如此，这项工作还提供了 精确的复杂度分析 。 例如，作者证明了Dijkstra演算法在具有工作集属性的堆上的比较次数是 O(OPTQ(G)+n+max∈WG∣FG,w∣)。 其中，OPTQ(G)是解决距离排序问题的最优演算法所需的比较次数，n是顶点数，∣FG,w∣ 是前向边的数量。 这也为演算法的效能提供了更精确的界限。 总而言之，这些成果不仅推动了图演算法的研究，也为实际应用中的演算法设计提供了新 的视角和工具。 喝咖啡时诞生的演算法 关於Dijkstra演算法诞生的故事，其实是始於一次意外的灵感。 1956年，年仅26岁的荷兰电脑科学家 Edsger Dijkstra 当时正试图为一台新型电脑ARMAC 编写一个程序，来展示它的运算能力。 这篇论文介绍了他提出最短的路径演算法，後来成为了电脑科学中 被引用最多的论文之 一 。 尽管Dijkstra的演算法十分优雅，但当时几乎没有电脑科学期刊，发表过程十分困难，最 後他选择将其发表於新创刊Numerische Mathematik上。 Dijkstra在职业生涯中赢得了极高的声誉，并於1972年获得电脑科学领域最负盛名的图灵 奖。 他不仅在程式语言、作业系统和并发控制等领域做出了许多基础性贡献，还以其对程式方 法的深入思考而闻名。 他强调程式的正确性，认为程式应该从一开始就正确地设计，而不是透过调试来达到正确 。 不过同时，Dijkstra的性格也非常独特，他既被赞赏也被批评，是一位充满争议的人物。 他对於电脑科学的教育和研究有着强烈的观点，常常发表极具挑战性的言论。 例如，他反对使用goto语句，并在1968年发表了着名的文章Go To Statement Considered Harmful，这篇文章引发了广泛的争议，但最终他的观点得到了普遍认可。 Dijkstra演算法不仅可以计算从起始点到一个目的地的最短路径，还可以给出从起始点到 所有其他节点的排序，这正是单源最短路径问题的解。 它的核心思想是不断探索目前距离最短的路径，更新每个节点的最短距离，直到所有节点 的距离都确定。 这种演算法的简洁性和高效性使得它成为经典的路径规划工具。 麻省理工学院的电脑科学家Erik Demaine曾评论： 这是一个伟大的演算法，速度非常快，简单易实现。 但演算法的成功不仅归功於其核心思想，还离不开资料结构的选择，在几十年的发展中， 研究人员不断改进堆资料结构，使得演算法的整体效能不断提升。 而这一次，改良堆资料结构，可以说是再次立功了。 论文地址： https://arxiv.org/abs/2311.11793 参考连结： [1]https://www.quantamagazine.org/computer-scientists-built-the-best-way-to-traverse-a-graph-20241025/ [2]https://inference-review.com/article/the-man-who-carried-computer-science-on-his-shoulders --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.253.165.148 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1730032237.A.247.html