4. 4 Двухмерные клеточные автоматы




Скачать 107.4 Kb.
Название4. 4 Двухмерные клеточные автоматы
Дата публикации19.03.2013
Размер107.4 Kb.
ТипДокументы
skachate.ru > Информатика > Документы

4.4 Двухмерные клеточные автоматы



В данном подразделе рассмотрим несколько различных вариантов определения двухмерных клеточных автоматов. Наиболее часто используются окрестности двух видов: фон Неймана (5 клеток, включая саму клетку и ближайших соседей по горизонтали и вертикали) и Мура (9 клеток, включая саму клетку и всех непосредственных соседей, как в игре «Жизнь»). Иногда рассматриваются расширенные окрестности Мура или фон Неймана. Для этого дополнительно нужно задать диапазон  ­ целое положительное число. Тогда расширенная окрестность Мура диапазона  ­ квадрат со стороной 2+1. Расширенная окрестность фон Неймана содержит все клетки на расстоянии  по горизонтали и вертикали. Кроме того, саму центральную клетку иногда не включают в окрестность.
^

Циклические клеточные автоматы



Для определения циклического клеточного автомата задается n различных состояний клеток, которые линейно упорядочиваются так, чтобы после последнего состояния шло первое (тем самым получается период длиной n). С каждым состоянием клетки связан определенный цвет. Кроме того, задается некоторое пороговое число m. Состояние клетки меняется на следующее, если, по крайней мере, имеется m клеток следующего цвета (состояния) в пределах расширенных окрестностей Мура или фон Неймана. Этот класс клеточных автоматов был открыт и изучен Дэвидом Гриффитом.

Такие клеточные автоматы показывают появление сложной самоорганизации из «случайного состояния». В качестве примера возьмем правило под названием CCA, найденное Д. Гриффитом в 1989 г. Здесь имеются всего 14 состояний, порог равен 1 и используется простая окрестность фон Неймана. Если начальное распределение состояний клеток задать случайным образом, то происходит самоорганизация и очень скоро клеточный автомат изображается в виде спиралей (рис. 4.22).






а

б

Рис. 4.22  Циклический автомат CCA: (а) исходная конфигурация;

(б) состояние автомата приблизительно после 300 шагов
Существует также разновидность циклических клеточных автоматов – модель Greenberg­-Hastings ­ возможно, самый простой класс клеточных автоматов с возбудимым центром. Выделяются два подряд идущих состояния: 0 ­ спокойное состояние и 1 ­ возбужденное состояние. Состояние клетки 0 меняется на 1, если в ее множестве соседей есть, по крайней мере, m клеток с состоянием 1. Все другие состояния меняются автоматически. Начинают с однородной произвольной смеси, в которой возможные цвета распределены случайным образом; возбуждение затухает, если порог слишком велик по сравнению с установленным размером окрестности клеток, тогда как беспорядочная смесь фактически неотличима от результатов шума, если порог слишком низок. Однако при промежуточных порогах волны возбуждения самоорганизовываются в крупномасштабные спиральные пары, которые стабилизируются в локальном периодическом состоянии.

В качестве примера возьмем правило под названием Percolation («просачивание»), найденное Д. Гриффитом. Здесь имеются всего 8 состояний, порог равен 10 и используется расширенная окрестность Мура диапазоном 5 (рис. 4.23).

Рис. 4.23  Циклический автомат с возбудимым центром;

эволюция из случайного состояния через 40 тактов

«Поколения»



«Поколения» («Generations») – класс клеточных автоматов, которые создают, быть может, самые красочные конфигурации клеток. Правила игры «Поколения» очень похожи на правила игры «Жизнь», с одним дополнением: добавляется история клеток. Клетки, которые в игре «Жизнь» умирают, в «Поколениях» становятся старше. Они не могут создать новые клетки, но влияют на правила, занимая место на решетке.

Рассмотрим два примера, найденные Войтовичем (M. Wojtowicz) в 1999 г. В обоих примерах используются 4 цвета. Первое правило называется «Конвейер» (рис. 4.24­4.25).

