用了数学,魔方拧得更快了

标签: 业余 科普 魔方 数学 果壳 | 发表时间:2011-08-17 19:44 | 作者:fwjmath Slipper
出处:http://fwjmath.wordpress.com

本文遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守。

本文在果壳网发表,地址:http://www.guokr.com/article/49680/

魔方大概是现在最有影响力的智力游戏了,不仅有花式繁多的各种比赛(明着拧、盲着拧,用脚拧,潜水拧,总之就是拧着方法拧),连国内也有某名为“魔方”的超级计算机。魔方是一个3×3×3的正方体,一开始每个面的9个方格都涂上同样颜色,6个面一共6种颜色。作为一个智力游戏,它的目标就是将任意拧乱的魔方尽快还原为每面所有小方格同色的初始状态。为了赢得比赛,大家都致力于找到更快的魔方复原方法。

大概一年前,Google的一帮人就验证了任意拧乱的魔方可以在20步内复原。他们用的是一种相当聪明的暴力搜索方法,但即使这样,整个暴力搜索也需要一个CPU工作35年才能解决,当然他们有很多的CPU。但是,一般人要在20步内复原任意魔方的话,就要记住一个硕大无比的表格(大约8EB,一EB大约是十万TB),这东西只有拥有全知全能的上帝及其类似物(比如说团长、春哥或者高斯)才能做到,所以20这个数又被称为魔方的“上帝之数”。

魔方当然不只有一种。最简单的变化方法就是将魔方的“边长”(或者叫阶数)变大。原版的魔方是3阶的,也就是3×3×3的立方体。我们可以扩展到4阶(4×4×4),5阶,一直到7阶,甚至有人目击过11阶的魔方。魔方的阶数越大,解起来也越复杂,需要的步数也越多,它们的上帝之数也越大而且越难计算。

现在,一帮在MIT的由Erik Demaine领衔的数学家,竟然说他们找到了任意阶数魔方的上帝之数,而且还给出了一个复原的算法,需要的步数与上帝之数相差不远!我们现在就来看个究竟。

怎么转都转不出那24个陷阱

初看起来,魔方每个面可以拧得千变万化,让人无从捉摸。然而对于魔方面上涂色的小方块来说,它们可去的地方并不多。我们假设我们能做的操作就是将魔方的某排拧动90度。

无论魔方被如何拧动,途中所示的小色块一共只能到达最多24个位置。我们把这些位置称作一个位置群。一个n阶的魔方,不算边角上的色块,只有大约(n-2)^2/4个位置群。这些位置群都是相互独立的。要复原魔方,就相当于要将所有位置群复原。

Demaine从玩魔方的人们那里了解到,有标准的手法可以单单将一个位置群内的小色块复原,而不影响别的位置群的色块。这就是为什么我们所这些位置群是独立的。而因为每个位置群内色块的数目都是固定的(不多于24个),所以要复原一个位置群里的所有色块,只需要固定步数的操作。这些知识,魔方社区早就一清二楚。

但是,如果单靠这种方法来解n阶魔方的话,因为至少有(n-2)^2/4个位置群,所以用这种方法复原魔方需要的步数大约与n^2成正比。有没有可能用更少的步数复原魔方呢?尽管笔者没有下限,复原所有魔方的步数有没有下限呢?

上帝之数不能太小

为了方便,我们记n阶魔方的上帝之数为D(n)。他们首先证明了,对于足够大的n,D(n)不能太小,至少是cn^2/ln(n),其中c是某个常数。这个计算并不太难,我们就一起来试试看。

对于足够大的n,我们大约有n^2/4个位置群,它们各自有24个不同位置的小色块。在这24个色块中,6种颜色分别各有4个,这是初始状态决定的。用一点简单的组合知识就可以知道,我们一共有(24!)/(4!)^6种方法打乱一个位置群中的色块。因为位置群之间是独立的,所以魔方至少有((24!)/(4!)^6)^(n-2)^2/4种不同的打乱方式(还没算边角排列的各种可能性)。

由上帝之数的定义,我们可以在D(n)步内将任意魔方复原。如果我们将这些复原的步骤倒过来操作,这其实就意味着我们可以用至多D(n)步将魔方打乱到所有可能的打乱方式。每一步我们有(6n+1)种操作,每次操作就是将某一排拧上90度,另外复原后举起魔方炫耀然后被打倒在地踩上一万只脚也算一次操作,可以爬起来然后多次重复这项操作。所以魔方至多有(6n+1)^D(n)种打乱方式,因为某些系列操作会导致同样的打乱结果。

我们就有了以下的不等式:

