[原创]魔方循环变换理论概述 （待完善）

铯_猪哥恐鸣

首先纠正个错误：

正六面体的三阶魔方共有 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以内，且不需要保存搜索过的节点，即搜索过程的额外空间占用可以忽略。

ggglgq

　　
  
    嗯，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
  
等都是我后来加的。
  
  
    能指出《循环变换概论》这些不严谨的地方，说明 铯 是个有心人啊。希望我们能
  
从不同角度出发，不断挖掘深藏在魔方内部的宝藏，为我们的魔方最少步理论添砖加瓦。
  
　　
　　
　　
　　
　　
　　

铯_猪哥恐鸣

ggglgq 发表于 2015-5-18 16:18
　　
  
    嗯，Two-Phase Algorithm 并非是 双向广搜算法，不然它就是严谨的最少步算法了。

好吧，这样啊。

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

轻描淡写3333333

收藏了慢慢看吧。。。。。