非专业分析KCube

aubell

7.cubepars.cpp
  就是CubeParser,处理命令行的。
  从命令行接受输入，稍作错误检查，填写一个贴纸层魔方。
  写这段程序需要耐心。逻辑上很简单。
  每个参数对应一个面，整面整面的填写就可以了。

8.cube.cpp
  这个是方块水平的魔方。每块的排列和方向是分开存储的。是可以转动的魔方。
  贴纸魔方在检查着色后，就会填写一个方块魔方。
  文件中定义了各种转动方法，以及求一个简单操作的逆操作，求一个面的对面等。
  同时，这个类是KociembaCube的基类。

9.KociembaCube
  这个大概是最重要的一种Cube了。也就是“坐标水平的魔方”，在“方块水平”，使用
  四个数组存储角排列、角方向、棱排列、棱方向，在“坐标水平”将使用六个整数来代
  替魔方的状态。

在第一步骤中，用3个整数表示魔方状态：棱的翻转状态、角的方向、E层棱在魔方中的位置
  
  因为第一步骤要还原这些。
  棱的翻转直接用2进制整数，角的方向用3进制整数，

  E层棱的位置表示有两种不同实现方式，一种是把选择方式同整数之间对应，
实现起来也是用专门的算法，注释的很详细； 令一种就直接在一个12位
整数上mark一下；编译的时候可以选择用何种方式。  
无论哪种方式，要确保组合方式同整数的一一对应。
这一部分似乎应该分离到combinat中，因为这个才是真正的组合。

  数量：只记录7个角的方向和11个棱的方向。因为最后的一个“被决定”的。
  3的7次方2187；2的11次方2048；12选4为495。

  在第二个步骤中，也用三个整数来表示：
  八个角的排列，八个非E层棱的排列，四个E层棱的排列。

  排列同整数的对应就用combinat中的方式。
  数量：8个角的全排列为40320，八个非E层棱的排列也如此40320，
        4个E层棱的排列24
  以上六个数字都不大，但全乘起来正好是魔方状态数的两倍。

  因为有恰好一半的状态不能达到，孤Parity。
通过两步分治，每个步骤都减轻了负担。

[ 本帖最后由 aubell 于 2010-4-17 21:55 编辑 ]

aubell

再重写这个程序的时候，会把以下模块分离出来：
3进制数同数组的转换
2机制数同数组的转换
以上两个合并起来

整数同排列的转换
整数同组合的转换
以上两个放在一起，是排列组合相关内容
已经有成熟的完美的算法，不用再自己设计了

以上是关于魔方状态数组与整数之间的转换，使用频率并不高
只在生成表的时候用一次
在每次搜索之前用一次
都是程序外围的非关键部分，效率高下与否不重要，
随便怎么设计都可以。

10.表的生成 movetabl.cpp 和 pruningt.cpp
这里的表，按照类型可以分两类：状态转移表和剪枝表
按照用途也可分两类：第一步骤的表和第二步骤的表

第一步骤的表
Flip.mtp   棱的方向状态转移表
Twist.mtp  角的方向状态转移表
Choice.mtb E层棱的位置选择状态转移表

FlipChce.ptb Flip和Choice的合并剪枝表
TwstFlip.ptb Twist和Flip合并的剪枝表
TwstChce.ptb Twist和Choice合并的剪枝表

第二步骤的表
CrnrPerm.mtb 角的排列状态转移表
EdgePerm.mtb 非E层棱的排列状态转移表
SlicePerm.mtb E层棱的排列状态转移表

CrnrSlic.ptb CrnrPerm和SlicePerm合并的剪枝表
EdgeSlic.ptb EdgePerm和SlicePerm合并的剪枝表

可以看到，每个步骤三个状态转移表。
两两合并，成三个剪枝表。
但第二个步骤，由于CornerPerm的表和EdgePerm的表乘起来太
大了，所以没有合并成剪枝表。
剪枝表的存在也是为了提高搜索的速度。


生成表的过程

状态转移表的生成
由于整数对应着魔方的状态（twist,flip,choice,perm等），
所以依次取这些整数，作为“老状态”，为每一个“老状态”分别作
18种（12种）基本操作，生成“新状态”，表存储：
Table[老状态][操作]=新状态
表查询 到达状态=Table[出发状态][操作]；

分支表的生成
分支表是由两个状态转移表合并的
TB[表1中的状态][表2中状态]=还原态到达这个状态需要的步长
两个状态整数被合并了成一个整数，索引的时候用一个数字乘
表的宽度，再加另一个状态。

合并的状态是既满足表1的状态，也满足表2的状态。

存储的是步长，生成的时候采用的是多次扫描，为一层层的生成。
从初始态开始，一层一层向下扩展。

