.fav_bar { 浮动：左边; 边框：1px 实心 #a7b1b5; 上边距：10px; 下边距：20px; } .fav_bar span.fav_bar-label { 文本对齐：中心; 填充：8px 0px 0px 0px; 浮动：左边; 左边距：-1px; 右边框：1px 虚线 #a7b1b5; 左边框：1px 实心 #a7b1b5; 显示：块; 宽度：69px; 高度：24px; 颜色：#6e7476; 字重：粗体; 字号：12px; 文本转换：大写; 字体：Arial, Helvetica, sans-serif; } .fav_bar a, #plus-one { 浮动：左边; 右边框：1px 虚线 #a7b1b5; 显示：块; 宽度：36px; 高度：32px; 文本缩进：-9999px; } .fav_bar a.fav_de { 背景：url(../images/icons/de.gif) 不重复 0 0 #fff } .fav_bar a.fav_de:hover { 背景：url(../images/icons/de.gif) 不重复 0 0 #e6e9ea } .fav_bar a.fav_acm_digital { 背景：url(‘../images/icons/acm_digital_library.gif’) 不重复 0px 0px #FFF; } .fav_bar a.fav_acm_digital:hover { 背景：url(‘../images/icons/acm_digital_library.gif’) 不重复 0px 0px #e6e9ea; } .fav_bar a.fav_pdf { 背景：url(‘../images/icons/pdf.gif’) 不重复 0px 0px #FFF; } .fav_bar a.fav_pdf:hover { 背景：url(‘../images/icons/pdf.gif’) 不重复 0px 0px #e6e9ea; } .fav_bar a.fav_more .at-icon-wrapper{ 高度： 33px !important ; 宽度： 35px !important; 填充： 0 !important; 右边框： none !important; } .a2a_kit { 行高： 24px !important; 宽度： unset !important; 高度： unset !important; 填充： 0 !important; 右边框： unset !important; 左边框： unset !important; } .fav_bar .a2a_kit a .a2a_svg { 左边距： 7px; 上边距： 4px; 填充： unset !important; }
计算机科学先驱Edsger Dijkstra的算法成为许多计算机子程序的基础，因为它们具有优雅的效率。然而，需求上的看似细微变化可能导致这些通常概念简单的公式无法提供准确答案。替代算法提供了正确的答案，但通常速度慢了几个数量级。
组合技术的最新突破展示了如何重新利用这些早期算法。
最短路径问题是算法对其要求的特定性敏感性的良好例子。作为许多应用程序的基础，从导航到芯片布局，这些问题提出了一个简单的基本命题：根据应用到每个跳跃的权重，找到通过有向路径网络的路径，其成本最低。该权重可能反映距离或延迟，在物理世界中始终是正数。
问题出现在遇到具有负权重的类似网络时。纽约州新不伦瑞克市罗格斯大学计算机科学助理教授Aaron Bernstein说：“当你处理边权重对应成本的情况时，负权重是自然的。”。
例如，在金融领域，可能存在一些货币或期权交易的情况，通过一种顺序的买入和卖出比采取不同路径更有利可图，只要搜索算法足够快。但是，这些负权重可能会使Dijkstra的最短路径算法陷入困境。
问题在于上世纪50年代发展起来的算法的高效贪婪性：它经常会从考虑中去除负权重路径。它逐个处理每个顶点，并且不返回，因此算法可能不会考虑高权重与负权重的组合是否可能比低权重的单个跳跃具有更低的成本。
修订后的方法通常称为Bellman-Ford算法，可以正确处理负权重连接，但由于它依赖于处理节点的能力，因此缺乏Dijkstra技术的原始效率，后者的完成时间基于节点和连接数之和。相比之下，Bellman-Ford需要更多的步骤：总数基于节点数和顶点数的乘积。
尽管计算机科学家们尝试使用类似组合技术来寻找问题的更高效解决方案，但他们未能显著缩小这些传统算法之间的计算差距。在过去的几十年里，通过将图形表示为矩阵中的系数，并利用线性代数工具取得了更大的进展。这种技术已经成功应用于各种与路径相关的问题，不仅仅是用于确定最短路径，还可以用于最大化管道或交通路线网络中的流量，正如在去年的计算机科学基础研究会议（FOCS）上发表的一篇论文中所展示的。
佐治亚理工学院的博士生李晨与瑞士苏黎世联邦理工学院、斯坦福大学和多伦多大学的数学家合作，开发了一种基于梯度下降的机制，这与训练神经网络所使用的核心方法相同，可逐步移动到最佳答案以最大化网络流量。该算法将计算时间缩短到几乎线性性能。
基于优化的最新技术的缺点是它们比传统组合算法更难实现和理解。德国萨尔布吕肯的马克斯·普朗克计算机科学研究所的主任和科学成员丹那那恺（Danupon Nanongkai）表示：“这种方法通常使用很多动态算法，这往往很复杂。它们涉及许多需要组合在一起的动态部件。”
贝尔曼-福特算法可以正确处理负权重连接，但缺乏迪杰斯特拉算法的原始效率。
伯恩斯坦（Bernstein）、那那恺（Nanongkai）和哥本哈根大学计算机科学副教授克里斯蒂安·沃尔夫·尼尔森（Christian Wulff-Nilsen）希望看看是否能够找到一个高效的组合解决方案来解决带有负权重的单源最短路径问题。
团队首先研究了安德鲁·戈尔德伯格（Andrew Goldberg）及其同事在上世纪90年代发表的一篇论文，该论文通过尝试将权重值缩放为正值，从而降低了复杂度，使得可以使用迪杰斯特拉算法找到最短路径。那那恺说：“最初的目标只是稍微改进戈尔德伯格的结果，但最终，一切都到位后，我们可以走得更远。”
一种长期以来用于缩放的技术是使用价格函数，尽管在不扭曲权重之间的关系的情况下有效地分配价格可能会很困难。该团队找到了一种适用于特定类型图形的高效算法：低直径图。这被证明是取得更大突破的关键，也可能有助于发现其他问题的更高效组合解决方案。
低直径图是路径较短且相互之间可以看作强连接的结构。低直径属性一直是将图形分割成多个部分以便可以在多台计算机上进行分布式处理的关键组成部分。确保强连接的组件保持在同一台机器上有助于最小化网络流量。
团队发现可以将输入图形分割成低直径子图的群集，然后使用一系列价格函数逐步重构权重，从而构建一个几乎完全可以使用迪杰斯特拉算法处理的重构图形。这涉及随机删除具有负权重的路径，从而使源图形转换为有向无环图：只包含正向路径且没有连接强连接群集的循环。选择这种形式是因为它为使用最快算法提供了可能。稍后的阶段重新引入了缺失的负权边。这些路径的数量很少，可以使用贝尔曼-福特算法进行处理，对运行时间影响相对较小。
尽管为有向图构建的低直径分解形式对解决方案至关重要，但伯恩斯坦表示，对于无向图来说，传统分解方法并不明显。“当我们开始研究时，不清楚在这种情况下低直径分解意味着什么，我们没有意识到它可能是一个相关的概念。只有当我们从不同的角度开始工作，发现我们在处理与低直径属性相连的图形时，我们开始看到它如何被使用，”他说。
这种分解使得可以将价格函数的计算分成几个步骤进行，并且以高效的方式进行，而不会出现单步方法所带来的扭曲。
伯恩斯坦补充道：“从某种意义上说，我们的算法正在对图形进行分解，解决一些具有少量负边权的问题，然后逐步解决这些问题，并找出下一个问题，逐渐尝试减少负权重。”
核心算法在图中的顶点数量上有几个元素具有对数依赖性，每个元素都代表了改进的空间。
Wulff-Nilsen指出：“这种渐进改进是通过多次使用价格函数来改变边缘来实现的。因此，我们不仅仅是找到一个价格点。”
结果是一个具有接近线性性能的算法，与陈在去年同一FOCS活动中展示的最大流优化技术相比，其任务性能稍微更好。两者都获得了该研讨会的最佳论文奖，并且由于其相对简单性，许多教师已将这种组合算法和同事们纳入他们的课程中。
尽管核心算法接近线性，但它有几个元素对图中顶点数量具有对数依赖性，每个元素都代表了改进的空间。来自萨尔兰大学的Karl Bringmann和Alejandro Cassis与以色列威茨曼科学研究所的Nick Fischer合作，在4月份发表的一篇论文中成功地优化掉了八个对数因子中的六个。他们认为其中一些是简单的，例如改变元素呈现给底层Dijkstra算法的顺序，但其他一些则“更加复杂”。
在他们的工作中，Bringmann和同事们提出了一种更直接的分解形式，用于更高效的算法，以及一种不适用于这个特定问题的低直径分解形式。
这样的处理方式可能对于有向图来说像低直径分解一样有用。Bernstein表示：“我认为人们对于低直径分解可以这样使用感到兴奋。人们一直在与我们所有人讨论将其用于其他有向图问题。”
在对低直径分解的深入研究中，Bernstein、Nanongkai和其他人在三月份发表了一篇论文，展示了一种用于最短路径计算的分布式算法。然而，对于问题如流量最大化等的高效组合解决方案的寻找仍然是一项艰巨的任务，尽管它们更复杂且依赖于需要操纵动态数据结构的技术，但基于优化的方法仍然是计算机科学的关键工具。
Bernstein观察到：“优化技术确实是我们解决一些问题的唯一方法。我们的算法展示了一个组合解决方案，但它仍然是一个特定的问题。例如，对于最小成本流，我们还没有关于如何进行组合性解决的想法。”
进一步阅读
Bernstein, A., Nanongkai, D., and Wulff-Nilsen, C. 《近线性时间负权单源最短路径》第63届IEEE计算机科学基础研讨会论文集 (2022), 600–611
Chen, L., Kyng, R., Liu, Y.P., Peng, R., Probst Gutenberg, M., and Sachdeva, S. 《几乎线性时间最大流和最小成本流》第63届IEEE计算机科学基础研讨会论文集 (2022), 612–623
Bringmann, K., Cassis, A., and Fischer, N. 《近线性时间负权单源最短路径：现在更快了！》ArXiv 2304.05279 (2023)
Linial, N. and Saks, M. 《低直径图分解》Combinatorica 13 (4) (1993) 441–454
返回顶部
作者
Chris Edwards是一位位于英国萨里的作家，专门报道电子、信息技术和合成生物学。
©2023 ACM 0001-0782/23/8
未经费用授权，允许个人或课堂使用部分或全部作品的数字或印刷副本，但副本不能用于盈利或商业优势，并且副本必须在第一页上带有此通知和完整引用。必须尊重ACM拥有的作品组成的版权。允许带有信用的摘要。复制、再发表、发布在服务器上或分发给列表，需要事先特定许可和/或费用。请向permissions@acm.org申请发布许可或传真(212) 869-0481。
数字图书馆由计算机协会出版。版权 © 2023 ACM，Inc.