标签

2014年12月28日星期日

SOJ 1151 魔板

题目描述
SOJ 1151是一道关于搜索的题目,魔板由八个方块组成,为一个2×4的矩阵,每块分别用1-8表示颜色区别,每一次均可以对其进行一次操作,其中可选操作为A,B,C:
A操作(上下行互换)
B操作(每次以行循环右移一个)
C操作(中间四小块顺时针转一格)
魔板初始状态为
1 2 3 4
8 7 6 5
给定一个目标状态,给定一个最大步数,要求求出从初态到目标态的最小操作序列,若超出最大步数则停止计算,输出-1

算法思想及解题用到的主要数据结构
由于本题的目标是尽快找到解,通过分析,我们可以知道从一个状态执行三种操作到达其下一个状态,在决策树中三个分支是代价一致的(即所有深度相同的节点代价相同),因此我们可以通过广度优先搜索搜寻解,其找到的解必定是最优解。
广度优先搜索的过程我们需要用到队列这种数据结构来辅助。
关于魔板的表示方式,我们可以使用字符串,定义一个结构体board,其中包括两个字符串status和op,status为一个表示此魔板状态的8长字符串,只有字符1-8,op表示初态转换为当前魔板状态的操作序列,由字符ABC组成,初态的op为空字符串。
同时,由于由1-8组成的8串只有8!=40320种不同情况,我们可以想办法记录已经搜索过的状况,确保没有重复搜索。
记录已经搜索状况的数据结构,需要用到关联数组。

详细解题思路
根据广搜的原理,我们首先将目标状态放入队列,对于维护队列的队头,我们先检查其符不符合目标状态,若不符合,我们获得它经过三种操作后的三种状态,放入队尾,然后把当前队头弹出队列。直到我们找到目标状态,或者操作的深度已经超过最大限度,循环结束。
同时为了方便判断重复状态,我们在将状态放入队列之前还需要将其记录下来,以map为例,我们在将下一状态放入队列前,先在map中搜索,判断其是否为已经搜索过的状态,若否,我们将该状态的<status, op>数据对放入用于判断的map中。

逐步求精算法描述
由于在map中搜索也需要一定的时间复杂度,为了避免不必要的搜索,我们可以在插入队列前先做一定的剪枝。
考虑如同XX……XX的一个操作序列/字符串,我们可以知道,一个状态连续进行两次A操作会变为它本身,一个不必搜索的状态,在计算三种操作能到达的状态前,我们可以先分析当前状态的op串的最后一个字符串,若为A,则我们不必搜寻其进行A操作后得到的下一个状态,达到剪枝的目的,并节省需要在map中搜索才得出结果的时间。
同理XX……X = XX……XBBBB,XX……X = XX……XCCCC,可以帮助剪枝。
当然,上面这个方法只是小儿科,当我们能将进行一次操作的复杂度降低时,便不需要上面的这个预分析的办法,下面讲讲两种优化技巧。

康托展开
康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序,因此是可逆的。比如说题目中的这种情况,一个魔板状态相当于一个1到8的全排列状态,通过康托展开,我们可以用一个0 到 40319的数字表示8!种状态,又因为这是一个双射,很容易可以通过这个数字还原这个全排列。


位运算处理
模板状态的保存问题,我们看到题目,很自然会想到用一个2x4的字符矩阵来保存这个状态,又或者是一个大小为8的数组,所以储存一个状态占用8个字节。对于ABC三类操作,通过交换数组/矩阵内的元素位置实现。这里引入位运算的办法来简化这一过程。
8个1-8的十进制数,用二进制表示,每个数至少要4位,一共需要32位(四字节),即一个int类型的大小。我们就用一个int类型内的二进制位表示一个魔板状态。
这样一来,对数组内的元素交换位置,可以改为速度更快的微操作:
A(x) = (x ≪ 16) | (x ≫ 16)
前16位表示第一行,后16位表示第二行,将x左移16位和右移16位的结果合并,则实现上下行的交换
B(x) = [(x &0xFFF0FFF0) ≫ 4] | [(x &0x000F000F) ≪ 12]
(x &0x000F000F),取出魔板的最右一列,左移12位变为左数第一列,将其余的三列((x &0xFFF0FFF0))右移4位,表示循环右移的结果
C(x) = (x &0xF00FF00F) | [(x &0x0F000000) ≫ 4] | [(x &0x00F00000) ≫ 16]
| [(x &0x00000F00) ≪ 16] | [(x &0x000000F0) ≪ 4]
相当于初始状态中2-3-6-7循环交换位置。
这一做法是一个同学的启发,他用位操作用得非常巧妙,经常受他启发。当然很多时候很多问题用位操作都可以加速,只是思考编码的过程如果不熟练的话需要更多的时间。

总结
N为状态总数,在预处理时,广度优先需要访问每个状态,对于每个状态需要O(log N)的时间复杂度。将其插入到关联数组中。在回答输入的查询时,对于每个查询需要O(log N)的时间复杂度来得到关联数组中的元素。假设一共有M个查询,则该算法的时间复杂度为O(Nlog N + Mlog N) = O((N + M) log N)

简单地说,我们求精的思路过程是:
简单的广搜,没有记忆化(会有很多重复状态)->加入记忆化,记录已经走过的状态(判断一个状态有没有走过也需要时间)->剪枝,通过查看操作序列判断是否应该执行某操作,因若进行该操作,得到的状态必然为已经走过的(判断这个也需要时间)->把所有可能先搜出来并记录,对于每条查询,直接在答案中找。

没有评论 :

发表评论