迄今最快的网络流算法，网友：几乎与数学理论一样快

文章预览

金磊 发自 凹非寺 量子位 | 公众号 QbitAI 迄今为止 最快、近乎完美 的 网络流 （Network Flow） 算法，来了！ 有多快？ 对于任何类型的网络，计算速度几乎与数学理论一样快。 而且还是以 最低成本 计算 最大运输流量 的那种。 这就是来自苏黎世联邦理工学院计算机系Rasmus Kyng （下文简称“京爷”） 团队最新研究： 其实早在两年前，京爷团队所做的“前代”研究就已经在圈内走红，曾被Quanta Magazine评为当年的计算机科学十大发现之一。 网络流算法先驱Daniel A. Spielman也给出了相当高的评价： 快得离谱，像保时捷超跑一样。 而就在最近，他们在ACM计算理论研讨会 （STOC） 中带来了 “进化版” 研究—— 不论是网络里增加或删除了什么路径，依旧能够以最低成本、最大传输流量的“姿势”，用几乎线性的速度进行计算。 就好比徒步旅行一样，管你道路 ………………………………