魔方吧·中文魔方俱乐部

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

[原创]魔方循环变换理论概述 (待完善) [复制链接]

Rank: 7Rank: 7Rank: 7

积分
3923
帖子
2556
精华
6
UID
15558
性别
保密
WCA ID
2008CHEN27
兴趣爱好
理论

魔方理论探索者 国家(地区)纪录(NR) 十年元老

发表于 2015-5-17 15:47:12 |显示全部楼层
本帖最后由 铯_猪哥恐鸣 于 2015-5-17 15:52 编辑

首先纠正个错误:
正六面体的三阶魔方共有 4.325200 E+19 种不同状态的图案, 它大约是 1.0 E+10 的平方,因此设正六面体的三阶魔方的前 N 步的节点 个数为 1.0 E+10 ,那么正六面体的三阶魔方的前 2N 步的节点便可超过 正六面体的三阶魔方 4.325200 E+19 种不同状态的图案。(分两个 N 步) 这就是开发正六面体三阶魔方最少步软件 Cube 的作者 H.Kociemba 采用 The Two-Phase Algorithm 算法的理论基础,他制作了一个大小 1G 左右的“表”,便于求解时查表计算。

Two-Phase Algorithm并不是这个原理。

从上下文来看可能你想表达的是双向广搜算法。那么问题来了:
对于给定状态,如何用你生成的表(循环变换集合)来求解该状态?
请给出一个精确可操作的算法,我会在你基础之上分析它的时间复杂度、空间复杂度等。

注:如果是传统的双向广搜,复杂度依然大的不可接受。比如以18f的状态为例,你需要遍历所有9f及以内的状态,并且把这些节点都保存在内存中。从现有的知识来看,这总共约有20G个节点,而且在这一步,对称性优化是用不上的,尽管生成的表可以除以48,搜索空间是无法除的。于是如果采用双向广搜,即便抛开时间复杂度不谈,内存里如何存储这20G个节点就是问题。而相比而言,现在IDA*算法搜索的节点只需要500M以内,且不需要保存搜索过的节点,即搜索过程的额外空间占用可以忽略。

使用道具 举报

Rank: 8Rank: 8

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

魔方理论探索者 十年元老

发表于 2015-5-18 16:18:46 |显示全部楼层
本帖最后由 ggglgq 于 2015-5-18 16:22 编辑

  
  
    嗯,Two-Phase Algorithm 并非是 双向广搜算法,不然它就是严谨的最少步算法了。
  
记得 铯 的《论二阶魔方的计算机求解及优化》是 双向广搜算法,但 不知何故 被阁下
  
删除了?!   上面的引用说的就是 双向广搜算法。
  
  
    想当初我对 循环变换 的浓缩法还是信心满怀的。但就一个 正六面体三阶魔方 的
  
最少步就已让我费尽心机,撞得头破血流了,到现在才知道 正六面体三阶魔方 最远态
  
要 26 步(我以前一直想象的是 22 步),就别说高阶魔方了(双向广搜算法 不现实)。
  
    因此,后来我把 循环变换 引向 循环变换球面网 —— 希望用图论(结合群论)和
  
度量(高维度量空间)等方法,来拓展研究 魔方 的最少步。  比如:
  
      http://bbs.mf8-china.com/forum.php?mod=viewthread&tid=34872
  
      http://bbs.mf8-china.com/forum.php?mod=viewthread&tid=7532
  
等都是我后来加的。
  
  
    能指出《循环变换概论》这些不严谨的地方,说明 铯 是个有心人啊。希望我们能
  
从不同角度出发,不断挖掘深藏在魔方内部的宝藏,为我们的魔方最少步理论添砖加瓦。
  
  
  
  
  
  
  
~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
3923
帖子
2556
精华
6
UID
15558
性别
保密
WCA ID
2008CHEN27
兴趣爱好
理论

魔方理论探索者 国家(地区)纪录(NR) 十年元老

发表于 2015-5-18 20:49:47 |显示全部楼层
ggglgq 发表于 2015-5-18 16:18
  
  
    嗯,Two-Phase Algorithm 并非是 双向广搜算法,不然它就是严谨的最少步算法了。

好吧,这样啊。

因为已经有文章指出求解某个状态的最少步解是NP难问题了,不知道这一块的研究可能的价值是什么。

使用道具 举报

Rank: 1

积分
15
帖子
15
精华
0
UID
1346163
性别
保密
居住地
郑州市
兴趣爱好
结构
发表于 2017-12-21 18:48:33 |显示全部楼层
收藏了慢慢看吧。。。。。

使用道具 举报

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

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

GMT+8, 2019-1-17 02:04

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部