bt365手机平台-下载首页

  • 图像:恭达尼洛夫/ MIT

    全屏

新算法可以显着简化解决方案,以“最大流量”问题

研究可以提高甚至喜欢上网庞大网络的效率。


记者联系

艾比abaz要么ius
电子邮件: abbya@mit.edu
电话:617-253-2709
bt365手机app新闻办公室

媒体资源

1张图片下载

媒体访问

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

寻找到遇到像美国的网络传输项目的最有效方式公路系统或互联网是已征税的数学家和计算机科学家几十年的问题。

解决这个问题,研究人员传统上使用的最大流量算法,也可作为已知的“最大流”,在其中一个网络被表示为一系列节点,被称为顶点的图表,以及连接它们之间的界线,边呼吁。

假定每个边缘具有最大容量 - 就像道路或用于在互联网发送信息的光纤电缆 - 这样的算法试图找到最有效的方式来发送货物从一个节点图中的另一个,而不超出这些约束。

但像互联网网络规模已成倍增长,往往是过于耗费时间用传统的计算技术来解决这些问题,根据乔纳森Kelner,应用数学在bt365手机app的副教授,bt365手机app的计算机科学的一个成员,人工智能实验室(CSAIL)。

所以,在纸的离散算法在俄勒冈州波特兰市,本周ACM-暹研讨会呈现,Kelner和他的同事洛伦佐ORECCHIA,一个应用数学讲师,沿着研究生阴达利和亚伦Sidf要么d,将描述这种新的理论算法,可以大大减少,解决了最大流问题所需操作的数量,从而能够解决甚至巨大的网络,如Internet或人类基因组。

“最近一直在图表的大小爆炸正在研究,” Kelner说。 “举个例子,如果你想路由流量在互联网上,研究在Facebook的上的所有连接,或者分析基因组数据,你可以轻松地结束了图形数以百万计,数十亿或边缘甚至万亿美元。”

以前的最大流算法来在这一问题的一个边缘,或路径,在同一时间,Kelner说。因此,例如,当从发送节点项目节点B,该算法将传输部分商品下一个路径,性传播疾病,直到他们达到最大容量,然后开始发送一些向下的下一个路径。

“很多以前的算法,” kelner说,“会发现从点到B点的路径,一起发送它的一些流量,然后说,“鉴于我已经做了,我能找到一起,我可以发送另一个路径更多?“当一个需要发同时沿着许多不同的路径流动,这导致对算法的速度固有的局限性“。

但在2011年Kelner,CSAIL亚历山大madry研究生,本科生数学克里斯蒂保罗和他的同事在耶鲁大学和美国南加州大学开发的技术来分析所有路径的同时。

研究人员观察到的图形作为电电阻器的集合,然后连接想象一个电池到与接地节点到节点B,并且允许通过网络向电流流动。 “电流不挑只有一个路径,它会发送当前的一点点在网络上的每一个电阻器,” Kelner说。 “因此,探讨全图全球范围内,在同一时间学习很多路径。”

这允许新的算法来解决比以前的尝试明显更快的最大流的问题。

现在MIT的研究小组已经开发出一种技术,以进一步减少运行时间,从而可以分析甚至巨大的网络,kelner说。

不像以前的算法,已经看到所有的路径在一个图作为平等的,新技术识别那些路由产生瓶颈内网。球队的算法将各图分成以及连接节点的群集,以及它们之间的路径创建瓶颈,Kelner说。

“我们的算法计算出的曲线图的哪些部分可以轻松的路线,他们需要什么,哪些部分是瓶颈。 ESTA让您专注与其花大量的时间做决定不重要的,这意味着你可以有很多更有效地利用你的时间对问题领域和高层次的结构,“我说。

其结果是几乎线性的算法,Kelner说,这意味着所需的时间来解决的一个问题是非常接近正比于数量的网络上的节点直接量。因此,如果在图上节点的数量乘以10的时间量将乘以东西非常接近10,而不是100或者1000相乘,我说。 “这意味着,它扩展以及你基本上可以与输入的尺寸希望,”我说。

尚华腾在他并没有在最新的论文所涉及的南加州大学计算机科学教授说,这代表了图形算法和优化软件的重大突破。

“这篇论文,这是最佳论文奖在[ACM-暹]会议的赢家,是通电时的流量设计高效图形算法的持续努力Kelner和他的同事的结果,说:”腾“本文包含的技术贡献问题一系列惊人的。”

该文件被张贴一起由美国加州大学伯克利分校,世卫组织已研制出一种也是线性算法求解几乎是最大流问题,使用替代技术的乔纳·谢尔曼工作。


主题: 算法, 计算机科学和人工智能实验室(CSAIL), Electrical Engineering & Computer Science (eecs), 数学, 最大流

回到顶部