魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 1652944|回复: 30
打印 上一主题 下一主题

[FM]状态集转换法——Ryan的两封信 [复制链接]

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

积分
3197
帖子
1034
精华
12
UID
564
性别

魔方理论探索者 魔方破解达人 论坛建设奖 六年元老

跳转到指定楼层
1#
发表于 2008-3-24 14:55:00 |只看该作者 |倒序浏览
这是Ryan Heise关于Thistlethwaite方法的两封E-mail
Translated by noski.

注:FMC,Fewest Moves Challenge。
For 3x3x3 Rubik's Cube.

在2002年的圣诞节,我研究了Thistlethwaite计算机算法的人脑计算理论。
下面是我在Yahoo! speedsolvingrubikscube上发的有关这个方法的邮件。

Post 1:
From: Ryan Heise <[email=rheise@it]rheise@it[/email]....>
Date: Sun, 22 Jun 2003 11:30:52 +1000
To: Ron van Bruchem <[email=rvb@chello]rvb@chello[/email]....>
Subject: Thistlethwaite, human version

On Sat, Jun 21, 2003 at 06:13:28PM +0200, Ron van Bruchem wrote:
> Hi Ryan,
>我对你的主意很感兴趣,请给我讲讲你提出的这套方法,以及每一步所使用的公式。

第一阶段:<U,D,L,R,F2,B2> 状态集(group)
  - 简单,没有公式。
第二阶段:<U,D,L2,R2,F2,B2> 状态集
  - 把上/下层的棱块移到上/下层(简单,没有公式)
  - 把角块移到上/下层(8-60个公式)
第三阶段:<U2,D2,L2,R2,F2,B2> 状态集
  - 角块(1-2个公式)
  - 棱块(1-4个公式)
第四阶段:各块归位
  - 角块(凭直觉)
  - 棱块(凭直觉)

各个步骤的细节

**第一阶段**

  完成这一阶段平均需要4.6步。

**第二阶段** 棱块

  这一步骤很简单,如果你愿意,你可以研究一下所有的20-30种情况。我忘记了确切的数字。完成这一步骤平均需要4步。

**第二阶段** 角块

  我用的方法和Gaetan相同,首先把三个角移到同一边,然后做8个公式中的一个。当然你可以直接学会所有的60种情况(我记不清确切数字了)。我认为这一步平均需要8.5步。

**第三阶段** 角块

  在第三阶段,很重要一点是要先做角块,因为因为你很难看出是否它们在U2D2L2R2F2B2状态集(group)中。仅仅让每个面上只包含其自身颜色和相对面颜色是不够的。当不需要考虑棱块时,完成这一步骤需要的公式会更短。

  在这里,我只是描述了只要两个公式的最简单的技巧,但这个技巧需要你有很快的手指和大脑:

  首先,分离上/下颜色(每个颜色都在各自的面上),平均需要3.2步。例如应该是这样:所有的红色角都在顶层,所有的橙色角都在底层。

  现在,几对相邻的角块可能匹配,也可能不匹配。我们的目标是让它们或者全匹配,或者全不匹配。所以,在这一步,我们把与众不同者找出来(无论匹配或不匹配),然后解决它们,让它们与其它对一样。这里一共有4对角块,所以与众不同者,只可能是一对两对。

  一对的情况:转动你的魔方,把这一对置于UF的位置,并做R'FR'B2RF'R。这是对角块移动的一个修正,不用考虑每个角块的具体位置。

  两对的情况:转动你的魔方,把这两对置于F面上(你可能需要把某一个移动过去),并做R2UF2U2R2U。(如果你需要事先把某一对移过去的话,可以使用一点小技巧来优化。。)

  我花了很长时间来寻找其它的用更短步数来完成这一步骤的方法,并且也找到了一些,但这个方法到目前为止绝对是最快的一个。

**第三阶段** 棱块

  4种情况-很简单(2、4、6或8个错棱(bad edges)),平均步数6.1步。

  到目前的步数一共为33.4,显然,为了达到最终平均少于40步的目标,寻找更短的步数是必要的。我也找了一些捷径,但我认为它们不值一做,因为我可以更快的执行这个稍长一点的方法。

