魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
楼主: cube_master

离初始状态最远的图案 [复制链接]

Rank: 10Rank: 10Rank: 10

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

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

发表于 2004-10-19 09:31:14 |显示全部楼层

楼上的内容来自:http://coolow.02835.com/swr.html 今天没事干把老贴翻出来,发觉里面java图片看不到,所以用老猫的贴助手编了一下贴出来看看

使用道具 举报

Rank: 10Rank: 10Rank: 10

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

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

发表于 2004-10-19 09:58:31 |显示全部楼层

看了半天还是不懂得讲什么东西,是否说魔方只能旋转一个面,但整个魔方可以随意摆放哪个位置。

如魔方只能转顶面U, 现在要转底面D的时侯,就把整个魔方倒个位置,又变成了只转顶面U。这有什么意义?肯定能复原魔方的嘛。

使用道具 举报

Rank: 8Rank: 8

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

魔方理论探索者 十年元老

发表于 2005-3-10 08:14:25 |显示全部楼层


终极状态

先给一个“终极状态”的特例:(请参考“终极状态”)





本文所涉及的内容默认为“正六面体三阶魔方”,可以很容易扩展到其它各类
魔方中去。为使结论尽量不产生偶然的冲突,特规定 旋转 180 度为 2 步!

为了阐述方便,下面先引入几个描述性的概念:
描述性理解的概念有:状态、终极状态、路过、偶尔路过、出路

1.状态:本文所提的所有的“状态”均为从“初始状态”出发,由某一最少步
变换序列而产生的“状态”。通常我们用这个最少步变换序列表示这个“状态”。
一个“状态”往往可以有很多“最少步变换序列”!
比如:从 初始状态 出发,由最少步变换序列 r1 r1 产生的状态,记作:
状态 r1 r1 。当然 状态 r1 r1 有两个最少步变换序列: r1 r1 和 r3 r3 。

2.路过:如果 状态 A 的步长大于 1 ,并且最少步变换序列 A 是唯一最少步,
变换序列 B 为去掉 变换序列 A 最后 一个 步长为 1 的变换 的 任一子变换序列,
此时我们称 状态 A “路过” 状态 B 。
比如:状态 r1 u1 f1 是唯一最少步变换序列,则 状态 r1 u1 f1 分别 路过
状态 r1 、状态 u1 、状态 r1 u1 。

3.偶尔路过:如果 状态 A 的步长大于 1 ,并且变换序列 A 不是唯一最少步,
变换序列 B 为去掉 变换序列 A 最后 一个 步长为 1 的变换 的 任一子变换序列,
此时我们称 状态 A “偶尔路过” 状态 B 。
比如:状态 r1 r1 不是唯一最少步变换序列,则 状态 r1 r1 分别 偶尔路过
状态 r1 、状态 r3 。 这是因为 状态 r1 r1 和 状态 r3 r3 为同一状态的
两个最少步变换序列。

4.终极状态:设 c 为任意一个步长为 1 的变换,对于状态 A 存在一个由 c
结束的最少步变换序列 B ,使得 A = B ,则称状态 A 为“终极状态”。
由 [宇宙飞碟] 的 离初始状态最远的图案 的定理可知:
任一 离初始状态最远的状态 都为 终极状态 ,但反过来说却是错误的!

5.出路:如果 状态 A 不是 终极状态,我们称 状态 A 有 “出路” 。
只有 状态 A 有 出路时,我们才有可能沿着状态 A 的 出路 构造比 状态 A
更远的 状态 !而寻找这种 出路 ,照目前看来,在没有更先进的理论面世之前,
也只能用“循环变换”理论更容易些了!

定理:任一 状态 不 偶尔路过 某一 终极状态



证明非常简单,因为若一个状态 P 偶尔路过 某一 终极状态,设状态 P 变换序列为
a1 a2 ... b1 b2 ... bm -c ... an ,其中 b1 b2 ... bm 为终极状态,那么对于这个
终极状态 b1 b2 ... bm ,存在一个由 c 结束的最少步变换序列 c1 c2 ... c(m-1) c ,
使得 b1 b2 ... bm = c1 c2 ... c(m-1) c ,这时我们发现,变换序列 P 已经变为
a1 a2 ... b1 b2 ... bm -c ... an = a1 a2 ... c1 c2 ... c(m-1) c -c ... an ,
a1 a2 ... b1 b2 ... bm -c ... an = a1 a2 ... c1 c2 ... c(m-1) ... an ,即说明
P = a1 a2 ... b1 b2 ... bm -c ... an 不是 最少步变换序列,这与 状态 的概念矛盾,
故定理得证。

