Shooter szinkronizálási probléma

A lövészek szinkronizálásának problémája a számítástechnika és a sejtautomaták elmélete területéről származik .

Először John Myhill javasolta 1957-ben, és 1962-ben adta ki (megoldással együtt) Edward Moore [2] . A név a katonák kivégzés közbeni viselkedéséhez vagy puskatisztelgéshez kapcsolódik – minden katona egyszerre lő egy jelre.

A következőképpen fogalmazódik meg: lehetséges-e úgy programozni egy véges hosszúságú egydimenziós sejtautomatát, hogy a G●●…●●● kiindulási állapotból minden cella egyidejűleg átmegy az FFF…FFF állapotba, függetlenül a a lánc hossza, ha kötelező az átmeneti szabály ●●●→● és megfelelői a láncvégekre ⌀●●→●, ●●⌀→●? Közérthető nyelven [3] :

$n \geqslant 2$ robotok ( véges automaták ) fegyverrel állnak sorban. Az automatáknak legalább három ● állapota van, G és F – „kezdeti”, „parancsnok” és „lövés”. E három mellett tetszőleges számú köztes állapotot adhat hozzá.
A robotok egy program szerint önállóan működnek, és csak láncban kommunikálnak: a dob (szinkronizáló) jelei szerint, pillanatnyi állapotuktól és két szomszéd állapotától függően új állapotba lépnek. Kivételt képeznek az extrém robotok, amelyeknek csak egy szomszédjuk van; saját programjaik vannak. $t-1$
Mindhárom programnak nem szabad semmit tennie, ha a robot és szomszédai a kezdeti állapotban vannak.
Minden robot az eredeti állapotában áll és nem csinál semmit. A szélsőbal pillanatában átkerülnek a "parancsnoki" állapotba. $t=0$
Létezik-e olyan három program (állapotkészlet és három átmeneti szabálykészlet - a parancsnok, az utánfutó és a többi robot számára), hogy bármikor egyszerre (egy dobütésre) „lövés” állapotba kerüljenek? $n$

Mivel a jel órajelenként 1 pozíció sebességgel terjed a vonal mentén (a cellaautomaták elméletében ezt "fénysebességnek" nevezik), nyilvánvaló, hogy a szinkronizálási idő a növekedéssel növekszik . $n$

Történelem

nyitott matematikai probléma

Van megoldás a nyilak öt állapotú szinkronizálásának problémájára - bármely , időben nem feltétlenül optimális? $n$

Az első megoldást erre a problémára John McCarthy és Marvin Minsky találta meg, és Edward Moore a Sequential Machines-ben publikálta.

Minimális időigényű megoldást talált 1962-ben Eiichi Goto, az MIT professzora [4] . Több ezer állapotot használ, és pontosan időegységeket igényel a robotok számára. Könnyen bebizonyítható (lásd alább), hogy nincsenek időtakarékosabb megoldások. $2n-2$ $n$

Az optimális megoldást, mindössze hat állapotot használva (beleértve a végső "lövést" is), Jacques Mazoyer találta meg 1987-ben [5] . Korábban Robert Balzer számítógépes felsorolással bizonyította, hogy nincsenek négy cellaállapotú megoldások [6] . Peter Sanders később rájött, hogy Balzer keresési eljárása hiányos volt, de miután kijavította az eljárást, ugyanazt az eredményt kapta. A 2010 -es években több száz különböző, hat állapotú megoldás született evolúciós felsorolással [7] . Még mindig nem ismert, hogy létezik-e öt sejtállapotú megoldás.