\bigg( \frac{24!}{(4!)^{6}} \bigg)^{(n-2)^2/4} \leq (6n+1)^{D(n)}

从这个不等式我们可以得到:

D(n) \geq \frac{(n-2)^2}{4\log(6n+1)} \log(\frac{24!}{(4!)^{6}})

当n趋向于无穷大的时候,上面那个看起来很复杂的量就跟cn^2/ln(n)差不多了,其中c大约是35.7164。

可能我们做不到在cn^2/ln(n)步内还原任意的n阶魔方,但是能不能提出一种方法,即使还原的步数稍多一点,但是起码增长速度跟n^2/ln(n)一样呢?

互搭便车的暴力复原方法

可能是经济危机中人们的各种节俭方式(拼车之类的)启发了Demaine,他想,虽然位置群之间是相互独立的,但是也许可以将不同位置群的复原操作兼并起来,一次拧动同时解决多个位置群的问题。如果说原来的复原方法是每个位置群各自为政,各自拥有一条复原线路的话,Demaine他们的方法就相当于建起了一条公交线路,一次将多个位置群送到彼岸。

利用这个方法,他们给出了一个算法,可以在c’n^2/ln(n)步内还原任意的n阶魔方。在这里c’是另一个常数,它比c大得多。

本来笔者想在这里描述一下证明过程,但无奈这个证明过于暴力,打上R-18也不为过,所以笔者也不好说太细,想详细观赏的重口味同学请上arXiv看现场。这里笔者只能写意地描绘一下。

证明过程中最重要的引理之一是,对于某些特定的k*m个位置群,要复原它们中被打乱方式相同的位置群,按照传统的方法平均需要的步数正比于k*m,但我们可以建一条公交线路,只用正比于(m+k)的步数就可以将这些位置群一下子全部解决,代价是一些别的位置群“躺着也中枪”,不知不觉就被改变了。

然后,在一些必要的预处理(比如说先解决边角问题)后,Demaine他们将魔方的所有位置群大约平均地分成n/4份,通过巧妙地应用上面的引理,使每次中枪的都是固定的几个位置群。当所有其它的位置群都被复原后,剩下满身弹孔(认识QB的同学请自行脑补)的“中枪专用位置群”数目也不多,可以用传统的方法一个一个解决。整个过程所需要的步数,恰好差不多正比于n^2/ln(n),与最优的可能性只差一个乘法常数。这种过于暴力的方法,也是使常数c’变得很大的原因之一。

步步逼近上帝之数

可能你会说笔者太坑爹,刚才那种魔方社区都知道的办法需要的步数,增长趋势也只是n^2,也就是说最多是另一个常数乘以n^2。我们现在这么费劲也就是削下来了一个ln(n)的因子,这个看起来没什么用啊。

但不要小看ln(n)。常数毕竟是常数,它是不会变的,但是ln(n)可以无限增长。当n不断增长,总有一天ln(n)会比任何常数都要大,n^2会比n^2/ln(n)大得多。

那么,Demaine他们的工作意义是什么呢?他们其实证明了任意n阶魔方的上帝之数D(n)的增长趋势与n^2/ln(n)是一样的。更具体地说,尽管我们现在仍然不知道D(n)的具体表达式(可能永远也不会知道),但它必定在cn^2/ln(n)和c’n^2/ln(n)之间,c和c’都是常数。用数学的语言来说,我们第一次确定了任意n阶魔方上帝之数的阶,第一次将它困在了一个区间里。这是万里长征第一步,之后我们可以进行更精细的分析,缩短两个常数的距离,更好地确定上帝之数的位置。这也是Demaine他们下一步打算做的事情。

这个结果在魔方界也引起了不少人的兴趣。据某些魔方高手所言,Demaine他们的“差一个常数最优”的算法过程,对他们探索解高阶魔方的快速方法相当有启发,只是观摩已经满足不了他们了。


Filed under: 业余 Tagged: 科普, 魔方, 数学, 果壳

相关 [数学 魔方] 推荐:

用了数学,魔方拧得更快了

- Slipper - fwjmath的相空间
本文遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守. 本文在果壳网发表,地址:http://www.guokr.com/article/49680/. 魔方大概是现在最有影响力的智力游戏了,不仅有花式繁多的各种比赛(明着拧、盲着拧,用脚拧,潜水拧,总之就是拧着方法拧),连国内也有某名为“魔方”的超级计算机.

创新 - 王屋村的魔方们

