科技猎奇客 最大流量问题的新算法“快得离谱”
一计算机科学家团队针对计算机科学领域里最古老的问题之一——最大流量（maximum flow）——提出了一种速度显著快得多的算法。最大流量问题指的是如果网络中链路容量有限，有多少物质可通过网络从源头流到目的地。论文发表在预印本平台 arXiv 上。耶鲁大学的 Daniel Spielman 表示，新算法“快得离谱”。“我实际上倾向于认为……这个问题不会存在这么好的算法。”
自 1950 年代以来，我们一直在研究最大流量问题，这个问题当时是为了研究苏联的铁路系统而制定的。加利福尼亚州山景城 Google 研究中心的 Edith Cohen 表示：“它可能比计算机科学的理论还要古老。”这个问题有很多应用：互联网数据流、航空公司调度，甚至是将求职者与空缺的岗位匹配。新论文同时解决了最大流量和你可能希望实现的、这个问题的另一个更普遍的版本——成本最小化。多年来，这两个问题激发了算法技术领域的许多重大进步。新算法在“几乎线性”的时间内解决了两大问题，这意味着算法运行的时间大致与写下网络细节所花费的时间成正比。对于所有可能的网络，其他的算法解决这些问题的速度都无法接近这个速度。
目前这主要是理论上的进步，因为速度提升只适用于大型网络——远大于我们在现实世界中遇到的网络，这些网络的最大流量问题已经可以相当快地解决。但是该算法六位创造者之一、加拿大滑铁卢大学的 Richard Peng 预测，新算法的某些部分可能会在一年内得到实际应用。研究人员表示，未来几年计算机科学家可能会找到实际使用它的方法，甚至可能让它变得更快一点。
自 1950 年代以来，我们一直在研究最大流量问题，这个问题当时是为了研究苏联的铁路系统而制定的。加利福尼亚州山景城 Google 研究中心的 Edith Cohen 表示：“它可能比计算机科学的理论还要古老。”这个问题有很多应用：互联网数据流、航空公司调度，甚至是将求职者与空缺的岗位匹配。新论文同时解决了最大流量和你可能希望实现的、这个问题的另一个更普遍的版本——成本最小化。多年来，这两个问题激发了算法技术领域的许多重大进步。新算法在“几乎线性”的时间内解决了两大问题，这意味着算法运行的时间大致与写下网络细节所花费的时间成正比。对于所有可能的网络，其他的算法解决这些问题的速度都无法接近这个速度。
目前这主要是理论上的进步，因为速度提升只适用于大型网络——远大于我们在现实世界中遇到的网络，这些网络的最大流量问题已经可以相当快地解决。但是该算法六位创造者之一、加拿大滑铁卢大学的 Richard Peng 预测，新算法的某些部分可能会在一年内得到实际应用。研究人员表示，未来几年计算机科学家可能会找到实际使用它的方法，甚至可能让它变得更快一点。