出现了超快网络流算法，可以在最大限度降低传输成本的同时实现最大流量

拉斯穆斯·金斯·金斯穆斯·金开发了几乎最大的快速流算法背后的两位研究人员 还有马克西米利安·普罗布斯特·古腾堡。图片来源：瑞士苏黎世联邦理工学院

科技日报记者 张佳欣

瑞士苏黎世联邦理工学院的研究人员开发了一种超快算法，即网络流算法。该算法在最大限度地降低传输成本的同时，成功地解决了在网络中实现最大流量的问题。该算法成功解决了在最大限度降低传输成本的同时实现网络流量最大化的问题。这种超快计算能力是研究高度复杂、数据丰富、动态和快速变化的网络(如生物学中的分子网络或大脑网络)的重要环节。

新型算法可以为任何类型的网络(包括铁路、公路、水上交通和因特网)计算出最佳和最低成本的交通流量计划。它的计算速度非常快，几乎可以在计算机读取描述网络数据的瞬间提供解决方案。

所有计算方法在寻找最佳流量和最低成本路线时，原则上都要面临多次迭代分析网络的挑战。这个过程中，他们会逐一分析网络连接状态，包括哪些是开放的，哪些是关闭的，或者因为达到容量极限而拥堵。

在此之前，计算机科学家在解决这个问题时，往往要在两个关键策略之间做出选择。一种是以铁路网络为模型，每次迭代都要计算整个网络部分，调整交通流量；另一种是受电网中电力流的启发，整个网络都是在每次迭代中计算的，但是统计网络各部分修改流量的平均值，以加快计算速度。

如今，研究小组结合了这两种策略的优点，创造了一种全新的组合方法。基于许多小、高效、低成本的计算步骤，新算法将这些步骤加起来比一些单一的大步骤快得多。

计算最佳流量的时间复杂程度通常表现为m的某一幂次方，其中m代表计算机必须计算的网络连接数。在2000年之前，没有一个算法的计算速度可以超过m1.5。在2004年，解决这个问题所需的计算速度成功降至m1.33。

新算法进一步解决了这个问题。在使用该算法时，计算时间和网络规模以相同的速度增加，这可能会改变整个网络流算法研究领域。