会员登录
最经典的算法问题之一是计算两点之间的最短路径。这个问题更复杂一点的版本是当路线穿过一个不断变化的网络时——无论是公路网还是互联网。40年来，研究人员一直在寻找一种算法，为这个问题提供最佳解决方案。
当我们前往一个新的地方时，大多数人都会让计算机算法帮助我们找到最佳路线，无论是通过汽车的GPS，还是公共交通工具和手机上的地图应用程序。尽管如此，有时提议的路线与现实并不完全一致。这是因为道路网络、公共交通网络和其他网络不是一成不变的。最好的路线可能突然变成最慢的路线，例如由于道路施工或事故导致大拥堵。
在这种情况下，一般人可能想不到导航建议背后的复杂数学问题。而正在使用的软件则试图解决经典算法“最短路径”问题的一个变体，即动态网络中的最短路径。40年来，研究人员一直在寻找一种算法，以最优地解决这一数学难题。现在，哥本哈根大学计算机科学系的克里斯蒂安·伍尔夫-尼尔森(Christian Wulff-Nilsen)与两位同事成功地破解了这个难题。
“我们已经开发了一种算法，我们现在有数学证明，它比目前所有其他算法都要好——即使我们展望1000年后的未来，它也将是最接近最优算法。”伍尔夫-尼尔森副教授说。研究结果FOCS 2020大会上公布。
在这种情况下，最优指在给定的网络中花费尽可能少的时间和尽可能少的计算机内存来计算最佳路由的算法。这不仅适用于公路和交通网络，也适用于互联网或任何其他类型的网络。
研究人员用所谓的动态图来表示一个网络。在这种情况下，图是一个网络的抽象表示，它由边(例如道路)和节点(例如表示交叉点)组成。当一个图形是动态的，这意味着它可以随着时间而改变。新的算法处理由删除的边组成的变化——例如，如果等效的一段道路因道路施工而突然变得拥堵。
传统的算法假设一个图是静态的，这在现实世界中很少是真的。当这类算法在动态网络中使用时，每当图中出现小的变化时，它们都需要重新运行——这浪费了时间。
克里斯蒂安·伍尔夫-尼尔森(Christian Wulff-Nilsen)指出:“我们生活在一个数据量以惊人的速度增长的时代，而硬件的发展根本跟不上。为了管理我们产生的所有数据，我们需要开发更智能的软件，需要更少的运行时间和内存。这就是为什么我们需要更智能的算法。” 他希望在实践中使用这种算法或其背后的一些技术是可能的，但他强调这是理论证据，首先需要实验。
译/前瞻经济学人APP资讯组
参考资料：
https://techxplore.com/news/2021-03-classic-math-problem-scientists-superb.html
https://arxiv.org/abs/2004.04496
关注【深圳科普】微信公众号，在对话框：
回复【最新活动】，了解近期科普活动
回复【科普行】，了解最新深圳科普行活动
回复【研学营】，了解最新科普研学营
回复【科普课堂】，了解最新科普课堂
回复【科普书籍】，了解最新科普书籍
回复【团体定制】，了解最新团体定制活动
回复【科普基地】，了解深圳科普基地详情
回复【观鸟知识】，学习观鸟相关科普知识
回复【博物学院】，了解更多博物学院活动详情
深圳市宝安区国际会展中心20号馆
