魔方计算机求解中状态表示层次与效率

铯_猪哥恐鸣

先声明这个东西不是我原创，CE的算法里就有。主要是因为先前和GGGLGQ讨论他那个48同态的算法效率的时候发现其实大部分人对计算机解魔方的一些认识还只是片面的。这里只是稍微引出一个关于状态快速转换的想法。
先说魔方的表示层次：
1、色片层：即记录魔方的每个位置块的颜色。总共54个数字。
2、色块层：类似盲拧的记录方法，即记录每一个块（角块或棱块）的方向与位置。总共40个数字
3、编码层：这个比较难解释，我举个例子吧：比如说三阶的角块方向，每个角块一共有3个方向，考虑角块方向的特殊性只需要记录7个角块。每个角块有3个方向，那么在计算机中每个角块方向的表示就是7个数字，每个数字都在0~2，那我们不妨将它们看作3进制，最后可以算到一个介于0~2186数，与角块方向一一对应。这个用很大的数字表示魔方的方法就是编码层。每个魔方只需要4~5个数字表示。

为什么要讨论魔方由多少数字表示呢？因为魔方转换其实就是对数字的循环赋值过程。比如对于色片层，每次转动都会涉及20个数字，而色块层呢？大约也有16个数字。但是对于编码层，每次只有5个数字在变化，效率自然不用我解释了。层次低这正是为什么我说G大师效率低的原因。

[ 本帖最后由 铯_猪哥恐鸣 于 2010-4-13 17:22 编辑 ]

ggglgq

　　
　　
  
    呵呵，这个方法我在后续版本中已经考虑了。
  
    只要按照下面这个状态分布图，我的那个程序的状态分布与楼主的最优
  
方案（3、编码层）是完全一样的效果。只需要做 mod 3 即可。
  
  
　　
　　
　　
　　
　　

ggglgq

　　
　　　　
  
    最后，再次提醒楼主，我的算法是“最优”的，关键是你接受和处理
  
问题的方法——如何移植。 这是你自己的 个人问题。 不要以为只有你的
  
算法优秀，那就大错特错了。 我在这里只是给出一些大家都能接受的一般
  
性方法而已，关于你上面的方法我早在《论二阶魔方的计算机求解及优化》
  
说过，这是常用技巧，没什么可炫耀的。
  
    此事到此为止，希望今后大家正确对待自己的算法即可。
　　
　　
　　

aubell

这个讨论没有什么意义。好像网络协议一样，底层协议处理bit流的，高层的处理字符流，更高层的才处理数据本身。
其间也需要不断的变换 pac k和 unpack，类似LZ的 zip 和unzip。
高层的协议并不意味着最高的效率。
效率的高下也不是以代码的行数来决定的。比如，您可以用汇编写完整个程序，然后用一句basic来调用。
希望大家不要被“效率”迷惑。

铯_猪哥恐鸣

回楼上，可能我没明白你的意思，我的程序搜索过程中是不会调用那两个过程的

铯_猪哥恐鸣

噢，还有回G版，不知能否分享下您写的二阶搜索程序

aubell

我正在慢慢学习LZ的程序，很快就有结果了。

ggglgq

　　　　
　　
  
    楼主探讨“效率”是无可厚非的。但是楼主搞个“层次论”就 ......
  
按楼主的说法，我给出的是“色片 指针”，楼主的便是“编码 技巧”。
  
  
    我们知道，48 同态的算法的“最优算法”是“指针”。对于我给出的
  
“色片层（母）指针”完全可以在程序设计时抽取为“编码层（子）指针”。
  
这个明眼人一看就知道，算法还是“指针”，丝毫没有改变算法的复杂度。
  
其间必然涉及类似 zip 和 unzip 式的 编码 转化，故称为“编码 技巧”。
  
   
    含有“编码 技巧”的程序，其效率有所提高，但其“可移植性”就差
  
远了。在魔方上讲，就是一个 魔方，一套“编码技巧”，其“拓展效率”很
  
低。 这是辩证的问题，正是困扰楼主的 48 同态的算法 受挫 的根本原因。
  
  
    另：正六面体二阶魔方任意状态最少步开解源代码.rar 在 2006-6-6
  
      http://bbs.mf8-china.com/viewthread.php?tid=2191&extra=&page=2
  
早就公开，大家可以下载。 我的其他优化程序现在不在身边，它对楼主的
  
PK 式算法不会有任何帮助的！ 我就更不想和别人 PK 了，呵呵！
  
　　
　　
　　

铯_猪哥恐鸣

关于复杂度，魔方状态转化怎么算复杂度都一定是O(1)的。。。