Asetelma (solukkoautomaatin konfiguraatio)

Asetelma on konfiguraatioiden luokka Lifessa , Conwayn mallissa solukkoautomaatista .

Kuvaus

Yleisimmässä muotoilussa käsite "asetelma" tarkoittaa samaa kuin "vakaa hahmo" - "Elämän" tai muun soluautomaatin konfiguraatiota, joka ei muutu evoluutioprosessissa [nb 1] . Toisin sanoen asetelma on 1 [1] [2] [3] jakson oskillaattori .

Terminologia: asetelmat ja pseudo-asetelmat

On useita termejä, jotka ovat merkitykseltään läheisiä ja tarkoittavat konfiguraatioita, jotka eivät muutu evoluutioprosessissa ( konfiguraatiot, jotka ovat heidän omia vanhempiaan ). Niiden väliset erot liittyvät seuraaviin kysymyksiin annettuihin kysymyksiin:

  1. Onko asetelma, joka koostuu kahdesta itsenäisestä asetelmasta (esimerkiksi kahdesta riittävän suurella etäisyydellä toisistaan) koostuva kokoonpano asetelmaksi? [neljä]
  2. Onko asetelma konfiguraatio, joka koostuu kahdesta osasta, joista jompikumpi voidaan irrottaa siten, että toinen osa pysyy oman itsensä vanhempana?

Nykyiset sanakirjat ja verkkotietosanakirjat [3] [5] [6] [7] tarjoavat seuraavat määritelmät:

"Vakauden" tarkka määritelmä on kiinnostava asetelmien luetteloimisen yhteydessä: esimerkiksi annettujen määritelmien mukaan "Elämässä" on ääretön määrä stabiileja kokoonpanoja, joiden koko on 8 (eli koostuvat 8 elävästä solusta). , koska lohkopari millä tahansa etäisyydellä toisistaan ​​on kestävä; rajoitetun kokoisten asetelmien lukumäärää pidetään kuitenkin rajallisena [5] [6] [7] .

Pseudo-asetelu "Elämässä". Yhden saaren poistaminen ei vaikuta toisen saaren vakauteen.
"Tiukka" asetelma. Kunkin saaren vakaus riippuu toisen saaren saatavuudesta.

Asetelmien ja pseudo-asetelmien lukumäärä, joka on enintään 24 solua, tunnetaan [7] [10] [11] .

Vakaan konfiguraation tyypin (asetelu, pseudo-asetelu) määrittelyongelma ratkaistaan ​​polynomiajassa etsimällä syklejä yhdistetystä vinosymmetrisestä graafista [12] .

Asetelma "Elämässä"

" Elämässä " on monia luonnollisia [13] asetelmia.

Yksinkertaisia ​​esimerkkejä

Estä

Yleisin asetelma on lohko [14] [15] [16] - 2 × 2 neliön muodossa oleva konfiguraatio. Kaksi 2 × 5 -kokoiseen suorakulmioon sijoitettua lohkoa muodostavat bilohkon - yksinkertaisin pseudo-still elämää. Lohkoja käytetään rakennuspalikoina monissa monimutkaisissa laitteissa, kuten Gosper-liukutykissä [16] .

Hive

Toiseksi yleisin asetelma on mehiläispesä ( eng.  hive, mehiläispesä ). Nokkosihottuma esiintyy usein neljässä kokoonpanossa, jota kutsutaan mehiläisalueeksi ( englanniksi  hunajatila ) [14] [15] [16] .

Loaf

Kolmanneksi yleisin asetelma on leipä ( eng.  loaf ). Leivät esiintyvät usein pareittain ( englanniksi  bi-loaf ) [14] [15] [16] . Kaksoisleivät puolestaan ​​esiintyvät myös pareittain, joita kutsutaan leipomoiksi ( englanniksi  bakery ) [17] .

Laatikot, proomut, veneet, laivat

Laatikko ( eng.  tub ) koostuu neljästä elävästä solusta von Neumannin naapurustossa keskikuolleessa solussa. Yhden elävän solun lisääminen diagonaalisesti keskisoluun muuttaa laatikon veneeksi ( englantilainen  vene ) ja toisen solun lisääminen symmetrisesti laivaksi ( englantilainen laiva ) [ 18] . Näiden kolmen kokoonpanon luonnollinen venymä antaa proomun ( englanniksi proomu ), pitkän veneen ( englanniksi long-boat ) ja pitkän laivan ( englanniksi long-ship ). Pidentämistä voidaan jatkaa loputtomiin [5] [6] [15] [16] .     

