[原创]基于N阶定律的魔方最短步数分析导论

pengw 发表于 2006-6-28 23:37:04

<h1>忍冬</h1><h1>------------------</h1><h1>1.分析对象 </h1>正方体色子阵N阶魔方任意二个状态的最短步数<h1>2.基础知识</h1>掌握N阶定律<h1>3.术语定义</h1>魔方状态：魔方所有块的位置与色向的一个静态集合簇状态：簇所有的块的位置与色向的一个静态集合转层：不含中棱块的所有内层；所有表层转动单位：任意转层90度转动视为一个转动计量单位，这也是影响状态的最小转动动作：一个转层在特定方向进行一个转动单位的运动公式：实现任意二个状态转换的转动序列，以转动单位为计量单位公式步数：公式转动步数之和，以转动单位为计量单位最短步数：实现任意二个状态转换的最短公式步数最远状态：对魔方任意状态A总是存在状态B，状态B转换到状态A的最短步数不小于所有其它状态转换到状态A的最短步数，则称B为A的最远状态或A为B的最远状态。将一个簇看成一个子魔方时，以上定义同样适用于簇。子魔方：与簇同义魔方：子魔方的集合<h1>4.目标设定</h1>最短步数与最远状态讨论向来是魔方问题的极品，人们总是关心以下问题：1．   如何找出魔方任意二个状态的最短步数2．   如何找出魔方任意状态的最远状态从魔方状态穷举这个层面寻求答案是最纯朴的方法，几乎不得不面临天文数字的魔方状态挑战。从魔方公式分析的角度寻求答案，形同盲人摸象，连基本方向都错了,远没有切入问题的本质。本文仍然从魔方基本变换分析入手，找出解决以上问题切实可行的重要线索，并揭示解决以上问题的关键因素。从魔方基本转动入手，已经解决了状态描述问题，不同的是，现在要从簇的基本转动入手，分析最短步数问题。在此并不是要给出一个最终解决方案，仅仅是运用现有知识进行定量定性分析，确定一个解决问题的正确方向，明确真正需要解决的问题是什么，纠正以往魔方最短步数研究存在的盲人摸象的困境,并最终给出一个适用于N阶魔方最短步数/最远状态求解的通用方法指导.<h1>5.分解魔方</h1>魔方由簇构成。二阶魔方仅有一个簇，二阶以上魔方有多个簇。三阶有三个簇。所有块只能在自已所属的簇内变换。因此，我们可以将魔方的每一个簇的变换独立出来分析，再合在一起分析簇与簇之间的相互影响。如果将簇视为子魔方，所有子魔方当前状态的集合构成一个魔方当前状态，这些子魔方的状态及这些状态的组合关系，受N阶定律完全制约。以三阶为例，三阶可以分解为边角块簇A，中棱块簇M，中心块簇H。将每个簇想象为一个独立的子魔方，这些子魔方分别都存在以下性质：1．   独立的扰动关系，即自扰动2．   独立的簇内变换3．   任意二个簇状态之间存在最短步数4．   任意一个簇状态存在最远状态1．   与其它簇分享部分或全部转层2．   任意簇的一次转动必然代表魔方的一次转动，反之，魔方一次转动代表一个或多个簇的转动本质上：1．   魔方是子魔方组合在一起共同变换的杂合体2．   每个子魔方的性质不受子魔方组合方式的影响3．   魔方任意当前状态是子魔方当前状态的集合4．   子魔方状态的搭配方式受制于子魔方组合方式，即N阶定律描述的扰动关系3．   子魔方的最短步数/最远状态完全制约魔方最短步数/最远状态4．   让尽可能多的子魔方同时沿着各自的最短步数变换，是解决魔方最短步数求解的核心思想<h1>6.子魔方类 </h1>从N阶定律对簇的分类可知，N阶魔方从结构上可将簇分为以下类型：（二楼续） 
[此贴子已经被作者于2007-3-11 8:23:04编辑过]

pengw 发表于 2006-6-28 23:47:45

<TABLE cellSpacing=0 cellPadding=0 width=641 border=1>

<TR>
<TD vAlign=top width=64 rowSpan=2>


