Почему я предлагаю анализировать "замкнутные" сегменты вообще ?
Я провел небольшой анализ поведения нашей системы:
Пусть матрица состоит из N точек. Из них P равны 1, остальные N-P
равны нулю. При достаточно случайном заселении матрицы этими P
точками вероятность точке быть в состоянии "1" равна P/N, быть в
состоянии "0" (1-P/N). Назовем величину P/N ro, т.е.
ro=P/N-плотность заселения матрицы точками. Рассмотрим произвольную
точку матрицы, окруженную 8-мью точками:
XXX
XPX
XXX
После очередного шага эволюции у точки есть два способа остаться
"в живых", быть в состоянии "1": либо у нее будет 3 соседа, либо
она уже была в состоянии "1" и соседей у нее будет два.
Вычислим среднюю вероятность обоих событий:
Вероятность получить 3-х соседей(назовем ее s3) равна:
s3 = ro^3 * (1-ro)^5 * C38,
где C38 есть число различных способов заселения восьми окрестных
точек 3 единицами:
Ckn = n! / ( (n-k)! * k! ),
C38 = 8! / ( 5! * 3! ) = 8*7*6/3*2 = 56
Вероятность получить 2-х соседей(назовем ее s2) равна:
s2 = ro * ro^2 * (1-ro)^6 * C28,
где C28 есть число различных способов заселения восьми окрестных
точек 2 единицами:
C28 = 8! / ( 6! * 2! ) = 8*7/2 = 28.
Итак, вероятность того, что точка останется "в живых", назовем
ее s, равна:
s = s3 + s2,
для N точек всей матрицы среднее число точек после очередной
эволюции равно:
N' = N * s,
новая плотность заселения равна:
ro' = N'/N = s = s3 + s2 =
= ro^3 * (1-ro)^5 * C38 + ro * ro^2 * (1-ro)^6 * C28.
Теперь вспомним, что начальное заселение при достаточно
равновероятном генераторе случайной величины примерно равно 0.5.
Получается, что плотность заселения матрицы описывается такой
реккуретной формулой(выше) при стартовом значении ro = 0.5.
Я написал простейшую программу, в котрой вычислял значения
плотности заселения в зависимости от номера эволюции, и получил,
что она в конце-концов стремится к величине ~0.37, при которой
плотность заселения уже не меняется.
Выводы:
- Очевидно, система в своей эволюции движется к "коллпасу",
характеризующемуся плотностью заселения ~= 0.37;
- Следовательно, повторы, возможно, начианют происходить
на шагах эволюции, близких к точке "коллапса";
- Необходимо выработать алгоритм "детектирования" точки
"коллапса" и запомнить в ней матрицу для дальнейшего
анализа на прямое совпадение или просто принять без
строгого доказательства, что после этой точки повторы
неизбежны.
Для детектирования "точки коллапса" я и предлагал анализ
"закрытых" сегментов. Полагаю, что достаточно следить за
наличием либо таких сегментов:
0000 0000
0110 или 0000
0110 0000
0000 0000
> такой это нарисованный выше(/из базы "стандартных сегментов") или же
> любой "замкнутый"?
Например, такой - мне кажется, это неважно.
Или, как ты заметил, "мигалок":
> P.S. непонятно как быть с мигалками(их обычно достаточно много):
> 1 мигалка-
>00000`````00000
>00000`````00100
>01110`<->`00100
>00000`````00100
>00000`````00000
> если она одна - то ее можно считать неизменным сегментом
> а вот две и более:
- именно, если она одна !!!
Итак, замечаем один или несколько таких сегментов. Запоминаем этот
факт и их координаты в матрице. На следующем шаге проверяем, не
поменялся ли сегмент(квадрат вообще никак, мигалка - мигнула) в
тех же координатах ? Если нет, то для сегмента локальный его счетчик
делаем +1. Далее надо будет поэкспериментировать, насчет того, когда
считать точку коллапса - при значении такого счетчика 1 ... 10 ?
Я полагаю, 5-10 будет достаточно ! ;)
|
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
Анализ эволюции +Сегменты. - Chingachguk