Рис. 4.24  «Конвейер»: начальная конфигурация

Рис. 4.25  «Конвейер» двигается
На рис. 4.25 из левого верхнего узла начинают по конвейеру двигаться блоки из шести клеток. Обойдя весь конвейер по часовой стрелке, они исчезают в левом верхнем узле, чтобы возникнуть снова и продолжить движение. Очень красочное зрелище! Напоминает работу заброшенного завода, описанного Станиславом Лемом в романе «Эдем».

Второе правило называется «Стипл-чейз» (гонки с препятствиями) (рис. 4.26­4.27).

Рис. 4.26  Две дорожки с препятствиями перед гонками

Рис. 4.27  Гонки начались
Трудно передать динамику этого автомата на статической картинке. На рис. 4.26 изображены две беговые дорожки (верхняя и нижняя) с различными препятствиями ­ это начальная конфигурация. В результате эволюции автомата из первых препятствий на каждой дорожке появляются «лошади» в виде блоков по 6 клеток. Они двигаются по дорожке и, встретив очередное препятствие, разделяются на две части и обходят препятствие по боковым сторонам. Потом снова соединяются и продолжают движение, чтобы исчезнуть в «стене», которой заканчивается дорожка. А в это время на дорожку вступают новые «лошади» и т.д. Эта картинка напоминает движение машин по шоссе, появляющихся из одной «дыры» на одном конце шоссе и исчезающих в другой «дыре» на другом конце шоссе, как описано в повести братьев Стругацких «Попытка к бегству».

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

Рассмотрим несколько приложений двухмерных клеточных автоматов в компьютерном моделировании физических процессов.
^

Эрозия почвы



Рассмотрим проблему эрозии почвы. Пусть почва целины содержит некоторые участки с эрозией ­ ямки. В зависимости от конфигурации таких участков и их численности эрозия почвы может стабилизироваться со временем или увеличиваться («плохие» участки разрастаются в размерах). Какова динамика этого процесса?

В изучении эрозии почвы естественно использовать двухмерные клеточные автоматы. Будем представлять целину с помощью клеточного автомата с двумя состояниями 1 («хороший» кусочек почвы) и 0 («пустыня» ­ «плохой» кусочек почвы). В качестве окрестности клетки выберем окрестность Мура. Сущность процесса эрозии почвы опишем следующим транзитивным правилом:

а) если у клетки с какой-нибудь стороны все три соседа есть клетки «пустыни», то почва этой клетки «не закреплена» и она становится (или остается) «пустыней»;

б) во всех других случаях состояние клетки не меняется.

Кусочек почвы, представленой единицей, останется на месте, если с каждой стороны (северной, южной, восточной и западной) от него есть хоть чуть-чуть почвы. В первых трех случаях, изображенных ниже, почва в центре окрестности «устойчива», в то время как в четвертом она «не закреплена» (так как никакая из трех ее восточных позиций не занята):


101

010

010

010

010

110

111

110

010

001

010

110


Если вы запустите этот автомат, начиная со сплошной почвы, то ничего не произойдет. Если вы удалите в некоторых местах изолированный кусочек почвы, то в дальнейшем эрозия не возникнет. Если вы продолжите удаление кусочков случайно, то, в конечном счете, получите места, где удалены два или три примыкающих кусочка; в зависимости от формы такой «ямки» стенки могут «рушиться», увеличивая саму ямку. Пока количество удаленной почвы остается ниже определенного критического уровня (около 17%), такие обрушения обычно самозалечиваются и почва в целом остается устойчивой (рис. 4.28).


Рис. 4.28  Эрозия стабилизировалась; в начальном состоянии

«плохие» участки составляли 10%
Однако, когда доля удаленной почвы превышает этот уровень, некоторые из ямок проявляют неограниченный рост ­ они становятся центрами образования зародышей, и в конечном счете вся почва выветривается (рис. 4.29).






а

б

Рис. 4.29  Эрозия растет: (а) начальное состояние почвы («плохие» участки ­ 20%); (б) состояние почвы после 10 единиц времени

Диффузия



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

