关于最少还原步数

咖啡味的茶

无效动作一定存在，一些步骤左后一定会变回来，比如R U R' U'重复6次会回来，并且种类众多

乌木

<P>此前人家算出“27步……”等多种值，不断变小，一次次接近于早先的预言22步，有帖子还说有人算出“23步……”。随着技术的提高，此值多次被改进。楼主的算法得到的N究竟是27，还是26，还是23，甚至别的值？如果你的M值确定，则N值也确定了。你的N值和人家算的“……步数……”是一回事吗？难道你靠一次次修改M值来改进N值吗？而你说M不难计算，那么，你的结果N是多少呢？</P>
<P>&nbsp;</P>

[ 本帖最后由 乌木 于 2008-8-10 23:53 编辑 ]

乌木

还有，随着步数N的不同，各种N步之中要排除的无效步骤串的数目也会不同，M好像与N有关系的，修改了M，N会变（因为你的算式的等号右边为一定数）；N一变，M又会变，还有完没完？此事是否我理解错了，还是你的算法有矛盾？难道你的N和M之间的相互修正是良性的，是逐步逼近法？

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

乌木

<P>1楼加红补充说“<FONT color=#ff0000><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">我指的</SPAN><SPAN lang=EN-US style="FONT-SIZE: 10.5pt; FONT-FAMILY: 'Times New Roman'; mso-bidi-font-size: 12.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-fareast-font-family: 宋体">N</SPAN><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">，是指某一个魔方，至少需要</SPAN><SPAN lang=EN-US style="FONT-SIZE: 10.5pt; FONT-FAMILY: 'Times New Roman'; mso-bidi-font-size: 12.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-fareast-font-family: 宋体">N</SPAN><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">步还原（也就是保证转动</SPAN><SPAN lang=EN-US style="FONT-SIZE: 10.5pt; FONT-FAMILY: 'Times New Roman'; mso-bidi-font-size: 12.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-fareast-font-family: 宋体">N</SPAN><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">步可以还原，只要你知道方法）”<FONT color=dimgray>，</FONT></SPAN></FONT><FONT color=#ff0000><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><FONT color=dimgray>也许你是指不同的打乱态都有其“至少的复原步数”，即不同的态可有同N值，也可有不同的N，N是个变数。那么，你这个N和人家证明“……26步……”中的26不是同一概念，人家的“26”是指任何打乱态可以<FONT color=red>最多</FONT>26步（即≤26）复原。</FONT></SPAN></FONT></P>
<P><FONT color=#696969><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"></SPAN></FONT><FONT color=#696969><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"></SPAN></FONT>&nbsp;</P>
<P><FONT color=#696969><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">此事暂放一下。你的算式是，先列出一个“毛值”12^N＋12^（N-1）+………＋12^0 ，再减去含有无效步骤串的复原步骤的数目M，得到A（＝4.3×10^19，假定是三阶纯色）。上述不同的态可有相同的N值，也可有不同的N值，而你是进而把这些不同体现在固定N之后的N-1，N-2，……1，0之中了，即N不再是变数了。对吗？</SPAN></FONT><FONT color=#696969><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"></SPAN></FONT></P>
<P><FONT color=#696969><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"></SPAN></FONT>&nbsp;</P>
<P><FONT color=#696969><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">任一态都只计一次，或归入N，或归入N-1，或N-2，……或1，或0（12^0＝1，即复原态；12^1＝12，即12个“一步态”，等等），各自“对号入座”。</SPAN></FONT><FONT color=#696969><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"></SPAN></FONT></P>
<P><FONT color=#696969><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"></SPAN></FONT>&nbsp;</P>
<P><FONT color=#696969><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">你的算式蛮深奥，颇有“曲线救国”的味道。好像在一棵大态树上，修剪掉无用枝，剩下的整理分层求和。只不过是倒过来据和值求N值，此N值就是这态树的层数。</SPAN></FONT></P>
<P><FONT color=#696969><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"></SPAN></FONT>&nbsp;</P>
<P><FONT color=#696969><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">不知我是否误解这个算式了？</SPAN></FONT></P>

[ 本帖最后由 乌木 于 2008-8-11 12:57 编辑 ]

乌木