由上面的定理直接得到: 离初始状态最远的状态 不 偶尔路过 某一 终极状态

这个定理告诉我们,如果一个状态是 终极状态 ,那么它有可能是一个 离初始状态
最远的状态
,如果它不是 最远的状态 ,那么我们不可能再通过这个 终极状态 来构造
其它任何 状态 ,当然更不可能通过这个 终极状态 来构造 离初始状态最远的状态 了!
呵呵,希望魔友们在寻找 离初始状态最远的状态 时一定要避开 终极状态 的暗礁呀!

_____________________________________________________________________________________

正六面体三阶魔方的最远状态,我考虑了一段时间,也用了些方法试过,却“无果而终”。
但我可以断言: 对于 正六面体三阶魔方 仅 旋转侧面( 上、下、左、右、前、后 ) 90 度
算 1 步,正六面体三阶魔方的最远状态为 偶数 步!(假如国外专家评估三阶魔方的最远状态
最少步为 22 步 或 23 步 是准确的话,即得:正六面体三阶魔方的最远状态为 22 步!)

看样子有些问题很难被证明,这使我联想起人们曾想证明“四色问题”和“阿当斯幻方”,
但最终“无果而终”。它们却都是被计算机“遍历”证明(算出)的!

四色问题:经计算机遍历全部情况,证明了平面地图最多用四种颜色即可使任意相邻区域
不同色!

阿当斯幻方(请参考“阿当斯幻方”):经计算机遍历全部情况,证明了“阿当斯幻方”
的答案仅有唯一的一种!


呵呵,我想,老猫先生不必担心你那“正六面体五阶魔方”会被人得到,不妨继续“悬赏”!
因为即便有最先进的算法(程序和产生的库)想要让现今最超快的计算机“遍历”证明(算出)
三阶魔方的最远状态,没有一年半载的时间都不可能实现!




[此贴子已经被作者于2005-12-15 9:52:37编辑过]

~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

Rank: 8Rank: 8

积分
5032
帖子
251
精华
1
UID
118
性别
居住地
广州市
兴趣爱好
速度

十年元老

发表于 2005-3-10 17:23:28 |显示全部楼层

我认为国外专家评估三阶魔方的最远状态最少步为 22 步 或 23 步,这个猜想肯定是把180度的旋转是算1步的。如果是按ggglgq 老师的180度的旋转是算2步的计算法,就不止23步了。因为只用180度转打乱和还原魔方的玩法已经找到12步的状态了,按ggglgq 老师的180度的旋转是算2步的计算法,已经是24步了。

使用道具 举报

Rank: 8Rank: 8

积分
5252
帖子
1815
精华
9
UID
22
性别

八年元老

发表于 2005-3-10 18:55:32 |显示全部楼层
以下是引用还猪哥哥在2005-3-10 17:23:28的发言:

我认为国外专家评估三阶魔方的最远状态最少步为 22 步 或 23 步,这个猜想肯定是把180度的旋转是算1步的。如果是按ggglgq 老师的180度的旋转是算2步的计算法,就不止23步了。因为只用180度转打乱和还原魔方的玩法已经找到12步的状态了,按ggglgq 老师的180度的旋转是算2步的计算法,已经是24步了。

还猪这个说法不对,打乱是24步,但是如果不限定复原用180度,应该不需要24步了。

使用道具 举报

Rank: 10Rank: 10Rank: 10

积分
24796
帖子
4852
精华
33
UID
3
性别
兴趣爱好
结构
发表于 2005-3-10 22:58:26 |显示全部楼层

ggglgq 老师真厉害

你现在的 Java 帖不用助手了吗?其中“codeBase”地址可以改为本地了,如

三阶:codeBase=3 四阶:codeBase=4 五阶:codeBase=5

这样是为以后打算,就算魔方吧迁移到别的空间,论坛也不需要修改帖了

整段代码为: <APPLET code=RubikPlayer.class codeBase=3 height=400 width=300> <ARAM NAME="scrpt" VALUE="R F2 U R2 U2 B L R B2 L' D' F2 U' L B L' F' U2 R' U'"> <ARAM NAME="initscrpt" VALUE="U R U2 F L B L' U F2 D L B2 R' L' B' U2 R2 U' F2 R'"> <ARAM NAME="scrptlanguage" VALUE="HarrisENG"> </APPLET>

[此贴子已经被作者于2005-3-10 23:11:27编辑过]

-,'''╭⌒╮⌒╮.',''',,',.'',,','',.,,'
.╱◥██◣''o┈ 魔方吧 ┄o.'',,',.
︱田︱田田︱ '',,',.o┈ 欢迎您光临 ┄o
╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬

