bt365手机平台-下载首页

  • 图文:克里斯蒂娜达尼洛夫

    全屏

10年的基本算法的第一个改进

最大流的问题,这是在网络分析,调度和物流无处不在,现在可以比以往更有效的解决。


记者联系

杰西卡·霍姆斯
电子邮件: newsoffice@mit.edu
电话:617-253-2700
bt365手机app新闻办公室

媒体资源

1张图片下载

媒体访问

媒体只能从本网站的桌面版本下载。

最大流量问题,或者最大流量,是计算机科学中最基本的问题之一:筹备柏林空运中首先需要解决,这是许多后勤问题的组件和入门课程对算法的主食。几十年来,这是一个突出的研究课题,与解决它了一年多,更有效地走出来一次或两次的新算法。但随着问题变得更好的理解,创新的步伐放缓。但是,现在,bt365手机app的研究,在耶鲁大学的同事和美国南加州大学一起, 证明 最大流算法在10年来第一个改进。

最大流问题是,粗略地讲,计算出的“东西”,可以从网络到另一个的一端移动的最大金额,鉴于网络的链路的容量限制。东西可能是行驶在互联网上或货物行驶在高速公路的箱数据包;链接的限制可能是互联网连接的带宽或拥堵路段的平均交通速度。

技术上更,这个问题有什么数学家称之为图形做。的曲线图是顶点和边,其通常被描绘为圆圈和连接它们的线的集合。通信网络的标准图是曲线图,因为是,比方说,一个家族树。在最大流问题,在图中的顶点中的一个 - 的圆圈之一 - 被指定为源,在那里所有的东西来自;另一个被指定为排水,所有的东西是领导。各边缘的 - 连接所述圆的线 - 具有相关联的容量,或多少东西能够越过它。

隐藏的流

这样的图模型真实世界的运输和通信网络在一个相当简单的方法。但他们的应用实际上是更广泛,乔纳森kelner,应用数学在bt365手机app助理教授,谁帮助引领新作解释。 “非常,非常多的优化问题,如果你在最快的算法看,现在解决这些问题,他们使用的最大流量,” kelner说。网络分析,使用最大流量可能包括航空公司调度,电路分析,在超级计算机任务分发,数字图像处理,和DNA序列比对应用程序的简短列表之外。

传统上,kelner解释,计算最大流量的算法将通过在一个时间图表考虑一个路径。如果有未使用的容量,算法将简单地发送更多的东西过目一下,看看发生了什么。在算法效率的提高,从选择其中的路径进行了探索的顺序的聪明和聪明的方式来了。

图形以网格

但kelner,CSAIL研究生亚历山大madry,数学本科生保罗克里斯蒂和丹尼尔教授斯皮尔曼和分别的,赏画腾耶鲁大学,南加州大学,都采取一种全新的解决问题的方法。他们所代表的图形作为基体,这是数字的大电网数学发言。图表中的每个节点分配一个行和矩阵的一列;其中行和列交叉的数字表示的东西可在两个节点之间传送的量。

在被称为线性代数数学分支,一个矩阵的行也可以被解释为一个数学方程式,和线性代数的工具使由所有的矩阵的行所体现的所有方程的同时解决方案。通过在基质反复修改号码并重新求解方程,研究人员有效地评估一次全图。这种做法,这kelner将在描述 bt365手机app在9月STATA中心的演讲。 28结果表明,它比尝试路径逐一更有效。

如果n是节点中的曲线图的数量,l是它们之间的链路的数量,那么最快先前最大流算法的执行成比例(N + 1)(3/2)。新算法的执行是正比于(N + 1)(4/3)。对于喜欢上网,其中有几千亿个节点的网络,新的算法可以解决最大流问题轻车熟路比其前身快。

该算法的直接实用性,但是,是不是有什么印象约翰·霍普克洛夫特,工程的IBM教授,康奈尔大学应用​​数学和图灵奖的获得者,计算机科学最高奖。 “我的猜测是,这个框架将是适用于范围广泛的其他问题,” hopcroft说。 “这是一个全新的技术。当有这种性质的突破,一般的话,一个分支学科的形式,并在四,五年,多项成果出来“。


主题: 算法, 计算机科学和人工智能实验室(CSAIL), 计算机科学与技术, 拉普拉斯算子, 最大流

评论

这里是原来的纸吗?

上述文章介绍此与,基本上,θ(E + V)^(4/3)的运行时间的精确算法。从我可以从kelner谈话的描述看,不过,该算法实际上是近似的,带O(E ^(4/3))的运行时间·θ(1 /ε^ K)...?也就是说,它不能在全或我误解用于精确的结果吗?一个伟大的结果,无论如何,当然,但也许不完全是这个公告称什么?

你是正确的 - 算法并只提供一个近似值。但由于近似可以像你一样精确,这使得在实践中几乎没有差别。我认为这是一个相当精细的技术区别,将只会让事情对于普通读者更加混乱。

-lh

我觉得有一个非常大的区别..还有就是旅行商,可以是“像你一样精确”的近似算法,但所需的错误率越接近0,运行时间接近无穷大。从mlhetland的评论,同样也适用于该算法。我不知道什么是“K”是方程式中,但如果说k是2,那么它会采取4倍,只要拿到5%的误差对10%的误差造成的。

乔纳森kelner只是告诉我,现在paper's了@

HTTP://math.mit.edu/~kelner/pu ...

玩得开心

G。

请提供一个链接,并于周一给出的纸和介绍的PDF文件。还有谁在等待看到很多很多人。

与beoman同意。这听起来像一个概率的解决方案。贪婪算法更容易与像遗传算法的机制来设计,并且可以通过附加迭代做得任意精确。这并不奇怪,仅仅近似更快解决,然而,由于该解决方案是不完整它不完全是一个公平的测试。

其实这听起来像一个NP难问题,因此,即使在最好的答案这种算法的土地概率,它提供了没有任何迹象表明它的解决方案是完整的。在现实生活中,这可能是“足够好”,但作为计算机科学家,我们当然应该认识到的差异。

有用..不错

回到顶部