Число юридических предыдущих движений в игре жизни

Учитывая текущий тик игры в игре жизни Конвея (или любой другой игры сотовой автоматизации), как можно найти количество законных предыдущих тиков, которые могли быть оценены в установлен тик?Число юридических предыдущих движений в игре жизни

Например, предполагая, что игра жизни может быть представлена в виде:

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 
}

Очевидно, что можно найти каждый возможного состояния предыдущей игры от размера сетки и определить, что будет оценивать в с текущее состояние с использованием обычных правил.

Однако должны быть некоторые очевидные способы ускорить этот процесс, чтобы он не был O(2^n) (где n - общее количество ячеек в сетке).

Кэширование, конечно, может помочь в местах, но где именно он будет вписываться?

Любая помощь будет оценена

источник

2017-01-25 Joe Swanson

https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_automaton) –

Я бы предположил, что эта проблема NP-Complete. Жизнь завершена, поэтому алгоритм перемотки чувствует себя ужасно близко к поиску входных данных, которые заставляют программу возвращать true. Посмотрите, сможете ли вы найти сокращение до 3-SAT или что-то в этом направлении. –

@CraigGidney: Я думаю, что ты прав. Я ожидал бы, что, как и во многих проблемах NP-Complete, большинство «случайных» наборов входов будут поддаваться решениям с полиномиальным временем, но если P = NP, для всех входных данных не будет применяться многочлен-временной подход. – supercat

Для m*m платы, вы можете сделать это в O(m*8^m) с динамическим программированием.

Идея заключается в том, чтобы начать в верхней части доски и работать вниз, вычисляя для каждой пары строк для i-1, i «-й позиции всех строк, которые могут быть в i+1„-й позиции, чтобы дать право i“ й строке вывода.

Это лучше, чем 2^O(n) = 2^(O(m*m)), но довольно медленно.

Я не думаю, что вы сделаете намного лучше этого.

источник

2017-01-25 19:18:49 btilly

Число юридических предыдущих движений в игре жизни

ответ

Смежные вопросы