Megpróbálják megdönteni a rekordot az átmeneti szabályok számában is (beleértve a parancsnok kötelező, de nem használt szabályát ⌀●●→● [7] . Mazoyer megoldásában 119 szabály van. Van egy nem időben optimális szabály megoldás hat állapottal és 78 szabállyal, az optimális pedig a 80.-tól.

Keressen hiányos megoldásokat négy állapottal - például egy robotsor szinkronizálása [1] . $2^{m}$

A legegyszerűbb megoldás

A probléma legegyszerűbb megoldása két állapothullámot ír le, amelyek egy robotsor mentén terjednek, amelyek közül az egyik háromszor gyorsabban mozog, mint a másik. A gyors hullám a sor túlsó széléről verődik vissza, és középen találkozik a lassú hullámmal. Ezt követően két hullámot négy részre osztanak, amelyek a központtól különböző irányokba mozognak. A folyamat folytatódik, minden alkalommal megduplázva a hullámok számát, amíg a sor szakaszainak hossza 1 lesz. Ebben a pillanatban minden robot lő. Ez a döntés egységnyi időt igényel a katonáktól. $3n$ $n$

Minimális időt igénylő megoldás

Abraham Waksman által 1966-ban [8] leírt meglehetősen egyszerű, 16 állapotból álló megoldást ismertetünk itt . A parancsnok frekvenciájú jeleket küld a szomszédos robotnak . A jel a sor jobb végéről visszaverődik, és a cellában találkozik a (for ) jellel. Amikor az visszapattan, egy új parancsnokot is létrehoz a jobb oldalon. $S_{1},~~S_{2},~~S_{3}~~\dots ~~S_{i}\dots$ $1,~{\frac {1}{3)),~{\frac {1}{7)),~\dots ~{\frac {1}{2^{i-1}-1} }\pontok$ $S_{1}$ $S_{i}$ $i\geq 2$ $n/2^{i-1}.$ $S_{1}$

A jelek előállítása balra terjedő segédjelek segítségével történik. Minden második pillanatban a normál jel egy segédjelet generál, amely balra terjed. önállóan mozog 1-es sebességgel, míg a lassabb jelek csak akkor mozognak, ha segédjeleket kapnak. $S_{i}$ $S_{1}$

A minimális idő igazolása

Ha a parancsnok (a lövészet kezdeményezője) és a robotok legközelebbi vége között van, a szinkronizáláshoz legalább [9] lépés szükséges . $k$ $2n-2-k$

Speciális eset: ha a parancsnok a szélen van, akkor lép. $2n-2$

Bizonyíték. Tegyük fel, hogy három program oldja meg a szinkronizálási problémát, és egyeseknél a , és képes lesz lőni a -ra . Úgy gondoljuk, hogy a parancsnok közelebb van a bal szélhez. $n$ $k$ $t<2n-2-k$

Bármilyen jel nem terjed robotról robotra gyorsabban, mint az úgynevezett "fénysebesség" - 1 pozíció időlépésenként. Az első robot pillanatnyi tevékenysége a pillanatnyi első két robottól, a pillanatnyilag az első háromtól , …, az összes pillanatnyi robottól függ . Ebben a pillanatban az utolsó robot még a kezdeti állapotában van (a jel pillanatnyilag érkezik ). $t$ $t-1$ $t-2$ $n$ $t_{1}=t-(n-1)\leqslant n-2-k$ $n-1-k$

Ez azt jelenti, hogy ha több robotot adunk a jobb oldali véghez , pillanatnyilag az első robotok állapota ugyanaz lesz, az első robotnál semmi sem változik, és ugyanabban a lépésben fog lőni . A lépés utolsó része az eredeti állapotában marad - a jelnek nem lesz ideje elérni. Tehát ez a programhármas nem megoldás. Ellentmondás. ${\megjelenítési stílus (n+2)}$ $t_{1}$ $n$ $t$ $(2n+2)$ $t$

A másik alsó korlátot, a lépéseket ugyanígy bizonyítjuk , de a szám nem kisebb. $n-1+k$ $2n-2-k$

Jegyzet. További követelmények a és -on , ha nem korlátozzák felülről, növelhetik az állapotok számát, de nem időben, és valóban létezik a Waksman-féle 17 állapotú megoldás általánosítása, amely bármely lépésre és lépésre is működik [10] . $n$ $k$ $n$ $n$ $k$ $2n-2-k$

Általánosítások

A probléma számos általánosabb megfogalmazását javasolták és tanulmányozták, beleértve az önkényesen rendezett sorozatokat, zárt gyűrűket, négyzeteket, kockákat, Cayley-gráfokat és általános gráfokat.

Ha az a tudás, hogy a parancsnok a lineáris formáció szélén van, nem nyeri el a szinkronizálási időt, akkor a kétdimenziós formációban abból a tudásból, hogy ő négyzet, nyereség lesz [11] .

Meg lehetett találni a megoldást egy lineáris rendszerre, ha minden robotnak jelet kell adnia a lövés előtt, akkor a robot tudja a maximumot és a sajátját , és ennek megfelelően van programozva [12] . A legegyszerűbb megoldás, ha a robotoknak további állapotokat és ugyanannyi ciklust adunk a szinkronizáláshoz, de ezt a késleltetést is megtehetjük, ha elég hosszú a formáció. Az egyes programok összetettsége (sőt, a klasszikus feladatból emlékszik a robot állapotára ). ${\displaystyle \tau _{i))$ ${\displaystyle \tau _{i))$ $\max \tau _{i}$ $a^{2\max \tau _{i}+1}$ $2\max \tau _{i}+1$

A pontos minimális szinkronizálási idő különböző skálákon
(megoldást találtak, és bebizonyosodott, hogy nem is lehet gyorsabb)

A cselekvés formája	Minimális idő
Vonal, a parancsnok és a robotok közeli széle között $k$	$2n-2-k$ [9]
Gyűrű	$n-1$ [9]
Gyűrű az információ egyirányú terjedésével	$2n-2$ [9]
Kare a parancsnokkal a sarkon $m\szer n$	$m+n+\operátornév {max} \{m,n\}-3$ [tizenegy]
Négyzet a parancsnokkal a sarkon $n\szer n$	$2n-2$ [tizenegy]
Kocka parancsnokkal a tetején $n\times n\times n$	$3n-3$ [tizenegy]

Jegyzetek

↑ 1 2 https://www.researchgate.net/publication/220977377_About_4-States_Solutions_to_the_Firing_Squad_Synchronization_Problem
↑ FR Moore, GG Langdon, Egy általánosított tüzelőosztag-probléma . Információ és ellenőrzés, 12. kötet, 3. szám, 1968. március, 212-220. oldal. DOI
↑ [Konfetti] Tüzelőosztag szinkronizálási probléma – YouTube
↑ Goto E. Minimális időre szóló megoldás a lőosztag problémájára. Hasonló kurzusjegyzetek az Applied Mathematics számára, 298. kötet, 52-59. Harvard Egyetem, Cambridge (1962)
↑ Jacques Mazoyer, Hat állapotú, minimális időbeli megoldás a lőosztag szinkronizálási problémájára . Elméleti Számítástudomány, 1987, vol. 50 pp 183-238 DOI
↑ Robert Balzer, Nyolc állapotú, minimális időre szóló megoldás a lőosztag szinkronizálási problémájára . Information and Control, 1967, 10. kötet, 22-42 DOI
↑ 1 2 Accueil - Archívum ouverte HAL
↑ Abraham Waksman, Optimális megoldás a lövészosztag szinkronizálási problémájára . Information and Control, 1966, 9. kötet, 66-78 DOI
↑ 1 2 3 4 A tüzelőosztag probléma
↑ https://www.sciencedirect.com/science/article/pii/S0019995868903094
↑ 1 2 3 4 Shinahr, Ilka. Két- és háromdimenziós lőosztag szinkronizálási probléma // Információ és vezérlés : folyóirat. - Akadémiai Kiadó, 1974. - 1. évf. 24 . - 163-180 . o . - doi : 10.1016/S0019-9958(74)80055-0 .
↑ V. I. Varshavsky, V. B. Marakhovsky, V. A. Peschansky, „Some variations of the problem of automaton chain synchronization”, Probl. peredachi inform., 4:3 (1968), 73-83; Problémák Tájékoztassa….

Irodalom

Shinahr, Ilka. Két- és háromdimenziós lőosztag szinkronizálási probléma // Információ és vezérlés : folyóirat. - Akadémiai Kiadó, 1974. - 1. évf. 24 . - 163-180 . o . - doi : 10.1016/S0019-9958(74)80055-0 .

Linkek

Conway Game of Life és más sejtautomaták

Konfigurációs osztályok

Konfigurációk

Feltételek

Más űrhajók
kétdimenziós rácson

Élethű	Éjjel-nappal Élet halál nélkül magas életvitel magvak
Egyéb	homokhalom modell Von Neumann géppuska Drótvilág Ant Langton Lények Paterson férgei

Egydimenziós űrhajó

Szoftverek és algoritmusok

Golly_
ünnepe
hashlife

KA kutatók