最大流量算法新突破
http://www.mittrchinese.com/article.jsp?id=3032最近，physorg网站对计算机领域的最大流量（maximum-flow）算法进行了报道，报道称，这项基础算法十年内首次得到了改进。
..........
但是，凯尔纳、人工智能实验室(CSAIL)毕业生亚历山大•马诸（AleksanderMadry）、数学系本科生保罗•克里斯提娜、耶鲁大学丹尼尔•斯帕尔曼（Daniel Spielman）教授以及南加州大学的滕尚华采用了一种全新的方法来解决这个问题。他们用矩阵代表图形，这是用数学语言来解读一个大的数字表格。图形中的每个节点都被分配到矩阵的每行和每列，行和列相交的点数量代表着可能在两个节点之间运送物质的数量。
在数学的分支领域线性代数中，一个矩阵的一行也可以被解释成一个数学方程式，线性代数的工具可以解决一个矩阵所有的列呈现的方程式。通过反复修改矩阵中的数字和不停的解方程，研究人员有效地一次性计算出了整个图形的值。
如果N是一个图形中的节点数量，L是它们之间的连接数，那么先前最快的最大流量算法的执行结果就与(N + L)(3/2)成正比。而新算法的执行结果与(N + L)(4/3)成正比。研究人员事实上还没有写出能表达他们的算法的公式，在实践中，一个算法的性能可能取决于一些因素，比如，它编码的效率如何，它管理内存的性能如何。但在理论上，对互联网上的一个网络来说，它有大约1000亿个节点。那么，新的算法可以比先前的算法在解决最大流量算法问题上快100 倍。 只是因为说是改进基础算法才转来的，但感觉文中什么也没说。。。
好像只是说弄成个邻接矩阵，实在想不到这有什么值得说。。。
页:
[1]