生命遊戲中法律訴訟的數量

Question

考慮到康威目前的生命遊戲（或任何其他蜂窩自動化遊戲）中的遊戲時間點，如何找到可以評估到的合法的先前蜱數量勾號提供了什麼？

例如，假定生命的遊戲可以被表示爲：

0 0 0 0 0 ... 
X 0 X 0 0 ... 
0 X 0 0 0 ... 
0 0 0 0 X ... 
... 

其中X是「活/開/真」和0是「死/關/假」，或更簡單地作爲一個boolean[][]，一個人如何能制定出以下幾點：

public static int numberOfValidPreviousTicks(boolean[][] current) { 
    return -1; // return answer 
} 

很顯然，人們可以從電網尺寸找到每可能之前的比賽狀態，並決定是否將評估到c urrent狀態使用正常的規則。

但是，必須有一些明顯的方法來加速此過程，以便它不是O(2^n)（其中n是網格中的單元格總數）。

緩存當然可以在地方幫助，但它在哪裏適合？

任何幫助，將不勝感激

Answer 1

對於m*m板，你可以用動態規劃做在O(m*8^m)。

的想法是開始在板的頂部和工作下來，「個位置都可以是在i+1行的‘個位置計算對於每一對行爲i-1, i的給予正確i’第三排輸出。

這比2^O(n) = 2^(O(m*m))好，但相當慢。

我不認爲你會做得比這更好。