先取分支表的索引，分解成两个状态表中的状态，让这两个状态在
同一个操作的加工下，生成两个新状态，再把两个新状态合并成分支
表的索引。这个索引在第几层扫描的时候遇到，深度就填几。

以上是moveTable和pruningTable的生成过程。
在对应的文件中定义。

生成表的过程因为是只工作一次，所以，效率不高也没有关系。也可分离模块，
成为 基础支持，表的生成，表的应用。

生成的数据是为了配合高效率搜索的，IDA*的搜索到底是怎样使用这种表的呢?

[ 本帖最后由 aubell 于 2010-4-16 18:46 编辑 ]

aubell

就要开始分析最关键的代码了，这里遗留了几个小问题：
1.排列、组合同整数的对应，那种经典算法工作原理是怎样的；
   要学习算法--生成排列、生成组合。
2.验证Parity 的那段朴素而神奇的代码为什么有效。

开始之前，先复习一下深度优先搜索和广度优先搜索。
因为IDA*是改进过的A*搜索，叫做“依赖循环子的A*搜索”。
A*搜索使用的广度优先的控制结构，由于加入对深度的估计，所以又像深度优先。
所以从本质上讲，应该算是深度优先的算法，但与传统的深度优先不同：
如果认为某一支深度会太深，就不去扩展那一支了。

搜索的过程中加入了估值函数，估计当前状态还需要多少“消耗”可到达目标状态。

... ...

[ 本帖最后由 aubell 于 2010-4-18 20:14 编辑 ]

aubell

再次认识一下与那些表相关的文件，发现它们的构造函数真的太繁杂了，内部结构也不尽合理，
把一个cube放在管理表的类里作为私有成员，也是不太讲究的。
这些表一旦生成，就不再改写，这些类的构造函数没有必要用魔方状态做参数，
长长的初始化列表，原来是混淆视听的。

那些生成表的过程基本就没有用了。
只在搜索开始的时候，提示一下起点和终点。

再重写的时候，用c，不再用c++了。
c++花俏的东西太多了。

从本质上讲，只有solver和这些表重要。
这些表是数据结构，solver是算法，两个合在一起是程序。

除了solver和表，其它部分所做的工作就是“魔方状态与整数的转换”，或者说叫做
“如何用六个整数表示魔方的状态”。

而这个solver却是我所读不懂的
加油。

[ 本帖最后由 aubell 于 2010-4-17 21:54 编辑 ]

aubell

solver.cpp

就剩下这一句，没有理解了。

else{
     if (totalCost < newThreshold1)
            newThreshold1 = totalCost;
}

没有理解这一句，就意味着没有理解IDA*。
只好暂时先把这个当做一种搜索用“框架”结构，以后写程序照着用就是了。
铯解释过了，我暂时还是没有明白。

整个搜索的流程是这样的：
先开始第一阶段的搜索
如果找到了第一阶段的解，就开始第二阶段的搜索。
第一阶段的搜索并不停止，深度渐渐加深，
第二阶段跟随着，如发现比以前过程中的解还要短，就输出；
如果发现更长的解，不输出。

第一阶段搜索过程中，到达一定的深度，如果没有发现解，
就不向下搜了。但是额外做一件事情：
告诉下一次来搜的时候，要到达什么样的程度。

[ 本帖最后由 aubell 于 2010-4-18 22:19 编辑 ]

铯_猪哥恐鸣

回楼主，move table是转动表，prun table是剪枝表。我先说下前者的用处。
对于魔方在计算机中的储存，楼主可以看到，在声明类的时候已经有两种方式，但如果楼主细心看会发现，在搜索的过程中为了提高效率，程序必然会舍弃用类来表达魔方，楼主应该可以看到一个递归的搜索程序，他关于魔方信息的参数只有3个。其中每个参数分别表示了魔方的部分信息，比如色向等。然后很显然在搜索的时候不能再把这些信息转换为魔方开执行转动，那怎么办呢？就使用打表的方法，把每个状态经过每种转动后的相应状态储存在内存中直接查找即可。而这表，就是move table，也就是mtb文件。这个想法在我二阶的论文中也有提到。
而关于prun table，它就涉及到了IDA*的核心，一下还很难讲清。

aubell

多谢铯的指点。我再仔细看看。
我准备用3个月的时间消化这个程序

[ 本帖最后由 aubell 于 2010-4-15 23:47 编辑 ]

superflip

来晚了，lz加油！

我看过ce的简易实现版，貌似确实很“简易”，不知这个kcube什么来头，有什么特殊地方吗？

aubell

没有特殊来头，好像48种同态都没有处理，也没有多方向搜索。
也算简易版吧。就是注解的详细，相对可能好懂点。

据说CubeTwister里的开解方法是参照这个程序的。

superflip

这个，我是觉得没有比CE的帮助更好的注释了~

ps：48同态在2-phase算法体现为：16同态 * 3 搜索方向