魔方机器人DIY 之算法系列(二叉树)

我们学习数据结构的时候，经典的二叉树结构绝对是必修的，可是很多同学表面上是理解了二叉树的基本结构，可是如何套用到日常生活中，或者我们的作品上呢？

二叉树，顾名思义，拓补结构是树状分布的，每个树节点上最多只允许出现２个分支．当然每个树节点上可以只有一个子分支，或者没有子分支．二叉树分别有满二叉树，完全二叉树，非完全二叉树等，如下图：

在实现魔方机器人的时候，二叉树也是对提高速度有着非常重要意义．今天我们来讲讲二叉树是怎样加速我们魔方还原动作的，以及是如何实现的．

在实现四爪的魔方机器人的时候，一个很明显的特征是：魔方拥有６个面，且６个面都可以单独旋转，但机器人只有４只手，无法在任意时刻都控制到６个表面，如上图．

那么在这个情况下，我们如何实现旋转顶面和底面呢？

我们可以通过爪子，将魔方整个翻转下来，这时候，顶面就会落在上下左右其中一个机械臂上，此时我们就可以实现对魔方所有面旋转的控制了．（如下图）

好了，这时候我们要注意了，将魔方翻转９０°的这个动作，不知道大家留意到没？其实这个翻转９０°是有３个旋转轴可以转的，分别是Ｘ，Ｙ，Ｚ．按我们日常的定义：

左右机械手的轴线定义为Ｘ轴；

上下机械手的轴线定义为Ｙ轴；

垂直于Ｘ和Ｙ平面的垂直法线定义为Ｚ轴；

那么，我们可以分析得出，不管是绕Ｘ轴还是Ｙ轴旋转９０°，都可以把顶面和底面翻过来给上下左右手来控制旋转，而绕Ｚ轴不管转多少度，前(F)面依然是前(F)面，背(B)面依然是背(B)面．很多同学，包括我以前做第一代的时候，都觉得既然绕Ｘ和绕Ｙ轴旋转都可以达到控制的目的，那为了方便快速实现，我每次遇到前面或者背面需要旋转的时候，都可以随机绕其中一个轴旋转９０°，或者甚至都只绕Ｘ轴转９０°就好了。可是大家仔细想想，是不是真的绕哪个轴转都无所谓呢？

还是引用我在＂四爪和六轴魔方机器人的区别?＂文章中用到的经典例子．我们通常在解魔方算法运行完毕后，会得出一串还原的序列，如：U1R3D2L1F2B3. 其中 URDLFB 分别是 U（Up顶面），Ｄ（Down底面），R（Right右面），Ｌ（Left左面），Ｆ（Front前面），Ｂ（Back后面）。

字母后面的数字为顺时针旋转９０°的次数，比如：Ｕ１代表顶面顺时针旋转一次（９０°），Ｒ２代表右面顺时针旋转２次（１８０°），Ｄ３代表底面顺时针旋转３次（２７０°）或逆时针旋转一次（－９０°）。

大家仔细想象一下，如果绕Ｘ轴顺时针旋转，那么原来的Ｕ（顶面）就会被放到Ｂ'（背面），但是原来的Ｂ（背面）也会被放置到Ｄ'（底面），如果原来的动作顺序是F（前面）旋转后跟着U（顶面）旋转的话，我们将会出现２次沿Ｘ轴翻转的动作，因为第一次把F（前面）翻到U'（顶面）了，仍需要一次Ｘ翻动，才能将U'（顶面）翻到B''（背面）实现旋转．而如果第一次是沿Ｙ轴旋转，那么F（前面）会被翻到Ｌ'（左边），而原来的U（前面）依然在U'（前面），此时我们的机械手就能顺利控制两个动作了。

以下通过动画更清晰地演示这个过程．

比如当前的还原序列为：B1R1F1L1

假设我们遇到 (F) (B) 面都往 Y方向转 90度.

序列将变换为 (Y1) R1 (Y1) L1 (Y1) R1 (Y1) L1

整个过程将需要 8 步才能完成

而假设我们遇到 (F) (B) 面都往 X方向转 90度.

序列将变换为 (X1) D1R1U1L1

整个过程仅需要 5 步就能完成

到这里，相信大家应该能跟上了，因为每次的Ｘ轴或者Ｙ轴的旋转，都会使得后面整个序列的操作面发生改变，而且后面的改变都是和前面每次的旋转轴选取相关的．其实这个过程完全就是二叉树的结构。

当遇到ＵＤ面操作需要整个翻下来的时候，就面临二叉选择（往Ｘ轴翻还是往Ｙ轴翻），翻了之后，后面所有的序列都会因此发生变化，而再次遇到ＵＤ面的时候，又是一个二叉的分支节点．只有到最后序列处理完，二叉树才结束。

为什么要引入二叉树呢？因为我们对不同的魔方初始状态的还原序列是未知的，因此我们如果不全部都遍历一次，我们并不知道到底在哪一个环节往Ｙ轴旋转，哪一个环节往Ｘ轴旋转，会让整个最终的还原序列最短，操作步骤最少。而引入二叉树的目的就是给与我们方法去遍历所有的可能性，得出最短的还原序列．而谈到这里，相信应该有同学能意识到，这并不是一颗满二叉树，因为通常会出现有些路径很快就结束了，但有些路径需要走很远才能结束，好比上面的例子。

好了，大家理解了二叉树引入的目的后，下来我们就去分析，如何去实现二叉树进行遍历．

----------------------------我是分割线-----------------------------

概述：对于魔方机器人来说，假设机械臂只能触及上(Up)，下(Down)，左(Left)，右(Right)，而无法直接操控前(Front)，背(Back)，每次遇到需要操控（前）/（背）面的话，则需要尝试往（X）轴和（Y）轴各翻转魔方一次，并计算最终长度。

以下举个相对简单的例子，当还原序列为

R3F2B1L1D1R1U1F1

我们可以分解出以下全部可能的路径：

R3X1U2D1L1X1U1R1D1X1D1

R3X1U2D1L1X1U1R1D1Y1R1

R3X1U2D1L1Y1L1X1U1R1X1D1

R3X1U2D1L1Y1L1X1U1R1Y1R1

R3X1U2D1L1Y1L1Y1L1X1U1X1D1

R3X1U2D1L1Y1L1Y1L1X1U1Y1R1

R3X1U2D1L1Y1L1Y1L1Y1L1U1

R3Y1L2R1X1D1X1U1X1D1X1U1L1

R3Y1L2R1X1D1X1U1X1D1Y1L1X1D1

R3Y1L2R1X1D1X1U1X1D1Y1L1Y1R1

R3Y1L2R1X1D1X1U1Y1R1D1X1D1

R3Y1L2R1X1D1X1U1Y1R1D1Y1R1

R3Y1L2R1X1D1Y1L1U1R1X1D1

R3Y1L2R1X1D1Y1L1U1R1Y1R1

R3Y1L2R1Y1R1D1L1U1X1D1

R3Y1L2R1Y1R1D1L1U1Y1R1

我们会发现，选出其中一个最长的路径：

R3Y1L2R1X1D1X1U1X1D1Y1L1X1D1

与其中最短的路径比较：

R3Y1L2R1Y1R1D1L1U1X1D1

最长的步骤比最短的步骤多出了3个动作，这还只是某次随机只有8步还原动作的情况下，随着还原步骤增加，差距会大幅增加。

比如以下22步还原序列：

U1L3U2R1D1L1B3L1B2R1F3L1F2L2B2L2U3D2F2L2U2B2 : 22 moves

完全遍历后，最长序列为：

U1L3U2R1D1L1Y1R3Y1R1Y1L2Y1R1Y1L3Y1R1Y1R2Y1L2Y1R2X1D2Y1R3L2X1D2Y1L2X1U2Y1R2

而最短序列则为：

U1L3U2R1D1L1X1D3L1D2R1U3L1U2L2D2L2Y1R3L2U2X1D2R2Y1L2

足足多出了11个机械动作，如果我们可以在机械动作执行前，预知最短步骤，这将会使得我们最终还原魔方时花费更少的机械时间。

当解算序列长度增加时，完全遍历整个序列将会耗用大量的时间，而实际上完全遍历是没有必要的。因为我们假设的前提是，还原步骤越多，机械耗时约长，所以我们可以在遍历的过程中剪枝来节省搜索时间。

随着搜索序列长度的增加，搜索时间并非线性增加，但由于魔方的特性，增加比例也并非指数级别上升，因为每一步变换对后面序列长度都会产生影响，而且序列本身也并非满二叉树，不过我们仍然可以初步认为是一个接近于指数函数增加趋势的函数。因此如果我们可以控制在一定长度的时候把后面的枝叶剪掉，则可以节省非常可观的搜索时长。

那么剪枝的依据从何而来呢？

介绍其中一个比较简单做法：每次遇到分支最终步骤数比之前的都少，则把当前步骤数作为剪枝点。这意味着，如果某一根分支已经达到剪枝点，但还原步骤仍未完成，则放弃求解后续步骤。如此一来，大幅度的降低整个搜索范围，提高了算法效率，何乐而不为。

以下举实际运行实例说明：