算法leetcode

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

字数统计: 2.3k字   |   阅读时长: 10分
, , ,

摘要: 本文详细拆解 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