|
Приветствую вас, уважаемые читатели!
В этом выпуске я расскажу о клеточных автоматах (cellular automaton).
Нейман сформулировал идею клеточных автоматов в 40-х годах XX века.
Клеточные автоматы были задуманы, как "универсальная вычислительная среда
для построения, анализа и сравнения характеристик алгоритмов" (cellular
automata machine).
Представьте себе поле, разделённое равномерной сеткой.
В идеале это поле должно быть бесконечно. Каждая ячейка может нахоиться
в n -состояниях. Причём в зависимости от состояния соседних клеток она может
дискретно менять своё состояние.
[ ][N][ ]
[W][+][E]
[ ][S][ ]
Очевидно, что можно постулировать число клеток, которые оказывают влияние,
на "центральную ячейку". Так на клетку могут влиять только четыре клетки,
с которыми она граничит сторонами (т.е. Север, Восток, Юг, Запад) это
"окрестность фон Неймана". Если на ячейку влияют ещё диагональные клетки
(Северо-Восток,Юго-Восток,.. etc.) это полная окрестность клетки носит название
"окрестность Мура".
| Note: в общем случае пространство
n - мерное. Обычное поле из клеток - тоже упрощение; ячека
может иметь другое количество граней => число соседей тоже различно.
|
Сфера применения клеточных автоматов необычно широка: от "крестиков-ноликов"
(tic-tac-toe) до моделирования фазовах переходов в физических системах и
искусственного интеллекта(Artificial Intelligence).
| Note: крестики-нолики это уже не только
обычные девять клеток; так у меня в университете происходят баталии
на бесконечной плоскости, с выстраиванием пяти символов в ряд . Так
же большой популярностью пользуются крестики-нолики на полубесконечной
плоскости, когда символы ставятся от границы, как в тетрисе. |
Cледующий выпуск о самом известном клеточном автомате.
Счастливо!
|