<P>我再想想，还有问题。次序倒过来看方便些：12^0＝1，0步态数目为1，即复原态。12^1＝12，1步态有12个，没问题。接下来就有问题了－－12^2＝144，其中一定有12个态是回到复原态的，2步态的数目不是12×12，而是12×11。后面的一系列计算，直到12^N，你都是先把每一层的态数统统扩大12倍再说，是否把消同态的事情集中于那个“－M”了？</P>
<P>&nbsp;</P>
<P>实际上，2步态开始每层有扩大，同时有消同态。起初是扩大超过减少，净结果是增长。过了一顶层数后，减少超过扩大，净结果是减小。总的模样呈现“大肚子”样子。到最远层时，态数决不是12^N啊！相对而言是个小得多的数目啊。要把（12^N＋……＋1）修剪为正确值，单单靠减去你的M就够了吗？我是不懂了，出于一种担心－－除了回到前一层的态已经在“－M”中得到扣除外，别的方式引起的同态，－M能加以扣除吗？你不妨解释一下。</P>
<P>&nbsp;</P>
<P>我说的“别的方式引起的同态”最简单的比如：R L 得到的2步态和另一条步骤 L R 得到的2步态，你的M能找出并处理类似它俩但步骤更复杂些的同态吗？它俩可是各自都没有“无效步骤”啊。</P>
<P>&nbsp;</P>
<P>再例如，步骤UUFUFUF'U'F'U'F'U'和步骤URBLFU'F'L'B'R'分别得到的两个态完全一样，那“－M”能觉察出来吗？所以，看来统计时只能瞄准态，根本不允许去管获得该态的具体步骤是什么。否则真不知会有多少重复记数，防不胜防啊。</P>

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

乌木

此类计算在二阶时计算量尚可，本区固顶帖中“黑王子”的工作就是一例，只不过他是求N和A，结果为11步和3674160。g老师也有大量相关研究。类似的工作在三阶时计算量将有多大？能否实现？我不懂，论坛也未见有关信息。只是看到关于“证明……26步……”等的介绍。

[ 本帖最后由 乌木 于 2008-8-11 19:17 编辑 ]

咖啡味的茶

嗯，我将努力计算，或者更换更好的方式，我会努力的，谢谢你的支持和建议

乌木

<P>25楼说“看来统计时只能瞄准态，根本不允许去管获得该态的具体步骤是什么”，这无异于自杀－－为了计算M值，非得看步骤（有无无效步骤串）；为了避免比如12步态UUFUFUF'U'F'U'F'U'和10步态URBLFU'F'L'B'R'是重复态，又只能一态计一次，不许看步骤，岂非折杀人？！</P>
<P>&nbsp;</P>
<P>何况拿到一态不看其获得步骤的话，又如何把此态归于几步态（所谓N步态，还是N－1步态，还是N－2步态，……）？如果说只要求出N，故无须具体把4.3×10^19－1个态分门别类，那么在求M值时总得看具体步骤吧。</P>
<P>&nbsp;</P>
<P>还有，由于获得一个态的步骤不是唯一的，所以在求M之前还得证明一个态所附的具体步骤是最少步，这又是难上加难啊。再考虑到同一个态的最少步有时也不是唯一的，所以，看步骤时不能脱开态。真是陷阱多多啊。</P>
<P>&nbsp;</P>
<P>涉及具体步骤后为何带来这样那样的问题，是否和魔方的态和态的关系是个很复杂的网络这一事实有关？要在任意两个态之间找出最短的变化路线（其步数关乎1楼说的N）很不容易，对吗？</P>
<P>&nbsp;</P>
<P>看来，1楼那种倒轧账式的计算N的式子只有象征意义，难以执行，是不是？</P>

[ 本帖最后由 乌木 于 2008-8-12 10:44 编辑 ]

bbshanwei

不是很明白。不容易理解的东西。

ggglgq

原帖由 <I>咖啡味的茶</I> 于 2008-8-10 16:03 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=208810&amp;ptid=12360" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A>
<DIV class=t_msgfont id=postmessage_208810>无效动作一定存在，一些步骤左后一定会变回来，比如<FONT color=blue><STRONG>R U R' U'重复6次会回来</STRONG></FONT>，并且种类众多</DIV>

<BR>&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp; 楼主的最初想法是好的，尤其是以上说法，更说明您的思路比较清晰。<BR>&nbsp; <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp; 只是楼主的数学语言不太准确，除了 乌木 先生所说的一些问题外，还有就是<BR>&nbsp; <BR><FONT color=blue><STRONG>重复 6 次的</STRONG></FONT> <FONT color=blue><STRONG>R U R' U' 并非“无效动作”</STRONG></FONT>，它与<FONT color=red><STRONG>“无效操作” R R' U U'</STRONG></FONT> 不同，<BR>&nbsp; <BR><FONT color=blue><STRONG>重复 6 次的 R U R' U' 是“循环变换”。</STRONG></FONT>&nbsp; 有关内容请您参考“循环变换理论”<BR>&nbsp; <BR>的相关内容。&nbsp; 它是解决各类魔方最少步还原问题的关键！<BR>&nbsp; <BR>&nbsp;&nbsp; <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp; 如果您能正确理解“循环变换理论”相关内容，对本主题会有很大帮助的。<BR>&nbsp; <BR>希望楼主继续您的理论。<BR>&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp;