算法模拟

模拟-元胞自动机

字数统计: 3.5k字   |   阅读时长: 14分
, , ,

摘要: 本文介绍元胞自动机，并解决三个力扣上的问题。

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

元胞自动机是一类模拟中常见的算法，应用非常多，在力扣上也有一些相关的问题。本文我们就简单了解一下元胞自动机，最后我们解决 3 个元胞自动机的题目。主要内容如下：

  • 模拟算法
    • 构造，分类讨论，细节处理，找规律，公式推导
  • 元胞自动机理论
  • 题目
    • 生命游戏
    • 矩阵置零
    • 数组变换

模拟

模拟，是根据实际问题建立模型，模拟实际按程序走一遍，最终求出答案。

简单模拟的问题，直接按照题意编程即可，没有什么拐弯的地方。但是模拟经常会混进去其它内容，比如需要找规律和一些公式推导，需要选择合适的数据结构，需要分类讨论等等，以及要处理的细节问题有很多，综合起来难度就比较大了。

算法工程师经常会做一些复现论文的工作，复现论文也可以可以理解为模拟。

元胞自动机

元胞自动机是一种经典模型。主要用于模拟和分析几何空间内的各种现象。

元胞自动机暂时没有统一的定义，有几种各自领域里主流的定义：

  • 物理：定义在一个具有离散，有限状态的原包组成的元胞空间上，并按照一定局部规则在离散的时间维上演化的动力系统
  • 数学：
    • 基于集合论的定义
    • 基于拓扑学的定义
  • 计算机，生物也有自己的解释

元胞自动机有一些一般特征：

  • 同质性：元胞的分布方式，大小，形状相同
  • 齐性：每个元胞服从相同规则
  • 空间离散
  • 时间离散
  • 状态离散且有限
  • 同步计算(并行性)
  • 时空局部性
  • 维数高

基于动力学行为可以分为平稳型；周期型；混沌型；复杂型。

与元胞自动机相关的一些研究方向主要有微分方程，分形，Markov 过程，随机游走模型，凝聚扩散模型等。元胞自动机的应用涉及到社会学，数学，物理，化学，计算机，生态等。

元胞自动机更详细的理论，包括元胞自动机的定义，基本组成，特点和关于周期性平稳性的研究，可以参考下面这份资料：

题目

289. 生命游戏

生命游戏是著名的元胞自动机，其作者为约翰·何顿·康威，曾用数学理论设计多款游戏。

生命游戏的局部规则可以模拟生态学里种群的繁衍：

  1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
  2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
  3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
  4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

其中各个规则与生态现象的对应：

规则1：竞争(种群密度太大，资源争抢，个体被淘汰)
规则2：灭绝(种群密度太小，交配失败，个体被淘汰)
规则3：生存(种群密度合适，个体存活)
规则4：繁殖(种群密度合适，产生新个体)

生命游戏中，给定种群初始状态，无限发展下去可以有各种状态。

题目描述

根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

示例：
输入：
[
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0]
]
输出：
[
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0]
]

Follow Up：

  • 你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
  • 本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？

算法1：额外开辟数组

直接按照规则模拟的话有一个陷阱，就是如果直接在原数组更新状态的话，就做不到同步更新了，因为后续细胞的状态更新还要用到当前细胞的状态。因此需要复制一份原数组。

这里的复制一份原数组，有点类似双缓冲技术，输入缓冲区平分成两份，应对单词被缓冲区拦腰切断的情况。

代码(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
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int n = board.size(), m = board[0].size();
        vector<vector<int> > tmp(board.begin(), board.end());
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                int cnt = _check(tmp, i, j);
                if(cnt < 2 || cnt > 3)
                    board[i][j] = 0;
                if(cnt == 3)
                    board[i][j] = 1;
            }
    }

