QT C++ 算法 广搜BFS 最下步数复原二阶魔方

QT C++ 算法 广搜BFS 最下步数复原二阶魔方

本人不是计算机专业，学过半年数据算法，当时有个大作业求解二阶魔方，有一个例子就是通不过测试，心存遗憾，工作时摸鱼想到问题所在，利用休假时间写个博客分享一下，能力水平有限，海涵。算法经过测试，随机打乱20次7ms左右就可以解出结果，而且改个20~30行就能改成三阶魔方。QT只是写个壳子，比较粗糙。

https://download.****.net/download/weixin_38640921/11142415

1.广搜原理在求解魔方问题的应用
广搜的原理不再赘述，各类资源相当丰富，我想我理解的不深也讲不好，我就聊聊在解魔方上的应用。

1.1二阶魔方的构成与状态表示
平面展开吧，就是这样

六色，六面，二十四小块（已标出）。

1.2二阶魔方的状态表示
二阶魔方的变化数为3674160，不是很大。为什么聊二阶魔方的变化数呢，因为广搜需要用一个变量确定一个状态，作为程序员我要考虑用何种方式去存储这种状态（可以理解为状态的编号、编码，唯一标识）。
看过不少解魔方的源码，很多都是用2D数组存储状态，这么做有
好处：直观，简单，占空间少
缺点是扩展性不好，泛化能力弱，现代是泛化编程的时代，什么讲究的都是扩展性，所以这是硬伤。
我的方法：六进制
也就是将每一个小块（24个）看成6进制数的一位，那么一个24位的6进制数就可以表述独一无二的一个状态。将六种颜色定义为012345,那么上图可以表示为十进制数：
黄×6⁰ +黄×6¹+…+蓝×6⁴ +蓝×6⁵+………（我想大家都懂吧）
这样做的好处是可以做到很好的泛化，也就是说广搜的引擎可以通用，不用受数据形式的局限。缺点也很明显，就是内存大，625=2.8E19，但是为了泛化性能这点牺牲对我来说值得。

1.3数据表示形式的改进？
想过改进，因为这两个数相差挺大的，也就是说这种表示冗余很多，但是想到降低数据量势必会带来算法的复杂（发掘其中的数据关系），时间的延长，没有必要。

2.程序上魔方上如何广搜
首先要说，有两种思路
第一种：朴素的广搜，从初始状态开始长树，一层一层长，长到一个树梢碰到了一个复原的状态为止（手画图如下）：

第二种，双向的广搜

这种交替的双向广搜显然更快而且内存占用少，但是有一个问题就是必须知道我将要达到的目标状态是什么，这点在下面讨论。
方法有了，就要讨论下细节：
（1）最终状态可以确定吗？
显然这取决于我们如何操作它，我们定义了魔方的几种操作：
U F R u f r V T Y

分别是Up，Front，Right三个面的操作，其中U代表的是上面进行顺时针旋转，r代表右面逆时针旋转，V代表上面180°的旋转，也就是两次U或u。用这套操作可以保证有一块永远不动（左后块），也就是说复原的状态可以唯一确定。也就是说用双向的广搜这个选择不错。
（2）数据如何表示？
状态之前讨论过，这个数很大，用int是不行了，浮点数又不专业，最终采用的是unsigned long long，合适。
（3）数据结构如何选择？
先考虑都要用什么结构，首先需要一个容器存储所有曾经出现过的状态，可以用map。
再者考虑如何存储要搜索的状态，用两个Queue，完美。
所以不需要什么复杂的结构，STL都有。
（4）简要流程

（5）代码中容易误解的地方
关于具体的操作函数例如F，U等是怎么实现的。这么说，如果一个一个写，那太LOW了，我的代码中用了一个标准函数，传入变化数列实现了，很简单，拓展性好。还有，一系列的操作函数如果每次都F（）…那也太LOW，一个函数指针就解决了，而且和enum完美融合。
在具体的设计我就不详说了，代码里都有，我也都标注了，简简单单200行代码。
前面放过软件的图片，不难用。