Неиреративный алгоритм для жизни 1D жизни

Question

Рассмотрим булевой массив a[n], где каждый элемент является ячейкой. Ячейка становится живой (установлена ​​в true) в следующем поколении, если одна и только одна соседняя ячейка жива, в противном случае она становится мертвой (установлена ​​в false). Первая и последняя ячейки считаются соседями.

Учитывая a[n], размер массива n, и положительное целое число t, я хочу, чтобы вычислить a[n] после t'th поколения эволюции, но без использования каких-либо итерационного алгоритма на t, который может быть потенциально очень большой.

То, что я заметил: если мы определим S_k(a[n]) быть циклический сдвиг из a[n] справа от k элементов. То есть, a[0] становится a[k] после одной смены, если 0 <= k < n. Определите a[n]^b[n] как элементную операцию xor между двумя булевыми массивами. Если 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 (массив нулей), так как полный круговой shift - это исходный массив. Как это использовать для получения нетеративного выражения r^t(w[n])?

Edit: Узор

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

Answer 1

Представьтесь, пожалуйста, в качестве столбцового вектора 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 

И вы можете легко вычислить M^t в O(n^3.log(t)), используя многострочное возведение в квадрат.

Answer 2

Насколько я знаю, нет, не итерация способа решить эту игру как here сказал. Даже алгоритм «Hashlife» также является итеративным, но со многими вспомогательными памятью.

Но вы можете использовать несколько способов сделать выбор в пользу простой итерации Algo:

• Используйте биты, а не целочисленный массив: Таким образом, можно сэкономить много памяти и ускорить скорость в некоторых случаях.
• Хранение поколений бит: вы можете легко сравнить биты из разных поколений, чтобы узнать, существует ли несколько повторений шаблонов между поколениями, и в этом случае больше не требуется больше вычислений. Учитывая, что у вас есть только одно измерение, вероятность может быть очень высокой.

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, то сделайте то же самое для остатка (t '= t-2^n) и т. д., так что вы опуститесь до O (log (t)). Если ???область фактически пуста, вы должны иметь возможность ограничить шаги до 3 (избегайте 2^n-1, вычисляя значение раньше, затем переходите на один шаг).