魔方吧·中文魔方俱乐部

标题: 询问这个局面的20步解法 [打印本页]

作者: f4f4f4 时间: 2008-12-28 19:51:14 标题: 询问这个局面的20步解法

看了魔方与上帝之数
了解到还原任何状态只需要20步
有一个全部棱方块都反转的局面
用Cube Explorer计算需要21步
R L F U2 R2 U' D' F2 R' F B U L2 B2 D2 R2 D' L2 D B2 D (21f)
问20步怎么解决？

作者: ares_g 时间: 2008-12-28 19:56:37

3阶魔方最远态要超过20步，目前证明是少于26步。

作者: tyeken8 时间: 2008-12-28 21:00:17

这个…把Explorer设置成从少向多搜索，出来的必是目标解

作者: purple 时间: 2008-12-28 21:02:24

现在还不能确定下限是不是20吧

作者: sokoban 时间: 2008-12-28 21:15:56

你要选中 optimal 之后，再算，才能得到20步的解法。这要算好一会，取决于你机器的速度。我的破机器（AMD Athlon 1.5 GHz, 512MB内存）算了15分钟都没算出来，就被我暂停。一会换一台机器算算。

[ 本帖最后由 sokoban 于 2008-12-28 21:16 编辑 ]

附件: sf.JPG (2008-12-28 21:16:58, 66.54 KB) / 下载次数 1
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MzQyMDZ8YjRhMjZjYWR8MTc0ODcxOTI3OXwwfDA%3D

作者: Cielo 时间: 2008-12-28 21:16:49

我从看到这个帖子开始就用 cube explorer 算了，现在终于算出来了：
U R U2 R F2 L U2 R F' B' R2 D R' L U2 F2 D2 F R2 D

作者: sokoban 时间: 2008-12-28 21:17:38

ls算了多久，机器什么配置？

作者: Cielo 时间: 2008-12-28 21:24:49

原帖由 sokoban 于 2008-12-28 21:17 发表
ls算了多久，机器什么配置？

不记得从几点开始算的了，不过我当时看见这帖时还没人回帖，所以应该是19：55左右吧！
我把 cube explorer 的窗口最小化了，只是偶尔看一次

发帖之前又看了一次就已经算出来了，所以可能算了1个小时多一点吧！

配置：1G内存、1.66GHz CPU

作者: sokoban 时间: 2008-12-28 22:24:45

呵呵, 计算时间还是挺长的

作者: 乌木 时间: 2008-12-29 11:09:14

不知道人家那理论探讨中说的“一步”，指90度，还是无论90度、180度都算一步的？这对于解法的总步数关系颇大呀。

作者: kexin_xiao 时间: 2008-12-29 12:38:18

乌木老师的问题，我也想问。还有，在“CROSS8步内完成”，180度算几步？

作者: sokoban 时间: 2008-12-29 12:52:51 标题: 回复 10# 的帖子

楼主这里所说的20步, 180度是算一步的.

作者: 乌木 时间: 2008-12-29 16:18:11

原帖由 sokoban 于 2008-12-29 12:52 发表
楼主这里所说的20步, 180度是算一步的.

这是明摆着的。我是问老外说的“20步”的一步是怎么样的“一步”？会不会人家把180度算作两步？如果是的，那楼主获得的步数和20步就不是差一步的问题了。

作者: sokoban 时间: 2008-12-29 16:27:30 标题: 回复 13# 的帖子

老外所说的20步，也是180度算一步的。可参加
http://bbs.mf8-china.com/viewthread.php?tid=19096
的5楼的说明。

[ 本帖最后由 sokoban 于 2008-12-29 16:28 编辑 ]

作者: f4f4f4 时间: 2008-12-30 09:55:24

非常感谢大家。因为机器只有256内存，算个最少13步的就要1个多小时，所以才在这里询问了。我猜想，或许再过4年，上帝之数为20就可以被机器证明了，或许，这就是玛雅人选20进制为基本进制的根本原因。

作者: 乌木 时间: 2008-12-30 11:48:41

原帖由 sokoban 于 2008-12-29 16:27 发表
老外所说的20步，也是180度算一步的。可参加
http://bbs.mf8-china.com/viewthread.php?tid=19096
的5楼的说明。

那5楼的说明只是讲魔方表层转动方式的种类，他说：“为了使这一问题有意义，当然首先要定义什么是转动。在对魔方的数学研究中，转动是指将魔方的任意一个 (包含 9 个小方块的) 面沿顺时针或逆时针方向转动 90° 或 180°，对每个面来说，这样的转动共有 3 种 (请读者想一想，为什么不是 4 种？)。由于魔方有 6 个面，因此它的基本转动方式共有 18 种。”

我想想，或许老外在那种计算（有人叫“两阶段搜索法”，是吗？）中，还是把180度转当作两步的。上面那注释中把180度转当作转动方式之一，不见得在两阶段搜索时，也一定把180度转动当作一步来统计。转动方式和步数统计法不一定要一致的吧？

我的意思是想问问，楼主获得的21步解法是不是和数学家们猜想的“20步”仅差一步？会不会还差得多呢？

作者: sokoban 时间: 2008-12-30 12:01:34

