Credit: CC0公共领域最经典的算法问题之一涉及计算两点之间的最短路径。这个问题的一个更复杂的变体是当路线穿过一个不断变化的网络时——无论这是公路网络还是互联网。40年来，研究人员一直在寻找一种能够为这个问题提供最优解决方案的算法。现在，哥本哈根大学的计算机科学家克里斯蒂安·伍尔夫-尼尔森和两位研究同事提出了一个食谱。当我们去一个新的地方时，我们大多数人会让计算机算法来帮助我们找到最佳路线，无论是通过使用汽车的全球定位系统，还是公共交通和手机上的地图应用程序。尽管如此，有时提议的路线并不完全符合现实。这是因为道路网络、公共交通网络和其他网络不是静态的。最佳路线可能突然变得最慢，例如，因为道路施工或事故形成了队列。
在这种情况下，人们可能不会考虑路由建议背后复杂的数学问题。正在使用的软件试图解决经典算法“最短路径”问题的一个变体，即动态网络中的最短路径。40年来，研究人员一直在努力寻找一种算法，可以最佳地解决这个数学难题。现在，哥本哈根大学计算机科学系的克里斯蒂安·伍尔夫-尼尔森和两位同事一起成功破解了这个难题。
伍尔夫-尼尔森副教授说:“我们已经开发了一种算法，我们现在已经有了数学证明，这种算法比迄今为止的所有其他算法都好——而且是有史以来最接近最优的算法，即使我们着眼于1000年后的未来。研究结果在享有盛誉的2020年FOCS大会上公布。
在这种情况下，最佳是指一种算法，它花费尽可能少的时间和计算机内存来计算给定网络中的最佳路由。这不仅适用于道路和交通网络，也适用于互联网或任何其他类型的网络。
作为图的网络
研究人员将网络表示为所谓的动态图。在这种情况下，图是网络的抽象表示，例如由边、道路和代表交叉点的节点组成。当一个图形是动态的，这意味着它可以随着时间而变化。新算法处理由删除的边组成的更改，例如，如果由于道路施工，一段道路突然变得不可访问。
“将网络视为抽象图形的巨大优势在于，它可以用来表示任何类型的网络。可能是互联网，你想通过尽可能短的路径发送数据，也可能是人脑，或者是脸书的友谊关系网。这使得图形算法适用于各种各样的环境，”克里斯蒂安·伍尔夫-尼尔森解释道。
传统算法假设一个图是静态的，这在现实世界中很少是真的。当在动态网络中使用这类算法时，每当图形发生微小变化时，都需要重新运行它们，这浪费了时间。
更多的数据需要更好的算法
寻找更好的算法不仅在旅行时有用。正如克里斯蒂安·伍尔夫-尼尔森指出的那样，几乎在任何产生数据的领域，这都是必要的:
“我们生活在一个数据量以惊人的速度增长的时代，硬件的发展根本跟不上。为了管理我们产生的所有数据，我们需要开发更智能的软件，它需要更少的运行时间和内存。这就是为什么我们需要更智能的算法，”他说。
他希望有可能在实践中使用这种算法或其背后的一些技术，但强调这是理论证据，首先需要实验。
研究文章“密集加权有向图中的近似最优递减SSSP”在著名的2020年FOCS会议上发表。
来源：由phyica.com整理转载自PH，转载请保留出处和链接！