**第四阶段** 终章

  我想,你对此已经想好策略了。角块,然后棱块。我觉把角块的所有情况都学会是可能的(大概150个,但很好记)。

  一个缺点是那些180度旋转(Double turns)比较难做,但我尝试了几个公式,感觉它们可以做得足够快。我想这个方法最大的益处就是反应时间快速和不用去思考。另一个好处是当你还原了魔方的时候,你会觉得好Cool!不到最最后,没有一个块是还原好的。。

  以上,我列出了没有优化的每一步骤。合并步骤,或者适机采用不同的顺序都是可以的。上面的基本的方法,如果你学会了每一步的所有情况,就能够给出一个平均步数为45.7步的答案。


Ryan

http://www.ryanheise.com/cube/human_thistlethwaite_algorithm.html

[ 本帖最后由 noski 于 2008-11-25 00:38 编辑 ]
已有 1 人评分经验 收起 理由
Cheng_943 + 15 精品文章

总评分: 经验 + 15   查看全部评分

The Answer to the Ultimate Question of Life, the Universe, and Everything 

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

积分
3197
帖子
1034
精华
12
UID
564
性别

魔方理论探索者 魔方破解达人 论坛建设奖 六年元老

2#
发表于 2008-3-24 14:55:26 |只看该作者
Post 2:
To: speedsolvingrubikscube@yahoogroups.com
From: Ryan Heise <[email=rheise@progsoc]rheise@progsoc[/email]....>
Date: Wed, 9 Jul 2003 15:42:19 +1000
Subject: [Speed cubing group] Method with the fewest non-obvious algorithms - zero

On Tue, Jul 08, 2003 at 05:09:13PM -0000, tomrokicki wrote:
> So what method requires the fewest algorithms that aren't "obvious"
> or logically clear?

使用简化的Thistlethwaite方法,可以不用任何难懂的公式就能还原魔方。

步骤1 不需要公式
步骤2 用一个5步的公式
步骤3 用一个7步的公式和一个4步的公式
步骤4 用两个6步的公式

因为所有的公式都很短很简单,所以使用这一方法人可以说,他们还原了魔方,并且懂得他们是如何做到的!
也许你觉得这还不够简单,但这是一个还原魔方的有趣的方法,如果你能做到的话。

**步骤1**

  把魔方转到<L2,R2,F,B,U,D>状态集(我称它为G1)。也就是说,把魔方转到一个状态,使得它可以只使用L2,R2,F,B,U,D来还原。在这个方法中,在步骤4之前,把相对面的颜色看成相同的,会对你有帮助。我们把左/右面的颜色称为“绿色”(这在步骤1中并不重要),上/下面称为“红色”,前/后面称为“白色”。

  一旦进入G1状态集,就不可能再翻转棱了,所以为了让魔方进入G1状态集,我们所要做的就是确保所有的棱块都正确翻转。首先,你需要找出未正确翻转的棱块(Bad edges)。一个未正确翻转的棱块是指,如果只使用G1中允许的转动(L2,R2,F,B,U,D)去把这个棱块归回原位,它的朝向是错误的。(当然了,只为判断,你用不着把它转回原位去)

  未正确翻转的棱总是偶数个,在0到12之间,或者平均6个。翻转棱的唯一方法就是把L层或R层转动90度,这样会一下子把这一边的4个棱全部翻转。为了翻转4个棱,你只需要简单把它们都放在一边(比如左边),然后把该层转动90度。为了翻转2个棱,你可以把其中一个放到L层上,再转90度,这样2个就变成了4个(新出现的3个+原来的1个),就又可是用刚才的方法了。

  在步骤1的末尾,你应该看到,没有一个红色的棱朝向前或后,没有一个白色的棱朝向上或下。在别人看来,你的转动简直没有任何成果!然而现在,12个棱都已处在一个比较好的位置上了。

