计算机科学家找到了动态图可平面判定的最快算法

在图论算法领域，两位来自丹麦的计算机科学家解决了一个自上世纪90年代以来一直未能取得实质性进展的难题。

假设有三间房子排成一排——可以找张纸画画，用点替代；另一边则是自来水工厂、发电厂和煤气管道公司，同样每个都看成一个点。现在，我们要求为三家民宅通水电气，同时保证，线路管道不得交叉。

您能想到连接方法吗？

根据著名的Kuratowski定理，单纯从数学角度，在平面上是不可能实现上述管线设计的。

此类问题有一个名字：图的可平面化。Kuratowski定理是重要的理论工具。但是，可平面化问题不仅仅具有理论上的价值，比如说，CPU上的线路，按经典工艺，也是不能相交的，所以本质上就是一个可平面化问题。

当需要处理的图规模太大之后，在现实问题里纯数学工具就显得局促了。自1970年代以来，研究人员一直在设计算法，高效验证图是否可平面化。

但在1990年代取得了最后的进展之后，该领域数十年里停滞不前。直到去年，哥本哈根大学的计算机科学家Jacob Holm和来自丹麦技术大学的Eva Rotenberg经过艰苦工作，终于有所斩获。

Holm说：“我们原本的研究就差一步，但一直未能突破瓶颈，我们猜测，还需要再工作五年。”

就在那时，灵光乍现，他们意识到他们现有的结论已经有效地解决了另一个问题，即平面图的判定。

两人在接下来数周里玩命地写出了改良算法的正式证明。“我们连续五到六周加班加点写这篇文章。最终，80页。”

该算法可以用最少的计算时间来解决动态图是否可支持平面嵌入的问题。(简单来说，是否可以在没有交叉线的情况下将图绘制在一张纸上。)

这是一个很大的进步，因为在概念上很简单的问题在诸如微芯片设计或道路规划等现实领域变得极其复杂。

Holms解释说：“事实证明，对于动态图问题，通常可以建立一些数据结构，用于在每次更改图后重新计算答案，这要比从头开始重新计算答案要快得多。这一结果对我们来说是巨大的成就。”

论文 https://dl.acm.org/doi/10.1145/3357713.3384249

本文译自 sciencealert，由 majer 编辑发布。

*说个题外的，增加一下本文可理解信息量。就不专门写一篇了。印度研发的男性避孕针剂通过了当地的临床三期。据说男性打一针能不孕13年……

赞一个 (13)

煎蛋