Натюрморт (клеточный автомат)
В «Игре жизни» Конвея и других клеточных автоматах натюрморт — это образец, не меняющийся от поколения к поколению. Этот термин пришел из мира искусства, где натюрморт или фотография изображают неодушевленную сцену. В клеточных автоматах натюрморт можно представить как осциллятор с единичным периодом. [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 | Корабельный шпал [6] |
| 13 | 240 | 110 | |
| 14 | 619 | 279 | Би-буханка [7] |
| 15 | 1,353 | 620 | |
| 16 | 3,286 | 1,645 | |
| 17 | 7,773 | 4,067 | |
| 18 | 19,044 | 10,843 | |
| 19 | 45,759 | 27,250 | Пожиратель 2 [8] |
| 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 максимально плотного натюрморта привлекла внимание как тестовый пример программирования в ограничениях . [9] [10] [11] [12] [13] В пределе бесконечно большой сетки живыми может быть не более половины ячеек плоскости. [14] Для конечных квадратных сеток можно достичь большей плотности. Например, натюрморт с максимальной плотностью в пределах квадрата 8×8 представляет собой регулярную сетку из девяти блоков с плотностью 36/64 = 0,5625. [9] Оптимальные решения известны для квадратов всех размеров. [15] Йорк-Смит предоставляет список известных шаблонов конечной максимальной плотности. [16]
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б «Натюрморт - из «Сокровищницы жизни» Эрика Вайсштейна, Калифорния» Проверено 11 июля 2024 г.
- ^ Кук, Мэтью (2003). «Теория натюрморта». Новые конструкции в клеточных автоматах . Исследования Института Санта-Фе в области наук о сложности, Oxford University Press. стр. 93–118.
- ^ Jump up to: Перейти обратно: а б с Ахим Фламменкамп. «100 лучших предметов из ясеня из игры Game of Life» . Проверено 5 ноября 2008 г.
- ^ Количество стабильных n-клеточных узоров («натюрморты») в игре Конвея «Жизнь» (последовательность A019473 в OEIS ).
- ^ Количество n-клеточных псевдонатюрмортов в игре Конвея «Жизнь» (последовательность A056613 в OEIS ).
- ^ «Шпиль — из LifeWiki» . Проверено 11 июля 2024 г.
- ^ «Полубулочная — из LifeWiki» . Проверено 11 июля 2024 г.
- ^ «Пожиратель 2 — из LifeWiki» . Проверено 11 июля 2024 г.
- ^ Jump up to: Перейти обратно: а б Бош, РА (1999). «Целочисленное программирование и игра Конвея в жизнь». Обзор СИАМ . 41 (3): 594–604. Бибкод : 1999SIAMR..41..594B . дои : 10.1137/S0036144598338252 . .
- ^ Бош, РА (2000). «Стабильные закономерности максимальной плотности в вариантах игры Конвея в жизнь». Письма об исследованиях операций . 27 (1): 7–11. дои : 10.1016/S0167-6377(00)00016-X . .
- ^ Смит, Барбара М. (2002). «Двойной графический перевод задачи из «Жизни» ». Принципы и практика программирования с ограничениями - CP 2002 . Конспекты лекций по информатике. Том. 2470. Шпрингер-Верлаг. стр. 89–94. дои : 10.1007/3-540-46135-3_27 . .
- ^ Босх, Роберт; Трик, Майкл (2004). «Программирование ограничений и гибридные формулировки для трех проектов жизни». Анналы исследования операций . 130 (1–4): 41–56. дои : 10.1023/B:ANOR.0000032569.86938.2f . S2CID 27359250 . .
- ^ Ченг, Кенил С.К.; Яп, Роланд ХК (2006). «Применение специальных глобальных ограничений с ограничением регистра к натюрморту». Ограничения . 11 (2–3): 91–114. дои : 10.1007/s10601-006-8058-9 . S2CID 8241518 . .
- ^ Элкис, Ноам Д. (1998). «Проблема плотности натюрморта и ее обобщения». Влияние Вороного на современную науку, Книга I. Учеб. Инст. Математика. Нат. акад. наук. Украина, вып. 21. С. 228–253. arXiv : math.CO/9905194 .
- ^ Чу, Джеффри; Стаки, Питер Дж. (1 июня 2012 г.). «Полное решение проблемы натюрморта максимальной плотности» . Искусственный интеллект . 184–185: 1–16. дои : 10.1016/j.artint.2012.02.001 .
- ^ Нил Йорк-Смит. «Натюрморт максимальной плотности» . Центр искусственного интеллекта . НИИ Интернешнл .