Генерализованные муравьи

Ссылка на источник: http://www.math.stonybrook.edu/~scott/ants/

Это дополнительный материал к статье «Дальние путешествия с моим муравьем» (Further Travels with My Ant) Дэвида Гейла, Джима Проппа, Скотта Сазерленда и Сержа Трубецкого, которая выходит в летнем выпуске «Математического интеллекта» (Mathematical Intelligencer) 1995 года. В этой статье обсуждается некоторое поведение клеточного автомата, называемого «муравей». Муравей перемещается, и в каждой «ячейке» муравей поворачивается вправо или влево в зависимости от состояния ячейки, а затем изменяет состояние ячейки в соответствии с определенными заданными строками правил.

Вкратце, «муравей» движется по бесконечной шахматной доске, каждый квадрат которой мы называем «клеткой». Каждая ячейка в плоскости помечается либо как L-ячейка, либо как R-ячейка (обычно для заполнения плоскости заполняют L-ячейки). Муравей начинается на границе между двумя клетками, и, проходя через каждую клетку, он поворачивается на 90 градусов, поворачиваясь влево в L-клетках и вправо в R-клетках, и это меняет состояние ячейка, которую он только что оставил, переключая L-ячейки на R-ячейки, и наоборот. Следование этому простому набору правил приводит к довольно сложному поведению; рисунок пути муравья чередуется между кажущимся хаосом и симметрией, и в конце концов он начинает строить «шоссе», движущееся в одном направлении.

Вышеописанный муравей (и некоторые вариации) был первоначально изучен Крисом Лэнгтоном (тогда в Институте Санта-Фе, совсем недавно соучредителем корпорации Swarm). Позже Джим Пропп обобщил муравья, считая, что каждая ячейка находится в одном из n различных состояний: у каждого муравья есть какое-то «внутреннее программирование», которое сообщает ему, поворачивать ли налево или направо, когда ячейка находится в этом состоянии. Эта «программа» может быть представлена ​​в виде строки из n Ls и Rs, а k-я буква представляет действие муравья, когда оно попадает в ячейку в состоянии k. Например, муравей Лэнгтона, описанный выше, является муравьем из 2 состояний со строкой правила LR (или в двоичном коде 10, поэтому мы называем это «муравей номер 2»). Муравей из 7 состояний со строкой правила LLRRRLR (муравей номер 98) поворачивается влево, когда он посещает ячейку в состоянии 1, 2 или 6, и вправо, когда он посещает ячейки в состоянии 3, 4, 5 или 7.

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


Фотографии некоторых состояний муравьев.

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


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

* Симулятор муравьев на основе проклятий, который добавляет вывод плитки Труше в версию Джима Проппа.
Вы можете получить исходные файлы для ant.c в zip-архиве или загрузить файлы по одному за раз.

* Интерфейс на основе X11 с использованием библиотеки виджетов Athena. (в настоящее время не производит вывод на печать).
Вы можете получить исходные файлы для Xant в zip-архиве или загрузить файлы по одному за раз.

* Java-версия Муравья Лэнгтона, (строка правил 2) от Стива Уитэма.

* Еще одна Java-версия муравья Лэнгтона (строка правила 2) от Билла Кассельмана из Университета Британской Колумбии.

* Имитатор муравьев для Microsoft Windows, написанный Эдвардом Ричардсом. Он допускает более общий набор движений муравья (несколько муравьев, движение вперед и назад, а также вправо и влево и т.д.), поэтому числовые кодировки его строк правил отличаются от тех, которые обсуждались здесь. Очень хорошая программа.

* Симулятор муравья Лангтона с двумя состояниями (Ant 2), который работает на графическом калькуляторе TI-82 (написанный Адамом Бейтин, через mbeytin@umd5.umd.edu). Не имея TI-82, я не запускал эту программу.


Для получения дополнительной информации см.

  • Д. Гейл “Трудолюбивый муравей”, математический разведчик, вып. 15, № 2 (1993), с. 54-58.
  • Д. Гейл и Дж. Пропп “Дальнейшие статьи”, Математический интеллект, том. 16, нет 1 (1994), с. 37-42.
  • Д. Гейл, Дж. Пропп, С. Сазерленд, С. Трубецкой, “Дальнейшие путешествия с моим муравьем”, Математический интеллект, том 17, № 2 3 (1995), стр. 48-56.
  • И. Петерсон, “Путешествия муравья”, Science News, том 148 нет. 18 (1995), с. 280-281.
  • Л. А. Бунимович, С. Трубецкой “Рекуррентные свойства решетчатых газовых клеточных автоматов Лоренца”, Журнал статистической физики, вып. 67 (1992), с. 289-302.
  • Дополнительные ссылки, поддержанные Сергеем Трубецким.

Leave a Reply

Your email address will not be published. Required fields are marked *