Определим новый вид клеточного автомата ­ клеточный автомат на разбиение:

а) решетка клеток разбита на множество конечных отдельных однородных частей ­ блоков;

б) дается правило для блока, рассматривающее и обновляющее содержимое всего блока (а не отдельной клетки, как в обычном клеточном автомате). Одно и то же правило применяется ко всем блокам. Заметим, что блоки не перекрываются и нет обмена информацией между соседними блоками;

в) разбиение меняют от шага к шагу так, чтобы было некоторое перекрытие блоков, используемых на соседних шагах.

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

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

Мы будем использовать только простейшую схему разбиения, а именно:

1) решетка клеток разбита на блоки размером 22;

2) шаги, в которых блоки соответствуют четной решетке, чередуются с шагами, использующими нечетную решетку, как показано на рис. 4.30.

Тгруппа 18
акую схему разбиения называют окрестностью Марголуса.

Рис. 4.30  Блоки 22 окрестности Марголуса: на последовательных

шагах чередуется четная и нечетная решетка. В зависимости от этого помеченная клетка будет иметь окрестностью либо четный блок (а), либо нечетный блок (б)
Если черным цветом на решетке (рис. 4.30) обозначена клетка диффундированного вещества, то на одном шаге она должна обменяться местами с какой-то белой клеткой в соответствующем блоке. В качестве возможных изменений содержимого блока выберем два способа: поворот содержимого блока по часовой стрелке и поворот против часовой стрелки. В данной модели диффузии решение, в каком направлении вращать блок, будет определяться случайно. Результат диффузии показан на рис. 4.31.





а

б

Рис. 4.31  Постепенная диффузия плотного кластера частиц: (а) исходное состояние; (б) диффузия после 30 шагов
^

Ограниченное диффузией агрегирование



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

В данной модели клетка имеет три состояния: 0 (частица вещества среды), 1 (частица диффундирующего вещества), 2 (дендрит). В правиле используется окрестность Марголуса. Исходная конфигурация представляет собой случайно полученную смесь частиц: 80% ­ частицы среды; 20% ­ диффундирующие частицы. В центре решетки находится одиночный зародыш. Как и в предыдущем примере, происходит процесс диффузии с помощью генератора случайных чисел, но только для тех блоков, которые не содержат частицы дендрита. Если же часть дендрита появляется где-либо в блоке, то любые диффундирующие частицы, содержащиеся в этом блоке, будут прилипать к дендриту (менять состояние 1 на состояние 2), где они остаются неподвижными. Результат напоминает действие липкой бумаги для мух (рис. 4.32).






а

б

Рис. 4.32 Дендритный рост за счет ограниченного диффузией агрегирования: (а) исходное состояние; (б) дендрит после 20 шагов

Вернемся к саморепликации клеточных автоматов. Для того чтобы клеточный автомат был самовоспроизводящимся, совсем не требуется, чтобы он являлся универсальным конструктором. Первый пример такого двухмерного клеточного автомата, способного только саморепродуцироваться, изобрел Крис Лангтон (Christopher G. Langton). Его автомат состоял из 86 клеток, каждая клетка имела 4 соседа и могла быть в 8 состояниях (рис. 4.33).





а






б

в

Рис. 4.33  Самовоспроизводящийся клеточный автомат: а­ исходный организм; б­ организм со своими потомками, все они продолжают размножаться; в­ те организмы, которые блокированы другими организмами, уже не размножаются
Ячейки в состоянии 2 есть «кожа» или «оболочка» организма. Внутренние ячейки в состояниях 0, 1, 4 и 7 есть «ДНК» организма, они задают конструкцию размножающегося организма. «ДНК» размещена вокруг цикла, она копируется и посылается на конец «руки», где управляет созданием нового организма. Вы можете наглядно увидеть это развитие в программе Mcell. Позже появились еще более простые примеры самовоспроизводящихся автоматов.