</TD>
<TD vAlign=top width=277 colSpan=5>
2n阶魔方 

</TD>
<TD vAlign=top width=300 colSpan=5>
2n+1阶魔方 

</TD></TR>
<TR>
<TD vAlign=top width=55>
簇数 

</TD>
<TD vAlign=top width=42>
块数 

</TD>
<TD vAlign=top width=60>
每块色向数 

</TD>
<TD vAlign=top width=60>
每块色向状态数 

</TD>
<TD vAlign=top width=60>
每簇状态数 

</TD>
<TD vAlign=top width=72>
簇数 

</TD>
<TD vAlign=top width=48>
块数 

</TD>
<TD vAlign=top width=36>
每块色向数 

</TD>
<TD vAlign=top width=60>
每块色向状态数 

</TD>
<TD vAlign=top width=84>
每簇状态数 

</TD></TR>
<TR>
<TD vAlign=top width=64>
边角块簇A 

</TD>
<TD vAlign=top width=55>
1 

</TD>
<TD vAlign=top width=42>
8 

</TD>
<TD vAlign=top width=60>
3

</TD>
<TD vAlign=top width=60>
24 

</TD>
<TD vAlign=top width=60>
8!*3^7 

</TD>
<TD vAlign=top width=72>
1 

</TD>
<TD vAlign=top width=48>
8 

</TD>
<TD vAlign=top width=36>
3 

</TD>
<TD vAlign=top width=60>
24 

</TD>
<TD vAlign=top width=84>
8!*3^7 

</TD></TR>
<TR>
<TD vAlign=top width=64>
中棱块簇M 

</TD>
<TD vAlign=top width=55>


</TD>
<TD vAlign=top width=42>


</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=72>
1 

</TD>
<TD vAlign=top width=48>
12 

</TD>
<TD vAlign=top width=36>
2 

</TD>
<TD vAlign=top width=60>
24 

</TD>
<TD vAlign=top width=84>
12!*2^11 

</TD></TR>
<TR>
<TD vAlign=top width=64>
中心块簇H 

</TD>
<TD vAlign=top width=55>


</TD>
<TD vAlign=top width=42>


</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=72>
1 

</TD>
<TD vAlign=top width=48>
6 

</TD>
<TD vAlign=top width=36>
4 

</TD>
<TD vAlign=top width=60>
4 

</TD>
<TD vAlign=top width=84>
2^12 

</TD></TR>
<TR>
<TD vAlign=top width=64>
边棱块簇B 

</TD>
<TD vAlign=top width=55>
n-1 

</TD>
<TD vAlign=top width=42>
24 

</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=60>
24! 

</TD>
<TD vAlign=top width=72>
n-1 

</TD>
<TD vAlign=top width=48>
24 

</TD>
<TD vAlign=top width=36>


</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=84>
24! 

</TD></TR>
<TR>
<TD vAlign=top width=64>
心棱块簇E 

</TD>
<TD vAlign=top width=55>
n2-3n+2 

</TD>
<TD vAlign=top width=42>
24 

</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=60>
24! 

</TD>
<TD vAlign=top width=72>
n2-3n+2 

</TD>
<TD vAlign=top width=48>
24 

</TD>
<TD vAlign=top width=36>


</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=84>
24! 

</TD></TR>
<TR>
<TD vAlign=top width=64>
心角块簇C 

</TD>
<TD vAlign=top width=55>
n-1 

</TD>
<TD vAlign=top width=42>
24 

</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=60>
24! 

</TD>
<TD vAlign=top width=72>
n-1 

</TD>
<TD vAlign=top width=48>
24 

</TD>
<TD vAlign=top width=36>


</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=84>
24! 

</TD></TR>
<TR>
<TD vAlign=top width=64>
直棱块簇F 

</TD>
<TD vAlign=top width=55>


</TD>
<TD vAlign=top width=42>


</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=72>
n-1 

</TD>
<TD vAlign=top width=48>
24 

</TD>
<TD vAlign=top width=36>


</TD>
<TD vAlign=top width=60>


</TD>
<TD vAlign=top width=84>
24! 

