【搜索难题】力扣913-猫和老鼠

  |  

摘要: 本文详细拆解 leetcode 913-猫和老鼠,主要涉及对抗搜索与minimax、记忆化搜索、染色 BFS 等算法。

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


今天分享一个对抗搜索的问题。对抗搜索这种算法经常用于游戏等博弈场景中,非常具有应用价值。比如网上常见的,双方明手牌的斗地主残局谁能赢这种问题,如果会写对抗搜索的话,就可以终结讨论了。不过一般情况下这种题的代码过长,基本不会考虑在面试中问。

题目是 leetcode 913 猫和老鼠。有两种方法可以解决,一种是基于 DFS,需要记忆化,另一种是基于 BFS 的,但是需要增加染色。涉及到的算法要点如下:


$1 题目

913. 猫和老鼠

两个玩家分别扮演猫(Cat)和老鼠(Mouse)在无向图上进行游戏,他们轮流行动。

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

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

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

此外,猫无法移动到洞(结点 0)里。

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

  • 如果猫和老鼠占据相同的结点,猫获胜。
  • 如果老鼠躲入洞里,老鼠获胜。
  • 如果某一位置重复出现(即,玩家们的位置和移动顺序都与上一个回合相同),游戏平局。

给定 graph,并假设两个玩家都以最佳状态参与游戏,如果老鼠获胜,则返回 1;如果猫获胜,则返回 2;如果平局,则返回 0。

提示:

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

示例:

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


$2 题解

算法1: minimax + 记忆化搜索

Minimax 算法常用于棋类等由两方较量的游戏。该算法是一个零总和算法,即一方要在可选的选项中选择将其优势最大化的选择,另一方则选择令对手优势最小化的选择。参考 minimax

它是很多博弈型动态规划的基础: 参考 博弈DP

1
2
dp[m][c][t] := t 时刻,老鼠位于m, 猫位于c的结果。
(染色BFS的做法是把 (m, c, t%2) 作为状态,dp[m][c][t%2] 的值作为颜色,一起放入BFS队列中维护)
1
2
3
4
如果当前轮到老鼠行动,可以到dp[i][c][t+1],其中 i 属于 graph[m],若这些 dp[i][c][t+1] 的结果都为2,则老鼠输了,若其中有一个是1,则老鼠赢,否则平局。
如果当前轮到猫行动,可以到dp[m][j][t+1],其中 j 属于 graph[c],若这些 dp[m][j][t+1] 的结果都为1,则猫输了,若其中有一个是2,则猫赢,否则平局。
初始化:dp[0][c][t] = 1, dp[m][m][t] = 2
若t=2n时游戏仍未结束,则平局。(需要证明)

记忆化搜索的接口

1
int solve(const vector<vector<int>>& graph, int t, int x, int y, vector<vector<vector<int> > >& dp)

代码(C++)

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
class Solution {
public:
int catMouseGame(vector<vector<int>>& graph) {
int n = graph.size();
vector<vector<vector<int> > > dp(2 * n, vector<vector<int>>(n, vector<int>(n, -1)));
return solve(graph, 0, 1, 2, dp);
}

private:
int solve(const vector<vector<int>>& graph, int t, int m, int c, vector<vector<vector<int> > >& dp)
{
if (t == (int)graph.size() * 2)
return 0;
if (m == c)
return dp[t][m][c] = 2;
if (m == 0)
return dp[t][m][c] = 1;
if (dp[t][m][c] != -1)
return dp[t][m][c];


bool flag;
if (t % 2 == 0)
{
// 轮到鼠走
flag = true;
for (int i = 0; i < (int)graph[m].size(); i++)
{
int nxt = solve(graph, t + 1, graph[m][i], c, dp);
if (nxt == 1)
return dp[t][m][c] = 1;
else if (nxt != 2)
flag = false;
}
if (flag)
return dp[t][m][c] = 2;
else
return dp[t][m][c] = 0;
}
else
{
// 轮到猫走
flag = true;
for (int i = 0; i < (int)graph[c].size(); i++)
if (graph[c][i] != 0) {
int nxt = solve(graph, t + 1, m, graph[c][i], dp);
if (nxt == 2)
return dp[t][m][c] = 2;
else if (nxt != 1)
flag = false;
}
if (flag)
return dp[t][m][c] = 1;
else
return dp[t][m][c] = 0;
}
}
};

算法: minimax + 染色BFS

状态表示:

1
2
3
m : 老鼠位置
c : 猫的位置
t : 轮到谁动,t=0 老鼠动,t=1 猫动
  • 状态的集合:有向图的节点;
  • 当前的可选方案(状态的可能的转移方向):有向边

