搜索剪枝(魔方为例)x

《搜索剪枝(魔方为例)x》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、搜索(剪枝&打表）PocketCube（HDU4801）给了一个2*2的魔方，每步操作可以将任意一面翻转90度，现在问在N(<=7)步内，最多能翻出几面相同的。一、问题描述1、最朴素的实现首先可以发现，极限情况下，最多旋转7次，次数很小，可以考虑用穷举，或者说，DFS的方法来实现。其次考虑，对当前的魔方状态，有多少种单次转动的行为可以转成另一种状态：综上，一共12种基本操作。考虑一下运算次数：12^7*24=859963392,约8.5亿，也就是说，处理一个魔方最坏需要基本运算8.5亿个，这是不可接受的，所以需要考虑剪枝。二、解题思路计算对应关系以下约定：前面指6、7、12、13这一面，左

2、面指4、5、10、11这一面，上面指0、1、2、3这一面。a→b表示原来在a位置的数旋转后移动到b位置前面的旋转中顺时针旋转对应关系：(1)前面旋转对应关系：const intfront[24]={0,1,8,14,4,3,7,13,17,9,10,2,6,12,16,15,5,11,18,19,20,21,22,23};(2)上面旋转对应关系：const intup[24]={1,3,0,2,23,22,4,5,6,7,10,11,12,13,14,15,16,17,18,19,20,21,9,8};(3)左面旋转对应关系：const intleft[24]={6,1,12,3,5,11

3、,16,7,8,9,4,10,18,13,14,15,20,17,22,19,0,21,2,23};2、剪枝第一次首先可以注意到，相对运动的特点，上面顺时针旋转等效于下面逆时针旋转，上面逆时针旋转等效于下面顺时针旋转，等等。也就是说，在上述列举的12种基本操作中有6对操作两两等效。换言之，可以去除其中重复的6种操作，剩下6种操作：需要的运算次数：6^7*24=6718464，只需要6百万的基本运算，需要的基本运算是剪枝前的1/128，理论上效果极佳.。减少代码量首先可以预见，对每一种旋转方法，我们需要写出这种旋转方法操作后某个位置的色块移动到的区域。换言之，我们需要预先计算出6种对应关系，

4、对每种对应关系写出相应的表示旋转操作的数组——需要6个24个元素的一维数组。24*6=144，要写的量比较大，非常容易出错。可以注意到，逆时针旋转1次等效于顺时针旋转3次也就是说，具体实现中，可以只预先计算顺时针旋转的3个操作的对应关系，在实现逆时针旋转的时候，用3次顺时针旋转来替代。（当然也可以先算好逆时针实现，顺时针旋转时调用3次逆时针旋转）具体实现//剪枝第一次//12种基本操作中有6对操作两两等效//逆时针旋转1次等效于顺时针旋转3次intcurrent[12][24];voidturnup(intdepth){for(inti=0;i<24;i++)current[depth][

5、i]=current[depth-1][up[i]];//根据up对应关系}voidturnleft(intdepth){for(inti=0;i<24;i++)current[depth][i]=current[depth-1][left[i]];}voidturnfront(intdepth){for(inti=0;i<24;i++)current[depth][i]=current[depth-1][front[i]];}3、剪枝第二次注意到在题目要求中提到：在N步操作以内（包括N步）最多能使几个面的4个块的颜色相同。也就是说，可以0步，可以1步，可以2步，只要小于等于N步即可，不一

6、定恰好N步。也就是说，如果进行DFS，那么，每次DFS都要先对当前魔方状态进行检查，记录最大4块同色的面数。换句话说，如果对先顺时针转了上面，在逆时针转了上面，在这一题中，没有任何意义，还平白无故减少了2次操作。那这样，我们可以想到，上一次做过A操作，那本次就不应该进行一个等效于撤销A操作的操作。而对上述6个操作中的每一个，有且仅有1个操作与此操作作用刚好相互抵消，也就是，第一次旋转有6种选择，之后每次旋转有5种选择。那这样，极限情况下，需要的基本运算次数为6*(5^6)*24=2250000，相比第一次剪枝，理论上时间减少了约2/3.//第二次剪枝：判断是否做了上次操作的逆操作if(pr

7、e!=2){turnup(depth);dfs(depth+1,1);}if(pre!=1){//先模拟连续逆时针旋转了3次的操作turnup(depth);turnup(depth+1);turnup(depth+2);//再把最后结果拿回来，当做顺时针旋转1次的操作for(inti=0;i<24;i++)current[depth][i]=current[depth+2][i];dfs(depth+1,2);}if(