</TD></TR></TABLE>
注1：空格表示不存在，n>=1
注2：簇状态数都没有考虑消同态
要解决魔方最小步数计算，关键是必需首先解决以上每个簇任意二个状态的最短步数计算，而当前只解决了中心块簇最短步数计算，其余六个簇类尚没有高效快捷的算法见于世人，除了穷举法。而穷举法面对子魔方状态，从上表看以看出，并非天文海量，相对惊人运算能力的计算机，穷举法也许不算一个很坏的选择。


<H1>7.协调变换 </H1>
显示，要解决魔方的最短步数问题，必须使尽可能多的子魔方（簇）同时沿着自已的最短步数变换，而子魔方之间的差异性及魔方结构并不总是充许所有的子魔方同时沿着自已的最短步数变换，这就要求在魔方结构充许的条件下，协调各子魔方的变换，从而获得一个最佳协调变换的结果-任何二个魔方状态的最短步数。每次协调的结果，体现为：针对当前所有子魔方状态，选择一个最佳动作进入到下一个魔方状态，然后再针对下一个当前状态进行协调，再选择一个最佳动作，直到目标状态为止。这些协调出来的最佳动作序列，就是特定二个魔方状态间的最短步数。


<H1>8.转动分析
</H1>
n>=1,2n及2n+1阶魔方共有6n个转层，每个转层有二个动作（+90转动，-90转动），因此2n及2n+1阶魔方共有12n个动作。


除二阶魔方的转动是单簇进行外，所有其它阶的任意转动都是多簇联合参与。例如，三阶的任意转总是三个簇同时参与。12n个动作是改变当前魔方状态的最小行为，总是要选择满足协调原则的动作来改变魔方状态。显然魔方任意二状态转换的最短步数受制于魔方始态中，拥有最大最短步数的簇，拥有最大最短步数的簇决定魔方状态转换最短步数的下限。


<H1>9.核心问题
</H1>
1．找出计算每类簇任意二个簇状态之间最短步数的方法


2. “尽可能多的簇同时沿着各自的最短步数变换”为基本原则，以此协调各簇变换，从而求得 

（三楼续）
[此贴子已经被作者于2006-6-29 11:59:24编辑过]

pengw 发表于 2006-6-28 23:52:33

魔方任意二状态间的最短步数或求得魔方任意状态的最远状态的最短步数


<H1 2pt LINE-HEIGHT: normal? 0cm;>10.最短步数算法 </H1>
1. 在当前魔方状态上分别执行12n个动作后，分别获得12n个魔方状态


2. 对12n个状态分别计算所有簇相对于簇终态的簇最短步数及每个状态的所有簇最短步数之和


3. 取一个簇最短步数之和最小的状态作为当前状态，并记录其动作


4. 回到第一步，直到当前状态是魔方目标状态为止。


5. 所有记录下来的动作，即是魔方始/未二态的最短步数


<H1 2pt LINE-HEIGHT: normal? 0cm;>11.最远状态算法
</H1>
1. 在当前魔方状态上分别执行12n个动作后，分别获得12n个魔方状态


2. 对12n个状态分别计算所有簇相对于簇始态的簇最短步数及每个状态的所有簇最短步数之和


3. 取一个簇最短步数之和最大的状态作为当前状态，并记录其动作


4. 回到第一步，直到最大的簇最短步数之和小于等于前一次记录的最大簇最短步数之和为止。


5. 倒数第二次状态就是魔方始态的最远状态，记录下来的动作就是到达最远状态的最短步数。
<H1>12.核心思想 </H1>
1． 魔方由独立变换的子魔方构成,子魔方性质相对魔方阶数恒定不变
2 魔方扰动关系仅仅决定子魔方之间的状态搭配关系,不干涉任何子魔方的状态变换. 


3． 所有子魔方变换构成魔方变换


4． 魔方最短步数的本质是所有子魔方从各自的始态走向终态的过程中，所有子魔方转动数之和最小的求解





<H1 2pt LINE-HEIGHT: normal? 0cm;>13.比对分析
</H1>
1． 以前最短步数相关研究总是浮在魔方转层这个层面，而一个魔方转层往往对应多个簇转层，因此魔方转层这个层面的研究含混不清，目标不明确，研究者本人最终不可避免地走入死胡同.况且研究对象仅仅特定于二、三阶,并且连基本思路/基本原理都表达不清楚.