**步骤2**

  把魔方转到<L2,R2,F2,B2,U,D>状态集(我称它为G2)。在这个状态集中,中层的棱块都位于中层(被UD夹在中间的层)上且被正确翻转了,而顶部和底部的棱块只能在这两层之间交换且不会再被翻转。在步骤2的末尾,你应该看到,顶面和底面只有红色,而在中层,绿色朝向左/右,白色朝向前/后。

  切记我们刚刚进入G1状态集,所以为了进入G2状态集,我们只能使用G1中允许的转动(L2,R2,F,B,U,D)。我们希望在顶层和底层各得到一个红色的Cross,而在12个棱块中,有8个是红色,由于空间有限,必有至少4个已成为Cross的一部分。通用的策略是,先在顶层和底层各放3个红色的棱,然后调整一下U和D,使得Cross的缺口都朝前。这时,两个缺失的红色棱块一定在中层的某处(如果不是,那一定有4个红色棱同时在顶层或底层,而不是3个)。用180度旋转(L2,R2,F2,B2)把这剩下的两个红色棱移到中层朝前的地方,再把F层转动90度。当这样把棱块做好时,我们得到了“对称”的结构,所以现在我们可以把整个魔方绕着U-D轴转动,随时改变一下前和后的观念了。很方便。

  现在开始解决角块,我们可以一次翻转两个角块。把一个角块放在LUF位置上(角A),把另一个角放在FDR位置上(角B),然后做:

  R'D - 翻转角B
  L2 - 交换角B和角A
  D'R - 在返回时翻转角A

  重复的这样做直到所有的角块都被正确翻转。你应该让所有的红色都在顶面或底面上。

**步骤3**

  把魔方转到<L2,R2,F2,B2,U2,D2>状态集(我称它为G3)。在前面的状态集中,你只是把顶面和底面都变成了相对面的颜色(红色),在这一步骤,你要把前/后面(白色)、左/右面(绿色)也做到这样子。在G3状态集中,每个角块只能处在四个位置中的一个,我称它为一个“环”。在魔方上只有两个环,8个角块分属其中。在G3状态集中,你能做的只能是180度转动,即交换一个环中的两个角块,同时交换另一个环中的两个角块。这就限制了角块可能的排列,也意味着简单的使每个面只有它本身的颜色和相对面的颜色是不足以满足G3的。

  既然角块会出一点小问题,所以我们先使角块进入G3状态集,然后再处理棱块。现在为了判断是否满足G3,你必须要区分相对面的颜色了。在这里我用的颜色是红对橙、白对黄、绿对蓝。一个判断是否满足G3的简单方法是把所有红色的角块移到顶层,橙色的角块放在底层,这样这些角块分成四对,每一对可能是匹配的,也可能是不匹配的。当它们全匹配或全不匹配时,角块就进入G3状态集了。所有角块都匹配只有一种情况,所有角块都不匹配也只有一种情况(在两个层都有一对对角相交换)。做R2U2R2,就可以在全匹配和全不匹配之间转换(使顶层的一对对角交换,底层同样)。当你手中的魔方不处于这个状态时,这有一个公式可以交换底层的一对对角,同时交换顶层的一对相邻的角块:

  R'FR' - 使4个目标角块移到B层
  B2 - 交换!
  RF'R - 返回

  在这种情况下,可以非常高效的暂时打乱G2,在这一步骤的结尾,又返回到G2状态集中。这个公式会交换DF、DB、UB三对角块,而不会影响到在UF处的角块对。当你在寻找那些匹配或不匹配的角块时,你会经常发现有一对与其它的不一样(比如另外三对都匹配了,只有一对不匹配)。当你找到这一对并把它拿在UF的位置,然后做上面那个公式,就会使所有角块相协调。

  接下来开始处理棱块,这就没什么特别之处了。棱块也是位于几个环之中,魔方总共有12个棱,分为3个环。中层的棱块在步骤2中已经做好了,而且也不会再离开它们的环。所以现在,我们只有UD两层的8个棱块需要处理。我们要做的是把白色的棱移到白色那一侧(前/后,这里白色泛指白、黄),把绿色的棱移到绿色的一侧(左/右)。处于错误位置的棱块的数目一定是偶数。最简单的公式是把绿色那一侧的两个棱与白色那一侧的两个棱相交换,绿色那一侧的两个棱必须放在底层(DL、DR),而白色那一侧的两个棱必须放在顶层(UF、UB)。然后做:

  D'
  M2(M是被L和R层夹在中间的层)- 交换!
  D

  这应该不需要解释了。像步骤1一样,如果你遇到了只有两个不正确的棱,那你可以很容易的把它变成4个。
  在这个步骤的末尾,你应该看到,在每个面上都只有它自身的颜色和它相对面的颜色。

**步骤4**

  魔方现在只用180度旋转就可以还原了。当然,如果我们能看出一些明显的捷径来,也可以用180度旋转以外的操作。

  首先,用180度旋转来还原角块。先找到一个面,把两个角块连在一起,那么这个面上的另两个角块就会自动连在一起(如果你步骤3做对了的话)。然后把两对角块移到一个面,另外4个角块自然会自动复原(如果你步骤3做对了的话)。

  接着还原棱块,这有两个容易理解的简单公式:
  F2R2 F2R2 F2R2 - 交换不同环中的两对棱块,其它的块不受影响。
  F2 M2 F2 M2 - 交换同一环中的两对棱块,第二个F2会把其它的块复原。

  运用这两个公式及它们的一些变化,就能够还原所有的棱。

  第一个公式的变化包括:
  R (F2R2 F2R2 F2R2) R'
  L2B2R (F2R2 F2R2 F2R2) R'B2L2

  第二个公式的变化包括:
  F2 M F2 M' (将两对棱重叠在一起,这样就能交换三个棱)
  F (F2 M2 F2 M2) F'


CUBE SOLVED
魔方还原完毕

Ryan
Copyright &copy; 2003 Ryan Heise

[ 本帖最后由 noski 于 2008-11-25 00:39 编辑 ]
The Answer to the Ultimate Question of Life, the Universe, and Everything 

使用道具 举报

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

积分
3197
帖子
1034
精华
12
UID
564
性别

魔方理论探索者 魔方破解达人 论坛建设奖 六年元老

3#
发表于 2008-3-24 15:05:30 |只看该作者
OK,先发这些,其它方法会陆续整理出来。
从这两封E-mail中,我们会发现这是一个很有意思的方法。
现在国内鲜有最小步还原的理论,也似乎没有人玩,我希望能为这一玩法的推广做一点点贡献。

注:FMC,Fewest Moves Challenge。
World Record:28步。

这似乎只是很多方法中的一种,我还有一丝疑惑,要尝试一下,看看它到底是FMC,还是SpeedCubing..

[ 本帖最后由 noski 于 2008-11-25 00:39 编辑 ]
The Answer to the Ultimate Question of Life, the Universe, and Everything 

使用道具 举报

禁止发言

陆&天

积分
1156
帖子
655
精华
2
UID
6548
性别
4#
发表于 2008-3-24 17:15:51 |只看该作者
提示: 作者被禁止或删除 内容自动屏蔽
Waste Allocation Load Lifters -- Earth

使用道具 举报

银魔