- 余波 - 关心
最近我和一些同学们讨论了一些有关 “创新” 的问题. 我不由得想起王屋村发生的一个故事. 有一年开学, 一个叫果冻的同学从爪哇国带了这个新奇玩意到学校. 他口里念念有词, 转来转去, 居然能把魔方从凌乱的颜色还原成六面整齐的颜色. 班上的同学都很好奇, 课间的时候都看他表演. 一些同学托果冻给他们买魔方, 而且求果冻教他们玩,果冻采取”口传心授, 不立文字” 的方式教育, 很快获得了魔方大师的称号,并且成了魔方的唯一代理.

拧魔方?你们人类弱爆了!

- bamerl - 果壳网 guokr.com - 果壳网
作者:小杨 初学者复原魔方,通常都是采用层先法,公式少,也便于理解;高端竞速玩家一般是采用CFOP法,这种方法熟练之后可以在很短内将魔方的六面还原. 目前速拧魔方的世界纪录由澳大利亚的菲利克斯·曾姆丹格斯(Feliks Zemdegs)创造的5.66秒. 在2010年,迈克·道布森(Mike Dobson)和大卫·吉尔迪(David Gilday)设计出了一款名为“CubeStormer I”的乐高机器人,它的最快三阶魔方复原时间也只有12秒, 并且这也是当时机器人能达到的最快速度了.

[视频]乐高魔方机携手 Galaxy S II 5秒搞定随机魔方

- bill - cnBeta.COM
还记得由CubeStormer I 吗. 它只用12 秒来解一个魔术方块. 不过那已经是 2010 年的事了,现在它的第二代CubeStormer II 已经面世. 这一代除了在外观上变成了一个球形之外还有什么特别呢. 就是以 Samsung Galaxy S II 作为它的脑袋了. 这次它只是用了约 5 秒便完成任务,比第一代快一半有多,是一个颇惊人的纪录.

数学,传奇?

- cindy - 粉红小猪
   在国内就老是听到传奇,说是中国的数学有多么多么的好,国外的数学有多么多么的撇,还把这里的学生的数学,说得跟弱智一样,过来一看,都哪跟哪啊,这边的人还啭中国高中生呢:“微积分都不懂.   这边的数学书,搞得跟百科全书一样厚,都基本上没办法带回家,只能放学校个人的柜子里,是国内数学书的3-5倍厚重,从测量的历史开始写,图片跟历史地理一样漂亮,不大像数学书……我带回家给我爸看了一眼,他说:难怪学生不能自己拥有书,只能用完了下届学生继续用,这得多高的成本啊.

淘宝数据魔方技术架构解析

- 狗尾草 - 淘宝数据平台与产品部官方博客 tbdata.org
(本文首发于《程序员》8月刊,略有调整. 你可通过pengchun#taobao.com联系到作者. 淘宝网拥有国内最具商业价值的海量数据. 截至当前,每天有超过30亿的店铺、商品浏览记录,10亿在线商品数,上千万的成交、收藏和评价数据. 如何从这些数据中挖掘出真正的商业价值,进而帮助淘宝、商家进行企业的数据化运营,帮助消费者进行理性的购物决策,是淘宝数据平台与产品部的使命.

算法能解决任意大小的魔方

- 芸窗 - Solidot
可能只有铁杆玩家才会尝试挑战高于三阶的魔方,但现在一种算法将能解开任意阶数的魔方. 魔方研究在过去一年取得了重大突破,数学家Tomas Rokick等人证明魔方的最少还原步数(又被称为上帝之数)为20. 现在,MIT的计算机科学家Erik Demaine发现了一种通用算法可以解开任意阶数的魔方. 此前研究人员是利用“暴力破解”方式利用强大的计算能力去搜寻魔方的还原步法,但随着阶数越来越高,耗费的时间也越来越长,到最后暴力计算变得几乎不可能.

淘宝数据魔方技术架构解析

- So - 博客园新闻频道
淘宝网拥有国内最具商业价值的海量数据. 截至当前,每天有超过30亿的店铺、商品浏览记录,10亿在线商品数,上千万的成交、收藏和评价数据. 如何从这些数据中挖掘出真正的商业价值,进而帮助淘宝、商家进行企业的数据化运营,帮助消费者进行理性的购物决策,是淘宝数据平台与产品部的使命. 为此,我们进行了一系列数据产品的研发,比如为大家所熟知的量子统计、数据魔方和淘宝指数等.

魔方所有玩法谜题已被破解?

- flyq2000 - cnBeta.COM
最近,一支狂热的玩魔方国际团队借助计算机的帮助,声称已经破解了魔方的所有玩法谜题,而且每种解决方案都可以控制在转动20次以内. 他们力图寻找 移动次数最少的魔方同色归位解决方案.