solidot新版网站常见问题,请点击这里查看。

最大流问题的新算法“快得离谱”

数学
wanwan (42055)发表于 2022年06月09日 16时38分 星期四

来自总门谷
一计算机科学家团队针对计算机科学领域里最古老的问题之一——最大流(maximum flow)——提出了一种速度显著快得多的算法。最大流问题指的是如果网络中链路容量有限,有多少物质可通过网络从源头流到目的地。论文发表在预印本平台 arXiv 上。耶鲁大学的 Daniel Spielman 表示,新算法“快得离谱”。“我实际上倾向于认为……这个问题不会存在这么好的算法。”

自 1950 年代以来,我们一直在研究最大流问题,这个问题当时是为了研究苏联的铁路系统而制定的。加利福尼亚州山景城 Google 研究中心的 Edith Cohen 表示:“它可能比计算机科学的理论还要古老。”这个问题有很多应用:互联网数据流、航空公司调度,甚至是将求职者与空缺的岗位匹配。新论文同时解决了最大流和你可能希望实现的、这个问题的另一个更普遍的版本——成本最小化。多年来,这两个问题激发了算法技术领域的许多重大进步。新算法在“几乎线性”的时间内解决了两大问题,这意味着算法运行的时间大致与写下网络细节所花费的时间成正比。对于所有可能的网络,其他的算法解决这些问题的速度都无法接近这个速度。

目前这主要是理论上的进步,因为速度提升只适用于大型网络——远大于我们在现实世界中遇到的网络,这些网络的最大流量问题已经可以相当快地解决。但是该算法六位创造者之一、加拿大滑铁卢大学的 Richard Peng 预测,新算法的某些部分可能会在一年内得到实际应用。研究人员表示,未来几年计算机科学家可能会找到实际使用它的方法,甚至可能让它变得更快一点。