哥本哈根大学和丹麦技术大学(DTU)的计算机科学研究人员认为,距离1980年代的数学谜题还差5年。实际上,在不知不觉中,他们几乎破解了这个问题,并在一篇研究文章中放弃了很多解决方案。该解决方案可用于改进未来的电话和计算机。

名副其实的脑筋急转弯。这就是在图论学科中可以安全地描述这一数学问题的方式。哥本哈根大学计算机科学系和DTU的两位数学家现在解决了自1980年代以来世界上最快,最聪明的难题。

两位计算机科学家,UCPH的助理教授Jacob Holm和DTU的Eva Rotenberg副教授,在提交了一篇研究文章(该文章最终解决了数学难题)的先驱之后,几乎在2019年夏天放弃了他们的解决方案。

“我们几乎放弃了获得最后一块并解决难题的方法。我们认为我们取得了次要的结果,虽然很有趣,但是并没有解决问题。我们猜测在最好,在我们能够解决这个难题之前。”隶属于UCPH计算机科学系算法部分BARC的Jacob Holm解释说。

三种公用事业问题

1913年,现在已解决的数学难题的前身在《斯特兰德杂志》(The Strand Magazine)上发表,被称为“三个公用事业问题”。这使该杂志的读者挠头思索。问题是,三栋小屋中的每栋都必须有水,气和电,而房屋与水,电和气之间的“线”可能不会彼此交叉,这是不可能的。

线之间的解决方案

简而言之,难题是关于如何在图形中连接多个点而又不让连接它们的线交叉的问题。以及如何通过数学计算(一种算法)来更改广泛的“图形网络”,以确保没有线相交而无需重新开始。除其他事项外,这些属性可用于构建巨大的道路网络或计算机内部的微小内部,其中电路板上的电路可能不会交叉。

自1998年以来,雅各布·霍尔姆(Jacob Holm)就对数学难题产生了兴趣,但答案只有在两名研究人员通读他们已经提交的研究文章时才透露出来。同时,研究人员听说了一种新的数学技术,他们意识到可以将其应用于该问题。

“在阅读我们的研究文章时,我们突然意识到解决方案已经摆在我们眼前。我们的下一个反应是'哦,不,我们已经把自己开了枪,放弃了解决方案,” DTU的伊娃•罗滕伯格(Eva Rotenberg)副教授说。

关于图论

图形是一种非常简单的构造,用于对事物进行建模,这些事物可以描述为对象及其之间的连接。图论既是数学领域,也是计算机科学中的重要工具。

在这种情况下,可以通过由与多个线(边缘)相关的多个点(节点,顶点)组成的图来说明图。每个边缘都显示为一条线(或弯曲的片段),其节点为两个端点。

关于解决方案

动态图中有两种更新:一种可以删除边,而可以插入新边。这两个操作必须由用户执行,而算法则始终跟踪网络的绘制。这是研究人员找到配方的算法。

可用于计算机电子

这是两位研究人员忙于撰写研究论文并绑扎松散的末端以解决Holm自1998年以来就断断续续工作的难题的时候。

Eva Rotenberg说:“我们连续五到六周研究了该文章。最终,它填满了80多页。”

幸运的是,没有人击败他们,并且两位研究人员能够在原定于芝加哥举行的主要理论计算机科学会议上展示他们的研究结果,但最终还是以虚拟形式召开。

那么,该数学难题的解决方案可以用于什么呢?两位研究员不确定,但他们有一些建议。

“我们的研究是基础研究,因此我们几乎不知道它的最终用途。甚至从一开始,我们就发现难以想象的应用,” Jacob Holm补充道,“微芯片和电路板的设计被发现了。在所有电子产品中,最终结果可能会被使用。在电路板上绘制导线时,切勿相交,否则会发生短路,同样适用于包含数百万个晶体管的微芯片。一个必须有一个图形绘图。”