2．本文最短步数研究以簇为子魔方，以簇转层为基本转层，寻找魔方最短步数的问题转换为协调尽可能多的子魔方同时（显示魔方结构决定，所有簇大多数情况下，不可能同时沿着各自最短步数变换）沿着最短步数变换，从而获得魔方最短步数的求解，在求解过程中，动作就是彼此相互妥协而决定的产物，动作序列就是魔方的最短步数。


3． 当前魔方最短步数研究的焦点已转变为对各簇最短步数的求取，显示极大地简化了研究难度，为最终求解魔方最短步数做出了理论上的关键突破，纠正了以往宗教式的研究方法，重新确定了正确的研究方向，只要解决了七个簇类最短步数的求解决问题，就摘取了魔方问题最后一个桂冠，相信这个问题的解决指日可待。


<H1 2pt LINE-HEIGHT: normal? 0cm;>14.最终解决
</H1>
以上描述，已给出一个解决魔方最短步数非常清淅的思路及算法结构，显然,最短步数问题不是人工可以轻易解决的问题,因此实现最短步数算法的琐碎细节，就留给精力充沛的职业编程手去完成。


<H1 2pt LINE-HEIGHT: normal? 0cm;>15.论文后语
</H1>
<DIV 0cm; 24pt; mso-element: para-border-div; mso-border-bottom-alt: .75pt? PADDING-RIGHT: PADDING-LEFT: PADDING-BOTTOM: PADDING-TOP: 1pt solid; BORDER-TOP: BORDER-LEFT: BORDER-BOTTOM: medium none; windowtext solid>
<P 0cm 0cm; mso-border-bottom-alt: .75pt? PADDING-RIGHT: PADDING-LEFT: PADDING-BOTTOM: PADDING-TOP: BORDER-TOP: BORDER-LEFT: BORDER-BOTTOM: medium none; windowtext solid MARGIN: 24.0pt 0pt; mso-padding-alt:>以往仅想搞搞状态描述相关的问题研究，无意争辉于拥有众多高人出手的最短步数问题，但是所能读到的最短步数相关文章，如同大藏经般，令凡人不可企及，根本无法弄懂这些文章是如何引导最短步数问题的解决，也根本看不出这些文章是如何解决最短步数问题，因此，在N阶定律的基础上，完成了这篇以N阶魔方为对象的最短步数导论性论文，本人认为，与以往相关文章最大的不同在于给出一个目标明确、思路清淅、层次分明、论述完整、N阶通用的解决最短步数问题的方向引导。
<P 0cm 0cm; mso-border-bottom-alt: .75pt? PADDING-RIGHT: PADDING-LEFT: PADDING-BOTTOM: PADDING-TOP: BORDER-TOP: BORDER-LEFT: BORDER-BOTTOM: medium none; windowtext solid MARGIN: 24.0pt 0pt; mso-padding-alt:>-------------------------------

</DIV>
忍冬
<st1:chsdate IsROCDate="False" IsLunarDate="False" Day="7" Month="6" Year="2006" w:st="on">2006年6月7日</st1:chsdate>完成于福州长乐机场


[此贴子已经被作者于2006-6-30 6:23:27编辑过]

乌木发表于 2006-6-29 00:48:14

3楼说： [最远状态 1. 在当前魔方状态上分别执行12n个动作后，分别获得12n个魔方状态 2. 对12n个状态分别计算所有簇相对于簇始态的簇最短步数及每个状态的所有簇最短步数之和 3. 取一个簇最短步数之和最大的状态作为当前状态，并记录其动作 4. 回到第一步，直到最大的簇最短数之和小于等于前一次记录的最大簇最短数之和为止。 5. 倒数第二次状态就是魔方始态的最远状态，记录下来的动作就是到达最远状态的最短步数。]
我模糊地感到以上所述中是否应该在每一循环对于所得的“12n个魔方状态”先来个“消同态”，以免“走回头路”或“重复计算”。具体的我一时说不清楚，或许您的方法中不存在“同态”问题（？）。

