ZOJ 2477 Magic Cube IDA*

缘起

本题来研究IDA* 这种搜索算法。 ZOJ 2477 Magic Cube

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
给你一个魔方，让你在五步之内还原这个魔方，这个魔方只能让每个面进行顺时针或者逆时针操作，问能否在五步内解
决战斗，如果可以，请输出每一步转动的面，以及是逆时针还是顺时针。

【输入】
第一行是样例数, 后面每个样例就是一个魔方. 

【输出】
输出最少步数. 并且输出任何一种可行的方案，如果5步之内解决不了, 输出-1

【样例输入】
2
      w w w
      w w w
      w w w
r r r g g g b b b o o o
r r r g g g b b b o o o
r r r g g g b b b o o o
      y y y
      y y y
      y y y

      w w w
      w w w
      b b b
r r w g g g y b b o o o
r r w g g g y b b o o o
r r w g g g y b b o o o
      r r r
      y y y
      y y y
      
【样例输出】
0
1
1 1

【限制】
2s

其实我最讨厌的就是这种打表问题.

首先我们来学习一下 IDA* 这种搜索算法. 【1】中我们展示了如何使用得到的一组解作为剪枝条件来进行剪枝的dfs（即如果节点的下界(=当前真实代价+启发式函数, 这里启发式函数必须满足<=真实走完剩余路代价)>=已经得到的一组解,则该节点被剪枝掉）. 即使用搜索的节点的下界来优（剪）化（枝）dfs. 但是我们发现——在没有得到一组解的时候，我们的dfs是相当盲目的——即会去搜索很多无用的状态. 那么怎么优化它呢? 我们可以人为的假设一个界x, 即我们转换为考虑求<=x的解. x从0开始每次+1, 如果没找到, 则继续提高x(变成x+1), 直至找到解为止. 则第一个使得存在<=x的解的x就是答案（当然，前提是求最少，例如本题）

这种人为引入一个不断增加的界来优化dfs的算法就叫做IDA* 算法. IDA*算法的优势是内存耗费较少.

而且IDA* 中的启发式函数必须<=真实走完剩余路的代价函数.

回到本题，就是一个典型的IDA* 的应用场景. 其实就是求最少步数能还原魔方. 而启发式函数呢?

注意到旋转一个面将导致20个面的置换（4个角块的三个面和4个棱块的2个面, 一共 4*3+4*2=20）

即会引发一个长度为20的数组A变动到另一个长度为20的数组B去. 而旋转一共12种——每个面不是顺时针就是逆时针. 而且顺时针和逆时针就是A和B之间的互换. 所以我们需要准备12个长度为20的数组（一个面的两种旋转分别对应A和B的互换, 即一个面需要准备2个数组, 一共2*6=12个长度为20的数组.）

那么对于一种状态，我们如何给出启发式函数呢? 注意6个面的中心块是不会变化的. 所以只需要计算6个面所有和中心面颜色不一样的面的总数. 然后除以12即可——因为一次旋转你最多改变12个面的位置, 我们假设理想情况发生——即12个色块全部归位.

最后一个问题——如何判定魔方已经还原了呢? 很简单，就是启发式函数为0——没有和其中心色块不同色的色块.

1
2
3
4
5
6
7
8
9
10
本题给每个位置标号如下
          1  2  3
          4  5  6
          7  8  9
 10 11 12 13 14 15 16 17 18 19 20 21
 22 23 24 25 26 27 28 29 30 31 32 33
 34 35 36 37 38 39 40 41 42 43 44 45
          46 47 48
          49 50 51
          52 53 54

