"Информатика (базовый и углублённый уровни) (в 2 частях)", Поляков К.Ю., Еремин Е.А.
Сеточная модель описывает область или объект как набор ячеек, расположенных на регулярной сетке. Каждой клетке назначают состояние, например «пусто» или «занято», а правила связывают её изменение с состояниями соседей. Так можно пошагово исследовать распространение огня, эпидемий и другие процессы, где важны локальные взаимодействия. На результат влияют размер ячеек, определение соседства и способ обновления сетки.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Сеточная модель — способ представить объект или область как множество ячеек, расположенных на регулярной сетке. Вместо описания каждой точки пространства рассматривают конечное число участков. Такая модель нужна, чтобы упростить сложную систему и описывать её с помощью вычислений.
Клетка — отдельный элемент сетки, которому приписывают состояние, характеризующее соответствующий участок модели. Состоянием может быть число, цветовой код или значение из ограниченного набора, например «пусто» и «занято». Благодаря этому для каждого участка можно хранить и обрабатывать нужную информацию.
Соседство клетки — правило, определяющее, какие другие клетки считаются близкими к выбранной и могут влиять на неё. Например, соседями можно считать только клетки с общей стороной либо добавить клетки по диагонали. Явное определение соседства необходимо, чтобы одинаково вычислять взаимодействия на всей сетке.
Клеточный автомат — сеточная модель, в которой состояния клеток меняются по заданным правилам от одного шага к другому. Правило использует состояние самой клетки и, как правило, состояния её соседей. Автомат позволяет представить развитие процесса как последовательность вычислений.
Сначала непрерывную область делят на одинаковые или заданным образом упорядоченные ячейки и получают сетку. Это упрощает описание: вместо бесконечного множества точек достаточно учитывать конечное число клеток. Размер ячейки задаёт детализацию — мелкая сетка различает больше локальных особенностей, а крупная объединяет их. Поэтому слишком крупный шаг может скрыть важные детали, а слишком мелкий увеличит объём вычислений.
Затем выбирают множество возможных состояний клетки и задают начальную конфигурацию — состояния всех клеток в начале моделирования. Например, в модели распространения огня можно выделить состояния «дерево», «горит» и «пусто». Ограниченный набор состояний помогает сделать правила точными и однозначными. Начальная конфигурация нужна, потому что без исходных данных нельзя определить, с чего начнётся развитие системы.
После этого определяют соседей каждой клетки. При соседстве по сторонам у клетки внутри прямоугольной сетки обычно четыре соседа; если учитываются диагонали, их становится восемь. Выбор влияет на то, как быстро и в каких направлениях передаётся воздействие. Например, включение диагоналей позволяет процессу распространяться по сетке не только горизонтально и вертикально.
Правило перехода вычисляет новое состояние клетки по её текущему состоянию и состояниям соседей. В простом случае оно может учитывать число соседей с заданным состоянием: например, если таких соседей не меньше двух, клетка меняет состояние. Правило должно быть определено для всех допустимых сочетаний, иначе для некоторых клеток нельзя будет выполнить следующий шаг. Отдельно учитывают граничные клетки, у которых часть соседей находится за пределами сетки.
Чтобы смоделировать развитие системы, правила применяют снова и снова: конфигурация после одного шага становится исходной для следующего. Обычно сначала вычисляют новые состояния всех клеток по одной и той же старой конфигурации, а затем записывают их одновременно. Такая синхронность важна: при последовательном изменении клеток более поздние вычисления опирались бы уже на обновлённые данные, и результат зависел бы от порядка обхода. После нескольких шагов можно сравнить получившиеся конфигурации и проследить динамику процесса.
| Элемент модели | Что задаётся | Для чего используется |
|---|---|---|
| Сетка и размер ячейки | Разбиение области и детализация | Определяет, какие участки различаются в модели |
| Состояния клеток | Допустимые характеристики участков | Хранит сведения о каждом участке |
| Начальная конфигурация | Состояние всех клеток в начале | Задаёт исходные условия процесса |
| Правило определения соседей | Клетки, взаимодействующие с выбранной | Определяет, откуда поступает влияние |
| Правило перехода | Способ вычисления нового состояния | Описывает изменение клеток |
| Шаг моделирования | Порядок обновления конфигурации | Позволяет проследить развитие системы |
Таблицу удобно использовать как проверочный список при построении модели: у каждого элемента должна быть задана конкретная характеристика. Если для клетки нельзя определить соседей или вычислить новое состояние, описание модели неполно. Сначала задают сетку и исходные состояния, затем правила и порядок шагов.
Задача 1. Клетка меняет состояние на «занято», если среди её соседей по сторонам занятых не меньше двух; иначе становится «свободной». Нужно перечислить соседей центральной клетки и определить её новое состояние, если заняты левый и верхний соседи. Решение:
Ответ: соседи — клетки сверху, снизу, слева и справа; новое состояние — «занято».
Задача 2. В клеточном автомате «Жизнь» клетка с тремя живыми соседями рождается, а живая клетка сохраняется при двух или трёх живых соседях. Нужно выполнить один шаг для небольшой конфигурации. Решение:
Ответ: новая конфигурация состоит из клеток, отмеченных по этим условиям; конкретный рисунок результата зависит от заданного начального расположения клеток.
Задача 3. Процесс распространяется на соседние клетки. Требуется смоделировать несколько шагов, а затем сравнить варианты с разными размерами ячейки или соседством. Решение:
Ответ: результат получают последовательным обновлением; различия показывают, насколько на модель влияют размер ячейки и выбранное соседство.
Первая ошибка — считать соседями только клетки по сторонам, хотя условие включает диагонали. Так поступают, потому что привычное окружение клетки часто представляют как четыре направления. Перед подсчётом соседей выпишите или нарисуйте именно заданную окрестность и проверьте, сколько клеток в неё входит.
Вторая ошибка — обновлять клетки по очереди, используя уже изменённые состояния. Это кажется удобным, но меняет исходные данные для следующих вычислений и делает результат зависимым от порядка обхода. Проверка: для каждого шага храните отдельную старую и новую конфигурации, а переход вычисляйте только по старой.
Третья ошибка — не оговаривать поведение клеток на границе сетки. У них может быть меньше соседей, поэтому правило, рассчитанное для внутренней клетки, нельзя применять автоматически. Проверьте, задано ли условие для выхода за край, периодической границы или отсутствующих соседей, и используйте один выбранный вариант последовательно.
Четвёртая ошибка — считать сеточную модель точным описанием реальности. Сетка и правила упрощают исходный процесс, а крупная ячейка или неподходящее соседство могут изменить картину. Чтобы проверить себя, укажите допущения модели и сравните результаты при разумном изменении размера ячейки или правил.
Для работы с сеточными моделями нужны представления о моделировании, алгоритмах и таблицах или двумерных массивах: состояние клетки удобно хранить в элементе массива, а переход описывать алгоритмом. Клеточные автоматы применяют для процессов с локальными взаимодействиями, например распространения огня или эпидемии. Поэтому тема связывает компьютерное моделирование с обработкой двумерных данных и помогает переводить правила реального процесса в вычислительную процедуру.
Чем сеточная модель отличается от обычного рисунка на клетчатой бумаге?
В рисунке клетки служат только для удобства изображения, а в модели каждой клетке назначено состояние и задан смысл. Кроме того, сеточная модель может содержать правила, по которым состояния меняются от шага к шагу. Поэтому её можно использовать для вычислений и имитации процесса.
Как определить, какие клетки считать соседними?
Это задают в условии модели: например, соседями считают клетки, имеющие общую сторону, или клетки по сторонам и диагоналям. Выбор должен соответствовать тому, как предполагается взаимодействие элементов. Затем одно и то же определение применяют ко всем клеткам.
Почему при обновлении клеток нельзя бездумно использовать уже изменённые состояния?
Если менять клетки по очереди и учитывать уже обновлённые, поздние клетки получат другие данные, чем ранние. Тогда результат будет зависеть от порядка обхода сетки. Обычно сначала вычисляют новое состояние для каждой клетки по исходной конфигурации, а затем заменяют все состояния одновременно.
Что делать с клетками на границе сетки?
Нужно заранее выбрать правило для границ: например, считать пространство за сеткой пустым, запретить выход за край или соединить противоположные стороны. Без такого соглашения у граничных клеток окажется разное число соседей или правило для них будет неопределённым. Выбранный вариант следует применять на каждом шаге.
Как выбор размера ячейки влияет на точность модели?
Мелкие ячейки дают более подробное описание области, но требуют больше вычислений и исходных данных. Крупные упрощают модель и могут скрыть локальные особенности процесса. Поэтому размер выбирают с учётом цели моделирования, а влияние выбора проверяют сравнением результатов.
§ 68. Сеточные модели