←{―盲拧―≡

Rank: 7Rank: 7Rank: 7

积分
1841
帖子
699
精华
6
UID
7539
性别
兴趣爱好
破解

论坛建设奖 八年元老

5#
发表于 2008-3-26 23:05:33 |只看该作者

回复 2# 的帖子

精辟!独到!终于看到有实际意义的最少步还原方法了!  谢谢楼主
☆┏┅◇·◇┅┓☆    /の /))))   (\./)︵      
ツ┇眞┃ 想┇ツ飞☆    \\  (﹀(        ∠·_灬_)~
の◇┅→☆←┅◇ の    \\/\' _/     ~~~~~~~~~魔 迷

使用道具 举报

Rank: 10Rank: 10Rank: 10

积分
16322
帖子
6926
精华
47
UID
68
性别
兴趣爱好
结构

收藏爱好者 魔方破解达人 魔方结构大师 十年元老

6#
发表于 2008-3-27 09:16:43 |只看该作者
<P>魔方比赛中就有设一项最少步的比赛,参赛的人只能备一张纸与一支笔,不许转动魔方,谁算出的步最少就是冠军,这个项目目前的WCA纪录好象是28步。</P>
<P>&nbsp;</P>
<P>魔方吧论坛虽然有设这个“最少步”的分区,但基本上都没人研究这个项目,包括理论区的几位大佬。此贴象是一把锁匙,指引大家走入“最少步算法”的大门。</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>谢谢楼主提供分享。<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/handshake.gif" border=0 smilieid="17"> </P>
<P>&nbsp;</P>
<P>加精、加固、加亮!</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>&nbsp;</P>

[ 本帖最后由 大烟头 于 2008-3-27 09:22 编辑 ]

使用道具 举报

Rank: 3Rank: 3

积分
852
帖子
687
精华
1
UID
24752
性别
居住地
南宁市
兴趣爱好
其它

四年元老

7#
发表于 2008-3-27 09:27:46 |只看该作者
看不懂...
此时的我果然还是只能呆“菜鸟入门”及“FCOP”
此ID有两人使用,姐妹俩。淑紫&淑君。

使用道具 举报

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

积分
3197
帖子
1034
精华
12
UID
564
性别

魔方理论探索者 魔方破解达人 论坛建设奖 六年元老

8#
发表于 2008-3-27 10:11:17 |只看该作者
谢谢大家的支持和帮助,有什么好资料我还会再拿回来分享的
The Answer to the Ultimate Question of Life, the Universe, and Everything 

使用道具 举报

银魔

←{―盲拧―≡

Rank: 7Rank: 7Rank: 7

积分
1841
帖子
699
精华
6
UID
7539
性别
兴趣爱好
破解

论坛建设奖 八年元老

9#
发表于 2008-3-27 19:34:30 |只看该作者
原帖由 <I>大烟头</I> 于 2008-3-27 09:16 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=103597&ptid=7091" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 魔方比赛中就有设一项最少步的比赛,参赛的人只能备一张纸与一支笔,不许转动魔方,谁算出的步最少就是冠军,这个项目目前的WCA纪录好象是28步。   



不许转动魔方

规则不是说可以自带三个魔方的吗?应该可以试转的吧

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
又去比赛规则里看了看:


E3)参赛者可以使用以下物品纸和笔(均由裁判提供)、三个魔方(自备)、不限颜色的贴纸(自备)。

还提到了贴纸,难道是不可以转动魔方,只能在魔方上面贴帖纸?
一片茫然……

[ 本帖最后由 一叶知秋 于 2009-1-1 20:41 编辑 ]
☆┏┅◇·◇┅┓☆    /の /))))   (\./)︵      
ツ┇眞┃ 想┇ツ飞☆    \\  (﹀(        ∠·_灬_)~
の◇┅→☆←┅◇ の    \\/\' _/     ~~~~~~~~~魔 迷

使用道具 举报

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

10#
发表于 2008-4-3 11:17:06 |只看该作者
<P>&nbsp;<BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp;&nbsp; 应该可以试转的! 请参考: <A href="http://bbs.mf8-china.com/viewthread.php?tid=6905&amp;extra=page%3D2&amp;page=3"><FONT color=blue><STRONG>附则E 最少步数还原</STRONG></FONT></A>&nbsp; 22 楼 。<BR></P>
<P><A href="http://bbs.mf8-china.com/viewthread.php?tid=6905&amp;extra=page%3D2&amp;page=3">http://bbs.mf8-china.com/viewthread.php?tid=6905&amp;extra=page%3D2&amp;page=3</A></P>
<P><BR>E1)标准规则见文章 A(速拧)。最少步数还原的附加规则如下所述:</P>
<P>E2)最少步数还原的程序: <BR>    ·E2a)裁判把一个打乱算法交给所有参赛者,裁判启动秒表并说“开始”。 <BR>    ·E2b)参赛者有 60 分钟的时间 以尽可能少的步数解决这个打乱算法 <BR>    ·E2c)在60分钟结束时,参赛者必须把他的解法符号清晰的写下来交给裁判,符号写法参考第十二章。 <BR>    ·E2d)衡量解法长度的步数单位是“半转”,转动 180 度算作两步。 <BR>    ·E2e)参赛者的解法不能和打乱算法有任何的关联,否则将被取消本次还原的资格 <BR>    ·E2f)参赛者必须清楚的说明他的解法。</P>
<P>E3)参赛者可以使用以下物品纸和笔(均由裁判提供)、三个魔方(自备)、不限颜色的贴纸(自备)。 <BR>    ·E3a)如果使用其他物品,将被取消本次还原的资格。 </P>
<P>&nbsp;</P>
<P>&nbsp;</P>
~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2024-11-25 14:14

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部