Идею клеточного автомата в середине ХХ века предложил математик Джон фон Нейман. Всякая модель клеточного автомата состоит из множества клеток, которым ставится в соответствие конечный автомат. В конкретный момент времени каждая клетка может принимать одно из возможных состояний. Алгоритм вычисления следующего состояния вычисляется по определенным правилам. Так, меняя правила, возможно моделировать самые разные процессы. Клеточные автоматы широко используются в математике, теоретической биологии, физике, а также в экономике, информатике, социологии и многих других областях. Область их применения практически безгранична. Чаще всего клеточные автоматы используются при моделировании физических процессов.
В данной курсовой работе будет рассмотрена программная реализация клеточного автомата, моделирующего двумерную диффузию с помощью окрестности Марголуса. Такая модель является довольно популярной по причине своей «элегантности» – сочетания в себе простоты и эффективности.
Целью данной работы является исследование процесса распространения загрязнения с течением времени.
Итог работы – визуализированный процесс диффузии.
1.1 Клеточный автомат
1.1 Общие сведения
Как уже упоминалось во введении, каждая клетка клеточного автомата (далее – КА) является конечным автоматом, который в конкретный момент времени может находиться в одном из состояний, зависящем от состояния ее соседей.
КА можно рассматривать как некоторый стилизованный мир, законы которого выражаются единственным набором правил, по которому всякая клетка на каждом шаге вычисляет свое новое состояние по состоянию соседних клеток. Таким образом, чтобы узнать, что произойдет (или может произойти) с конкретной клеткой в следующее мгновение, достаточно посмотреть на состояние ее окружения, называемого соседством. Законы на всем поле действуют одни и те же, и клетки совершают переход в новое состояние синхронно и параллельно. При этом меняется глобальная картина распределения состояний по пространству клеточного автомата. Такая картина называется конфигурацией КА.
Клеточный автомат (2)
... елемент використовує для зміни свого стану значення вхідного параметра; Односторонній клітковий автомат . Такий автомат припускає лише односторонню взаємодію елементів. Наприклад, в одновимірному масиві елементів ... стан. Якщо для елементів КА множини можливих станів відрізняються, такий клітинний автомат називається полігенним . Але на практиці використовуються комірки з еквівалентною множинами ...
Из выше сказанного можно выделить несколько основных свойств клеточного автомата, описанных в [1].
Дискретность пространства, времени и состояний. Однородность. Синхронный режим изменения состояний. Пространственная и временная локальности.
Итеративная смена конфигурации при переходах всех состояний в новые называется эволюцией.
1. 2 Примеры клеточных автоматов
Кратко рассмотрим несколько примеров клеточных автоматов, представленных в [3].
Самым известным примером клеточного автомата является игра «Жизнь», созданная в 1970 году математиком Джоном Хортоном Конуэем. Она является ярким примером того, как имея очень маленькое количество правил или законов, с помощью КА можно моделировать огромное количество процессов, происходящих в живой природе. Принцип состоит в следующем.
Рассматривается бесконечная плоская решетка квадратных ячеек-клеток. Клетка может находиться в одном из двух состояний: жива или мертва. В системе выполняются все основные свойства клеточного автомата. Мир игры жизнь управляется всего тремя основными правилами.
Рождение. Новая клетка рождается на месте какой-нибудь мертвой клетки, если в окружении этой пустой клетки есть не менее трех живых клеток.
Выживание. Живая клетка продолжает жить, если имеет в своем окружении две или три клетки.
Смерть. Клетка погибает, если в ее окружении меньше двух или больше трех клеток.
Имея такой, казалось бы, скудный набор правил, игра «Жизнь» способна моделировать такие процессы, как морфогенез или логические элементы ЭВМ. В связи с этим, игра «Жизнь» нашла применение в различных науках. Более подробно работа этого клеточного автомата рассмотрена в [3].
Еще одним примером клеточного автомата, нашедшего свое применение в биологии, является игра «Аква-Тор». Игра моделирует поведение двух популяций, условно называемых «Хищники» и «Травоядные». «Хищники» едят «Травоядных», а пищи для «Травоядных» бесконечно много. Полем для игры является тор. Эта игра описывается следующими правилами.
Особь может переместиться на любую клетку, имеющую с данной общую сторону. Направление выбирается случайно из возможных свободных.
Аркадный автомат
... может привлечь начинающих игроков. Чтобы игрок не занимал автомат несправедливо долго, в игровых меню (в том числе в подсказке по игре и даже в режиме ввода имени победителя) ... в наше время. 6. Интересные факты Поиск конкретной модели автомата для игры в пинбол — основная сюжетная линия романа Харуки Мураками «Пинбол 1973» Данный реферат составлен на основе .
Особь может оставить потомство в той клетке, из которой она переместилась. Потомство появляется периодически.
Если особь является «хищной», то она может поглотить свою жертву, при этом перемещаясь на место жертвы.
Особь живет ограниченное количество времени, называемое временем жизни особи.
Если «хищная» особь не находит себе пищи в течение определенного времени (называемого временем голодной смерти), то она погибает.
КА описывает несколько важных явлений реальной жизни, например, процесс развития популяции на закрытом ареале. Более подробно рассмотреть действие «Аква-Тора» можно в [3].
1.3 Окрестность Марголуса
Рассмотрим еще один набор правил для клеточного автомата, представляющий собой так называемую окрестность Марголуса – полезную в физическом моделировании схему взаимосвязи клеток.
Имеется решетка – массив – клеток, разбитая на множество конечных однородных частей – блоков. В системе определяется правило не для одной клетки, а для блока в целом. Одно и то же правило применяется ко всем блокам в системе. Важно, блоки не перекрываются и не обмениваются информацией друг с другом, однако от шага к шагу разбиение меняется таким образом, чтобы происходило некоторое перекрытие блоков, используемых на предыдущих шагах.
Используя описанную схему, определим окрестность Марголуса. Решетка разбивается на блоки размера 2х2; шаги, в которых блоки соответствуют четному блоку, чередуются с шагами, использующими нечетные блоки, как показано на рисунке 1.
Рисунок 1 – Блоки 2х2 окрестности Марголуса
На рисунке 1 видно, что в зависимости от шага, клетка, помеченная в (а), будет иметь окрестностью либо четный блок ( b ), либо нечетный блок (c).
Также нетрудно заметить, что блоки одной четности не пересекаются, и напротив, блоки разных четностей – перекрывают друг друга.
Заметим, что окрестность Марголуса использует только два различных разбиения. В общем случае их может быть больше, но их количество должно быть строго ограничено, и они должны циклически повторяться, чтобы не нарушалось условие однородности пространства и времени.
Пример использования окрестности Марголуса будет рассмотрен позднее.
2 КА-модели двумерной диффузии
2.1 Общая информация
Модели двумерной диффузии являются наиболее простыми и хорошо изученными клеточно-автоматными моделями. Клетки могут находиться в одном из двух возможных состояний: 0 или 1. Состояния определяют наличие или отсутствие единицы массы, наделённой скоростью. Сама диффузия представляет собой процесс беспорядочного блуждания частиц, который приводит к выравниванию концентрации вещества в пространстве.
Бизнес-модель тур. предприятия
... разработка образа будущей компании, создание модели существующей компании, разработка нового бизнеса, внедрение перепроектированных процессов. В рамках данной работы подробно описана методология функционального моделирования IDEF0 (методология моделирования функциональных блоков). Этапы применения модели ...
Классические КА-модели диффузии имеют булев алфавит и эволюцию в виде последовательности булевых массивов. Все КА-модели диффузии являются стохастическими или случайными.
2.2 КА-диффузия с окрестностью Марголуса
Окрестность Марголуса уже была описана в пункте 1.3. Рассмотрим подробно её применение для моделирования процесса диффузии [1].
Дан клеточный массив размера NxN , где – область начального загрязнения. Этот массив имеет базовую часть с булевым алфавитом состояний A B и множеством имен , а также контекстную часть тоже с булевым алфавитом и множеством имен . В выделяются два подмножества имён и .
Для каждого имени определена локальная конфигурация
представляющая из себя блок из четырёх клеток.
Рисунок 2 – КА диффузия с окрестностью Марголуса
На рисунке 2 изображены покрытия блоками: белым показаны четные блоки, серым – нечетные.
Таким образом для любой пары блоков одной четности справедливо утверждение о том, что они не пересекаются:
