非迭代算法用于一维生命游戏。

Question

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

给定a[n]、数组大小n和正整数t，我希望计算出在第t代进化后的a[n]，但不使用任何t上的迭代算法，因为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])

异或运算符^是可结合和可交换的。利用这个性质，可以通过以下方式计算下几代的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]

- Henricus V.

---

为什么你不想在t上使用任何迭代算法？即使t非常大，在O(log(t))的迭代算法也会非常高效。 - fjardon

Answer 1

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

您可以通过使用矩阵乘法计算下一代向量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。

- fjardon

Answer 2

据我所知，就像这里所说的那样，解决这个游戏没有非迭代的方法。即使是“Hashlife”算法也是迭代的，但需要许多辅助内存。

但你可以使用一些方法来优化纯迭代算法：

• 使用位而不是整数数组：这种方式可以节省大量内存，并在某些情况下加快速度。
• 存储位的世代：您可以轻松比较不同世代的位，以找出是否存在世代之间的某些重复模式，在这种情况下，不再需要进行任何计算。考虑到您只有一个维度，机会可能非常高。

- Tony

Answer 3

我认为您需要揭示更多的模式... 它是像这样继续的吗：

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 的2的幂次方的 r，然后对余数也做同样的操作 (t' = t-2^n) 等等，这样你就可以将时间复杂度降至 O(log(t))。如果 ??? 区域实际上为空，你应该能够将步骤限制在三个 (通过先计算出之前的值避免 2^n-1，然后进行一步操作)。

- Stefan Haustein

---

是的。模式确实是这样的。??? 区域虽然不为空，但 [6,a] 的下一步是 [5,7,9,b]。我不确定您所说的回到以前的二次幂是什么意思。 - Henricus V.

假设您想前往t=99。计算r^64，如果我正确理解模式，则应仅具有一个项（s64），然后通过应用s32、s2和s1从那里计算r^96。它仍然是迭代的，但您要循环log(t)而不是t。 - Stefan Haustein