Теоретическая физика традиционно пытается найти «кратчайшие пути» в природе. То есть пытается найти методы, которые смогут воспроизвести конечное состояние системы, зная начальное состояние, но не прослеживая каждый шаг от начального состояния к конечному. Примером является любой физический закон такого рода, например, утверждение, что траекторией брошенного в гравитационном поле объекта является парабола. Или еще один пример: чтобы умножить число с помощью компьютера на 2n, нет необходимости 2n раз складывать его с самим собой, достаточно просто сдвинуть его представление в памяти компьютера на n двоичных разрядов. Системы, для которых такие более простые алгоритмы существуют, называют вычислительно приводимыми.

Несомненно, вычислительная приводимость физической системы должна быть, в принципе, возможна, если мы в состоянии получить конечное состояние системы, выполняя более сложные вычисления, чем вычисления, которые может делать сама физическая система. Рассмотрим компьютер. Поскольку компьютер сам является физической системой, он способен определить результат своего развития только явным следованием. Никакое сокращение невозможно. Такая вычислительная неприводимость происходит каждый раз, когда физическая система может действовать, как компьютер. В таких случаях общая прогнозируемость невозможна. Вычислительная неприводимость подразумевает, что существует самый высокий уровень, на котором могут быть сделаны абстрактные модели физических систем. Выше этого уровня необходимо только непосредственное моделирование.

Так как игру «Жизнь» можно рассматривать как универсальный компьютер, то система «Жизнь» является вычислительно неприводимой.

Существует гипотеза Стивена Вольфрама, состоящая в том, что многие физические системы и их модели, для которых в настоящее время неизвестно простое описание, являются вычислительно неприводимыми. Для них в принципе не могут быть построены эффективные теории. Единственный способ анализа таких систем ­ физический или компьютерный эксперимент (в т. ч. использование моделей клеточных автоматов).

Похожие:

4. 4 Двухмерные клеточные автоматы icon4. 4 Двухмерные клеточные автоматы
Вариант 10. Напишите программу для двумерного клеточного автомата, моделирующего процесс ограниченного диффузией агрегирования (раздел...
4. 4 Двухмерные клеточные автоматы iconНа конкурс Контрацептивы по-европейски
Вендинг-индустрия шагает по планете. Люди привыкли, что торговые автоматы продают им прохладительные напитки, шоколадки и чипсы....
4. 4 Двухмерные клеточные автоматы iconВсемирная Шашечная Федерация (fmjd) Генеральный офис: Утрехт, Нидерланды Член gaisf
Чемпионат в 64-клеточные шашки по русской версии среди женщин и одно соревнование по “чекерсу”), a вне этого в 100-клеточные шашки...
4. 4 Двухмерные клеточные автоматы icon1 кибернетика
Чеботарев А. Н. О классе формул языка L*, специфицирующих автоматы с конечной памятью
4. 4 Двухмерные клеточные автоматы iconМетодические указания по определению уровня естественной резистентности...
Клеточные элементы иммунной системы организованы в тканевые и органные структуры. К ним относятся: тимус
4. 4 Двухмерные клеточные автоматы icon44. Электрокинетический потенциал. Его зависимость от концентрации противоионов
Новые качества наночастиц. Обоснование минимального и максимального размера наночастиц. Разнообразие и многообразие форм наночастиц....
4. 4 Двухмерные клеточные автоматы iconЛабораторная работа №7 двухмерные массиы (матрицы)
Кроме приведенного ранее описания многомерный массив можно описать как одномерный, элементами которого являются массивы. Так, например,...
4. 4 Двухмерные клеточные автоматы iconЛабораторная работа №7 двухмерные массивы (матрицы)
Кроме приведенного ранее описания многомерный массив можно описать как одномерный, элементами которого являются массивы. Так, например,...
4. 4 Двухмерные клеточные автоматы iconРекомендации по стандартизации информационно-телекоммуникационные игровые системы
Внесены техническим комитетом по стандартизации тк 446 "Игровые автоматы и игорное оборудование"
4. 4 Двухмерные клеточные автоматы iconИсследование характерологических особенностей человека и стратегий...
Имеется ли связь личностных психологических особенностей человека с эффектами воздействия, производимыми им бесконтактно на клеточные...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница