Zátiší (mobilní automat) - Still life (cellular automaton)
v Conwayova hra o život a další mobilní automaty, a stálý život je vzor, který se nemění z jedné generace na druhou. Termín pochází ze světa umění, kde a stálý život malba nebo fotografie zobrazuje neživou scénu. V celulárních automatech lze zátiší považovat za oscilátor s jednotkovým obdobím.[1]
Klasifikace
A pseudo zátiší skládá se ze dvou nebo více sousedních ostrovů (připojené komponenty ), které lze rozdělit (jednotlivě nebo jako sady) na neinteragující části, které jsou také zátiší. To je srovnatelné s a přísné zátiší, které nemusí být takto rozděleny na oddíly. Přísné zátiší může mít pouze jeden ostrov, nebo může mít několik ostrovů, které na sobě závisí stabilita, a proto jej nelze rozložit. Rozdíl mezi nimi není vždy zřejmý, protože přísné zátiší může mít několik připojených komponent, z nichž všechny jsou potřebné pro jeho stabilitu. Je však možné určit, zda je vzorem zátiší přísné zátiší nebo pseudo zátiší polynomiální čas hledáním cyklů v přidruženém šikmo symetrický graf.[2]
Příklady
Existuje mnoho přirozeně se vyskytujících zátiší Conwayova hra o život. Náhodný počáteční vzor po sobě zanechá velké množství úlomků, které obsahují malé množství oscilátory a velké množství zátiší.
Nejběžnějším zátiší (tj. Nejpravděpodobnějším generovaným z náhodného počátečního stavu) je blok.[3] Dvojice bloků umístěných vedle sebe (nebo bi-blok) je nejjednodušší pseudo zátiší. Bloky se používají jako součásti mnoha složitých zařízení, příkladem je Gosper kluzák.
 Blok |  Bi-blok |
Druhým nejběžnějším zátiší je úl (nebo úl).[3] Úly jsou často vytvářeny v (neinteragujících) sadách čtyř, ve formaci známé jako a medová farma.
 Úl |  Medová farma |
Třetím nejběžnějším zátiší je bochník.[3] Chleby se často nacházejí společně v páru známém jako a biftek. Samotné bochníky jsou často vytvářeny v dalším (neinteragujícím) párování známém jako a pekařství. Dvě pekárny se mohou extrémně zřídka tvořit vedle sebe a vytvořit soubor čtyř chlebů známých jako tetraloaf vedle dalších dvou biftek.
 Bochník |  Bi-bochník |  Pekařství |
A vana se skládá ze čtyř živých buněk umístěných ve tvaru kosočtverce kolem centrální mrtvé buňky. Umístění další živé buňky diagonálně do centrální buňky dává další zátiší, známé jako loď. Umístěním další živé buňky na opačnou stranu získáte ještě další zátiší, známé jako a loď. Vanu, loď nebo loď lze rozšířit přidáním dvojice živých buněk, čímž získáte bárka, a dlouhý člun nebo a dlouhá loď resp. Toto rozšíření lze opakovat neomezeně dlouho, aby vznikly libovolně velké struktury.
 Zleva: vana, člun, dlouhý člun atd. |
 Zleva: člun, dlouhý člun atd. |
 Zleva: loď, dlouhá loď atd. |
Dvojice lodí může být kombinována, aby poskytla další zátiší známé jako lodní kravata (slovní hříčka motýlek, kterému se povrchně podobá). Podobně lze dvojici lodí kombinovat do lodní kravata.
 Kravata na člun |  Kravata na lodi |
