6.求解算法简介

1、1 算法设计算法是机器人的部分，借助于计算机本身计算速度的优势，解魔方算法是机器与人类真正拉开差距的所在。解魔方机器人的算法通常分为两个部分：一部分是求解如何解魔方，即先拧哪个面，后拧哪个面，输出的解法被称为拧动序列；另一部分为求解魔方机器人的动作，即先开哪个气缸，后转哪个电机，输出的解法被称为动作序列。1.1 约定术语介绍魔方总共 6 个面，分别称为：F、R、U、B、L、D，如图 5-1 所示。其中前面称为 F，即 front；右面称为 R，即 right；上面成为 U，即 up；后面为 B，即 back；左面为 L，即 left；下面为 D，即 down14。由于每个面的拧动方式都有三种，

2、即顺时针 90，逆时针 90，顺（逆）时针 180，所以为了描述一个拧动动作，还需要加上角度。规定顺时针 90为 1，顺（逆）时针 180为 2，逆时针 90为 3。则 L1 代表左面顺时针转 90 度， R2 代表右面顺（逆）时针 180。通常，拧 动序列由 一系列按 顺序排列 的拧动步 骤组成，比 如。图 5-1 魔方转动描述二臂二指型解魔方机器人运动示意图如图 5-2 所示。解魔方机器人有两个，为 L 和 R。每个有两个度：手腕旋转和手指开合。因此，左边手腕顺时针旋转 90可描述为 L1，为了与拧动序列做区分，每个动作序列前加前缀“M_”。因此动作序列所包含的动作有：M_L1，即左边手腕

3、顺时针转动 90；M_L2，即左边手腕顺（逆）时针转动 180；M_L3，即左边手腕逆时针转动 90；M_LO，即左边手指打开； M_LC，即左边手指关闭；M_R1，即右边手腕顺时针转动 90；M_R2，即右边手腕顺（逆）时针转动 180；M_R3，即右边手腕逆时针转动 90；M_RO，即右边手指打开；M_RC，即右边手指关闭。图 5-2 解魔方机器人运动示意图1.2 常见魔方算法1.2.1 层先法层先法是三阶魔方的入门解法，也是大多数人魔方者接触魔方时使用的解法。层先法解法一共分为 6 个步骤，下面用配图解释 6 个步骤各种所需要实现的目标15。层先法第一步为顶层如图 5-3 所示，即将魔方

4、 26 个块中的 4 个棱块拼到指定的位置。图 5-3 顶层复原层先法第二步为复原顶层角块如图 5-4 所示。与通常所理解的复原一面不同，该步骤需要在复原一面的基础上同时复原该面周围的一圈。图 5-4 顶层角块复原层先法第三步为复原中层的四个角块如图 5-5 所示。另一种说法为复原前两层。图 5-5层先法第四步的目标为底层拼出中层边块复原如图 5-6 所示，即底层边块复原。图 5-6底层复原层先法第五步的目标为将顶层的角块翻转到颜色冲上的位置如图 5-7 所示，即复原底面（为方便描述这里将魔方倒转）。图 5-7 底层复原层先法第六步为将底层的角块位置调整到正确位置如图 5-8 所示。至此，一个

5、三阶魔方已经解出。图 5-8 底层角块复原内容少，门槛低，只要经过一定训练就能学会，通常作为。很多异形魔方也可以用层先法的思路解出。层先法所需三阶魔方的入门1.2.2 CFOP 法CFOP 是层先法的升级版，CFOP 省略了层先法的第二步和第四步，只留下了一、三、五、六这四个步骤。魔方高级CFOP 最早是由 Fridrich 教授发明，所以叫做 Fridrich System，目前世界上绝大多数的顶尖魔方高手都在采用这个方法。CFOP 的意思是要分四步还原魔方，分别是，Cross-2 layers（简称F2L）-Orienion of last layer（简称 OLL）-Permuion o

6、f last layer（简称PLL），也就是：底层-同时对好前两层-调整好最后一层的朝向-调整好最后一层的顺序（排列）。CFOP 法解法顺序如图 5-9 所示。图 5-9 CFOP 法顺序内容相对较多，但解法步骤少，复原速度相对于层先法，CFOP 法快。1.2.3 二阶段算法二阶段算法是由 Kociemba 设计的，通常被称为 Two Phase Algorithm，目前可在上找到各种语言版本的算法。对于一个已经复原的魔方，如果你用除了之外的转法来拧动它，你能生成的状态表示魔方所有可能状态群中的一个子群。这个子群表示为 G1=。这个子群的一个典型特点是所有角块和棱块的朝向是不会改变的。也就是

7、说，当一个棱块或者是角块处于一个特定位置时，它的色向总是一样的。同时，UD 夹层上的棱块始终位于该夹层上。二阶段算法的第一阶段所要达成的目标便是让魔方转动到 G1 群内状态。即：角块和棱块的色向被限制，同时属于 UD 夹层的棱块也转至该层上。本阶段所使用的算法为迭代加深启发式搜索算法。在第二阶段，算法通过执行被允许的所有转动，将已属于 G1 子群的魔方还原。当二阶段算法求解出一个可行解之后，还会根据提前设定的参数决定是否继续搜索，若在最少步模式下，可以一直搜索到全局最优解，从而搜索到最少步。事实上，由于计算出最少步对计算机性能要求过高，为了避免过长时间段的等待，在程序中可人为调整算法终止步骤，

8、以防止进入长时间的运算。本文所使用魔方算法为二阶段算法。CubeExplore5.00 是Kociemba 教授基于Two Phase Algorithm 开发的一款魔方求解器，本文所介绍解魔方机器人利用在 8081 端口开启了网络服务，可从程序中传输一了其中网络接口功能。该个经过加密的包含 54 个色片位置的字符串，通过 URL 请求获取对应魔方的解法。该字符串按照 URFDLB 的顺序描述六个面，每个面从左向右，从上到下，依次描述每个色块，比如图 5-10 所示魔方经编码后的 url 请求为：。图 5-10 一个被打乱的魔方在上面这个例子中，由于 U 面（U 即 up，顶面）的中心块是蓝色，因此所有蓝色块所在位置用 u 来表示。上面例子中的字符“bdr”开头，因为对于例子中的魔方，U-1 位置（U 面第