拉斯穆斯·金 (Rasmus Kyng) 和他的团队取得了突破,他们开发出了一种超快的算法,看起来将改变整个研究领域,这让人想起了幸运卢克(Lucky Luke),那个射击速度比他的影子还快的人。
Kyng 团队的开创性工作涉及所谓的网络流算法,该算法解决了如何在网络中实现最大流量同时最小化传输成本的问题。
想象一下,您正在使用欧洲交通网络,并寻找最快、最便宜的路线,以便将尽可能多的货物从哥本哈根运送到米兰。在这种情况下,Kyng 的算法可以用于计算任何类型网络(无论是铁路、公路、水路还是互联网)的最佳、成本最低的交通流量。
他的算法执行这些计算的速度非常快,以至于它可以在计算机读取描述网络的数据时立即提供解决方案。
网络计算速度很快
在 Kyng 之前,没有人能够做到这一点——尽管研究人员已经研究这个问题大约 90 年了。以前,计算最佳流量所花的时间比处理网络数据所花的时间要长得多。
随着网络变得越来越大、越来越复杂,所需的计算时间相对而言比计算问题的实际规模增长得更快。这就是为什么我们也看到网络中的流问题太大,计算机甚至无法计算。
Kyng 的方法消除了这个问题:使用他的算法,计算时间和网络规模以相同的速率增加——有点像去徒步旅行,无论路有多陡峭,始终保持相同的步伐。
只要看一下原始数据,就能知道我们已经取得了多大的进步:直到千禧年,没有任何算法的计算速度能够超过 m1.5,其中 m 代表计算机必须计算的网络中的连接数,并且仅读取一次网络数据就需要 m 时间。
2004年,解决该问题所需的计算速度成功降低至1.33m 。使用Kyng的算法,读取网络数据后得出解决方案所需的“额外”计算时间现在可以忽略不计。