一维生命游戏的非迭代算法

Question

考虑一个布尔数组 a[n]，其中每个元素都是一个单元格。如果一个且只有一个相邻的细胞是活的，则在下一代中一个细胞变为活的（设置为true），否则它变为死的（设置为false）。第一个和最后一个单元格被认为是邻居。

给定a[n]、数组大小n和一个正整数t，我想计算第t代进化后的a[n]，但是没有在 t 上使用任何迭代算法，这可能非常大。

我观察到的情况：如果我们将 S_k(a[n]) 定义为 循环移位 a[n] 向右移动 k 个元素。也就是说，如果0 <= k < n，a[0]在一班后变成a[k]。将 a[n] ^ b[n] 定义为两个布尔数组之间的逐元素异或运算。如果w[n]是布尔数组，则下一代可以用

表示

r(w[n]) = S_{-1}(w[n]) ^ S_1(w[n])

xor 运算符 ^ 是结合和交换的。使用这个属性，接下来的几代w[n]可以通过

来计算

r^2(w[n]) = ( S_{-2}(w[n]) ^ S_0(w[n]) ) ^ ( S_0(w[n]) ^ S_2(w[n]) )
          = S_{-2}(w[n]) ^ S_2(w[n])

如果我们让s_j = S_{-j}(w[n]) ^ S_j(w[n])，就有一个模式

r(w[n]) = s_1
r^2(w[n]) = s_2
r^3(w[n]) = s_3 ^ s_1
r^4(w[n]) = s_4
...
r(s_m) = s_{m-1} ^ s_{m+1}

此外，s_n = 0（零数组）因为完整的循环移位是原始数组。我如何使用它来导出 r^t(w[n])?

的非迭代表达式

编辑：模式是

[1]
[2]
[1,3]
[4]
[3,5]
[2,6]
[1,3,5,7]
[8]

Answer 1

据我所知，没有non-iteration解决这个游戏的方法，因为here stated. Even the 'Hashlife算法也是迭代的，但有很多辅助记忆。

但是您可以使用一些方法来选择普通迭代算法：

使用bits而不是int数组：这种方式在某些情况下可以节省大量内存并加快速度。
存储比特的世代：您可以轻松地比较不同代的比特，以找出世代之间是否存在某些重复模式，在这种情况下，无需再进行任何计算更多的。考虑到你只有一个维度，这个几率可能会很高。

Answer 2

我认为你需要发现更多的模式...

是不是这样发展下去：

1
 2 
1 3
   4
  3 5
 2   6
1 3 5 7
       8
      7 9
     6   a
    5     b
   4       c
  3   ???   d
 2           e
1 3 5 7 9 b d f
               g

如果是这样，最简单的方法似乎是为两个 <= t 的最接近的幂计算 r，然后对余数 (t' = t-2^n) 等执行相同的操作，所以你会下降到 O(log(t))。如果？？？ area实际上是空的，你应该可以限制步数为3（通过计算之前的值避免2^n-1，然后单步走）。

Answer 3

让我们将您的输入表示为列向量 a_0，大小为 n，元素为 Z/2Z。

您可以使用矩阵乘法计算下一代向量，a_1：

a_1 = M.a_0 = |0 1 0 0 ... 0 0 0|  |a_01|
              |1 0 1 0 ... 0 0 0|  |a_02|
              |0 1 0 1 ... 0 0 0|  |a_03|
              ....
              |0 0 0 0 ... 0 1 0|  |... |
              |0 0 0 0 ... 1 0 1|  |... |
              |0 0 0 0 ... 0 1 0|  |a_0n|

鉴于此递归关系，您可以使用以下公式计算时间 t 的生成：

a_t = M^t . a_0

并且您可以使用重复平方轻松地在 O(n^3.log(t)) 中计算 M^t。

一维生命游戏的非迭代算法

Non-iterative algorithm for 1D game of life

arrays

iteration

algorithm

conways-game-of-life