使用道具 举报

Rank: 8Rank: 8

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

魔方理论探索者 十年元老

发表于 2005-3-11 11:05:07 |显示全部楼层

哦,知道了!我们这里的烂网是属于半脱机型的,网址不全就看不见 Java 帖, 现在大家发的 Java 帖我就看不见,不过我可以下载下来修改了再看![em07] 为以后魔方吧迁移到别的空间长远打算,我可以克服我的不便,为大家方便嘛![em01]

~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

Rank: 8Rank: 8

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

魔方理论探索者 十年元老

发表于 2005-5-15 09:33:06 |显示全部楼层
以下是引用noski在2005-5-11 14:19:33的发言:

1.关于哈密尔顿和哈密尔顿图

哈密尔顿是英国的一位数学家和天文学家。

自从哈密尔顿发现“四元数”之后,他又发现了另外一种他命名为“The Icosian Calculus”的代数系统,这系统有加和乘的运算子,可是乘法不满足交换律(xy=yx这个规律)。

他发现这代数系统是和正则20面体有关系。他想到一个游戏,怎样跑遍正则多面体上的所有顶点,而最后又能回到起点的问题。在1859年他把这个游戏的想法以25英镑的价钱卖给一位玩具和游戏制造商。

这玩具商把这游戏制造出来了,即“周游世界游戏”。在圆盘上有20个代表城市的圆孔,你必须把20个上面标有123,…,20的木条顺序插进去,代表你经过不同的城市,最后回到原出发点。这个游戏曾经风靡一时,它有若干个解,称为哈密尔顿圈。

以后人们因这游戏就称这类图为哈密尔顿图。

2.哈密尔顿回路的两个相关定义

定义1 图G的一个回路若它通过G中每个点一次,这样的回路称为哈密尔顿回路。具有这样的回路的图称为哈密尔顿图。

定义2 通过图G中每结点一次的通路(非回路),称为哈密尔顿通路。

3.魔方的状态图

将魔方的每个状态做为一个结点。而魔方六个面中的任何一面顺或逆时针旋转90°,即可生成一个新的状态。在这里,每个边代表某个面旋转了90°。因此,从每个结点出发,有12条边。

魔方状态数为N,则这N个结点组成一张状态图。由魔方的广义复原原理,不存在特殊的结点。每个结点出发,都有相同结构的12条边与其它结点相连。

由于已证明,魔方任意两个状态之间转换的步数不大于22或23步(类似U2这种算一步?),所以魔方的状态图将是一个密集集中在一个直径为22或23步的球体中的网络,或者存在于一个自封闭的三维空间中。

比如U面,四个U操作即回复到原来状态,所以魔方状态图中最基本的结构就是边为4的小四边形。

所有公式,都是此状态图中的一条通路。

魔方的遍历问题,就是寻找魔方状态图的哈密尔顿回路的问题。

4.哈密尔顿问题的求解

哈密尔顿回路与通路至今尚未找到一个判别它的充分必要条件。在大多数情况下,还是采用尝试的方法来解决。

发现这点是让我比较郁闷的事情。还是关注数学的发展吧。





以下是引用hw294在2004-8-18 22:21:00的发言:

假如能找到一个序列,能遍历魔方的所有状态,则拿到一个打乱的魔方,不管它是怎样的状态,只要按照该既定的序列旋转,经过一定的步数总会复原,也许一两步,也许很多步,最为惬意的是他不用看,只要一直转下去,不过头就行。也许可以叫“傻瓜转法”或“白痴转法”,好听点,可以叫“万能转法”。

以下是引用ggglgq在2004-8-20 8:51:30的发言:


问题:某一魔方“傻瓜转法”旋转的最少步数为多少 ? 现给出一个带有理想
色彩的猜想答案:魔方“傻瓜转法”旋转的最少步数有的它的所有的状态数

比如:正六面体的三阶魔方有 4.325200 E+19 种不同状态的图案,猜想:它的
“傻瓜转法”旋转的最少步数为 4.325200 E+19 ;
又如:正十二面体的五魔方有 1.006696 E+68 种不同状态的图案,猜想:它的
“傻瓜转法”旋转的最少步数为 1.006696 E+68 ;
此时的魔方“傻瓜转法”旋转的每一步必旋转成的状态,即:此时的魔方
“傻瓜转法”存在且只存在 一个 广义循环变换) ,否则就会出现重复状态,
从而导致魔方“傻瓜转法”旋转的最少步数 大于 它所有的状态数。



看来大家都有同感!我已经预感到“正六面体三阶魔方的状态图是一个密集
集中在一个大圆的半圆为 22 步的球面上的网络(旋转 180 度按 2 步计算)”