private:
    int _check(vector<vector<int> >& board, int i, int j)
    {
        int n = board.size(), m = board[0].size();
        int dx[8] = {0, 0, 1, 1, 1, -1, -1, -1};
        int dy[8] = {1, -1, -1, 0, 1, -1, 0, 1};
        int cnt = 0;
        for(int d = 0; d < 8; ++d)
        {
            int x = i + dx[d];
            int y = j + dy[d];
            if(x < 0 || x >= n || y < 0 || y >= m) continue;
            cnt += board[x][y];
        }
        return cnt;
    }
};

算法2：不开额外数组，利用位运算

因为输入状态是int，状态值只有0和1，高位都是没有用到的，可以在第二位保存更新后的状态。计算新状态的时候，只使用第一位；所有状态都更新完了，把状态值右移1位得到结果。

这里的处理可以理解为增大信息量的方式：原来一个位置只能存一个状态，处理之后可以存两个状态。

作为对比，后面提到的矩阵置零中为了使得额外空间为 $O(1)$，采用了对问题进行全局考虑（也就是一旦输入结果确定，我们就会知道输出结果）的方式，也可以用本题的方法：利用位运算增大信息量。

本题也可以利用对问题进行全局考虑的方式，但是全局考虑有点麻烦，没有增大信息量方便。

代码(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
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int n = board.size(), m = board[0].size();
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                int cnt = _check(board, i, j);
                if(cnt == 3)
                    board[i][j] |= (1 << 1);
                if(cnt == 2 && (board[i][j] & 1) == 1)
                    board[i][j] |= (1 << 1);
            }
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                board[i][j] >>= 1;
    }

private:
    int _check(vector<vector<int> >& board, int i, int j)
    {
        int n = board.size(), m = board[0].size();
        int dx[8] = {0, 0, 1, 1, 1, -1, -1, -1};
        int dy[8] = {1, -1, -1, 0, 1, -1, 0, 1};
        int cnt = 0;
        for(int d = 0; d < 8; ++d)
        {
            int x = i + dx[d];
            int y = j + dy[d];
            if(x < 0 || x >= n || y < 0 || y >= m) continue;
            cnt += board[x][y] & 1;
        }
        return cnt;
    }
};

算法3: 卷积

统计每一个位置 (i, j) 周围 1 的个数，类似于卷积个过程。

设定卷积核，把原数组做 padding 之后，直接用卷积的方式统计每个位置 1 的个数。

[
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]

但是卷积的方式也是要开额外数组保存结果的。此外这肯定不是卷积最好的实现方式，因此此法属于灵机一动抖机灵，不是正道。

代码(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
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        Mat kernel(3, vector<int>(3, 1));
        kernel[1][1] = 0;
        int n = board.size(), m = board[0].size();
        Mat input_padding(n + 2, vector<int>(m + 2, 0));
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                input_padding[i][j] = board[i - 1][j - 1];
        _conv2(input_padding, kernel, board);
    }

private:
    using Mat = vector<vector<int> >;

    void _conv2(const Mat& input, const Mat& kernel, Mat& output)
    {
        int n = input.size(), m = input[0].size();
        //计算卷积核的半径
        int kn = kernel.size(), km = kernel.size();
        int sub_x = kn / 2;
        int sub_y = km / 2;
        for(int j = 0; j < m - 2 * sub_y; ++j)
            for(int i = 0; i < n - 2 * sub_x; ++i)
            {
                int cnt = 0;
                for(int kernel_i = 0; kernel_i < kn; ++kernel_i)
                    for(int kernel_j = 0; kernel_j < km; ++kernel_j)
                    {
                        int weight = kernel[kernel_i][kernel_j];
                        int pixel = input[i + kernel_i][j + kernel_j];
                        cnt += weight * pixel;
                    }
                if(cnt == 3 && output[i][j] == 0)
                    output[i][j] = 1;
                if(cnt < 2 || cnt > 3)
                    output[i][j] = 0;
            }
    }
};

73. 矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

Follow Up:

  • 一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
  • 你能想出一个常数空间的解决方案吗？

