Sicily 1151魔板解题报告

Sicily 1151魔板解题报告  

1.  原题大意;  
2.  算法思想及解题用到的主要数据结构
3.  详细解题思路
4.  逐步求精算法描述（含过程及变量说明）
5.  程序注释清单（重要过程的说明）
6.  测试数据（5-10组有梯度的测试数据,要考虑边界条件）
7.  复杂度方面的分析、估算及程序优化的分析 和改进。
8. 1515 魔板C 的代码

一、 原题大意 

魔板由2*4个方块组成，用1到8的数字表示不同的块。 其初始状态是

1 2 3 4  

8 7 6 5  

对魔板可进行三种基本操作，这三种基本操作，可将任一种状态装换成另一种状态。  

A操作（上下行互换）：  

8 7 6 5 

1 2 3 4 

B操作（行循环右移一格）：  

4 1 2 3 

5 8 7 6  

C操作（中间四小块顺时针转一格）：  

1 7 2 4 

8 6 3 5  

Input： 输入步数上限和目标魔板状态,-1表示结束。
Output：在给定步数内，给出从初始状态到目标状态的步骤及步骤数。 若不能到达则输出-1.

二、 算法思想及主要数据结构  

1、 解题思想      广搜 + 康托展开    
2、 主要数据结构  队列 + 用int表示魔板状态。

三、 详细解题思路  BFS  +  康托展开 

1. BFS
   I． 将初始状态放入队列， 
   II．从队列中拿出队首元素，和目标状态比较，如果相等停止BFS。
   III.对队首状态分别进行A、B、C 三种操作，只把得到的新状态放入队列。若该状态曾经到达过，则忽略。
   IV． 只要队列不为空，重复II III操作。 
     
   
2. 康托展开
   康托展开是全排列和整数的双射, 即给定一个长为n的排列，康托展开则得到该排列在全排列中的序号(0 ~ n!-1)。
   例如 (2 1 3) 展开得 2，  (1 2 3)展开得 0， (3 2 1)展开得5。  
   
   
3. 状态的存储和A、B、C操作的实现。
   一个魔板 8 个数，每个数都小于16，只需4bit就能表示，所以一个int就能表示一个魔板。
   因为是4bit，恰好可以直接使用 16进制数 做位操作的掩码。
   初始状态    1 2 3 4 8 7 6 5    ---->   0x12348765
    
   A操作： 上下行互换，就是高4位和低4位互换。 结果 0x87651234.
   B操作： 循环右移， 就是第4,8位左移3位，其他位右移1位。结果 0x41235876
   C操作： 中间顺时针转90度。 对比操作前后的结果 就知道哪些位要移动多少。
                 0x12348765
                 0x17248635
   可以看出：第2位右移1位； 第3位右移4位， 第6位左移4位， 第7位左移1位。

四、 伪代码算法描述

由题目可知，每次BFS的初始状态，操作都没变。所以其实搜索树的内容是完全一样的。

因此只需要 遍历魔板的 8! 种状态都一次。之后就在搜索队列中查找即可。

//遍历 所有状态
initialize( queue, isVisited[] );
while( queue.notEmpty() ){for( op = A, B, C ){next_state = op();       order = cantor( next_state );  //计算康托展开if( isVisited(order) == FALSE ){  //是未访问的节点就放入队列。push();isVisited(order) = TRUE;}}
}
target = input();
index = search( target, queue );  //在队列中查找 目标状态
if( found >=0 && 步数小于限制  )  //found<0 说明没找到。print(  queue[found] )
else print(-1);

五、 程序注释清单

六、 测试数据  

4
4 1 2 3
5 8 7 6
B

4
5 7 2 6
4 8 1 3
BCA

3
8 7 6 5
1 2 3 4
A

4
5 8 7 6
4 1 2 3
AB

3
5 1 8 6 
4 2 7 3 
ABC



5
5 8 3 2 
4 1 6 7 
accb

15
5 8 2 3 
4 1 6 7 
-1

25
5 8 2 3 
4 1 6 7 
20  BBCBBCABCBCBBBCBCBCB

20
3 7 2 1  
6 5 8 4 
8 CCBBCABC

20
4 6 5 8  
1 3 7 2   
10 CCBBCABCAB

30
4 5 2 7  
3 8 1 6
 
22 ACBBBCBCBCBCBCABCABCBC

七、 复杂度分析及优化改进

因为状态数目40320，所以空间复杂度就是常数。
但是节点的体积是可以再减小的，节点无需存储所有操作，只需存储当前操作(1B)，还有父节点下标(2B).
每个节点只需 7个字节，由于存在字节对齐，所以每个节点会占用8字节。 
总内存： 8*40320 + 312KB(运行时系统) = 634KB 
采用这种方法，出乎意料的是 运行时间也减小了。
原来 0.02 sec 2376 KB
现在 0.01 sec 640 KB    内存使用量和估计值十分接近 。
整个搜索树是3叉的，  对于第i层，要搜索3^i个节点（i从0开始） 

通过判重来剪枝，可以显著减少搜索队列的长度。只留下 40320 个节点。

八、1515 魔板C 的代码

魔板c和 1151没有本质不同，仅仅是opa opb opc 有改变。三种操作修改如下。

[cpp]  view plain copy

1. unsigned opa( unsigned brd ){  
2.     unsigned a = (brd & 0xff00ff00)>>8,  
3.              b = (brd & 0x00ff00ff)<<8;  
4.     return a|b;      
5. }  
6.   
7. unsigned opb( unsigned brd ){  
8.     unsigned a=(brd & 0xf000f000) >> 12,   
9.              b=(brd & 0x0fff0fff) << 4;  
10.     return a|b;  
11. }  
12.   
13. unsigned opc( unsigned brd ){  
14.     unsigned a= (brd & 0x0f000000)>>16,  
15.              b= (brd & 0x00f00000)<<4,  
16.              c= (brd & 0x00000f00)>>4,  
17.              d= (brd & 0x000000f0)<<16;  
18.     return (brd &0xf00ff00f) |  a | b | c | d ;  
19. }