noski 先生讲解了“将魔方的每个状态做为一个结点。而魔方六个面中的任何
一面顺或逆时针旋转 90°,即可生成一个新的状态。 在这里,每个边代表某个面
旋转了 90°。因此,从每个结点出发,有12条边。”,看样子我们对魔方步长的
定义完全一致。看的出您对“魔方状态图的哈密尔顿回路的问题”研究的很深入了,
衷心希望您能对此再多发表些看法!


[此贴子已经被作者于2005-5-25 8:56:30编辑过]

~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

Rank: 8Rank: 8

积分
18017
帖子
16456
精华
9
UID
449
性别

魔方理论探索者 论坛建设奖 爱心大使 十年元老

发表于 2005-5-23 15:52:16 |显示全部楼层
我在即将贴出的“魔方关系网”(续)帖子中,看到魔方态总数N值不同,最远步数(h-1)值跟着不同! (h表示第h代“子孙”,初始态是第1代。) N取李世春的19次方的那个值时,h-1为18。 等等。还看到h-1应是整数。故对22-23这说法表示怀疑,且不知持该说法的玩群论的科学家葫芦里卖的什么N值?据我看,他的N会是23-24次方的数。若是的,太大了吧?若不是,则与(h-1)=22-23矛盾。另外,要么22,要么23,不可能22-23。那续文等我弟弟看过后就贴出(理论区)。

使用道具 举报

Rank: 8Rank: 8

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

魔方理论探索者 十年元老

发表于 2005-5-25 08:42:49 |显示全部楼层
以下是引用乌木在2005-5-24 16:15:02的发言:

魔方态关系网(续)

对于上述虚拟魔方的两点一线网、三角形网、正方形网、四面体网,分别轮流提溜一个态点时,下面悬挂的网的形状分别一样,不同的只是各态点的布局每次更新。如果不要看这种“互联网”,改看论资排辈式的树形网,则各点可轮流做老祖宗,分别都得到一母一子树,一母二子树,一母三子树。在树形网中,子-子之间无连线,它们的联系要“绕道”前辈。看来,某种意义上是网随人意,结构并非固定不可变。各态点之间的关系是客观存在,表现形式则还要受人的影响。

真实魔方的N个态点应同样如此。除了上篇我说不清楚什么样子的网(暂名为放射花网?)之外,我想改看它们的树形结构应不难。每点都可当老祖宗,又可当任一代子孙,真正的大同世界。一旦改朝换代,其余N-1个点自动论资排辈、对号入座。此外,把上述m个“直接邻居”改称为m个子女,把它们从放射花式布局改为排排坐方式,m个子女排名不分先后。在树网中随便找两个态点,它们的关系往往要经由前辈来沟通。或者令其中一个当新的祖宗,重组河山,“提溜”出新的树,另一个必改为某一代子孙之一,可很快回到新祖宗怀抱。除老祖宗和末代外,每个态点只与其一个上代、m个下代连线。基本网策是严格的计划生育:一人必须生也只能生m个子女(无性繁殖;我少年时看过的科幻故事中某外星人世界都是无性人)。一代一代繁衍下去,到h世时全部N个点各就各位,h世同堂。

N、m、树的高度(h-1)的关系为:

N=1+ m + m 2+ m 3+……+ m(h-1)

N=( m h -1)/(m-1) ,

m h=(m-1)N +1( = P ) ,

h=lg P / lg m,

以3阶魔方来说,(N值据李世春《魔方的科学和计算机表现》p.14)

P=(12-1)×4.3×1019 + 1=4.73×1020

h
=(lg4.73+20)/lg 12

=(0.675+20)/1.079

=19.2

从老祖宗(1世)到末代(h世或第h代)的任一个子孙,其间走的步数应为h-1,3阶时为18.2。这就是态态之间最远步数!如果N取别的值,则h-1就为别的值。有的说 h-1=22-23,则N应是23-24次方的数。问题在于N究竟为多少?

面对多种N值,我后来意识到:这里是送子观音的(h-1)供应处,不必问N谁对谁错,什么N值来都可抱回一个它自己的(h-1)胖娃娃,但孩子的标牌上必须注明是谁的孩子,是什么样的N,其定义如何,以免错换!上述虚拟魔方仅几个态点的系统来,照样可求得相应的最远步数。再比如,谢晋招来N名群众演员,拍《h世同堂》电影,角色分配定当,在上述“一母m子”的家谱树中各就各位。瞧这一家子,人各一面,秩序井然,齐声合唱“Nmh歌”。最奇妙的是,任一人走任一个亲戚的话,最多走过(h-1)个“宅院”。

