Натюрморт (клеточный автомат)
В «Игре жизни» Конвея и других клеточных автоматах натюрморт — это узор, который не меняется от одного поколения к другому. Термин происходит из мира искусства, где натюрморт или фотография изображают неодушевленную сцену. В клеточных автоматах натюрморт можно представить как осциллятор с единичным периодом. [1]
Классификация
Псевдонатюрморт состоит из двух или более смежных островов ( связанных компонентов ), которые можно разделить (по отдельности или в виде наборов) на не взаимодействующие части, которые также являются натюрмортами . Это сравнимо со строгим натюрмортом , который не может быть разделен таким образом. Строгий натюрморт может иметь только один остров или несколько островов, стабильность которых зависит друг от друга и поэтому не может быть разложена. Различие между ними не всегда очевидно, поскольку строгий натюрморт может иметь несколько связанных компонентов, каждый из которых необходим для его стабильности. Однако определить, является ли образец натюрморта строгим натюрмортом или псевдонатюрмортом, можно за полиномиальное время .путем поиска циклов в ассоциированном кососимметричном графе . [2]
Примеры
В «Игре жизни» Конвея много естественных натюрмортов . Случайный начальный узор оставит после себя много мусора, содержащего маленькие осцилляторы и большое разнообразие натюрмортов.
Самый распространенный натюрморт (т. е. тот, который, скорее всего, будет создан из случайного начального состояния) — это блок . [3] Пара блоков, поставленных бок о бок (или библок ) — простейший псевдонатюрморт. Блоки используются в качестве компонентов во многих сложных устройствах, например, в планерной пушке Госпер .
 Блокировать |  Би-блок |
Вторым по распространенности натюрмортом является улей (или улей ). [3] Ульи часто создаются наборами (не взаимодействующими) по четыре штуки в так называемой медовой ферме .
 Улей |  Медовая ферма |
Третьим по распространенности натюрмортом является каравай . [3] Буханки часто встречаются вместе в паре, известной как двойная буханка . Сами двойные буханки часто создаются в дополнительном (невзаимодействующем) соединении, известном как пекарня . Две пекарни могут очень редко располагаться рядом друг с другом, образуя набор из четырех буханок, известных как тетрабуханка , вместе с еще двумя двойными буханками.
 Буханка |  Би-батон |  Пекарня |
Ванна состоит из четырех живых клеток, расположенных в форме ромба вокруг центральной мертвой клетки. Размещение дополнительной живой клетки по диагонали к центральной ячейке дает еще один натюрморт, известный как лодка . Размещение еще одной живой клетки на противоположной стороне дает еще один натюрморт, известный как корабль . Кадку , лодку или корабль можно расширить, добавив пару живых ячеек, чтобы получить соответственно баржу , баркас или баркас . Это расширение можно повторять бесконечно, чтобы получить произвольно большие структуры.
 Слева направо: кадка, баржа, баржа и т. д . |
 Слева направо: лодка, баркас и т.д... |
 Слева направо: корабль, баркас и т.д... |
Пару лодок можно объединить, чтобы получился еще один натюрморт, известный как галстук-лодочка (каламбур на галстуке -бабочке , который внешне напоминает). Точно так же пара кораблей может быть объединена в галстук корабля .
 Галстук-лодочка |  Корабельный галстук |
