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

铯_猪哥恐鸣

首先纠正个错误：

正六面体的三阶魔方共有 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 发表于 2015-5-18 16:18
　　
  
    嗯，Two-Phase Algorithm 并非是 双向广搜算法，不然它就是严谨的最少步算法了。

好吧，这样啊。

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