leetcode 913. 猫和老鼠 极大极小搜索+alphabeta剪枝

缘起

继续研究极大极小搜索, 这道题目是leetcode上极大极小搜索的困难tag的题目. leetcode 913. 猫和老鼠

这题确实比较难~

分析

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
两个玩家分别扮演猫（Cat）和老鼠（Mouse）在无向图上进行游戏，他们轮流行动。

该图按下述规则给出：graph[a] 是所有结点 b 的列表，使得 ab 是图的一条边。

老鼠从结点 1 开始并率先出发，猫从结点 2 开始且随后出发，在结点 0 处有一个洞。

在每个玩家的回合中，他们必须沿着与他们所在位置相吻合的图的一条边移动。例如，如果老鼠位于结点 1，那么它
只能移动到 graph[1] 中的（任何）结点去。

此外，猫无法移动到洞（结点 0）里。

然后，游戏在出现以下三种情形之一时结束：

如果猫和老鼠占据相同的结点，猫获胜。
如果老鼠躲入洞里，老鼠获胜。
如果某一位置重复出现（即，玩家们的位置和移动顺序都与上一个回合相同），游戏平局。
给定 graph，并假设两个玩家都以最佳状态参与游戏，如果老鼠获胜，则返回 1；如果猫获胜，则返回 2；如果平
局，则返回 0。

 

示例：