Kahdesta veneestä voit tehdä toisen asetelman - venejousen ( englantilainen  boat tie ) ja kahdesta laivasta - laivan keulan ( englantilainen  laivatie ) [5] [6] .

Muut asetelmat

  • Kanootti

  • Lentotukialus

  • Integroitu merkki

  • Mango / sikari

  • Lampi

  • Käärme

Devourers and Reflectors

Asetelmia voidaan käyttää muiden esineiden muokkaamiseen tai tuhoamiseen. Syöjä pystyy tuhoamaan avaruusaluksen ja  toipumaan reaktiosta. Heijastin ( englanniksi reflektor ) muuttaa avaruusaluksen tuhoamisen sijaan lentonsa suuntaa.  

Heijastimien ja Devourersin ei tarvitse olla asetelmia.

  • Syöjät

  • Fishhook / Eater-1

  • Devourer-2

Suurin tiheys

Ongelma asettaa asetelma, jossa on enimmäismäärä soluja n  ×  n -alueelle, on herättänyt ohjelmoijien huomion rajoitusohjelmointiongelmana [19] [20] [21] [22] [23] . Koska alueen koko pyrkii äärettömään, enintään 50 % soluista voi olla elossa [24] . Äärillisillä neliöalueilla voidaan saavuttaa suurempia tiheyksiä. Siten asetelman maksimitiheys 8 × 8 neliössä on 36/64 = 0,5625 - tämä tiheys saadaan yhdeksästä lohkosta koostuvan näytteen avulla [19] Neliöiden, joiden koko on 20 × 20, optimaaliset ratkaisut tunnetaan [25] ] [26] .

  • "Elämän" suurimman tiheyden asetelmat

  • 19x19

  • 20x20

Asetelmien määrä

"Elämän" asetelmien ja pseudoasetelmien määrä tunnetaan 24 solun kokoon asti [27] [28] [29] .

Elävien solujen lukumäärä Asetelmien määrä Esimerkkejä
yksi 0
2 0
3 0
neljä 2 lohko, laatikko
5 yksi vene
6 5 proomu, lentotukialus, mehiläispesä, laiva, käärme
7 neljä koukku, leipä, pitkä vene
kahdeksan 9 kanootti, mango, pitkä proomu, lampi
9 kymmenen kiinteä merkki
kymmenen 25 veneen keula
yksitoista 46
12 121 laivan keula
13 240
neljätoista 619 kaksinkertainen leipä
viisitoista 1353
16 3286
17 7773
kahdeksantoista 19044
19 45759 syöjä 2
kaksikymmentä 112243
21 273188
22 672172
23 1646147
24 4051711

Alaviitteet

  1. ↑ Katso tarkemmat määritelmät kohdasta Terminologia.

