Comments 6
Я так понимаю, сколько бы ни было цветов, на достаточно большом случайном поле спираль возникнет. Нельзя ли оценить функцию размера поля от количества цветов, при котором спираль возникнет с вероятностью 50\50?
Интересная постановка задачи. Я думаю план ее решения будет примерно такой:
1. Определить количество начальных паттернов, которые приводят к образованию спирали (при фиксированном размере решетки и числе состояний).
2. Определить количество всех возможных паттернов (при фиксированном размере решетки и числе состояний).
3. Построить зависимости этих двух чисел (число паттернов, порождающих спираль, и всех возможных) от двух параметров: размера решетки и числа состояний клеточного автомата.
В результате мы получим две поверхности. Делая их срезы можно будет получить представление об искомой функции. Начинать, я думаю, стоит с одномерного клеточного автомата.
1. Определить количество начальных паттернов, которые приводят к образованию спирали (при фиксированном размере решетки и числе состояний).
2. Определить количество всех возможных паттернов (при фиксированном размере решетки и числе состояний).
3. Построить зависимости этих двух чисел (число паттернов, порождающих спираль, и всех возможных) от двух параметров: размера решетки и числа состояний клеточного автомата.
В результате мы получим две поверхности. Делая их срезы можно будет получить представление об искомой функции. Начинать, я думаю, стоит с одномерного клеточного автомата.
Если учесть то, что в п.2 ответ n^(m*m) где m — сторона поля, задача нуждается в вероятностном подходе. Я попробовал посчитать, получилось довольно странная формула (1-(1-6/n^3)^(m^2))^n для заданных m, n, которая не учитывает то, что случайные величины здесь зависимые (т.е. их здесь m*m, а не m*m*n, и если какая-то клетка имеет соседа-пищу, то та клетка имеет соседа-хищника с вероятностью 1). Отсюда и оценка как в комменте ниже.
PS: для одномерного автомата ответ 0, он всегда не сумеет образовать спираль. Если там кольцо, то может суметь, если цвета таки образуют кольцо.
PS: для одномерного автомата ответ 0, он всегда не сумеет образовать спираль. Если там кольцо, то может суметь, если цвета таки образуют кольцо.
Так ли полезен одномерный случай?
Допустим, рассматривая двумерный массив, мы нашли «хорошую» кольцевую последовательность ячеек, в том смысле, что кольцевой одномерный автомат стартующий с этой последовательности образует спираль. Вопрос: точно ли возникнет спираль в двумерном автомате? Не испортит ли что-то окружение?
Допустим, рассматривая двумерный массив, мы нашли «хорошую» кольцевую последовательность ячеек, в том смысле, что кольцевой одномерный автомат стартующий с этой последовательности образует спираль. Вопрос: точно ли возникнет спираль в двумерном автомате? Не испортит ли что-то окружение?
Навскидку, m^2=n^3/x, где х примерно равен 6, а m — сторона квадратного поля. Округлять вверх. Кстати для n=2 ответ 2х1.
Да, вторую поверхность посчитать просто: n^(m^k), где n — число состояний, m — сторона решетки, k — размерность решетки. Для k=2 имеем:
Но ответ в п.1 так легко не получить.
P.S. я почти уверен, что если в k=1 автомате расположить все состояния в ряд одно за другим, то спираль образуется (для k=2 автомата это сработало)
Но ответ в п.1 так легко не получить.
P.S. я почти уверен, что если в k=1 автомате расположить все состояния в ряд одно за другим, то спираль образуется (для k=2 автомата это сработало)
Sign up to leave a comment.
О возникновении спиралей в циклическом клеточном автомате