任何N都只能有一个(h-1)!故“22-23步”说法是有问题的,不能徘徊于两个数之间!

各N谁对谁错是另外的问题,与(h-1)算法无关。

上面h为何非整数,是否与N值本身精度及计算误差有关?我看不是。造成h非整数会不会是由于这N个点的树形是“残缺”的?比如,开始所说的四点系统,如果既要一母二子,又要总数为4,该树只能让第3代夭折掉3个,留下的一个第3代不管是单传还是两房合一子,树都是残缺的,宁缺毋滥。但如上计算h值时就会出现非整数。换言之,若计入空缺位的态点(它们都是一套N之内已有态的重复态或称同态),则所得h必为整数。注,N数并不缺,是N树形缺!

树形缺了多少可计算:h若干次取整,倒算并选出一个大于且最接近N的N’。 N’是用同态点补缺后的态点总数。不能补过头,补到末代中出现N内点和N外点共处一代即可。所以N’要刚刚大于或等于N。(N’-N )即为所缺。如3阶魔方,h取不同整数时,算得 N’=12h / 11 分别为:(供不同的N值去对号入座)

h=18, N’=2.4×1018

19, 2.9×1019

20, 3.5×1020

21, 4.2×1021

22, 5.0×1022

23, 6.0×1023,

所以,手捧N=4.3×1019ersonName w:st="on" ProductID="李">李ersonName>教授只能选h=20, h-1=19步!比上面算出的18.2合理地补了0.8步!

还是ersonName w:st="on" ProductID="李">李ersonName>教授的吆喝声令人听得懂,以下就买下他的N数,(管它假货真货,用于做广告无所谓。)来算算N树形的残缺情况等。

N’-N=3.5×1020-4.3×1019 =(35-4.3)×1019=3.07×1020。哇!缺得多得去得去得去啦!20世纪大大大屠杀呀!还都是娃娃娃呀!别大惊小怪!它们都好好的,只不过不可计入N而已!那谢晋的《h世同堂》故事中许多房间空关着,原因是这家子有也只有N个成员。若要住满空关房,办法只有克隆一批人去填补树形,但讲好家谱中无他们的位置,宁缺毋滥。谢导将拍他们后来分家的故事。

树的树冠(第h代子孙总数,包括N之外的补缺的态点)
Q= m(h-1) 。对3阶来说,Q=1219=3.2×1020,Q是N=4.3×1019的7.4倍;Q占N’=3.5×1020
的91% 。要是不割去96% (即3.07/3.2)的Q,让 N’这一大帮子上场的话,那可真是尾大不掉呀。

若继续繁殖下去,到某一代总能出来个老祖宗的转世灵童吧?这现象也是一种 “ 循 环 变 换 ” 吗?

突然想到,每一代同辈之中以及它们与所有前辈之中有没有同态?若有,如何消?(不消的话,以上叙述和计算就不对了!)若无,也要论证为何同态不会提前出现。换言之,上面初步发现的、树上可以有多达(N’-N)这么一大大大群重复又重复的果子,不一定集中于末代呀,不会分布于多个代中吗?哎呀!我本末倒置了?好像应该先解决最后所想到的问题,视情况如何,再确定如何做类似上面的讨论和计算的。可是,我,我……

我招来了大头鬼啦!让钟馗来吧,我还是走为走为......

M.Yu 2005.5.24.

冬兄教诲我们说要对自己的理论有自信心。我在这皮毛理论的续篇中,开始还努力自信;可最后那大头鬼一来,我的自信心玩完了。留下一点不死心,还要惶惶然发帖如上。预ersonName w:st="on" ProductID="谢李">谢李ersonName>教授不计较我文中对他的不严肃。感谢我弟Z.Yu拨冗对全文提了意见。




由乌木先生的理论提醒,特此更改 28 楼的结论,在此谢谢乌木先生。


特更改“一个直径为 22 步的球体中”为“一个大圆的半圆为 22 步的球面上”。所谓大圆就是
球体表面最大的圆,它的特点是圆心就是球体的球心,其它的圆心不过球心的圆都叫小圆。特此更正。

提醒 noski 先生能参考乌木先生的理论“魔方态关系网是怎样的”,或许对您的理论有所帮助!
因为如果正六面体三阶魔方的状态图是一个密集集中在“一个直径为 22 步的球体中”,那么它的
分布是不均匀的,比如球心到球体中任何一点的距离最大为 11 步。因此需要改动“一个直径为 22
步的球体中”为“一个大圆的半圆为 22 步的球面上”。

~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

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

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

GMT+8, 2024-3-29 01:56

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部