Клеточный автомат. Клеточный автомат
 Скачать 21.98 Kb.
|
|
Клеточный автомат Что такое клеточный автомат? Кле́точный автома́т — дискретная модель, изучаемая в математике, теории вычислимости , физике, теоретической биологии и микромеханике. Основой является пространство из прилегающих друг к другу клеток (ячеек), образующих решётку. Каждая клетка может находиться в одном из конечного множества состояний (например, 1 и 0). Решётка может быть любой размерности, бесконечной или конечной, для решётки с конечными размерами часто предусматривается закольцованность при достижении предела (границы). Для каждой клетки определено множество клеток, называемых окрестностью. Например, окрестность фон Неймана ранга 2 включает все клетки на расстоянии не более 2 от текущей. Устанавливаются правила перехода клеток из одного состояния в другое. Обычно правила перехода одинаковы для всех клеток. Один шаг автомата подразумевает обход всех клеток и на основе данных о текущем состоянии клетки и её окрестности определение нового состояния клетки, которое будет у неё при следующем шаге. Перед стартом автомата оговаривается начальное состояние клеток, которое может устанавливаться целенаправленно или случайным образом. Основное направление исследования клеточных автоматов алгоритмическая разрешимость тех или иных задач. Также рассматриваются вопросы построения начальных состояний, при которых клеточный автомат будет решать заданную задачу. ПРИМЕНЕНИЕ КЛЕТОЧНЫХ АВТОМАТОВ Предположим, что каждый человек в группе стремится двигаться в определенном (одном для всех) направлении. При невозможности двигаться в этом направлении, наличии на пути непре одолимых препятствий или значительного количества других людей человек пытается изменить направление движения, выбирая то, на котором препятствия минимальны. Будем также считать, что движущиеся люди могут просматривать обстановку в толпе на рас стоянии г и выбирать направление движения, в котором они наблюдают наименьшее количество других людей и отсутствие препятствий. Пусть поле клеточного автомата представляет собой совокупность двух прямоугольных мат риц (F; V), где F - матрица значений^ в узлах равномерной ортогональной сетки, ftj е {0; 1; 2; 3; 4} - величина, соответствующая наличию (1) или отсутствию (0) человека в данном месте (ос тальные значения используются на промежуточном шаге динамики модели и собственного смысла не имеют), V- матрица значений vtj в узлах, v^e {0; 1} - величина, соответствующая на личию (1) или отсутствию (0) препятствия в данном месте. Выберем для нашей модели окрестность фон Неймана. На изменение состояния клетки влияют четыре ее соседа; традиционно обозначим их первыми буквами названий сторон света: W С Е • Введем переменную а, которая может принимать значения N, W, С, Е, 5, определим для этой переменной операцию а, результатом которой будет противоположное направление (напри мер, N =S, причем С = С), и примем соответствующие обозначения для состояний соседей вы бранной клетки: AN)г_ЛЕ) г_АС) i+l,у Jij ' Ji,j+l Jij » Jij Jij • Аналогичные обозначения введем для значений элементов матрицы V, соседних с выбран- НЫМ. Зададим правила вычисления вероятностей перемещения из данной клетки в соседние (при меним его только к клеткам, для которых Д =1). Прежде всего запретим перемещаться в занятые клетки и клетки, содержащие препятствия: Py(a) = i(l-/ijx ) )(l-vi;) ). (i.i) Затем введем в модель элемент анализа окружающей обстановки людьми, движущимися в группе. На каждом шаге для каждой клетки поля клеточного автомата, находящейся в состоянии 1, рассчитаем вероятности смещения человека из данного положения в одну из четырех соседних клеток. Для этого положим эти вероятности равными нулю в случае, если соседняя клетка заня та. Для оставшихся направлений осуществим "просмотр" на расстояние г (являющееся парамет ром модели) следующим образом: суммируем число всех клеток, лежащих в данном направлении на расстоянии, не превышающем г, находящихся в состоянии 1, причем если в этом направлении встречается клетка с препятствием, то она и все клетки, лежащие за ней, рассматриваются как занятые. Для реализации этого вычислим вероятности ос) перемещения в соседние клетки, умень шив их в тех направлениях, где большое число клеток занято людьми или препятствиями: (г* Yl 1-1 fi-kj + r-r г здесь г - глубина просмотра при оценке ситуации (задаваемый произвольно параметр модели), г* - расстояние от данной клетки до ближайшей в данном направлении клетки, содержащей препят ствие, a P'ij(a) - вероятности, вычисленные по формулам (1.1). Теперь увеличим вероятность движения в заданном направлении, выбрав в качестве такого направления, например, N: или p{j(N) = p;;(^)+amin[i-p;;(iv);p;A(5);p;'(w);p;;(£)], Puis) = p;;(5)-^min[i-p;;(iv);p;;(S)], ри(Е) = p;;(£)-^min[i-p;;(iv);p;;(£)], Pij(w) = p;;(w)-|min[i-p;;(iv);p;;(W)], где a E [0; 1] - некоторый коэффициент, задающий степень стремления двигаться в этом направ лении от 0 (такого стремления нет) до 1 (такое движение осуществляется при любой возможно сти). Вероятности (1.2), вычисленные для каждой клетки, находящейся в состоянии 1, определяют динамику модели на данном шаге. Теперь зададим закон изменения конфигурации поля клеточного автомата F на каждом шаге в виде рекуррентного соотношения Fn + i = (p(F„), где отображение представим в виде ф = ф2 ° (Pi- Вначале рассмотрим отображение фх . Введем для каждой клетки, в которой ftj= 1, перемен ную Р,у, которая может принимать значения N, W, С, £, 5, и вычислим значения этих переменных как случайных величин с законом распределения покойных". Теперь определим отображение фх : (здесь а принимает любые значения). \ff\ если р;;(сс) = а, L 0 в ином случае, Р(% =а) = Рфи = С) = О, если Pi;(Y) = 0 2>,(Y) Vy, в ином случае, Р(р\у = а) = Р,7 (а), Р(р\у = С) = l-TPij(a), (1.3a) (1.36) -уф С 1, если Р^у) = 0 0 в ином случае Vy*C, (здесь а ФС). ПРИМЕНЕНИЕ КЛЕТОЧНЫХ АВТОМАТОВ 2097 Таким образом, отображение фх описывает смещение частиц (людей) на свободные места, иг норируя то, что на одно свободное место может найтись до четырех "претендентов". Надо отме тить, что матрица ф^/7 ) не является полем битов ( ф ^ ) е {0; 1; 2; 3; 4}). Теперь рассмотрим отображение ф2 , введенное для того, чтобы решить эту проблему "пере населения" некоторых клеток. Его проще всего описать при помощи следующего алгоритма. Для всех i,j выполнить Маг 1. Если tyiifij) < 1, то перейти к шагу 4. Маг 2о Присвоить переменной а случайное значение из возможных, определяемых условием Маг Зо Изменить значения элементов матрицы (пользуясь терминологией клеточных автома тов, изменить состояние клеток поля) по следующему закону: ф^Д"*) присвоить значение 1, присвоить значение ф ^ ) - 1. Маг 4о Перейти к шагу 1. Маг So Положить фгСф^у)) = Описание закона изменения конфигурации поля клеточного автомата закончено. Этот закон задает перемещение частиц по полю клеточного автомата, при котором каждая частица перемещается в выбранном направлении, стремясь обходить препятствия такому движе нию в направлении, наиболее свободном для движения. Надо отметить, что заданный таким об разом закон изменения конфигурации поля сохраняет число клеток, находящихся в состоянии 1 (^Г. .fij = const), что является естественным требованием к модели. 2. РЕШЕНИЕ НЕКОТОРЫХ ЗАДАЧ ПРИ ПОМОЩИ МОДЕЛИ Интересно проверить эффективность этой модели на некоторых тестовых задачах, возмож но имеющих практическую ценность. Первая заключается в том, чтобы, исследовав различные профили сужения подземного перехода (вид сужения представлен на фиг. 1), найти наибольшее значение угла ф (при этом общая длина сужения будет наименьшей, что, по-видимому, выгодно конструктивно), при котором не будет наблюдаться ярко выраженный затор при потоке людей большой плотности. Моделирование этой ситуации при различных значениях параметров - угла ф и плотности по тока людей L - показало, что при значениях угла, не превышающих фк р = я/4, затор возникает лишь при плотности потока, превышающей 1/3 от максимально возможной (на входе заполняет ся треть всех клеток). Это связано с ограничением физической пропускной способности узкой части перехода. Если же значение угла превышает фк р = я/4 (в модели из-за дискретного характера конфигу рации препятствий наименьшим из таких углов был ф = arctg (3/2) = 0.98), то затор возникает при сравнительно небольших плотностях потока; на фиг. 2 показана зависимость от времени плот ностей потока перед сужением (I) и после него (II) при начальной плотности потока, равной 0.1. Видно, что на протяжении некоторого периода времени (15 < t < 45) плотность входящего потока стабильно превышает плотность выходящего, при этом последний даже несколько снижается. |