Jedlíci
Zátiší lze použít k úpravě nebo zničení jiných objektů. Zátiší se nazývá jedlík když to může být použito k absorbování nějakého jiného vzoru (často a kluzák, kosmická loď nebo úlomky ze složitější reakce) a po srážce se vrátí do původního stavu. Existuje mnoho příkladů, z nichž nejpozoruhodnější je háček na ryby (Také známý jako jedlík 1), který je schopen absorbovat několik typů kosmických lodí. Podobné zařízení je reflektor, který mění směr přicházející kosmické lodi. Oscilátory s podobnými vlastnostmi mohou být také nazývány jedlíci nebo reflektory, ale je obtížnější je použít, protože musí být synchronizovány se vzorem, který upravují. Jedlíci a reflektory zátiší na druhé straně fungují správně bez ohledu na načasování vzoru, který upravují, pokud dojde k postupným reakcím s dostatečným časovým odstupem, aby umožnil jedlíkovi nebo reflektoru obnovit svůj původní tvar.
Výčet
Počet přísných a pseudo zátiší v Conwayově hře o život existujících pro daný počet živých buněk byl zdokumentován až na hodnotu 34 (sekvence A019473 a A056613 respektive v OEIS ).[4][5]
| Živé buňky | Přísné zátiší | Pseudo zátiší | Příklady[1] |
|---|---|---|---|
| 1 | 0 | 0 | |
| 2 | 0 | 0 | |
| 3 | 0 | 0 | |
| 4 | 2 | 0 | Blok, vana |
| 5 | 1 | 0 | Loď |
| 6 | 5 | 0 | Barge, úl, dopravce, loď, had |
| 7 | 4 | 0 | Háček na ryby, bochník, dlouhý člun, krajta |
| 8 | 9 | 1 | Kánoe, mango, dlouhý člun, rybník |
| 9 | 10 | 1 | Klobouk, integrální znamení |
| 10 | 25 | 7 | Blok na stole, vázanka, smyčka |
| 11 | 46 | 16 | |
| 12 | 121 | 55 | Kravata[Citace je zapotřebí ] |
| 13 | 240 | 110 | |
| 14 | 619 | 279 | Bi-bochník[Citace je zapotřebí ] |
| 15 | 1,353 | 620 | |
| 16 | 3,286 | 1,645 | |
| 17 | 7,773 | 4,067 | |
| 18 | 19,044 | 10,843 | |
| 19 | 45,759 | 27,250 | Eater 2[Citace je zapotřebí ] |
| 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 |
Hustota
Problém osazení oblasti n × n s maximálně hustým zátiší přitahoval pozornost jako testovací případ programování omezení.[6][7][8][9][10]V limitu nekonečně velké mřížky může být živá maximálně polovina buněk v rovině.[11]U konečných čtvercových mřížek lze dosáhnout větší hustoty. Například zátiší s maximální hustotou v rámci čtverce 8 × 8 je pravidelná mřížka devíti bloků s hustotou 36/64 = 0,5625.[6] Pro čtverce všech velikostí jsou známa optimální řešení.[12] Yorke-Smith poskytuje seznam známých konečných vzorů maximální hustoty.[13]
Reference
- ^ A b „Still Life - from Eric Weisstein's Treasure Trove of Life C.A.“ Citováno 2009-01-24.
- ^ Cook, Matthew (2003). "Teorie zátiší". Nové konstrukce v celulárních automatech. Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press. 93–118.
- ^ A b C Achim Flammenkamp. „Top 100 předmětů Ash-of-Life Ash“. Citováno 2008-11-05.
- ^ Počet stabilních n-celulárních vzorů („zátiší“) v Conwayově hře o život (sekvence A019473 v OEIS ).
- ^ Počet n-celled pseudo-zátiší v Conwayově hře o život (sekvence A056613 v OEIS ).
- ^ A b Bosch, R. A. (1999). „Programování celého čísla a Conwayova hra o život“. Recenze SIAM. 41 (3): 594–604. Bibcode:1999SIAMR..41..594B. doi:10.1137 / S0036144598338252..
- ^ Bosch, R. A. (2000). "Stabilní vzory s maximální hustotou ve variantách Conwayovy hry o život". Dopisy o operačním výzkumu. 27 (1): 7–11. doi:10.1016 / S0167-6377 (00) 00016-X..
- ^ Smith, Barbara M. (2002). „Duální grafický překlad problému v„ životě “'". Principy a praxe programování omezení - CP 2002. Přednášky z informatiky. 2470. Springer-Verlag. str. 89–94. doi:10.1007/3-540-46135-3_27..
- ^ Bosch, Robert; Trik, Michael (2004). "Omezení programování a hybridní formulace pro tři návrhy Life". Annals of Operations Research. 130 (1–4): 41–56. doi:10.1023 / B: ANOR.0000032569.86938.2f..
- ^ Cheng, Kenil C. K .; Yap, Roland H. C. (2006). "Uplatnění globálních omezení ad hoc s omezením případu na zátiší". Omezení. 11 (2–3): 91–114. doi:10.1007 / s10601-006-8058-9..
- ^ Elkies, Noam D. (1998). "Problém hustoty zátiší a jeho zobecnění". Vliv Voronoi na moderní vědu, kniha I. Proc. Inst. Matematika. Nat. Acad. Sci. Ukrajina, roč. 21. s. 228–253. arXiv:math.CO/9905194.
- ^ Chu, Geoffrey; Stuckey, Peter J. (06.06.2012). „Kompletní řešení problému zátiší s maximální hustotou“. Umělá inteligence. 184–185: 1–16. doi:10.1016 / j.artint.2012.02.001.
- ^ Neil Yorke-Smith. „Maximální hustota zátiší“. Centrum umělé inteligence. SRI International.