26步还原鲁比克魔方论文中文版.doc

26步还原鲁比克魔方论文中文版26步还原鲁比克魔方 丹尼尔.孔克勒* 东北大学计算机科学院 波士顿，麻省02115/美国 K 吉恩.库珀曼* 东北大学计算机学院 波士顿，麻省02115/美国 译者 Alexandrell 提要 还原鲁比克魔方所需步数是一个为期甚久超过25年的难题-从鲁比克魔方出现时算起。这个数字有时被称为“上帝的数字”。上世纪90年代早期证明了上限是29步（以一面旋转为一步度量），后来2006年证明上限是27步。 证明上限是26步用了8000个小时的机时。得到这个成果的一个关键点是，用到了新的快速乘法对鲁比克魔方进行计算。另一个关键点是采用了基于磁盘的非核心并行计算，使用了上T（1024G）字节的磁盘存储空间。任何人可以使用预先计算好的数据结构，在零点几秒内，对一个特定的鲁比克魔方的状态，算出所需还原步数。进一步的研究将采用新的“暴力穷举”技术，以便进一步缩减还原鲁比克魔方所需步数的上限。 目录和标题描述：I.1.2符号和代数操作:代数公式 一般名词：公式，实验 关键字：鲁比克魔方，上限，置换群，快速乘法，基于磁盘的方法 1.绪言 在过去几十年，最少步还原鲁比克魔方是一个吸引人的问题对研究搜索和枚举技术的研究人员和爱好者都是如此。对于研究人员来说，鲁比克魔方作为一个知名的难题，可以用来比较不同算法的优劣。1982年，辛马斯特和弗雷2完成其著作“魔方数学”，推测“上帝的数字”在20到25步之间。 没人知道“上帝的算法”需要多少步，假设他总是用最少的步数还原魔方。已经可以证明有些图形最少需要17步还原，但是没人知道这些图形是什么样子的。有经验的理论家推测，最少步还原打任意打乱状态的魔方，“上帝的算法”所需最少步数很有可能在20到25步之间。 这个推测到今天仍然未被证明。提出它的时候，最为人所知的是，还原鲁比克魔方所需步数的大于17步小于52步2。现在证明出所需步数大于20步7。在证明它之前，能够证明出的所需步数小于27步5。这里，我们取得的进步是证明所需步数小于26步。 注意，在各种情况下，我们任为一步是旋转魔方一面的任意四分之一或者一半，也就是按照旋转一面为一步计量。我们不考虑可选择的旋转90度为一步计量，那种计量方式把旋转180度算作两步。 我们提出一个新的，代数的方法用于和数组对应的陪集。新颖之处在于下列各条之组合: 基于正方形子群的长度为二的子群链（顺序663，552） 新的快速乘法（所需时间小于100纳秒）用于对称陪集，或者发生器产生的对称群元素（见第三节，4.1和5 的定义）； 使用集合带宽为7TB的并行磁盘作为中间存储媒介，做有效的并行运算。（集合带宽是针对单个的随机存储器子系统带宽而言的。） 高效完善可计算对称陪集（见4.1节的定义）的哈希方程式，和对相反陪集的高效计算。 使用紧凑的数据结构表示图形陪集，每个状态用四个字节表示，对1.4x1012个状态进行编码。方法的基础是判定本体在正方形子群和相应的图形陪集中最远的距离。实话实说，计算只是用18个鲁比克魔方状态发生器（包括正方形发生器和逆向发生器）简单地做广度优先搜索。非核心运算需要建立超过65万亿个图形陪集。 使用48个对称的鲁毕克魔方（由24个几何形状的魔方，每个魔方附带一个倒置的几何形状的魔方形成）使得问题在空间上和时间上得以减化。这组鲁比克魔方的对称方式是自同构的。我们可以定义等价的群元素类别和等价的自同构陪集类别。这使图形陪集减少到大约1.4万亿个对称陪集。 *这项工作部分地得到了国家科学基金会在ACIR-0342555和CNS-06-19616许可下的支持。 为了个人或教学目的，可以免费得到这篇论文的数字拷贝或硬拷贝的许可。保证不利用或发布拷贝做商业或盈利的用途。拷贝中要提供这个注意事项，所有的引证在第一页。要拷贝其余部分，翻版，发布到服务器，或分配到列表，需要事先得到明确的许可，并可能需要付费。 ISSAC 2007 7.29-2007 8.1 加拿大安大略省滑铁卢 Copyright 2007 ACM 978-1-59593-743-8/07/0007 .$5.00 本文这样组织。第二节概要地回顾一些相关工作。第三节在高级别上提出全部公式。第四节描述背景和基本概念，特别地，包括了对称陪集和对称群元素的定义。第五节详述快速乘法公式，同时讲述完善的哈希方程式。第六节描述在对称陪集中，找到本体元素和全部元素距离相关地紧缩上限的细节。第七节讲述计算的细节和最终结果。 2.相关工作 一条找到还原鲁比克魔方所需步数上限的捷径是为对应的群生成完整的凯莱图。库珀曼，芬克尔斯坦，萨拉瓦吉使用这个方法证明11步可以还原鲁比克2阶魔方1。对于鲁比克3阶魔方来说，这个方法是不可行的，因为3阶魔方共有超过4.3x1019种状态。 最先发表的还原所需步数上限为52步。由西斯尔韦斯特2发现，他的方法基于用4个步骤还原魔方，对应一个长度为4的子群链。已经证明，4个步骤在最坏情况下的步数分别为7，13，15，和17，总步数52步。 1992年，这个算法被科切姆波尔3用一个长度为2的子群链改进。1995年，赖德证明，两个步骤在最坏情况下的步数分别分12步和18步，总步数为30步。进一步的分析表明最坏的情况不会出现，所以29步的上限得以证明。2006年，上限被拉杜进一步改善为27步，这是在本文发表之前找到的最小上限了。 除了对可证明的最坏情况分析的工作以外，一些对非最坏情况下最优解的分析也得到了发展。由科切姆波尔发展的方法，赖德在保证最优解的前提下做了自然延伸。科尔夫4用类似的技术最优地还原了10个随机打乱的魔方，一个用了16步，一个用了17步，另外6个用了18步。 3.方法综述 用正方形子群（只用半面旋转产生的子群）作为中间子群，把鲁比克魔方群分解成长度为2的链。正方形子群只有663,552个元素，而在鲁比克群中有大约6.5x1013个陪集。这与之前相关的研究大不相同，之前使用子群导致了近乎相同数量的子问题。改善还原鲁比克魔方所需步数上限的策略为以下三点。一，3.1节，制造一个对称子群图（对称凯莱图），子群元素作为结点，发生器作为边界，并证明没有元素和本体之间的距离超过13。二，3.2节，制造一个对称陪集图（对称施赖埃尔陪集图）,并证明没有陪集和平凡陪集之间的距离超过16。前两步证明一个初始的上限29。最后在第6节，我们通过检测对称陪集中的群元素和平凡群元素之间的距离，有效地找出更紧凑的上限，最后产生的上限是26. 3.1 构造对称凯莱子群图 由于正方形子群的体积很小，去除对称的状态只有15,752种情况，和相应的陪集的计算量相比，对它的计算量可以忽略不计。 首先，使用正方形发生器，用广度优先的方式构造正方形子群的对称凯莱图。这一步甚至只要在一台计算机上使用简单的工具，计算几秒钟就可以完成了。因此，我们在充许使用18个发生器中任意一个的前提下，找到了正方形子群中所有元素的最优解。这步对每个子群元素做双向搜索，用了一天的机时。 我们选择如下的方式做双向搜索，从两个状态出发。首先，使用全部的发生器做一个深度为7的向前搜索。然后，对正方形子群中的15,752个群元素分别做向后搜索。向后搜索需要的时间从几毫秒到最坏情况下的几小时不等。总之，优化的过程需要略小于一天的时间，不需要并行化。 3.2构造对称施赖埃尔陪集图 从本质上说，构造是基于队列的广度优先搜索。算法的复杂性主要归于减少搜索魔方48种对称状态所需空间的必要性，和对磁盘的使用。主数据结构是一个近乎完美的稠密哈希数组，含有1.5x1012条数据。所有的对称陪集都在相应的哈希索引范围之内。每条数据是一个四字