Едоки
Натюрморты можно использовать для изменения или уничтожения других объектов. Натюрморт называется пожирателем , когда он может быть использован для поглощения какого-либо другого рисунка (часто планера , космического корабля или обломков более сложной реакции) и возвращается в исходное состояние после столкновения. Существует множество примеров, наиболее примечательным из которых является рыболовный крючок (также известный как пожиратель 1 ), способный поглощать несколько типов космических кораблей. Аналогичным устройством является рефлектор', который изменяет направление приближающегося космического корабля. Осцилляторы с похожими свойствами также могут называться пожирателями или отражателями, но их сложнее применять, поскольку они должны быть синхронизированы с модифицируемым ими паттерном. С другой стороны, пожиратели натюрмортов и отражатели работают правильно независимо от времени изменения модели, если последовательные реакции происходят с достаточным временным интервалом, позволяющим пожирателю или отражателю восстановить свою первоначальную форму.
перечисление
Количество строгих и псевдонатюрмортов в «Игре жизни» Конвея, существующих для данного количества живых клеток, было задокументировано до значения 34 (последовательности A019473 и A056613 соответственно в Онлайн -энциклопедии целочисленных последовательностей ( OEIS). 4] [5]
| Живые клетки | Строгие натюрморты | Псевдо натюрморты | Примеры [1] |
|---|---|---|---|
| 1 | 0 | 0 | |
| 2 | 0 | 0 | |
| 3 | 0 | 0 | |
| 4 | 2 | 0 | Блок, ванна |
| 5 | 1 | 0 | Лодка |
| 6 | 5 | 0 | Баржа, улей, перевозчик, корабль, змея |
| 7 | 4 | 0 | Рыболовный крючок, буханка, длинная лодка, питон |
| 8 | 9 | 1 | Каноэ, манго, длинная баржа, пруд |
| 9 | 10 | 1 | Шляпа, интегральный знак |
| 10 | 25 | 7 | Блок на столе, галстук-лодочка, петля |
| 11 | 46 | 16 | |
| 12 | 121 | 55 | Корабельный галстук [ нужна ссылка ] |
| 13 | 240 | 110 | |
| 14 | 619 | 279 | Би-хлеб [ нужна ссылка ] |
| 15 | 1353 | 620 | |
| 16 | 3286 | 1645 | |
| 17 | 7773 | 4067 | |
| 18 | 19 044 | 10 843 | |
| 19 | 45 759 | 27 250 | Пожиратель 2 [ нужна ссылка ] |
| 20 | 112 243 | 70 637 | |
| 21 | 273 188 | 179 011 | |
| 22 | 672 172 | 462 086 | |
| 23 | 1 646 147 | 1 184 882 | |
| 24 | 4 051 732 | 3 069 135 | |
| 25 | 9 971 377 | 7 906 676 | |
| 26 | 24 619 307 | 20 463 274 | |
| 27 | 60 823 008 | 52 816 265 | |
| 28 | 150 613 157 | 136 655 095 | |
| 29 | 373 188 952 | 353 198 379 | |
| 30 | 926 068 847 | 914 075 620 | |
| 31 | 2 299 616 637 | 2 364 815 358 | |
| 32 | 5 716 948 683 | 6 123 084 116 | |
| 33 | 14 223 867 298 | 15 851 861 075 | |
| 34 | 35 422 864 104 | 41 058 173 683 |
Плотность
Проблема подбора области n×n с максимально плотным натюрмортом привлекла внимание как тестовый пример для программирования в ограничениях . [6] [7] [8] [9] [10] В пределе бесконечно большой сетки живыми могут быть не более половины ячеек плоскости. [11] Для конечных квадратных сеток может быть достигнута большая плотность. Например, натюрморт максимальной плотности в квадрате 8×8 представляет собой регулярную сетку из девяти блоков с плотностью 36/64 = 0,5625. [6] Оптимальные решения известны для квадратов всех размеров. [12] Yorke-Smith предоставляет список известных конечных шаблонов максимальной плотности. [13]
использованная литература
- ^ a b «Натюрморт - из Сокровищницы жизни Эрика Вайсштейна, Калифорния» Проверено 24 января 2009 г. .
- ^ Кук, Мэтью (2003). «Теория натюрморта». Новые конструкции в клеточных автоматах . Исследования Института Санта-Фе в области сложных наук, издательство Оксфордского университета. стр. 93–118.
- ^ a b c Ахим Фламменкамп. «100 лучших пепельных объектов Game-of-Life» . Проверено 5 ноября 2008 г. .
- ^ Количество стабильных n-клеточных паттернов («натюрморты») в игре Конвея «Жизнь» (последовательность A019473 в OEIS ).
- ↑ Количество псевдонатюрмортов с n ячейками в игре Конвея «Жизнь» (последовательность A056613 в OEIS ).
- ^ a b Bosch, RA (1999). «Целочисленное программирование и игра жизни Конвея» . Обзор СИАМ . 41 (3): 594–604. Бибкод : 1999SIAMR..41..594B . doi : 10.1137/S0036144598338252 ..
- ^ Бош, Р.А. (2000). «Стабильные паттерны максимальной плотности в вариантах игры Конвея в жизнь». Письма об исследованиях операций . 27 (1): 7–11. doi : 10.1016/S0167-6377(00)00016-X ..
- ^ Смит, Барбара М. (2002). «Двойной граф перевода проблемы в« Жизни » ». Принципы и практика программирования с ограничениями — CP 2002 . Конспект лекций по информатике. 2470 . Спрингер-Верлаг. стр. 89–94. doi : 10.1007/3-540-46135-3_27 ..
- ^ Босх, Роберт; Уловка, Майкл (2004). «Программирование с ограничениями и гибридные формулировки для трех дизайнов Life». Анналы исследования операций . 130 (1–4): 41–56. doi : 10.1023/B:ANOR.0000032569.86938.2f ..
- ^ Ченг, Кенил CK; Яп, Роланд ХК (2006). «Применение специальных глобальных ограничений с ограничением случая к натюрморту». Ограничения . 11 (2–3): 91–114. doi : 10.1007/s10601-006-8058-9 ..
- ^ Элкис, Ноам Д. (1998). «Проблема плотности натюрморта и ее обобщения». Влияние Вороного на современной науке, Книга I . проц. Инст. Мат. Нац. акад. науч. Украина, вып. 21. С. 228–253. arXiv : math.CO/9905194 .
- ^ Чу, Джеффри; Стаки, Питер Дж. (01.06.2012). «Полное решение проблемы натюрморта с максимальной плотностью» . Искусственный интеллект . 184–185: 1–16. doi : 10.1016/j.artint.2012.02.001 .
- ^ Нил Йорк-Смит. «Натюрморт максимальной плотности» . Центр искусственного интеллекта . НИИ Интернэшнл .
- Паттерны клеточного автомата