输入：[[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
输出：0
解释：
4---3---1
|   |
2---5
 \ /
  0
 

提示：

3 <= graph.length <= 200
保证 graph[1] 非空。
保证 graph[2] 包含非零元素。

题目就是用邻接链表法表示了一张无向图. 然后猫从2出发, 老鼠从1出发. 两者都是理智的. 要问最后谁能获胜. 一旦题目中出现”最佳状态”、”理智的” 这种字眼, 那就是极大极小算法+alphabeta剪枝.

显然, 本题不需要设置固定深度. 直接到底. 状态的话, 使用x表示老鼠的位置, y表示猫的位置即可.

然后开始套用【1】中的极大极小模板.

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
class Solution {
typedef vector<int>::iterator vit;
public:
	int catMouseGame(vector<vector<int>>& graph) 
	{
		memset(v, 0, sizeof(v));
		g = graph;
		switch(alphabeta(1,2,-1,1,true))
		{
		case -1: // 猫获胜
			return 2;
		case 0: // 平局
			return 0;
		case 1: // 老鼠获胜
			return 1;
		}
		return 0;
	}

	int alphabeta(int x, int y, int alpha, int beta, bool player) // x是老鼠的位置, y是猫的位置
	{
		if (!x) // 老鼠进洞, 老鼠胜
		{
			return 1;
		}
		else if (x==y) // 猫抓到老鼠, 猫胜
		{
			return -1;
		}
		else if (v[x][y]) // 故地重游, 平局
		{
			return 0;
		}
		v[x][y] = true;
		if (player) // 老鼠走
		{
			for (vit i = g[x].begin(); i!=g[x].end(); i++) // 遍历状态进行开拓
			{
				alpha = max(alpha, alphabeta(*i, y, alpha, beta, false));
				if (alpha>=beta) // beta剪枝
				{
					break;
				}
			}
			v[x][y] = false; // dfs搜索改回来
			return alpha;
		}
		else // 猫走
		{
			for (vit i = g[y].begin(); i!=g[y].end(); i++)
			{
				if (!(*i)) // 猫不能进洞
				{
					continue;
				}
				beta = min(beta, alphabeta(x, *i, alpha, beta, true));
				if (alpha>=beta) // alpha剪枝
				{
					break;
				}
			}
			v[x][y] = false; // dfs搜索改回来
			return beta;
		}
	}

	bool v[205][205]; // 用于哈希猫和老鼠的位置, 如果g[x][y]=true, 则表明猫和老鼠曾经处于过这个状态
	vector<vector<int>> g; // 无向图
};

但是比较遗憾，上面的极大极小+alphabeta剪枝代码被T掉了. 其实也不难想象——因为图的节点可能到达200. 而本题又不能设置启发式评价函数（因为要求最优而不是近似解）. 所以即便有alphabeta剪枝也可能出现暴搜200层深度的局面. 导致算法超时. 事实上, leetcode反映过来的超时的数据仅仅也只有31个节点. 但是我相信, 上面的算法并不是因为死循环导致超时的. 仅仅是因为算法搜索的深度太大导致的.

也就是, 正向搜索太多的节点了

那么怎么解决呢? 我耻辱的看了题解（【2】）. 题解的思路是这样的. 要倒过来搜索.

首先如何刻画一个局面? 显然用三元组 (x,y,0或者1)就可以刻画当前局面了. 其中x代表老鼠的位置, y代表猫的位置. 0代表当前轮到老鼠走,1 代表当前轮到猫走（即从当前局面向下一个局面演进时是谁走）.

显然, 猫的必胜局面是 (i,i,0) 或者 (i,i,1), 其中i不等于0

老鼠的必胜局面是(0,i,0)或者(0,i,1), 其中i不等于0

然后我们的思路是从必胜局面倒推. 倒推的过程使用bfs来描述. 而队列中仅仅保存必胜局面，而不会保存僵持局面. 开拓节点是简单的——队首首先出队，然后当前走的玩家（猫或者老鼠）按照无向图的边（猫不能到0）来开拓子局面. 但是因为队列中仅仅能维护必胜局面, 所以我们自然要问这个开拓出来的子局面是不是必胜局面?

这得分情况

  1. 如果父节点（即出队的队首）是老鼠的必胜局面.

    1.1 如果子局面是老鼠走. 则子局面也是老鼠的必胜局面. 则此子局面应该入队.

    1.2 如果子局面是猫走, 则子局面就未必是老鼠的必胜局面了. 因为猫又不傻, 猫肯定不会往老鼠的必胜局面（即当前出队的节点）走啊~ 但是如果该子局面的所有父亲都是老鼠的必胜局面的话（显然, 能够到达该子局面的父局面可能不止一个）, 那么当前局面就是老鼠的必胜局面. 则我们就应该将此子局面入队.

  2. 如果父节点是猫的必胜局面.

    2.1 如果子局面是猫走, 则子局面也是猫的必胜局面. 则此子局面也应该入队.

    2.2 如果子局面是老鼠走, 则子局面就未必是猫的必胜局面了. 因为老鼠又不傻, 老鼠肯定不会往猫的必胜局面（即当前出队的节点）走啊~ 但是如果该子局面的所有父亲都是猫的必胜局面的话（显然, 能够到达该子局面的父局面可能不止一个）, 那么当前局面就是猫的必胜局面. 则我们就应该将此子局面入队.

根据上面的算法描述，我们知道了队列中的节点不仅要有三元组（这方便扩展（未必是必胜局面的）子节点），而且队列节点还要有一个属性刻画当前局面到底是谁的必胜局. 其次, 为了方便最后查询答案, 我们还必须要维护一张表 ans[205][205][2] , 其中 ans[i][j][k]=x 表示局面(i,j,k)是x的必胜局, 在有节点入队的时候（不论是初始化队列还是开拓节点入队）, 要维护一下这张表.

然后, 我们如何描述”如果该子局面的所有父亲都是老鼠的必胜局面的话” 这种事情呢? 显然, 就要用到入度这一图论概念——因为我们不就是想知道有多少个父局面可以抵达子局面吗? 所以我们要维护一张表 indeg[205][205][2]

其中 indeg[i][j][k] = x 表示局面 (i,j,k)的 入度是x——即有x个局面能到达(i,j,k)

注意, 严格来讲, 本题存在圈——即完全可能从一个局面出发最后又回到自己. 例如样例数据就是这样——

老鼠从1到3, 猫从2到5,

然后老鼠从3到4, 猫从5到2,

老鼠从4到3, 猫又从2到5,

然后老鼠从3到4，猫从5到2

….

即来来回回振荡. 其实你知道的, 如果一旦进入了这种局面, 就是僵局. 我想表达的是, 本题bfs的数据结构其实并不是一棵树. 而是一个图. 说了这么多, 写代码了

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
class Solution {
typedef vector<int>::iterator vit;
public:
	struct Node // 队列中的必胜局面的数据结构.
	{
		int i, j, turn; // 老鼠位于i, 猫位于j, turn=0表示当前轮到老鼠走, turn=1表示当前轮到猫走
		Node(int i, int j, int turn):i(i),j(j), turn(turn){}
	};

	int catMouseGame(vector<vector<int>>& graph) 
	{
		g = graph;
		n = graph.size();
		while(!q.empty())
		{
			q.pop();
		}
		memset(ans, 0, sizeof(ans));
		memset(indeg, 0, sizeof(indeg));
		bfs(); // 第一遍bfs初始化indeg以及ans, 注意, 这一次bfs 队列中并不是仅仅有必胜节点的
		bbfs(); // 第二遍bfs, 这次bfs仅仅允许必胜节点入队
		return ans[1][2][0]; // (1,2,0)是最初的局面
	}

	int n, ans[205][205][2], indeg[205][205][2]; // ans维护答案, indeg维护入度, ans取值为0表示僵局, 1表示老鼠必胜, 2表示猫必胜, n是顶点的个数
	queue<Node> q; // 局面队列
	vector<vector<int>> g;

	void bfs()
	{
		for (int i = 0;i<n; i++)
		{
			if (i)
			{
				q.push(Node(i,i,0));
				q.push(Node(i,i,1));
				q.push(Node(0,i,0));
				q.push(Node(0,i,1));
				ans[i][i][0] = ans[i][i][1] = 2; // 猫必胜局面
				ans[0][i][0] = ans[0][i][1] = 1; // 老鼠必胜局面
				indeg[i][i][0] = indeg[i][i][1] = 1; // 只是为了防止再次进队
			} // 推入必胜局面, 它们是bfs的出发点
		}
		while(!q.empty())
		{
			Node front = q.front(); // 从front开始拓展节点
			q.pop();
			for (vit i = g[front.turn?front.i:front.j].begin(); i!=g[front.turn?front.i:front.j].end(); i++) // front局面是猫走的话(即front.turn=1), 则上一次移动的就是老鼠
			{
				if (front.turn) // front是猫走, 所以上一步, 即子局面是老鼠走, 所以上一步老鼠处于*i, 即子局面是 (*i, front.j, 0)
				{
					if (!(indeg[*i][front.j][0]++)) // 如果此节点尚未被访问过
					{
						q.push(Node(*i,front.j,0));
					}
				}
				else // front是老鼠走, 所以上一步, 即子局面是猫走, 所以上一步猫处于*i, 即子局面是 (front.i, *i, 1)
				{
					if (!*i) // 猫不能来自于洞
					{
						continue;
					}
					if (!(indeg[front.i][*i][1]++))
					{
						q.push(Node(front.i,*i,1));
					}
				}
			}
		}
	}

	void bbfs()
	{
		for (int i = 0;i<n; i++)
		{
			if (i)
			{
				q.push(Node(i,i,0));
				q.push(Node(i,i,1));
				q.push(Node(0,i,0));
				q.push(Node(0,i,1));
			} // 推入必胜局面, 它们是bfs的出发点
		}
		while(!q.empty())
		{
			Node front = q.front();
			q.pop();
			for (vit i = g[front.turn?front.i:front.j].begin(); i!=g[front.turn?front.i:front.j].end(); i++) // front是老鼠走(即front.turn=0), 则子节点就是猫走, front是猫走(即front.turn=1),则子节点就是老鼠走
			{
				if (ans[front.i][front.j][front.turn] == 1) // 如果父局面是老鼠的必胜局面
				{
					if (front.turn) // 子节点是老鼠走, 子节点是 (*i, front.j, 0) 也是老鼠的必胜局面
					{
						if (!ans[*i][front.j][0]) // 注意, 已经有ans的不能再改变了,下同
						{
							ans[*i][front.j][0] = 1;
							q.push(Node(*i, front.j, 0)); // 进入必胜局面队列q
						}
					}
					else // 子节点是猫走, 子节点是 (front.i, *i, 1)
					{
						if (!*i) // 猫不能进洞
						{
							continue;
						}
						if (!ans[front.i][*i][1] && !--indeg[front.i][*i][1]) // 入度自减, 如果减少到0, 表明（front.i, *i, 1）这个子局面的所有父节点都是老鼠必胜的局面,则即便该子局面是猫走, 也是老鼠必胜的局面
						{
							ans[front.i][*i][1] = 1;
							q.push(Node(front.i, *i, 1)); // 进入必胜局面队列q
						}
					}
				}
				else // 如果父局面是猫的必胜局面, 注意, 在第二遍bfs过程中, 队列中仅仅保存必胜局面, 所以ans[front.i][front.j][front.turn]不是1就是2, 不可能是0
				{
					if (front.turn) // 子节点是老鼠走, 子节点是 (*i, front.j, 0)
					{
						if (!ans[*i][front.j][0] && !--indeg[*i][front.j][0]) // 入度自减, 如果减少到0, 表明（*i, front.j, 0）这个子局面的所有父节点都是猫必胜的局面,则即便该子局面是老鼠走, 也是猫必胜的局面
						{
							ans[*i][front.j][0] = 2;
							q.push(Node(*i, front.j, 0)); // 进入必胜局面队列q
						}
					}
					else // 子节点是猫走, 子节点是 (front.i, *i, 1)
					{
						if (!*i) // 猫不能进洞
						{
							continue;
						}
						if (!ans[front.i][*i][1])
						{
							ans[front.i][*i][1] = 2;
							q.push(Node(front.i, *i, 1)); // 进入必胜局面队列q
						}
					}
				}
			}
		}
	}
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
52 ms
, 在所有 cpp 提交中击败了
93.02%
的用户
内存消耗 :
12.1 MB
, 在所有 cpp 提交中击败了
57.14%
的用户

这题做出来感觉挺不容易的~ 自己就看了思想, 没看【2】的实现代码, 也懒得看~

有的时候, 如果正向搜索状态太多的话, 可以考虑反向搜索. 节点就未必那么多了.

参考

【1】https://yfsyfs.github.io/2019/10/17/%E6%9E%81%E5%A4%A7%E6%9E%81%E5%B0%8F%E6%90%9C%E7%B4%A2%E4%BB%A5%E5%8F%8Aalphabeta%E5%89%AA%E6%9E%9D%E4%BC%98%E5%8C%96/

【2】https://blog.csdn.net/weixin_42102584/article/details/83314944