Muistiinpanot

  1. ↑ 1 2 Tasainen . Elämän sanakirja. Haettu 11. elokuuta 2013. Arkistoitu alkuperäisestä 10. helmikuuta 2013.
  2. ↑ 1 2 Vakaa (downlink) . elämän sanakirja. Haettu 11. elokuuta 2013. Arkistoitu alkuperäisestä 20. helmikuuta 2009. 
  3. ↑ 1 2 Eric Weisstein. asetelma . Life Treasure Trove CA. Haettu: 11. elokuuta 2013.  (linkki ei saatavilla)
  4. ↑ Jos vastaus tähän kysymykseen on kyllä, rajallisella määrällä soluja sisältävien asetelmien määrä on ääretön.
  5. ↑ 1 2 3 4 Nikolai Beljutšenko. Elämän sanakirja . Arkistoitu alkuperäisestä 10. lokakuuta 2012.
  6. ↑ 1 2 3 4 Stephen A. Silver. Elämän sanakirja  . Arkistoitu alkuperäisestä 26. toukokuuta 2013.
  7. ↑ 1 2 3 4 5 Asetelma . conwaylife.com. Haettu 11. elokuuta 2013. Arkistoitu alkuperäisestä 30. heinäkuuta 2013.
  8. ↑ Asetelma . Elämän sanakirja. Haettu 11. elokuuta 2013. Arkistoitu alkuperäisestä 10. helmikuuta 2013.
  9. ↑ Asetelma (linkki ei saatavilla) . elämän sanakirja. Haettu 11. elokuuta 2013. Arkistoitu alkuperäisestä 20. helmikuuta 2009. 
  10. ↑ 1 2 Pseudo-asetelu . Elämän sanakirja. Haettu 11. elokuuta 2013. Arkistoitu alkuperäisestä 6. toukokuuta 2019.
  11. ↑ 1 2 Pseudo-asetelma (linkki ei saatavilla) . elämän sanakirja. Haettu 11. elokuuta 2013. Arkistoitu alkuperäisestä 3. joulukuuta 2014. 
  12. ↑ Cook, Matthew (2003). "Asetelma teoria". Uudet rakenteet soluautomaatissa . Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press. s. 93-118.
  13. ↑ Luonnollinen näyte on kohde, joka esiintyy suhteellisen usein satunnaisen konfiguraation kehitysprosessissa.
  14. ↑ 1 2 3 Achim Flammenkamp. Game of-Life Ash -esineitä 100 parasta . Haettu 5. marraskuuta 2008. Arkistoitu alkuperäisestä 22. lokakuuta 2008.
  15. ↑ 1 2 3 4 Elämän peli (Gardner-arvostelu) . Haettu 11. elokuuta 2013. Arkistoitu alkuperäisestä 18. lokakuuta 2012.
  16. ↑ 1 2 3 4 5 Klumova I. N. Peli "Elämä"  // Kvant . - 1974. - Nro 9 . - S. 26-30 .
  17. ↑ Leipomo . Elämän sanakirja. Haettu 11. elokuuta 2013. Arkistoitu alkuperäisestä 6. toukokuuta 2019.
  18. ↑ Ei pidä sekoittaa avaruusaluksiin .
  19. ↑ 1 2 Bosch, RA Kokonaislukuohjelmointi ja Conwayn Life-peli  (määrittämätön)  // SIAM Review. - 1999. - T. 41 , nro 3 . - S. 594-604 . - doi : 10.1137/S0036144598338252 . .
  20. ↑ Bosch, RA Suurin tiheyden vakaat kuviot Conwayn Life-pelin muunnelmissa  //  Operations Research Letters : päiväkirja. - 2000. - Voi. 27 , ei. 1 . - s. 7-11 . - doi : 10.1016/S0167-6377(00)00016-X . .
  21. ↑ Smith, Barbara M. Rajoitusohjelmoinnin periaatteet ja käytännöt - CP 2002   : aikakauslehti . - Springer-Verlag, 2002. - Voi. 2470 . - s. 89-94 . - doi : 10.1007/3-540-46135-3_27 . .
  22. ↑ Bosch, Robert; Temppu, Michael. Rajoitusohjelmointi ja hybridiformulaatiot kolmelle Life-mallille  //  Annals of Operations Research : päiväkirja. - 2004. - Voi. 130 , ei. 1-4 . - s. 41-56 . - doi : 10.1023/B:ANOR.0000032569.86938.2f . .
  23. ↑ Cheng, Kenil C.K.; Yap, Roland HC Ad-hoc globaalien rajoitusten soveltaminen tapausrajoitteen kanssa asetelmiin  //  Rajoitukset : päiväkirja. - 2006. - Voi. 11 , ei. 2-3 . - s. 91-114 . - doi : 10.1007/s10601-006-8058-9 . .
  24. ↑ Elkies, Noam D. (1998). "Asetelmatiheysongelma ja sen yleistykset". Voronoin vaikutus moderniin tieteeseen, kirja I. Proc. Inst. Matematiikka. Nat. Acad. sci. Ukraina, voi. 21.s. 228-253. arXiv : math.CO/9905194 .
  25. ↑ J. Larrosa, E. Morancho ja D. Niso. Muuttujan eliminoinnin käytännön käytöstä rajoitusten optimointiongelmissa: "Asetelma" tapaustutkimuksena  //  Journal of Artificial Intelligence Research : päiväkirja. - 2005. - Voi. 23 . - s. 421-440 . Arkistoitu alkuperäisestä 16. heinäkuuta 2011.
  26. ↑ Neil Yorke-Smith. Suurin tiheys asetelma . Tekoälykeskus . SRI International. Haettu 11. elokuuta 2013. Arkistoitu alkuperäisestä 19. toukokuuta 2013.
  27. ↑ Pysyvien n-soluisten kuvioiden ("asetelmien") määrä Conwayn Life-pelissä
  28. ↑ N-soluisten pseudo-asetelujen määrä Conwayn Life-pelissä
  29. ↑ Niemiec, Mark D. Elämän asetelmia . Arkistoitu alkuperäisestä 21. tammikuuta 2013.

Ulkoiset linkit

 Conwayn Game of Life ja muut soluautomaatit
Konfigurointiluokat
Kokoonpanot
Ehdot
Muut avaruusalukset
kaksiulotteisessa hilassa
Elämänmukainen
muu
Yksiulotteinen avaruusalus
Ohjelmistot ja algoritmit
  • Golly_
  • Mirekin
  • hashlife
KA tutkijat