则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <math.h>
//#define LOCAL
char color[60]; // 54个面的颜色, cp用于还原现场用的
int face[6][9] = {{1, 2, 3, 4, 5, 6, 7, 8, 9},{10, 11, 12, 22, 23, 24, 34, 35, 36}, {13, 14, 15, 25, 26, 27, 37, 38, 39}, {16, 17, 18, 28, 29, 30, 40, 41, 42},{19, 20, 21, 31, 32, 33, 43, 44, 45}, {46, 47, 48, 49, 50, 51, 52, 53, 54}}; // 6个面
int center[6] = {5, 23, 26, 29, 32, 50}; // 6个中心面块
int depth, ans[10],dir[10]; // IDA*中搜索的深度,ans是旋转的面,dir是旋转的方向
int change[ 12 ][ 20 ] = { // 这就是我讨厌打表题的原因~ 0和1行表示旋转0面(即第0行变到第1行(逆时针-1)或者反过来(顺时针1)对应0面的两种旋转), 2和3行表示旋转1面, 4和5行表示旋转2面, 6和7表示旋转3面, 8和9表示旋转4面, 10和11行表示旋转5面
	{12, 24, 36, 35, 34, 22, 10, 11, 13, 25, 37, 46, 49, 52, 45, 33, 21, 1, 4, 7},
	{10, 11, 12, 24, 36, 35, 34, 22, 1, 4, 7, 13, 25, 37, 46, 49, 52, 45, 33, 21},
	{15, 27, 39, 38, 37, 25, 13, 14, 16, 28, 40, 48, 47, 46, 36, 24, 12, 7, 8, 9},
	{13, 14, 15, 27, 39, 38, 37, 25, 7, 8, 9, 16, 28, 40, 48, 47, 46, 36, 24, 12},
	{18, 30, 42, 41, 40, 28, 16, 17, 19, 31, 43, 54, 51, 48, 39, 27, 15, 9, 6, 3},
	{16, 17, 18, 30, 42, 41, 40, 28, 9, 6, 3, 19, 31, 43, 54, 51, 48, 39, 27, 15},
	{21, 33, 45, 44, 43, 31, 19, 20, 3, 2, 1, 10, 22, 34, 52, 53, 54, 42, 30, 18},
	{19, 20, 21, 33, 45, 44, 43, 31, 42, 30, 18, 3, 2, 1, 10, 22, 34, 52, 53, 54},
	{3, 6, 9, 8, 7, 4, 1, 2, 18, 17, 16, 15, 14, 13, 12, 11, 10, 21, 20, 19},
	{1, 2, 3, 6, 9, 8, 7, 4, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10},
	{48, 51, 54, 53, 52, 49, 46, 47, 40, 41, 42, 43, 44, 45, 34, 35, 36, 37, 38, 39},
	{46, 47, 48, 51, 54, 53, 52, 49, 37, 38, 39, 40, 41, 42, 43, 44, 45, 34, 35, 36}};

void read()
{
	int num = 1;
	while(num<=54)
	{
		char c = getchar();
		if (c==' '||c=='\n')
		{
			continue;
		}
		color[num++] = c;
	}
}

int h() // 启发式函数
{
	int ans = 0;
	for (int i = 0; i<6; i++)
	{
		for (int j = 0; j<9; j++) // center[i]为中心的面
		{
			if (color[face[i][j]]!=color[center[i]])
			{
				ans++;
			}
		}
	}
	return ans; // 得到所有面上和中心色块不同色的面的个数
}

