魔方吧·中文魔方俱乐部

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

由哈密尔顿图到魔方状态的遍历 [复制链接]

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

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

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

跳转到指定楼层
1#
发表于 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.哈密尔顿问题的求解

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

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

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

Rank: 8Rank: 8

积分
4825
帖子
2795
精华
7
UID
383
性别

魔方理论探索者 八年元老

2#
发表于 2005-5-11 16:49:01 |只看该作者
以下是引用noski在2005-5-11 14:19:33的发言:

1.让人眼睛一亮的见解,非常独到.对离散数学的引用非常传业,少见的传业数学观点

2.一个群论以外的新观点,其实群论在此问题走入死穴已多年没有改变了,凡是基于群论的理论,除了在状态表示上有作为外,其它基本没有可圈可点的表现(引用一个博士级人物的话)

3.基于状态分析的角度,对魔方性质的表达,暂时有比较实用的结论,但在最优解及最远状态处理方面当前也看不到方向

4.NOSKI有22或23步证明的资料吗?

5.最优解及最远状态处理也许与新数学手段相生相随,但还有很多不死心人的人在探索,当然包括我自已

6.好文好文...美酒.

使用道具 举报

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

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

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

3#
发表于 2005-5-12 22:10:37 |只看该作者

pengw过奖了

对这个问题, 我的描述还很粗略, 现在我还在思考中, 希望能再进一步完善一点, 给出一个详细一点的解释.

对于22或23步, 我是到吧里看帖子才知道的, 目前还没有证明...

和你们严密的理论相比, 我几乎是个猜想主义者, 我把我的想法贴出来, 希望对魔方理论的完善也能做出一点贡献.

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

使用道具 举报

Rank: 8Rank: 8

积分
4825
帖子
2795
精华
7
UID
383
性别

魔方理论探索者 八年元老

4#
发表于 2005-5-12 23:23:08 |只看该作者
以下是引用noski在2005-5-12 22:10:37的发言:

pengw过奖了

对这个问题, 我的描述还很粗略, 现在我还在思考中, 希望能再进一步完善一点, 给出一个详细一点的解释.

对于22或23步, 我是到吧里看帖子才知道的, 目前还没有证明...

和你们严密的理论相比, 我几乎是个猜想主义者, 我把我的想法贴出来, 希望对魔方理论的完善也能做出一点贡献.

建议继续深入研究下去,大家不要在群论一棵树上吊死,我发的贴子也跟群论毫不相干,而那些相干的又基本没有什么结论,敢踏一条新路真的很勇敢,很大气.反正我是不喜欢去重复验证别人的错误.

使用道具 举报

Rank: 8Rank: 8

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

魔方理论探索者 十年元老

5#
发表于 2005-5-25 08:48:15 |只看该作者

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

使用道具 举报

Rank: 8Rank: 8

积分
18050
帖子
16478
精华
9
UID
449
性别

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

6#
发表于 2005-6-15 20:24:22 |只看该作者

我想,分布成球体 、成球面,无非为能直观地帮助处理问题。鉴于N太大太大,成什么形状都于事无补。重要的是探究态态关系。我在自我否定的帖子中说过,把它们和水泥石子拌成混凝土也好,把它们抛向广袤的宇宙也罢,全都无所谓,态态之间的关系不变。现在好了,“后哈密尔顿”先生们在探路了。
确实,态A经UDU'D'等等的四边形回路,与UUUU一样,都回到态A,再小的回路(三角形)好像不存在。

[此贴子已经被作者于2005-6-15 20:25:12编辑过]

使用道具 举报

Rank: 8Rank: 8

积分
18050
帖子
16478
精华
9
UID
449
性别

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

7#
发表于 2005-6-15 20:55:35 |只看该作者
还有,1楼说的20面体是否应为12面体,后者才有20个顶点呀。
那周游20个城市的玩具可自制。12面体可“拓扑”为如下平面图形,20个点子相互关系不变:

哎呀,谁踩扁了老猫的五魔方?他还要发货给魔友的呀。
哪里,这是最新产品,搁信封里就可发寄啦。收到后吹口气就复原啦。

[此贴子已经被作者于2005-6-17 0:08:28编辑过]

使用道具 举报

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

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

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

8#
发表于 2005-7-23 02:59:05 |只看该作者
谢谢乌木,的确是12面体,20个顶点,是我写错了,一直没有注意到...
The Answer to the Ultimate Question of Life, the Universe, and Everything 

使用道具 举报

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

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

GMT+8, 2024-11-30 03:44

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部