pengw 发表于 2006-6-29 06:25:29

乌兄，同态在子魔方当前状态到终态最短步数的计算中呈现并消除，如果认为存在没有表达清楚的地方，烦请举例说明为盼，谢谢。从这篇论文中可以明白，为什么从魔方转动的角度的研究是如此模糊与不确定。

jinyou 发表于 2006-6-29 09:16:06

<DIV class=quote>以下是引用pengw在2006-6-28 23:47:45的发言： 


n>=1,2n及2n+1阶魔方共有6n个转层，每个转层有二个动作（+90转动，-90转动），因此n阶魔方共有12n个动作。</DIV>
是否是这个意思？
n>=1,2n及2n+1阶魔方共有6n个转层，每个转层有二个动作（+90转动，-90转动），因此2n及2n+1阶魔方共有12n个动作。

乌木发表于 2006-6-29 09:36:16

冬兄辛苦。我提不出何处未表达清楚，只能问些问题。
关于消同态，有的同态可以消灭于萌芽之前，例如初态A经12n个动作之一U得态B，那么在接下来的循环中，就不必考虑态B经U'这个动作了，因为B经U'必得同态A。所以态B就只要做12n-1个动作。余类推。
有的同态是“隔代”的，各代态数过了“高峰”后，隔代同态越来越多，以致同态数超过新生态数。为了隔代消同态，不知您有何好办法。如果用比对两个态的代码的方法，且仍然是穷举式的、历遍式的比对法，每出生一个态，就要和它的所有前辈比对。一则随着代数的增加，要比对的态数越来越多（几何级数增加），二则前面的态多次参与比对，徒唤无奈。
如果说原来人们的方法是不分簇的，计算量太大，而分簇的方案说是简化了（尽管每个态还是要做12n个动作），那么，暂不论两种方案在消同态方面的计算量有无差别，分簇方案中的“协调”工作计算量大吗？

乌木发表于 2006-6-29 09:38:53

“n阶魔方共有12n个动作。”应是笔误。

pengw 发表于 2006-6-29 10:11:31

<DIV class=quote>以下是引用jinyou在2006-6-29 9:16:06的发言： 
是否是这个意思？
n>=1,2n及2n+1阶魔方共有6n个转层，每个转层有二个动作（+90转动，-90转动），因此2n及2n+1阶魔方共有12n个动作。</DIV>
就是就是，大大的粗心，谢谢金优

pengw 发表于 2006-6-29 10:21:04

<DIV class=quote>以下是引用乌木在2006-6-29 9:36:16的发言： 
冬兄辛苦。我提不出何处未表达清楚，只能问些问题。
关于消同态，有的同态可以消灭于萌芽之前，例如初态A经12n个动作之一U得态B，那么在接下来的循环中，就不必考虑态B经U'这个动作了，因为B经U'必得同态A。所以态B就只要做12n-1个动作。余类推。
有的同态是“隔代”的，各代态数过了“高峰”后，隔代同态越来越多，以致同态数超过新生态数。为了隔代消同态，不知您有何好办法。如果用比对两个态的代码的方法，且仍然是穷举式的、历遍式的比对法，每出生一个态，就要和它的所有前辈比对。一则随着代数的增加，要比对的态数越来越多（几何级数增加），二则前面的态多次参与比对，徒唤无奈。
如果说原来人们的方法是不分簇的，计算量太大，而分簇的方案说是简化了（尽管每个态还是要做12n个动作），那么，暂不论两种方案在消同态方面的计算量有无差别，分簇方案中的“协调”工作计算量大吗？</DIV>
乌兄所言不无道理，问题是：
1.每一个动作都是在簇最短步数计算的基础上确定
2.魔方已分解为子魔方，同态必在子魔方中被消除
3.协调算法本身很简单，主要工作量，来自于簇最短步数计算
当然希望大家多提意见，必竞是新呈现的思路，不妥之处，再所难免

页: [1] 2 3 4 5 6 7 8

魔方吧·中文魔方俱乐部's Archiver

[原创]基于N阶定律的魔方最短步数分析导论