对状态染色:每个节点有三种颜色:

1
2
3
CAT=2: 猫赢
MOUSE=1: 鼠赢
DRAW=0: 胜负未知

minimax 的思想

  • 老鼠尽量移动到染成 MOUSE 颜色的节点,其次是移动到 DRAW 颜色的节点
  • 猫尽量移动到染成 CAT 颜色的节点,其次是 DRAW 点,最后才是 MOUSE 节点。

初始时有一些状态对应的节点胜负已定(已经确定颜色):m=0(鼠在洞里) 时鼠胜,m=c(鼠和猫同位置)时猫胜。

状态转移方向: 对于每个节点 (m, c, t):

(1) t=0 时(老鼠动)

  • 若存在一个子节点被标记为MOUSE颜色,则该点也标记为MOUSE颜色
  • 若所有的子节点都标记为CAT颜色,则该点也标记为CAT颜色

(2) t=1时(猫动)

  • 若存在一个子节点被标记为CAT颜色,则该点也标记为CAT颜色
  • 若所有的子节点都标记为MOUSE颜色,则该点也标记为MOUSE颜色

BFS过程

将所有初始时胜负已知的节点入队。

对于队中弹出的每个节点,考察其父节点:对满足条件的,立即染色,若不满足条件,尽量减少标为 DRAW 的子节点个数,直至标为 DRAW 的子节点个数为0,再染色。所有染色的点,在染色后立即进队。

队列里存放的内容:({m, c, t, color})

代码(C++)

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
class Solution {
public:
int catMouseGame(vector<vector<int> >& graph) {
int N = graph.size();
const int DRAW = 0, MOUSE = 1, CAT = 2;

vector<vector<vector<int> > > color(N, vector<vector<int> >(N, vector<int>(3)));
vector<vector<vector<int> > > draw_degree(N, vector<vector<int> >(N, vector<int>(3))); // 标记为 DRAW 的子节点个数

// draw_degree[node] := 节点的子节点个数
for(int m = 0; m < N; ++m)
for(int c = 0; c < N; ++c)
{
draw_degree[m][c][1] = graph[m].size(); // t = 0, 轮鼠动
draw_degree[m][c][2] = graph[c].size(); // t = 1, 轮猫动
for(int x: graph[c])
{
if(x == 0) // 猫无法移动到洞里
{
draw_degree[m][c][2]--;
break;
}
}
}

// 将初始时胜负已知的点染色,并进队
queue<vector<int> > q;
for(int i = 0; i < N; ++i)
for(int t = 1; t <= 2; ++t)
{
color[0][i][t] = MOUSE;
q.push(vector<int>({0, i, t, MOUSE}));
if(i > 0)
{
color[i][i][t] = CAT;
q.push(vector<int>({i, i, t, CAT}));
}
}

// BFS过程
while(!q.empty())
{
vector<int> node = q.front();
q.pop();
int i = node[0], j = node[1], t = node[2], c = node[3]; // c 颜色
for(vector<int> parent: _parents(graph, i, j, t))
{
int i2 = parent[0], j2 = parent[1], t2 = parent[2];
if(color[i2][j2][t2] == DRAW)
{
if(t2 == c)
{
// 父状态节点可以做必胜移动:
// 出队状态颜色是猫胜且父节点轮猫走
// 出队状态颜色是鼠胜且父节点轮鼠走
color[i2][j2][t2] = c;
q.push(vector<int>({i2, j2, t2, c}));
}
else // 当前轮到行动的角色与出队节点的颜色相反
{
draw_degree[i2][j2][t2]--; // 该父节点又有了一个子节点(出队节点v)不标记为 DRAW
if(draw_degree[i2][j2][t2] == 0)
{
color[i2][j2][t2] = 3 - t2;
q.push(vector<int>({i2, j2, t2, 3 - t2}));
}
}
}
}
}
return color[1][2][1];
}

private:
// 哪些状态节点可以转移到 (m, n, t)
vector<vector<int> > _parents(vector<vector<int> >& graph, int m, int c, int t)
{
vector<vector<int> > result;
if(t == 2) // 轮猫动, 上一轮轮猫动
{
for(int m2: graph[m])
result.push_back(vector<int>({m2, c, 3 - t}));
}
else // 轮鼠动,上一轮轮猫动
{
for(int c2: graph[c])
if(c2 > 0)
result.push_back(vector<int>({m, c2, 3 - t}));
}
return result;
}
};

Share