哥本哈根大学 信用:CC0公共领域 哥本哈根大学和丹麦技术大学(DTU)的计算机科学研究人员认为，他们距离解决20世纪80年代的一个数学谜题还有五年时间
事实上，在不知情的情况下，他们几乎破解了这个问题，并在一篇研究文章中给出了大部分解决方案
这个解决方案可以用来改善未来的手机和电脑
雅各布霍姆和伊娃罗滕博格 名副其实的脑筋急转弯
这就是如何在图论学科中安全地描述这个数学问题
来自哥本哈根大学计算机科学系和DTU的两位数学家现在已经解决了一个世界上最快最聪明的人自20世纪80年代以来一直在努力解决的问题
这两位计算机科学家，UCPH的助理教授雅各布·霍尔姆和DTU的副教授伊娃·罗滕博格在提交了一篇研究文章之后，几乎在2019年夏天放弃了他们的解决方案，这篇文章成为他们最终解开这个数学谜语的先驱
“我们几乎已经放弃了得到最后一块和解开这个谜
我们以为我们有了一个小结果，一个有趣的结果，但并没有解决问题
我们猜测，在我们能够解决这个难题之前，最多还有五年的工作要做，”雅各布·霍尔姆解释道，他是BARC的一员，UCPH大学计算机科学系的算法部门
三个效用问题 1913年，一个现已解决的数学难题的前身被发表在《斯特兰德杂志》上，名为“三个效用问题”
这让杂志的读者挠头思考
在这个问题中，三个村舍中的每一个都必须有水、气和电，而房屋与水、电和气之间的“线”可能不会相互交叉——这是不可能的
言外之意 简而言之，这个难题是关于如何在不允许连线交叉的情况下连接图形中的多个点
以及如何通过数学计算——一种算法——对一个广泛的“图形网络”进行修改，以确保没有线相交，而不必从头开始
这些特性可用于建造巨大的道路网络或计算机的微小内部结构，电路板上的电路可能不会穿过这些地方
雅各布·霍尔姆从1998年起就对这个数学难题感兴趣，但直到两位研究人员通读了他们已经提交的研究论文后，答案才得以揭晓
与此同时，研究人员听说了一种新的数学技术，他们意识到这种技术可以应用于这个问题
“在阅读我们的研究文章时，我们突然意识到解决方案就在眼前
DTU的副教授伊娃·罗滕博格说:“我们的下一个反应是‘哦，不——我们搬起石头砸自己的脚，把解决办法给扔了’。”
关于图论 图形是一种非常简单的结构，用于对可以描述为对象的事物以及它们之间的联系进行建模
图论既是数学的一个领域，也是计算机科学的一个重要工具
在这种情况下，一个图可以用一个由许多点(节点、顶点)和许多线(边)组成的图来表示
每条边都显示为一条线(或曲线段)，其两个端点为节点
关于解决方案 动态图中有两种更新:一种是删除边，另一种是插入新边
这两个操作必须由用户来完成，同时算法会一直跟踪网络的绘图
这是研究人员发现的算法
可用于计算机电子设备 这是两位研究人员忙于撰写研究论文和解决自1998年以来霍尔姆一直断断续续研究的难题的时候
“我们不停地写这篇文章，写了五到六个星期
伊娃·罗滕博格说:“最后，它占据了80多页。”
幸运的是，没有人能打败他们找到解决方案，两位研究人员能够在主要的理论计算机科学会议上展示他们的结果，这些会议本应在芝加哥举行，但最终以虚拟方式举行
那么，这个数学难题的解可以用来做什么呢？这两位研究人员不确定，但他们有一些建议
“我们的研究是基础研究，所以我们很少知道它最终会被用来做什么
雅各布·霍尔姆说:“即使从一开始，我们就发现应用程序很难想象，所有电子产品中的微芯片和电路板的设计可能是我们的成果最终被利用的一个领域。”
在电路板上绘制导线时，它们绝不能相交
否则，会发生短路
这同样适用于微芯片，它包含数百万个晶体管，并且必须有一个图形
"
来源：由phyica.com整理转载自PH，转载请保留出处和链接！
