导航不再智障！科学家开发出寻找最短路径的高超算法，接近最优解

最经典的算法问题之一是计算两点之间的最短路径。这个问题更复杂一点的版本是当路线穿过一个不断变化的网络时——无论是公路网还是互联网。40年来，研究人员一直在寻找一种算法，为这个问题提供最佳解决方案。

当我们前往一个新的地方时，大多数人都会让计算机算法帮助我们找到最佳路线，无论是通过汽车的GPS，还是公共交通工具和手机上的地图应用程序。尽管如此，有时提议的路线与现实并不完全一致。这是因为道路网络、公共交通网络和其他网络不是一成不变的。最好的路线可能突然变成最慢的路线，例如由于道路施工或事故导致大拥堵。

在这种情况下，一般人可能想不到导航建议背后的复杂数学问题。而正在使用的软件则试图解决经典算法“最短路径”问题的一个变体，即动态网络中的最短路径。40年来，研究人员一直在寻找一种算法，以最优地解决这一数学难题。现在，哥本哈根大学计算机科学系的克里斯蒂安·伍尔夫-尼尔森(Christian Wulff-Nilsen)与两位同事成功地破解了这个难题。

“我们已经开发了一种算法，我们现在有数学证明，它比目前所有其他算法都要好——即使我们展望1000年后的未来，它也将是最接近最优算法。”伍尔夫-尼尔森副教授说。研究结果FOCS 2020大会上公布。

在这种情况下，最优指在给定的网络中花费尽可能少的时间和尽可能少的计算机内存来计算最佳路由的算法。这不仅适用于公路和交通网络，也适用于互联网或任何其他类型的网络。

研究人员用所谓的动态图来表示一个网络。在这种情况下，图是一个网络的抽象表示，它由边(例如道路)和节点(例如表示交叉点)组成。当一个图形是动态的，这意味着它可以随着时间而改变。新的算法处理由删除的边组成的变化——例如，如果等效的一段道路因道路施工而突然变得拥堵。

传统的算法假设一个图是静态的，这在现实世界中很少是真的。当这类算法在动态网络中使用时，每当图中出现小的变化时，它们都需要重新运行——这浪费了时间。

克里斯蒂安·伍尔夫-尼尔森(Christian Wulff-Nilsen)指出:“我们生活在一个数据量以惊人的速度增长的时代，而硬件的发展根本跟不上。为了管理我们产生的所有数据，我们需要开发更智能的软件，需要更少的运行时间和内存。这就是为什么我们需要更智能的算法。” 他希望在实践中使用这种算法或其背后的一些技术是可能的，但他强调这是理论证据，首先需要实验。

译/前瞻经济学人APP资讯组

本文来源前瞻网，转载请注明来源。本文内容仅代表作者个人观点，本站只提供参考并不构成任何投资及应用建议。（若存在内容、版权或其它问题，请联系：service@qianzhan.com）