本文来具体介绍一种具体的魔方还原算法——科先巴的二阶段算法，有一部分相关内容在前篇帖子讲述，主要是方向定义那一块儿，没有看的建议先看一下。也可以在我的公号中看原文，格式更好，更方便阅读。
二阶段，顾名思义，解决问题分为两步，先完成一个目标，再最终复原。对于二阶段算法有一个生动的比喻，复原魔方就像是一条小船要在汪洋大海上行驶到一个固定的目的地。二阶段算法就是先让小船行驶到一个固定的特殊水域，再驶向最终的目的地，这显然比直接寻找目的地要容易简单的多。
比喻归比喻，终归抽象，我们来具体看看，本篇很长很长，我分开来说。
一、总述
为方便叙述，也避免搞混淆，我们定义任意打乱的魔方称为随机状态或者初始状态，处于特殊水域的那些状态称为目标状态，目的地为还原状态。
初始状态可以看作是由 U，R，F，D，L，B 这 6 个基本转动复合而成的，由这 6 个转动生成的群记为 G=<U,R,F,D,L,B> 。
而科先巴定义的目标状态是只由 U，D，L2，R2，F2，B2 这 6 种转动复合生成的，同样的记为 G1=<U,D,L2,R2,F2,B2>。
Ⅰ 目标状态性质
还记得上篇文章计算状态数时是怎么定义方向的么？再来复习复习重新看看：
1. 棱边有 2 种状态，未翻转(flip)用 0 表示，翻转用 1 表示， 只有 F，B 层的转动能够改变方向。
2. 角块有 3 种状态，未扭转(twist)用 0 表示，顺时针扭转用 1 表示，逆时针扭转用 2 表示，只有 U，D 层转动不改变角块方向。
目标状态由 U，D，L2，R2，F2，B2 这 6 种转动生成，而这 6 种转动不会引起角块和棱块方向的变化。因为不论怎么转动，角块拥有的 U 层面或 D 层面始终处于 U 层或者 D 层，所以方向不变。也不会引起棱块方向变化，因为只有 F，B 的转动会引起棱块方向的变化，而像 F2 这样的连续转动两次，翻转再反转棱块相当于未翻转，所以棱块的方向也是不会变化的。这 6 种转动也不会将中层块带到 U 层或者 D 层，所以处于中层的块只能处于中层。
因此目标状态的性质总结如下：
1. 棱块角块方向不变，即各自的方向值总和都为 0。
2. 还原状态下的中层块处于中层
Ⅱ 搜索算法
科先巴的二阶段算法使用的搜索算法是 IDA* 算法，也就是迭代加深搜索算法，而且两个阶段使用的都是 IDA* 算法。
关于IDA*，还有个 A*算法大家可能不太熟悉，也没什么神秘的，简单说说。A* 就是具有启发函数的广搜。IDA*就是有搜索深度限制，有启发函数的深搜。点到为止，详细的解释请百度 CSDN。
一般的，广搜是能够找到最短路径的，深搜不能，IDA*虽然使用的是深搜，但是它有深度限制，也是能够找到最短路径。比如说我搜索深度定为 1 ，没搜到，再定为 2 重新搜索，依次下去，就能够得到最短路径。
所以两个阶段都是能够得到相应的最短路径，能够使用最少的步数达到每个阶段的目标，但合起来会是最优解吗？
答案是否定的，因为阶段二得到的最优解是相对于阶段一来说的，举个例子
两个阶段都相应最优就好比上述方法 1 得到的距离，但两个阶段合起来明显不是最短距离，两点之间线段最短应该是方法 4。
那怎么解决呢，如何得到更优甚至最优的解法？也如上图所示，我们加深第一阶段的搜索深度，虽然第一阶段的路径变长了，但是第二阶段可能找到更短路径，这样它们合起来边可能更优。这样一步步下去，是总能找到最优解的，也就是说科先巴的二阶段算法一次搜索可能得不到最优解，但是只要给它时间，是一定能够找到最优解的。但是对于科先巴算法并不是拿来寻找最优解的，目的是短时间内找到一组比较优的解。
对于科先巴的二阶段算法应该有了很直观的基本认识了吧，如果还不清楚，再针对魔友举一个很形象的例子。咱们一般使用的 CFOP 还原公式，F2L 之后就应该是 OLL，PLL 的对吧，如果我们正常的按照 CFOP 的公式来，这几个阶段都得到的是最优解，合起来的话也是比较优的。但是如果我们在 F2L 时多花几步，是可能跳 O 甚至跳 P 的，这就会节省很多后续转动步骤，得到一个更优的解法。
上述有关两点之间线段最短的例子只是比喻，实际情况稍微有点不一样，前面说过二阶段算法就是小船先驶向一片特殊水域，再驶向目的地，但是某些情况的最短路径可能根本就不经过那片水域，如果还是先经过特殊水域的话，自然也就得不到最优解。那这是不是就与上述所讲的冲突呢？也不然，还原状态其实也是目标状态之一是吧，所以如果解决阶段一之后发现已经还原了，阶段二所需要的步骤降为 0 ，那这就是最优解。就好比完成 F2L 之后惊奇的发现跳 O 又 条 P 已经还原了。
好了，上述就是对科先巴的二阶段算法的一个总述，应该是很容易理解的。下面是算法细节，挺多，感兴趣的朋友可以看看，对魔方没什么兴趣的了解到这一步大概就够了。
不过学计算机的，关于魔方的还原算法还是很值得一看的。不知道大家有没有做过八数码的题，解魔方与解八数码本质上是一样的，英文也都用 puzzle 这个词来表示，只不过魔方的状态数比八数码要大得多，而且魔方方方正正的，有许多特殊的性质可以利用来优化算法，下面来具体看看：
二阶段，顾名思义，解决问题分为两步，先完成一个目标，再最终复原。对于二阶段算法有一个生动的比喻，复原魔方就像是一条小船要在汪洋大海上行驶到一个固定的目的地。二阶段算法就是先让小船行驶到一个固定的特殊水域，再驶向最终的目的地，这显然比直接寻找目的地要容易简单的多。
比喻归比喻，终归抽象，我们来具体看看，本篇很长很长，我分开来说。
一、总述
为方便叙述，也避免搞混淆，我们定义任意打乱的魔方称为随机状态或者初始状态，处于特殊水域的那些状态称为目标状态，目的地为还原状态。
初始状态可以看作是由 U，R，F，D，L，B 这 6 个基本转动复合而成的，由这 6 个转动生成的群记为 G=<U,R,F,D,L,B> 。
而科先巴定义的目标状态是只由 U，D，L2，R2，F2，B2 这 6 种转动复合生成的，同样的记为 G1=<U,D,L2,R2,F2,B2>。
Ⅰ 目标状态性质
还记得上篇文章计算状态数时是怎么定义方向的么？再来复习复习重新看看：
1. 棱边有 2 种状态，未翻转(flip)用 0 表示，翻转用 1 表示， 只有 F，B 层的转动能够改变方向。
2. 角块有 3 种状态，未扭转(twist)用 0 表示，顺时针扭转用 1 表示，逆时针扭转用 2 表示，只有 U，D 层转动不改变角块方向。
目标状态由 U，D，L2，R2，F2，B2 这 6 种转动生成，而这 6 种转动不会引起角块和棱块方向的变化。因为不论怎么转动，角块拥有的 U 层面或 D 层面始终处于 U 层或者 D 层，所以方向不变。也不会引起棱块方向变化，因为只有 F，B 的转动会引起棱块方向的变化，而像 F2 这样的连续转动两次，翻转再反转棱块相当于未翻转，所以棱块的方向也是不会变化的。这 6 种转动也不会将中层块带到 U 层或者 D 层，所以处于中层的块只能处于中层。
因此目标状态的性质总结如下：
1. 棱块角块方向不变，即各自的方向值总和都为 0。
2. 还原状态下的中层块处于中层
Ⅱ 搜索算法
科先巴的二阶段算法使用的搜索算法是 IDA* 算法，也就是迭代加深搜索算法，而且两个阶段使用的都是 IDA* 算法。
关于IDA*，还有个 A*算法大家可能不太熟悉，也没什么神秘的，简单说说。A* 就是具有启发函数的广搜。IDA*就是有搜索深度限制，有启发函数的深搜。点到为止，详细的解释请百度 CSDN。
一般的，广搜是能够找到最短路径的，深搜不能，IDA*虽然使用的是深搜，但是它有深度限制，也是能够找到最短路径。比如说我搜索深度定为 1 ，没搜到，再定为 2 重新搜索，依次下去，就能够得到最短路径。
所以两个阶段都是能够得到相应的最短路径，能够使用最少的步数达到每个阶段的目标，但合起来会是最优解吗？
答案是否定的，因为阶段二得到的最优解是相对于阶段一来说的，举个例子
两个阶段都相应最优就好比上述方法 1 得到的距离，但两个阶段合起来明显不是最短距离，两点之间线段最短应该是方法 4。
那怎么解决呢，如何得到更优甚至最优的解法？也如上图所示，我们加深第一阶段的搜索深度，虽然第一阶段的路径变长了，但是第二阶段可能找到更短路径，这样它们合起来边可能更优。这样一步步下去，是总能找到最优解的，也就是说科先巴的二阶段算法一次搜索可能得不到最优解，但是只要给它时间，是一定能够找到最优解的。但是对于科先巴算法并不是拿来寻找最优解的，目的是短时间内找到一组比较优的解。
对于科先巴的二阶段算法应该有了很直观的基本认识了吧，如果还不清楚，再针对魔友举一个很形象的例子。咱们一般使用的 CFOP 还原公式，F2L 之后就应该是 OLL，PLL 的对吧，如果我们正常的按照 CFOP 的公式来，这几个阶段都得到的是最优解，合起来的话也是比较优的。但是如果我们在 F2L 时多花几步，是可能跳 O 甚至跳 P 的，这就会节省很多后续转动步骤，得到一个更优的解法。
上述有关两点之间线段最短的例子只是比喻，实际情况稍微有点不一样，前面说过二阶段算法就是小船先驶向一片特殊水域，再驶向目的地，但是某些情况的最短路径可能根本就不经过那片水域，如果还是先经过特殊水域的话，自然也就得不到最优解。那这是不是就与上述所讲的冲突呢？也不然，还原状态其实也是目标状态之一是吧，所以如果解决阶段一之后发现已经还原了，阶段二所需要的步骤降为 0 ，那这就是最优解。就好比完成 F2L 之后惊奇的发现跳 O 又 条 P 已经还原了。
好了，上述就是对科先巴的二阶段算法的一个总述，应该是很容易理解的。下面是算法细节，挺多，感兴趣的朋友可以看看，对魔方没什么兴趣的了解到这一步大概就够了。
不过学计算机的，关于魔方的还原算法还是很值得一看的。不知道大家有没有做过八数码的题，解魔方与解八数码本质上是一样的，英文也都用 puzzle 这个词来表示，只不过魔方的状态数比八数码要大得多，而且魔方方方正正的，有许多特殊的性质可以利用来优化算法，下面来具体看看：
