最近，physorg网站对计算机领域的最大流量（maximum-flow）算法进行了报道，报道称，这项基础算法十年内首次得到了改进。

　　在计算机科学领域，最大流量（maximum-flow）问题是最基本的问题之一。在柏林空运事件的前期准备阶段，最大流量问题第一次得到解决。这个问题也是许多逻辑问题的一个部分，也是算法基础入门课程的一个主题。几十年来，它一直是一个重要的研究项目，新算法解决这个问题越来越有效率，每年都要出来新算法。但是，随着这个问题越来越容易理解，革新的脚步却慢了。现在，麻省理工学院的研究者们和耶鲁大学以及南加州大学同事们经过10年的努力已经论证了关于最大流浪算法的第一次改进。

　　图形中的每个节点都被分配到矩阵的每行和每列，行和列相交的点数量代表着可能在两个节点之间运送物质的数量。

　　最大流量问题概括来说就是，在给出网络链接的容量限制后，计算出从网络一端移动到另一端的“东西”的最大数量。移动的“东西”可能是经过网络的数据包，或者是在高速路上穿梭的货物箱。链接限制可能是网络连接的带宽或者是拥挤道路上的平均交通速度。

　　更技术一点，这个问题与数学家称作图形的东西有关。一个图形体现出来的是顶点和边界的集合，这些峰值和边界被描绘成与它们相连的圆和线条。一个通信网络的标准图表就是一个图形，比方说一个家庭树形。在最大流量问题上，图形中的峰值之一（圆形之一）被指定是来源，许多东西都来自这里。另一种被指定是排水渠，在这里所有的东西都朝一个方向前进。每一个边界（线连接圆的点）有一个相关联的容量，或者说在这个点上有多少东西可以通过。

　　乔纳森•凯尔纳（Jonathan Kelner）解释说，这些图形都以很简单的方式模拟了真实世界的交通和通信网络，但是这些图形的应用事实上更广泛。凯尔纳是麻省理工学院应用数学专业的一位助理教授，帮助领导了这项新工作。“现在有很大数量的优化问题，如果你想看马上能解决这些问题的最快的算法，那就是最大流量算法了。”凯尔纳说。除了网络分析之外，还有一小部分应用程序也使用最大流量算法，包括航班排列、电路分析、超级计算机里的任务分配、数字图像处理以及DNA排序。

　　凯尔纳说，传统上讲，计算最大流量的算法每次都应该考虑一条经过图形的路径。如果该路径的容量还未使用过，那么算法就会简单的发送更多的东西经过它，并且会检查发生了什么。对算法效率的提高还是源自非常聪明的方式，这些方式就是选择在其中开发路径的指令。

　　但是，凯尔纳、人工智能实验室(CSAIL)毕业生亚历山大•马诸（AleksanderMadry）、数学系本科生保罗•克里斯提娜、耶鲁大学丹尼尔•斯帕尔曼（Daniel Spielman）教授以及南加州大学的滕尚华采用了一种全新的方法来解决这个问题。他们用矩阵代表图形，这是用数学语言来解读一个大的数字表格。图形中的每个节点都被分配到矩阵的每行和每列，行和列相交的点数量代表着可能在两个节点之间运送物质的数量。

　　在数学的分支领域线性代数中，一个矩阵的一行也可以被解释成一个数学方程式，线性代数的工具可以解决一个矩阵所有的列呈现的方程式。通过反复修改矩阵中的数字和不停的解方程，研究人员有效地一次性计算出了整个图形的值。

　　如果N是一个图形中的节点数量，L是它们之间的连接数，那么先前最快的最大流量算法的执行结果就与(N + L)(3/2)成正比。而新算法的执行结果与(N + L)(4/3)成正比。研究人员事实上还没有写出能表达他们的算法的公式，在实践中，一个算法的性能可能取决于一些因素，比如，它编码的效率如何，它管理内存的性能如何。但在理论上，对互联网上的一个网络来说，它有大约1000亿个节点。那么，新的算法可以比先前的算法在解决最大流量算法问题上快100倍。

　　然而，这个新算法直接的应用还没有给约翰•霍普克罗夫（John Hopcroft）带来深刻的印象。霍普克罗夫是IBM的工程教授，是康奈尔大学的应用数学教授，也是图灵奖（计算机科学领域最高奖项）的获得者。“我推测，这项特殊的算法框架将会广泛应用于其它问题。”霍普克罗夫说，“这确实是一个新技术。当这个算法问题得到突破时，通常就会有分支学科出现，在4或5年内，许多成果就会出现。”