首页 > 代码库 > Sicily 1151 解题报告（魔板，广搜）
Sicily 1151 解题报告（魔板，广搜）
I. 原题中文大意
魔板由2*4个方块组成，用1到8的数字表示不同的块。 其初始状态是
1 2 3 4
8 7 6 5
对魔板可进行三种基本操作，这三种基本操作，可将任一种状态装换成另一种状态。
A (上下行互换) | B (行循环右移一格) | C (中间四块顺时针转90) |
8 7 6 5 1 2 3 4 | 4 1 2 3 5 8 7 6 | 1 7 2 4 8 6 3 5 |
II. 算法思想及解题用到的主要数据结构
- 广度优先搜索，已搜索过的节点不再进行记录，保证第一个找到的解即为最优解。
- HASH表，采用康拓展开表示序号数，共8!种可能性，无碰撞问题。
III. 详细解题思路
- BFS实现
- 将初始状态放入队列。
- 从队列中拿出队首元素，和目标状态比较，如果相等停止BFS。
- 若不等，对队首状态分别进行ABC三种操作，只把得到的新状态放入队列。若该状态已到达过，则忽略。
- 只要队列不为空，重复II III操作。
- 康托展开?
康托展开是全排列和整数的双射, 即给定一个长为n的排列，康托展开得到该排列在全排列中的序号(0 ~ n!-1)。?例如 (2 1 3) 展开得 2， (1 2 3)展开得 0， (3 2 1)展开得5。 ?因此它能对n个数的排列进行状态的压缩和存储。例如要对8的全排列进行判重，没有必要开一个87654321?这么大的数组。对于一个n的排列数，通过康托展开得到这个排列在全部的排列中排第几位。这个序号最大?也就 8!=40320。根据序号就能通过hash快速确定 该状态是否访问过。
- 以16进制掩码进行状态的存储及A、B、C操作
一个魔板 8 个数，每个数都小于15，只需4bit就能表示，所以一个int 32位就能表示一个魔板。
因为是4bit，恰好可以直接使用 16进制数 做位操作的掩码。
初始状态对应的16进制数： 12348765
0x12348765?
A操作: 上下行互换，就是高4位和低4位互换。 结果 0x87651234.
B操作: 循环右移， 就是第4,8位左移3位，其他位右移1位。结果 0x41235876
C操作: 中间顺时针转90度。 对比操作前后的结果 就知道哪些位要移动多少。
0x12348765
0x17248635
可以看出：第2位右移1位； 第3位右移4位， 第6位左移4位， 第7位左移1位。
IV. 逐步求精算法描述（含过程及变量说明）
- 变量：
/** * 魔板状态节点 * @board 当前魔板状态, @pre 到达此状态的前一状态在队列中的位置, * @op 到达此状态的操作 */struct node{ unsigned int board; unsigned short pre; char op;};/** * @fp 队头下标, @rp 队尾下标, * @q 广搜得到的所有序列, @isVisited 标记某序列是否访问过, * @QSIZE 队列大小，由前知为40320 */int fp = 0, rp = 1;struct node q[QSIZE];bool isVisited[QSIZE] = { false };
- 方法
/** initialize 遍历所有8!个状态 opa, opb, opc 三种操作，用函数指针循环调用 cantor 计算康托展开 isNew 判断是否是新的状态 print 输出所求字符串 */void initialize();unsigned opa( unsigned brd );unsigned opb( unsigned brd );unsigned opc( unsigned brd );unsigned (*funcp[3])( unsigned ) = {opa, opb, opc};int cantor( unsigned brd );int isNew( unsigned brd );void print( node& x, int limit );
V. 程序注释清单（重要过程的说明）
1 #include <cstdio> 2 #include <string> 3 #define QSIZE 40320 4 using namespace std; 5 6 struct node{ 7 unsigned int board; // 魔板序列 8 unsigned short pre; // 前一个状态在q中的下标 9 char op; // 操作 10 /* 11 void show() { // 用于调试 12 printf( "|%x %c\n", board>>16, op ); 13 printf( " %x \n", board& 0xffff ); 14 } 15 */ 16 }; 17 18 /** 19 * @fp 队头下标， @rp 队尾下标， 20 * @q 广搜得到的所有序列， @isVisited 标记某序列是否访问过， 21 */ 22 int fp = 0, rp = 1; 23 struct node q[QSIZE]; 24 bool isVisited[QSIZE] = { false }; 25 26 /** 27 initialize 遍历所有8!个状态 28 opa, opb, opc 三种操作 29 cantor 计算康托展开 30 isNew 判断是否是新的状态 31 print 输出 32 */ 33 void initialize(); 34 unsigned opa( unsigned brd ); 35 unsigned opb( unsigned brd ); 36 unsigned opc( unsigned brd ); 37 unsigned (*funcp[3])( unsigned ) = {opa, opb, opc}; // 函数指针，便于循环调用abc三种操作 38 int cantor( unsigned brd ); 39 int isNew( unsigned brd ); 40 void print( node& x, int limit ); 41 42 43 int main(){ 44 int n, i, temp; 45 unsigned int target = 0; 46 47 initialize(); 48 49 // 输入状态进行查找 50 while(scanf("%d", &n) && (n != -1)){ 51 target = 0; 52 for(i = 0; i < 8; ++i) { // 计算新状态对应16进制数 53 scanf("%d", &temp); 54 target <<= 4; 55 target |= temp; 56 } 57 58 for(i = 0; i < QSIZE; i++) // 在队列中查找 59 if(q[i].board == target) break; 60 61 print( q[i], n ); 62 } 63 64 return 0; 65 } 66 67 void initialize() { 68 q->board = 0x12348765; 69 q->op = 0; 70 q->pre = 65535; 71 isVisited[cantor(0x12348765)]=true; 72 fp = 0, rp = 1; 73 74 unsigned t; 75 while(fp != rp){ // 队列不可能满，所以 fp!=rp是可行的 76 // 对fp进行abc三种操作拓展，存入rp 77 for(int i = 0; i < 3; ++i){ 78 if(isNew(t = funcp[i](q[fp].board))) { 79 // q[rp-1].show(); 80 q[rp].board = t; 81 q[rp].op = ‘A‘+i ; 82 q[rp].pre = fp; 83 ++rp; 84 } 85 } 86 fp++; 87 } 88 // printf("----------%d\n", rp ); 89 // end 90 } 91 92 // 采用掩码进行ABC操作 93 unsigned opa( unsigned brd ){ 94 return (brd << 16) | (brd >> 16); 95 } 96 unsigned opb( unsigned brd ){ 97 unsigned a = (brd & 0x000f000f) << 12, b = (brd & 0xfff0fff0) >> 4; 98 return a | b; 99 }100 101 unsigned opc( unsigned brd ){102 unsigned a = (brd & 0x0f000000) >> 4,103 b = (brd & 0x00f00000) >> 16,104 c = (brd & 0x00000f00) << 16,105 d = (brd & 0x000000f0) << 4;106 107 brd &= 0xf00ff00f;108 brd |= a | b | c | d;109 return brd; 110 }111 112 int isNew( unsigned brd ){113 int hash = cantor(brd);114 if(isVisited[hash]) return 0;115 116 isVisited[hash] = true;117 return 1;118 }119 120 int cantor( unsigned brd ){121 int i, j, t;122 unsigned num=0, fac[8] = {0, 1, 2, 6, 24, 120, 720, 5040}, s[8];123 124 for(i = 0; i < 8; ++i ) s[i] = ( brd >> (4*i)) & 0xf;125 num = (s[0] - 1) * 5040;126 for(i = 1; i < 7; ++i) {127 t = 0;128 for (j = i + 1; j < 8; ++j)129 if(s[j] < s[i]) ++t;130 num += fac[7-i] * t;131 }132 return num;133 }134 135 void print(node& x, int limit) {136 int i, len = 0, str[23] = {x.op};137 for(i = x.pre; i != 65535; i = q[i].pre){138 str[++len] = q[i].op;139 }140 141 if(len > limit)142 printf("-1");143 else {144 printf("%d ", len);145 for(i = len - 1; i >= 0; i--)146 printf("%c", str[i] );147 }148 printf("\n");149 }
VI. 测试数据（5-10组有梯度的测试数据,要考虑边界条件）
测试数据及答案：
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
VII. 对时间复杂度，空间复杂度方面的分析、估算及程序优化的分析和改进
- 空间消耗：
因为状态数目40320，所以空间复杂度就是常数。
但是节点的体积是可以再减小的，节点无需存储所有操作，只需存储当前操作(1B)，还有父节点下标(2B).
每个节点只需 7个字节，由于存在字节对齐，所以每个节点会占用8字节。
总内存： 8*40320 + 312KB(运行时系统) = 634KB
采用这种方法，出乎意料的是 运行时间也减小了（0.01sec）。
整个搜索树是3叉的，对于第i层，要搜索3^i个节点（i从0开始）
通过判重来剪枝，可以显著减少搜索队列的长度。最后只留下 40320 个节点。
- 时间消耗：
采用位移的方法代替数组内部负值（如老师课堂所讲），可以减少时间开支；
状态节点使用一个char记录当前操作，一个int记录前一操作下表，代替用string记录到当前状态的所有操作以减小时空开支。
- 可能的优化方案：
640KB的空间消耗可以接受，考虑减小时间消耗。
最直观的考虑可以优化哈希函数cantor()。可以使用非康托展开的其他哈希函数来减少操作量，但考虑到可能有碰撞问题，有可能需要开一个较大的数组，加大空间消耗，但参考其他同学的成果，使用1000kb左右内存时，时间消耗可以降至0.00sec。
Sicily 1151 解题报告（魔板，广搜）