膜

膜

先收藏

首发 ɠźĥ：Rand_cs，求关注支持，格式烂观感不好的问题请移步 ɠźĥ，贴吧我实在没办法，只能这样
五、剪枝
剪枝，应该是科先巴的二阶段算法的核心了，综合运用了前面定义的所有数据结构来构建一个新的查找表——剪枝表，表里面存放的信息是距离目标状态(阶段一)或者还原状态(阶段二)最少还需要多少步。如果这个步数大于了还能走的步数，剪掉回溯。
两个阶段的剪枝表可能有多张，每个阶段都要选取最大的那个数作为到目标/还原状态的最少需要步数，比如说表一告诉我当前状态至少还需要 5 步到达目标状态，表二告诉我至少还需要 6 步，则将 6 作为至少需要步数。还是很好理解的是吧，表一表二分别描述了魔方的一部分状态，每部分状态都达到目标状态才算达到目标状态，所以要选取最大的。这也是 IDA* 算法里面的 h(n) 这个函数。
Ⅰ 建立剪枝表
剪枝表竟然能够出到目标状态的最少步数？是不是很神奇，其实没什么神奇之处，就是一个暴力广搜得到的结果。设定目标状态的深度为 0 ，然后对目标状态进行 18 种转动操作，得到第一层的状态结点深度为 1，再对第一层的每种状态转动，得到第二层状态结点，深度为2..........具体看下面伪码：

本质上就是广搜，只是形式上与我们平常看到的框架可能不太一样，这种形式费点时但省空间不用像常见广搜框架那样储存节点，魔方的状态数很多，我们要采用更省空间的形式
Ⅱ 存储技巧
如果知道初始状态距离目标状态有多远，而后每执行一步，距离目标状态要么要么加 1，要么不变，要么减 1，就这三种情况，那么我们就能够计算出转动后的状态距离目标状态多远。所以其实剪枝表里面我们只需要 2个 bit 来存储 实际距离 mod 3 的值。根据当前状态的距离，再根据剪枝表里面查到的 mod3 值就能够算出转动后的状态到目标状态的距离的。如此就大大减少了空间的使用。
但关键在于初始状态到目标状态距离有多远？你可能会说，查表嘛，查表没错，但是要记住，现在剪枝表里面存放的不是实际距离了，存放的是只用了 2 bits 的 mod3 距离。那怎么办呢？我们直接看伪码分析解决办法：

根据伪码应该能看出大概意思吧，因为我们从剪枝表里面查出来的是 mod3 距离，所以 mod3 距离从 3 到 0 一直循环的递减，实际距离从 0 开始一直递增，直到到达目标状态。因为我们每次更新两个距离值都是要转动后距离目标状态更近，所以最终得出的实际距离 depth 一定是初始状态到目标状态需要的最少步骤。这似乎都已经把魔方解了一遍了，但其实并不是，因为 index 只是魔方部分状态的坐标索引，所以这个函数算出来的值只是当作一个初始指标。

膜

阿哲

牛膜

太难了

近世代数😨

不明觉厉

靠，看不懂

刚好计算机专业，顶

6

牛