算法：元胞自动机

按要求模拟即可。

1
2
3
4
step1: 遍历左边和上边这两条边，记录着两条边最终是否都要置零 flag_left, flag_up。
step2: 遍历矩阵，若 A[i][j] == 0 则 A[0][j] = 0, A[i][0] = 0
step3: 遍历左边和上边着两条边，将对应位置的零法向扩展
step4: 若 flag_left, flag_up，将对应边置零

代码(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
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if(matrix.empty()) return;
        int n = matrix.size(), m = matrix[0].size(); // n 行 m 列
        bool flag_left = false, flag_up = false;
        for(int i = 0; i < n; ++i)
            if(matrix[i][0] == 0)
            {
                flag_left = true;
                break;
            }
        for(int j = 0; j < m; ++j)
            if(matrix[0][j] == 0)
            {
                flag_up = true;
                break;
            }
        for(int i = 1; i < n; ++i)
            for(int j = 1; j < m; ++j)
            {
                if(matrix[i][j] == 0)
                {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        for(int i = 1; i < n; ++i)
            if(matrix[i][0] == 0)
                for(int j = 1; j < m; ++j)
                    matrix[i][j] = 0;
        for(int j = 1; j < m; ++j)
            if(matrix[0][j] == 0)
                for(int i = 1; i < n; ++i)
                    matrix[i][j] = 0;
        if(flag_left)
            for(int i = 0; i < n; ++i)
                matrix[i][0] = 0;
        if(flag_up)
            for(int j = 0; j < m; ++j)
                matrix[0][j] = 0;
    }
};

1243. 数组变换

首先，给你一个初始数组 arr。然后，每天你都要根据前一天的数组生成一个新的数组。

第 i 天所生成的数组，是由你对第 i-1 天的数组进行如下操作所得的：

假如一个元素小于它的左右邻居，那么该元素自增 1。
假如一个元素大于它的左右邻居，那么该元素自减 1。
首、尾元素 永不 改变。
过些时日，你会发现数组将会不再发生变化，请返回最终所得到的数组。

提示：

1
2
1 <= arr.length <= 100
1 <= arr[i] <= 100

示例 1：
输入：[6,2,3,4]
输出：[6,3,3,4]
解释：
第一天，数组从 [6,2,3,4] 变为 [6,3,3,4]。
无法再对该数组进行更多操作。

示例 2：
输入：[1,6,3,4,3,5]
输出：[1,4,4,4,4,5]
解释：
第一天，数组从 [1,6,3,4,3,5] 变为 [1,5,4,3,4,5]。
第二天，数组从 [1,5,4,3,4,5] 变为 [1,4,4,4,4,5]。
无法再对该数组进行更多操作。

算法：元胞自动机

按要求模拟即可，下面直接给出代码。其中每一轮的模拟逻辑在函数 transfer 中。

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
class Solution {
public:
    vector<int> transformArray(vector<int>& arr) {
        int n = arr.size();
        if(n < 3) return arr;
        vector<int> result(arr.begin(), arr.end());
        bool flag = false;
        while(!flag)
        {
            if(transfer(result))
                flag = true;
        }
        return result;
    }

private:
    bool transfer(vector<int>& arr)
    {
        int n = arr.size();
        bool flag = true;
        for(int i = 1; i < n - 1; ++i)
        {
            if(arr[i] > (arr[i - 1] & ((1 << 7) - 1)) && arr[i] > arr[i + 1])
            {
                arr[i] |= ((arr[i] - 1) << 7);
                flag = false;
            }
            else if(arr[i] < (arr[i - 1] & ((1 << 7) - 1)) && arr[i] < arr[i + 1])
            {
                arr[i] |= ((arr[i] + 1) << 7);
                flag = false;
            }
        }
        if(!flag)
            for(int i = 1; i < n - 1; ++i)
                if((arr[i] >> 7) != 0)
                    arr[i] >>= 7;
        return flag;
    }
};
Share