bool ida(int cur) // 当前决定ans[cur]、dir[cur], 迄今已经旋转了step步(不包括本步骤)
{
	int hh = h();
	if (!hh) // 如果已经到达终点
	{
		printf("%d\n", cur);
		for (int i = 0;i<cur; i++)
		{
			printf("%d %d\n", ans[i], dir[i]);
		}
		return true;
	}
	if (cur+ceil(hh/12.0)>depth) // 用人为设定的界进行剪枝! 这就是IDA*算法的核心思想! 注意, 和使用真实存在的可行解剪枝不一样, IDA*剪枝不能用>=而要用> 因为depth是人为设定的界, 都不知道有没有解能达到它, 所以不能>=, 而用真实可行解构造界进行剪枝就可以使用>=,因为我们知道这个界是有解对应的, >=这个界, 就肯定至少不是唯一最优的, 所以可以剪枝掉的, 但是IDA*就不能去掉.
	{ // 注意, 这里使用ceil, 因为hh<12,比如hh=7(7个和中心色块颜色不同的),则你至少要旋转一次吧? 
		return false;
	}
	for (int i = 0; i<12; i++) // 12种旋转
	{
		char cp[60]; // 注意, 这个不能作为全局变量~ 不然的话, 会被后面的递归改的乱七八糟的! WA到吐~
		memcpy(cp, color, sizeof(color)); // 保护现场
		for (int j = 0; j<20; j++)
		{
			color[change[i^1][j]] = cp[change[i][j]]; // 异或运算可以很方便的表示相邻两行. 0变到1,1变到0, 2变到3, 3变到2, 注意,这里不要在原color上操作, 即等式右边的cp不要换成color,会乱的
		}
		ans[cur] = i/2; // 表示旋转哪个面
		dir[cur] = i&1?1:-1; // i是偶数, 则表示逆时针,i是奇数则顺时针旋转
		if (ida(cur+1))
		{
			return true; // 因为目的只是找一组解, 所以找到了就不玩了
		}
		memcpy(color, cp, sizeof(color)); // 如果没有成功的话, 是需要还原现场的
	}
	return false; // 12种旋转都不行
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		read();
		if (!h())
		{
			puts("0");
			continue;
		}
		depth = 1;
		while(depth<=5)
		{
			if (ida(0))
			{
				break;
			}
			depth++; // 加深搜索
		}
		if (depth>5)
		{
			puts("-1");
		}
	}
	return 0;
}

ac情况

1
2
Name	Result		Time(ms)	Memory(KB)
0		Accepted	3			288

最后强调一次

IDA*算法的核心思想是——没有可行解搞出的界, 我们就人为指定一个, 用这个界来进行剪枝!

注意， IDA* 和A* 其实分别就是dfs和bfs利用下界进行的剪枝优化. IDA* 延续了dfs的优点——不怎么花费内存. 而A* 花费的内存可能是关于搜索空间线性增长的内存空间. 但是IDA*的缺点也很明显——如果一个节点可以通过不同路径到达的话，IDA*算法可能重复多次经过某些状态而效率一落千丈，但是A* 通过选取合适的启发式函数可以使得节点只被经过一次（所以一般要开一个哈希数组来防止节点重新进堆）。

但其实在一次IDA* (即某一深度)中，你是可以对状态进行哈希（就像dfs做全排列）的. 只是一般在题目中不这么做而已(会略微提高编码的复杂度). 但是在不同深度的两次IDA*搜索中，是不能用哈希判重的. 所以这里说的IDA* 会重复经过状态指的是不同深度的两次IDA* 搜索, 而不是同一次IDA* 搜索. 同一次IDA* 搜索中你想判重的话, 还是可以开一个book数组做到的.

通常来讲，随着搜索深度的加深，搜索空间的大小呈几何级数增长. 所以虽然IDA*在不断增加递归深度的过程中重复搜索了很多状态，但是总的访问状态数量和最后（即最深，即找到x这个解）一次访问的状态数在一个数量级上.

正因为这个原因，所以IDA* 找x的时候是增加x，每次+1, 而不是使用二分查找（二分查找的话，你搜最大深度就让复杂度到顶了~ 所以IDA* 不能用二分查找最小的x）.

而且为什么名字中也有一个A*? 因为该算法里面也用到了启发式函数. 和宽度类型的A*是一样的. 所以名字中也有一个A*

参考

【1】https://yfsyfs.github.io/2019/09/17/poj-1084-Square-Destroyer-%E6%90%9C%E7%B4%A2%E5%89%AA%E6%9E%9D/