计算机科学家成功解决了1950年代的算法难题

半个多世纪以来，世界各地的研究人员一直在努力解决一个被称为“单源最短路径问题”的算法问题。问题本质上是关于如何设计一个数学方法来最好地找到网络中一个节点和所有其他节点之间的最短路线，其中可能存在负权重的连接。

听起来很复杂?可能吧。但事实上，这种类型的计算已经广泛应用于我们寻找周围道路所依赖的各种应用程序和技术中——例如，谷歌地图可以引导我们穿越风景和城市。

现在，哥本哈根大学计算机科学系的研究人员成功解决了单源最短路径问题困扰研究人员和专家数十年

“我们发现了一种算法，可以在几乎线性时间内解决问题，这是最快的方法。这是一个基本的算法问题，自1950年代以来一直在研究，并在世界范围内教授。这是促使我们解决问题的原因之一它，”副教授ChristianWulff-Nilsen解释说，他显然发现很难对一个未解决的算法问题置之不理。

更快地计算电动汽车的路线

去年，Wulff-Nilsen在同一领域取得了另一项突破，其成果解决了如何在随时间变化的网络中找到最短路径的问题。他对最近谜语的解决方案建立在这项工作的基础上。

研究人员认为，解决单源最短路径问题可以为算法铺平道路，这些算法不仅可以帮助电动汽车立即计算出从A到B的最快路线，而且可以以最节能的方式计算。

“我们正在添加一个以前的算法没有的维度。这个维度让我们看看我们称之为负权重的东西。一个实际的例子可以参考道路网络中的山丘，这很好知道是否你有一辆电动汽车，它可以在下坡行驶时充电，”Wulff-Nilsen解释道。

关于单源最短路径问题的事实

单源最短路径问题的目的是找到从给定起始节点到网络中所有其他节点的最短路径。

网络表示为由节点和它们之间的连接组成的图，称为边。

每条边都有一个方向(例如，这可以用来表示单向道路)，以及一个权重，表示沿着该边行进的成本。如果所有边的权重都是非负的，则可以使用经典的Dijkstra算法在几乎线性时间内解决该问题。

新结果解决问题的时间几乎与Dijkstra算法相同，但也允许负边权重。

“原则上，该算法可用于警告参与者，例如中央银行，如果投机者正在投机买卖各种货币。今天很多这种情况都是使用计算机发生的。但由于我们的算法非常快，它可能能够用于在漏洞被利用之前检测漏洞，”ChristianWulff-Nilsen说。

研究人员强调，计算电动汽车货币和路线的系统已经存在。但是解决单源最短路径问题使研究人员能够创建一种极好的算法，这种算法在速度方面几乎无可匹敌。同时，它的简单性使其易于适应社会的各种需求。

在美国获得荣誉

解决问题的工作并没有被忽视。事实上，世界各地的人们已经联系了ChristianWulff-Nilsen和他的同事，希望向他们表示祝贺，并进一步了解他们是如何做到的。

同时，详细介绍他们发现的研究文章在科罗拉多州丹佛市举行的FOCS(计算机科学基金会)会议上荣获“最佳论文奖”。

“来自世界各地的人们参加这次会议是为了看到最好的结果，”ChristianWulff-Nilsen说。

这项研究是由计算机科学系的ChristianWulff-Nilsen、马克斯普朗克研究所的DanuponNanongkai和他们的美国同事、罗格斯大学的AaronBernstein合作进行的。

　　免责声明：本文由用户上传，与本网站立场无关。财经信息仅供读者参考，并不构成投资建议。投资者据此操作，风险自担。 如有侵权请联系删除！