В игре Конвея жизни и других клеточных автоматов , А еще жизнь является образцом , который не меняется от одного поколения к другому. Термин пришел из мира искусства, где натюрморт или фотография изображают неодушевленную сцену. В клеточных автоматах натюрморт можно рассматривать как осциллятор с единичным периодом. [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 | 1,353 | 620 | |
| 16 | 3 286 | 1,645 | |
| 17 | 7,773 | 4 067 | |
| 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] Йорк-Смит приводит список известных моделей конечной максимальной плотности. [13]
Ссылки [ править ]
- ^ Б «Натюрморт - от Эрика Weisstein сокровищ Жизни CA» Получен 2009-01-24 .
- ^ Кук, Мэтью (2003). «Теория натюрморта». Новые конструкции в клеточных автоматах . Исследования Института Санта-Фе по наукам о сложности, Oxford University Press. С. 93–118.
- ^ a b c Ахим Фламменкамп. «100 лучших объектов ясеня из игры в жизнь» . Проверено 5 ноября 2008 .
- ↑ Число устойчивых n-клеточных узоров («натюрмортов») в « Играх жизни» Конвея (последовательность A019473 в OEIS ).
- ↑ Число n-клеточных псевдотюрмортов в « Играх жизни» Конвея (последовательность A056613 в OEIS ).
- ^ a b Bosch, RA (1999). «Целочисленное программирование и игра жизни Конвея» . SIAM Обзор . 41 (3): 594–604. Bibcode : 1999SIAMR..41..594B . DOI : 10.1137 / S0036144598338252 ..
- Перейти ↑ Bosch, RA (2000). «Стабильные паттерны максимальной плотности в вариантах игры Жизни Конвея». Письма об исследованиях операций . 27 (1): 7–11. DOI : 10.1016 / S0167-6377 (00) 00016-X ..
- ^ Смит, Барбара М. (2002). «Двойной графовый перевод проблемы из« Жизни » ». Принципы и практика программирования с ограничениями - CP 2002 . Конспект лекций по информатике. 2470 . Springer-Verlag. С. 89–94. DOI : 10.1007 / 3-540-46135-3_27 ..
- ^ Босх, Роберт; Уловка, Майкл (2004). «Ограниченное программирование и гибридные формулы для трех жизненных проектов». Анналы исследований операций . 130 (1–4): 41–56. DOI : 10,1023 / Б: ANOR.0000032569.86938.2f ..
- ^ Ченг, Кенил СК; Яп, Роланд ХК (2006). «Применение специальных глобальных ограничений с ограничением case к натюрмортам». Ограничения . 11 (2–3): 91–114. DOI : 10.1007 / s10601-006-8058-9 ..
- ^ Elkies, Ноам D. (1998). «Проблема плотности натюрморта и ее обобщения». Влияние Вороного на современной науке, Книга I . Proc. Inst. Математика. Nat. Акад. Sci. Украина, т. 21. С. 228–253. arXiv : math.CO/9905194 .
- ^ Чу, Джеффри; Стаки, Питер Дж. (2012-06-01). «Полное решение проблемы натюрморта максимальной плотности» . Искусственный интеллект . 184–185: 1–16. DOI : 10.1016 / j.artint.2012.02.001 .
- ^ Нил Йорк-Смит. «Натюрморт максимальной плотности» . Центр искусственного интеллекта . SRI International .
