论文部分内容阅读
8月，一个研究小组通过网站郑重地向世人宣布，他们在Google提供的超级计算机的支持下，已经破解了传说中的“上帝之数”——任意给定一种魔方布局，20步以内一定能将其还原。这在网络上立即引起了轩然大波。
要转动多少步?
从匈牙利建筑学教授Erno Rubik在1974年发明魔方的那一天开始，一个后来被称为“上帝之数”的终极魔方谜题便困扰着所有人：至少需要转动多少步才能保证解开任意一个魔方?
由于魔方的每个面都有顺时针90度、逆时针90度和180度三种旋转方式，因此魔方中的每一步就有多达3×6＝18种可能。步数一多，转动的方案数就将呈指数级增加。在所有的魔方布局中，一种叫做“超级大翻转”的特殊布局常被认为是最难还原的情形。在这种布局下，所有面的中心和所有角上的方块都位于正确的位置，只有每条棱上的颜色恰好都颠倒了。
在相当长的一段时间里，人们都一直认为还原“超级大翻转”至少得用22步。1992年，Dik I Wincer找到了用20步还原“超级大翻转”的方法；3年后，Michael Reid证明出，这已经是还原“超级大翻转”步骤最少的解法了。科学家们普遍猜测，不会存在比“超级大翻转”更困难的魔方布局了，也就是说“上帝之数”很可能就是20。
数十年的探索
为了明确“上帝之数”的真正数值，人们对“上帝之数”的探索长这数十年。科学家们早就想过，由于魔方的布局数量是有限的，因此可以借助计算机的力量对所有情况进行检验。然而，魔方中所有可能的布局有4300亿个之多，即使计算机每1秒钟能找出1万个布局的最优解，也需要1亿年的时间才能完成检验!
1992年，德国的一位数学教师Herbert Kociemba提出了著名的“二阶段算法”。他把还原魔方的过程分为了两个阶段，即先把魔方变为一种无需对四个侧面进行90度旋转便能还原的布局，再在这种限制条件下将此布局彻底还原。依据前一阶段的处理步骤，4300亿亿个魔方布局可以被划分为22亿组本质不同的情形，这个数字规模是当前的计算机能够承受的。在计算机程序中，Herbert Kociemba采用了一种叫做IDA的高效搜索方法，大大增加了寻找魔方解法的效率。
不过，由于当时计算机的运算能力有限，程序只能得到步骤尽可能少的还原方案。1995年，Michael Reid运用这种算法，验证了每一种魔方布局都能在30步以内还原。“上帝之数”的上限被降低到了30，但离科学家们的推测还有一段距离。
随着计算机硬件水平的提高，魔方问题不断地有了新的进展。从2005年开始，在连续三年里，“上帝之数”的上限先后被改进到了27步、26步、25步。2008年，天才程序设计师Tomas Rokicki对Herben Kcciemba的“二阶段算法”进行了一系列优化，成功地把“上帝之数”的上限降到了22，离胜利只有两步之遥了。
联合进攻最后一步
而这一回，程序设计师Tomas Rokicki与德国数学教师Herbert Kociemba联合了起来，与美国肯特州立大学数学家Morley Da—vidson和Google工程师John Dethridge一道，悄悄地组成了一支特别的国际研究小组，对“上帝之数”发起最后一波进攻。
他们利用魔方布局的对称性，将“二阶段算法”中的22亿组情形减少到了5588万组，并对计算机程序进行了新一轮的优化，使得每一组问题都可以在大约20秒内解决。最后，他们把这5588万组问题分配给了Google提供的一大批超级计算机，让所有的机器同时处理。这些超强性能的计算机只耗费了几个星期的时间便完成了运算，其运算量相当于一台普通计算机昼夜不停地工作长达35年。
8月份，研究小组建立了网站cube20org，不但宣布了“上帝之数”等于20，还给出了一些详细的统计数据：绝大多数魔方布局都需要16步以上才能获解，像“超级大翻转”一样至少得用20步才能还原的魔方布局竟然还有3亿多个!几十年来悬而未解的终极谜题得到了完美的解答，“上帝之数”的神秘面纱终于被揭开。
要转动多少步?
从匈牙利建筑学教授Erno Rubik在1974年发明魔方的那一天开始，一个后来被称为“上帝之数”的终极魔方谜题便困扰着所有人：至少需要转动多少步才能保证解开任意一个魔方?
由于魔方的每个面都有顺时针90度、逆时针90度和180度三种旋转方式，因此魔方中的每一步就有多达3×6＝18种可能。步数一多，转动的方案数就将呈指数级增加。在所有的魔方布局中，一种叫做“超级大翻转”的特殊布局常被认为是最难还原的情形。在这种布局下，所有面的中心和所有角上的方块都位于正确的位置，只有每条棱上的颜色恰好都颠倒了。
在相当长的一段时间里，人们都一直认为还原“超级大翻转”至少得用22步。1992年，Dik I Wincer找到了用20步还原“超级大翻转”的方法；3年后，Michael Reid证明出，这已经是还原“超级大翻转”步骤最少的解法了。科学家们普遍猜测，不会存在比“超级大翻转”更困难的魔方布局了，也就是说“上帝之数”很可能就是20。
数十年的探索
为了明确“上帝之数”的真正数值，人们对“上帝之数”的探索长这数十年。科学家们早就想过，由于魔方的布局数量是有限的，因此可以借助计算机的力量对所有情况进行检验。然而，魔方中所有可能的布局有4300亿个之多，即使计算机每1秒钟能找出1万个布局的最优解，也需要1亿年的时间才能完成检验!
1992年，德国的一位数学教师Herbert Kociemba提出了著名的“二阶段算法”。他把还原魔方的过程分为了两个阶段，即先把魔方变为一种无需对四个侧面进行90度旋转便能还原的布局，再在这种限制条件下将此布局彻底还原。依据前一阶段的处理步骤，4300亿亿个魔方布局可以被划分为22亿组本质不同的情形，这个数字规模是当前的计算机能够承受的。在计算机程序中，Herbert Kociemba采用了一种叫做IDA的高效搜索方法，大大增加了寻找魔方解法的效率。
不过，由于当时计算机的运算能力有限，程序只能得到步骤尽可能少的还原方案。1995年，Michael Reid运用这种算法，验证了每一种魔方布局都能在30步以内还原。“上帝之数”的上限被降低到了30，但离科学家们的推测还有一段距离。
随着计算机硬件水平的提高，魔方问题不断地有了新的进展。从2005年开始，在连续三年里，“上帝之数”的上限先后被改进到了27步、26步、25步。2008年，天才程序设计师Tomas Rokicki对Herben Kcciemba的“二阶段算法”进行了一系列优化，成功地把“上帝之数”的上限降到了22，离胜利只有两步之遥了。
联合进攻最后一步
而这一回，程序设计师Tomas Rokicki与德国数学教师Herbert Kociemba联合了起来，与美国肯特州立大学数学家Morley Da—vidson和Google工程师John Dethridge一道，悄悄地组成了一支特别的国际研究小组，对“上帝之数”发起最后一波进攻。
他们利用魔方布局的对称性，将“二阶段算法”中的22亿组情形减少到了5588万组，并对计算机程序进行了新一轮的优化，使得每一组问题都可以在大约20秒内解决。最后，他们把这5588万组问题分配给了Google提供的一大批超级计算机，让所有的机器同时处理。这些超强性能的计算机只耗费了几个星期的时间便完成了运算，其运算量相当于一台普通计算机昼夜不停地工作长达35年。
8月份，研究小组建立了网站cube20org，不但宣布了“上帝之数”等于20，还给出了一些详细的统计数据：绝大多数魔方布局都需要16步以上才能获解，像“超级大翻转”一样至少得用20步才能还原的魔方布局竟然还有3亿多个!几十年来悬而未解的终极谜题得到了完美的解答，“上帝之数”的神秘面纱终于被揭开。