五楼的

为了使这一问题有意义，当然首先要定义什么是转动。在对魔方的数学研究中，转动是指将魔方的任意一个 (包含 9 个小方块的) 面沿顺时针或逆时针方向转动 90° 或 180°，对每个面来说，这样的转动共有 3 种 (请读者想一想，为什么不是 4 种？)。由于魔方有 6 个面，因此它的基本转动方式共有 18 种。

是一个注释，解释了什么是一次转动。这是对正文中的

那么，最少需要多少次转动，才能确保无论什么样的颜色组合都能被复原呢[注四]？

的一个注释。也就说定义了什么是一次转动。无论转180，还是转90，都算成一次。

转帖时，注释关系看不清楚，可查看原文：http://www.changhai.org/articles/science/mathematics/rubikcube.php

作者: sokoban 时间: 2008-12-30 12:07:17

再给出一个最原始的文献中对步数的定义：

Each move on the cube consists of grabbing the
nine cubies that form a full face of the larger cube,
and rotating them as a group 90 or 180 degrees
around a central axis shared by the main cube and
the nine cubies.

摘自《Twenty-Five Moves Suffice for Rubik’s Cube》一文。就是此文
作者通过计算证明22步足矣。(注：文章是老文章，只证明到25步。但基本方法
一样，所以作者虽然证明到22步了，但文章没有更新。可以看他的主页：
http://63.197.151.31/)

从中可以看出，180度算是一步的。

[ 本帖最后由 sokoban 于 2008-12-30 12:11 编辑 ]

作者: 乌木 时间: 2008-12-30 15:33:08

谢谢指点。17楼介绍的“原文”中的讨论部分中卢昌海的话也说明了“20步”的一步包含180度也算一步的，卢说：“网友：卢昌海发表时间： 2008-12-01, 09:14:17
是的。也有人讨论只用90度转动的情形，这时180度就得算两次转动，不过在讨论“上帝之数”时人们不用那种约定（如果用的话“上帝之数”将不会是20，比如有些组合需要24次90度转动才能复原）。”

我还有一个问题请教各位。那些数学家探讨的“上帝之数”并不是针对哪个具体打乱态求复原的具体步骤，而是总体上探讨魔方复原的最少步数的极值－－任一打乱态有其最少复原步数，有的少，有的多；各种打乱态的种种最少步数，总起来看，数学家们认为不会多于20步。我这样理解对吗？

而本帖是这么回事－－提出一个状态，用有关软件获得具体的复原步骤，再加以讨论一番。诸如此类，我总觉得和“上帝之数”并非一回事。那开解软件所用的方法是否保证得到的是最少步？即使针对某一打乱态所得的复原步数小于20，比如19步，是否不能再少？这19步能说明什么问题呢？最多表明了没超过“上帝之数20”罢了。但是，这19步是不是该打乱态所对应的“上帝之数”（我是指该打乱态的最少复原步数）呢？

我没什么数学基础，也许问题本身就不对，望各位指正。

[ 本帖最后由乌木于 2008-12-30 16:00 编辑 ]

作者: sokoban 时间: 2008-12-30 16:07:30 标题: 回复 19# 的帖子

你对“上帝之数”的理解是对的。

对于楼主所提及的软件 Cube Explorer，有两种计算模式。一种是所谓“二阶段搜索法”，这个方法只是找到一个步数较少的还原公式，但软件用时很短。

另外还有一种计算模式，可以计算任何一个状态的最小还原步数。这是一种本质上是穷举的计算方法，软件计算时间比较长(6楼的结果计算了一个多小时)，但是算出来的还原公式一定步数最小（在180度算一步意义上）。在此种模式下计算的步数一定是最小步数。

作者: 乌木 时间: 2008-12-30 16:25:02 标题: 回复 20# 的帖子

噢，那么，6楼的结果恰好证明该打乱态的最少复原步数没超过20。或许可以这么说，凡是用穷举法获得的复原步数，应该不超过20（当然，“20”本身还有待最后敲定），否则就说明方法还有待改进。对吗？至于寻找“上帝之数”课题的目的，倒不在于开解哪个具体的打乱态，而是从理论上探究魔方复原最少步数的极值。这课题当然对有关的种种具体小课题会有莫大的指导意义。对吧？

作者: sokoban 时间: 2008-12-30 16:47:26

穷举法找最小步数，如果算法逻辑上没有错，编程过程也没有错，计算机硬件也没有问题的话，那么算出来的最小步数是值得信赖的。我们都没有检查过上述过程，所以也不能保证程序的计算一定是对的。另外，穷举法的计算速度还是有很大改进的地方。

据该程序作者说，他已经对成千上万（其实可能是数十万，数百万）的状态用穷举算法找最小步数，没有找到过需要20步以上的。

所谓“上帝之数”，的确是理论意义更大一些，是所有状态复原的最小步数的最大值。

作者: gozichen 时间: 2009-1-1 13:37:23

对进行理论研究的同志致于最高的敬意。

但对我来说，看到这种贴我想起了郑板桥最著名的那四个字。

作者: kexin_xiao 时间: 2009-1-1 20:10:22

我对各位研究者佩服之至,努力学习

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)