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

26步还原鲁比克魔方论文中文版 26步还原鲁比克魔方 丹尼尔.孔克勒* 东北大学计算机科学院 波士顿，麻省02115/美国 Kunkle@ccs.neu.edu 吉恩.库珀曼* 东北大学计算机学院 波士顿，麻省02115/美国 gene@ccs.neu.edu 译者 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.相关工作 一条找到还原鲁比克魔方所需步数上限的捷径是为对应的群生成完整的凯莱图。库