当前位置:主页 > 历史趣闻 >

快速解开魔方本来就很难,不信来看看!

来源: 网络整理 时间:2017-07-13 11:40

   快速解开魔方本来就很难,不信来看看!

快速解开魔方本来就很难

快速解开魔方本来就很难,不信来看看!

转动绿色方块以解开魔方。

图片来源:Marko Mrkonjic/PIXSELLL

如果你觉得解开一个魔方存在困难,那么你的感觉是对的,数学可以提供支撑。近日一项研究表明,能否通过一定次数的步骤解开任意尺寸的被打乱的魔方,这被称为NP—完全,它是一个即便对数学家来说也很难解开的问题。

为了证明该问题是NP—完全,美国麻省理工学院研究人员Erik Demaine、Sarah Eisenstat和Mikhail Rudoy表明,弄清如何通过最少的步骤让魔方的一面拥有任何数量的方块,还能够让人们找到解开另一个非完全多项式的问题:汉弥尔顿路径问题。

该问题为:是否有一条路径能够确切地到达由一系列点组成、并由线段相连的图中的每个顶点,如三角形、五角星或是社交网络如脸谱网中更广泛的连接点。

它让人想起旅行推销员问题,该问题旨在找到一次性访问若干城市的最短路径,可能是最为著名的NP—完全问题。“描述它如何运作非常简练。”伊利诺伊大学香槟分校的Jeff Erickson说。

NP-完全问题非常容易检验,如果你得到一个初步解决方案,但随着输入数据的增加,需要解开它们的时间会激增,至少对于今天人们所知道的算式是这样的。同时,用算式在合理时间内解开程序的问题所基于的数据输入被称为P。

研究人员仍不确定是否存在算式能够更快地解开NP-完全问题。这个问题通常被称为P vs NP问题,是目前尚未解决的最重要的数学问题之一,该问题解题人将能从马萨诸塞州剑桥克雷数学研究所获得1000万美元的奖金。

每个标准的3x3x3魔方无论如何被打乱,从任何一个未知开始最多都能够通过20步被解开。2010年,程序员将20称为彩色魔方“上帝的数字”,他们选择这一命名表明即便是神也不能更快地解开魔方。

一年后,Demaine、Eisenstat和同事设计了一个方程式以解开任何边长的魔方,他们发现一个边长为n的魔方多需要的步骤正比于n2(2上标)/log n。

找到n=3魔方的“上帝的数字”花费了若干年的计算时间,Demaine推测,找到n=4魔方的“上帝的数字”要花费的时间还会比这长得多。“我猜想,它可能永远不能被解开。”他说。“‘上帝的数字’是大多数被打乱的魔方的最高上限,但很多魔方并不需要花费那么多步骤。弄清楚任何一个魔方结构是否能够采取更少的步骤非常棘手。”

所以,如果你解开魔方所费时间比较久,请勿沮丧,它不是你一个人的问题。“现在你有了借口:魔方本身就很难解开。”Rudoy说。你不必快速解开它,因此可以坐下来慢慢思考。

另附《小纳偷闲系列魔方入门教程》:

小编:八月未央

来源:科学网新闻 编辑:晋楠

声明:本文转载仅仅是出于传播信息的需要,并不意味着代表本平台观点或证实其内容的真实性;如其他媒体、网站或个人从本平台转载使用,须保留本平台注明的“来源”,并自负版权等法律责任;作者如果不希望被转载或者联系转载稿费等事宜,请与我们接洽,我们会及时处理。

欢迎个人转发到朋友圈

公众号、报刊等转载请联系授权

bainazhishi@163.com

▼点击查看百纳历史干货

| 百纳博士硕士谈高考| | “双一流”能否回答“钱学森之问| 穷人孩子要不要读研读博| 高考结束如何科学规划做好志愿前准备工作?| 一个工科女博士的辛酸求职经历及经验谈| Science Bulletin实现IF突破|

《百纳知识》由百纳公益组织创办和运营,

由子斯月、王成禹、赵序茅3位博士担任主编

廉富镯担任执行主编,

60余位本硕博和青年老师参与公益运营。

科研是一场美丽的冒险,

《百纳》愿做大家冒险路程中最真诚的陪伴者。

    上一篇:古人写诗的趣闻趣事:中国历史上写诗最多的诗人是谁?

    下一篇:三国趣闻:东吴老将黄盖竟险些冻死在厕所

    相关文章