Problém se synchronizací střelců

Problém synchronizace střelců je problémem z oblasti informatiky a teorie celulárních automatů .

Poprvé navrhl John Myhill v roce 1957 a publikoval (s řešením) v roce 1962 Edward Moore [2] . Název je spojen s chováním vojáků při popravě nebo salvu z pušky – všichni vojáci střílejí současně na signál.

Je to formulováno následovně: je možné naprogramovat jednorozměrný celulární automat konečné délky tak, aby z výchozího stavu G●●…●●● všechny buňky současně přešly do stavu FFF…FFF, bez ohledu na délka řetězce, pokud je přechodové pravidlo ●●●→● povinné, a jeho protějšky pro konce řetězce ⌀●●→●, ●●⌀→●? Srozumitelně [3] :

$n \geqslant 2$ roboti ( konečné automaty ) se zbraněmi stojí v řadě. Automaty mají alespoň tři stavy ●, G a F — „počáteční“, „velitel“ a „výstřel“. Kromě těchto tří můžete přidat libovolný počet mezistavů.
Roboti jednají samostatně podle jednoho programu a komunikují pouze v řetězci: podle signálů bubnu (synchronizátoru) v závislosti na jejich aktuálním stavu a stavu dvou sousedů přecházejí do nového stavu. Výjimkou jsou extrémní roboti, kteří mají jen jednoho souseda; mají své vlastní programy. $t-1$
Všechny tři programy, pokud jsou robot a jeho sousedé ve výchozím stavu, by neměly nic dělat.
Všichni roboti stojí ve svém původním stavu a nic nedělají. V okamžiku krajní levice jsou převedeni do „velitelského“ stavu. $t=0$
Existují takové tři programy (soubor stavů a tři sady přechodových pravidel – pro velitele, přívěs a další roboty), že kdykoli současně (na jeden úder bubnu) přejdou do stavu „výstřel“? $n$

Protože se signál šíří po lince rychlostí 1 pozice za hodinu (v teorii celulárních automatů se tomu říká „rychlost světla“), je zřejmé, že čas synchronizace se bude prodlužovat s rostoucí . $n$

Historie

otevřený matematický problém

Existuje řešení problému synchronizace šipek v pěti stavech - pro jakýkoli , ne nutně optimální v čase? $n$

První řešení tohoto problému našli John McCarthy a Marvin Minsky a publikovali jej v Sequential Machines Edward Moore.

Řešení vyžadující minimální čas našel v roce 1962 profesor Eiichi Goto z MIT [4] . Využívá několik tisíc stavů a vyžaduje přesně jednotky času pro roboty. Je snadné dokázat (viz níže), že neexistují žádná časově výhodnější řešení. $2n-2$ $n$

Optimální řešení, využívající pouze šest stavů (včetně finálního „výstřelu“), našel Jacques Mazoyer v roce 1987 [5] . Dříve Robert Balzer dokázal počítačovým výčtem, že neexistují žádná řešení se čtyřmi stavy buněk [6] . Peter Sanders později zjistil, že Balzerův vyhledávací postup byl neúplný, ale po opravě postupu dostal stejný výsledek. V roce 2010 byly evolučním výčtem získány stovky různých řešení se šesti stavy [7] . Stále není známo, zda existuje řešení s pěti stavy buněk.

Snaží se také překonat rekord v počtu zapojených přechodových pravidel (včetně povinného, ale nevyužitého pravidla pro velitele ⌀●●→● [7] . V Mazoyerově řešení je 119 pravidel. Existuje nečasově optimální řešení se šesti stavy a 78 pravidly a optimální je od 80.

Najděte neúplná řešení se čtyřmi stavy – například synchronizace řady robotů [1] . $2^{m}$

Nejjednodušší řešení

Nejjednodušší řešení problému popisuje dvě vlny stavů šířící se podél řady robotů, z nichž jeden se pohybuje třikrát rychleji než druhý. Rychlá vlna se odráží od vzdáleného okraje řady a setkává se s pomalou vlnou uprostřed. Poté se dvě vlny rozdělí na čtyři a pohybují se různými směry od středu. Proces pokračuje s každým zdvojnásobením počtu vln, dokud se délka segmentů řady nerovná 1. V tomto okamžiku všichni roboti střílejí. Toto rozhodnutí vyžaduje jednotky času pro vojáky. $3n$ $n$

Řešení vyžadující minimální čas

Poměrně jednoduché 16stavové řešení popsané Abrahamem Waksmanem v roce 1966 [8] je popsáno zde . Velitel vysílá signály s frekvencemi sousednímu robotu . Signál se odrazí od pravého konce řady a narazí na signál (pro ) v buňce . Když se odrazí, vytvoří také nového velitele na pravém konci. $S_{1},~~S_{2},~~S_{3}~~\tečky ~~S_{i}\tečky$ $1,~{\frac {1}{3)),~{\frac {1}{7)),~\tečky ~{\frac {1}{2^{i-1}-1} }\tečky$ $S_{1}$ $S_{i}$ $i\geq 2$ $n/2^{i-1}.$ $S_{1}$

Signály jsou generovány pomocí pomocných signálů šířících se doleva. Každý druhý okamžik normální signál generuje pomocný signál šířící se doleva. se pohybuje nezávisle rychlostí 1, zatímco pomalejší signály se pohybují pouze tehdy, když přijímají pomocné signály. $S_{i}$ $S_{1}$

Důkaz o minimální době

Pokud mezi velitelem (iniciátorem střelby) a nejbližším koncem robotů, synchronizace vyžaduje alespoň kroky [9] . $k$ $2n-2-k$

Zvláštní případ: pokud je velitel na hraně, tak kroky. $2n-2$

Důkaz. Řekněme, že existují tři programy, které řeší problém synchronizace, a pro některé , a budou moci střílet pro . Věříme, že velitel je blíže levému konci. $n$ $k$ $t<2n-2-k$

Jakýkoli signál putuje od robota k robotu rychleji, než je takzvaná "rychlost světla" - 1 pozice za časový krok. Akce prvního robota v tuto chvíli závisí na prvních dvou robotech v tuto chvíli , na prvních třech v tuto chvíli , …, na všech robotech v tuto chvíli . V tuto chvíli je poslední robot stále ve svém výchozím stavu (signál přichází v tuto chvíli ). $t$ $t-1$ $t-2$ $n$ $t_{1}=t-(n-1)\leqslant n-2-k$ $n-1-k$

To znamená, že pokud přidáme další roboty na pravý konec , v tuto chvíli bude stav prvních robotů stejný, pro prvního robota se nic nezmění a bude střílet ve stejném kroku . Poslední krok na schodu zůstane v původním stavu - signál ho nestihne dosáhnout. Tato trojice programů tedy není řešením. Rozpor. $(n+2)$ $t_{1}$ $n$ $t$ $(2n+2)$ $t$

Další dolní mez, kroky, se dokazuje stejným způsobem , ale počet není menší. $n-1+k$ $2n-2-k$

Poznámka. Další požadavky na a , pokud nejsou shora omezeny, mohou přinést zisk v počtu stavů, ale ne v čase, a skutečně existuje zobecnění Waksmanova 17stavového řešení, které funguje pro všechny a pro kroky [10] . $n$ $k$ $n$ $n$ $k$ $2n-2-k$

Zobecnění

Bylo navrženo a studováno několik obecnějších formulací problému, včetně libovolně uspořádaných řad, uzavřených kruhů, čtverců, krychlí, Cayleyových grafů a obecných grafů.

Pokud se v synchronizačním čase nepodaří získat poznatek, že velitel je na hraně lineární formace, pak ve dvourozměrné formaci z poznání, že je čtvercový, dojde k zisku [11] .

Bylo možné najít existenci řešení pro lineární systém, pokud každý robot musí dát signál hodin před výstřelem, robot zná maximum a své a je podle toho naprogramován [12] . Nejjednodušším řešením je dát robotům další stavy a stejný počet cyklů k synchronizaci, ale můžete se obejít bez tohoto zpoždění, pokud je formace dostatečně dlouhá. Složitost každého jednotlivého programu (ve skutečnosti si pamatuje stav robota z klasické úlohy). $\tau _{i}$ $\tau _{i}$ ${\displaystyle \max \tau _{i))$ $a^{2\max \tau _{i}+1}$ $2\max \tau _{i}+1$

Přesná minimální doba synchronizace na různých měřítcích
(našlo se řešení a bylo prokázáno, že to nemůže být rychlejší)

Forma akce	Minimální čas
Linka mezi velitelem a blízkým okrajem robotů $k$	$2n-2-k$ [9]
Prsten	$n-1$ [9]
Prsten s jednosměrným šířením informace	$2n-2$ [9]
Kare s velitelem na rohu $m\krát n$	$m+n+\operatorname {max} \{m,n\}-3$ [jedenáct]
Čtvereček s velitelem na rohu $n\krát n$	$2n-2$ [jedenáct]
Kostka s velitelem nahoře $n\times n\times n$	$3n-3$ [jedenáct]

Poznámky

↑ 1 2 https://www.researchgate.net/publication/220977377_About_4-States_Solutions_to_the_Firing_Squad_Synchronization_Problem
↑ FR Moore, GG Langdon, Obecný problém popravčí čety . Informace a kontrola, svazek 12, vydání 3, březen 1968, strany 212-220. DOI
↑ [Konfety] Problém se synchronizací Fire Squad - YouTube
↑ Přejít na E. Minimální časové řešení problému popravčí čety. Stejné poznámky k kurzu pro aplikovanou matematiku, sv. 298, s. 52-59. Harvard University, Cambridge (1962)
↑ Jacques Mazoyer, Šestistavové minimální časové řešení problému synchronizace popravčí čety . Teoretická informatika, 1987, roč. 50 pp 183-238 DOI
↑ Robert Balzer, 8stavové minimální časové řešení problému synchronizace palebné čety . Information and Control, 1967, vol.10, pp.22-42 DOI
↑ 1 2 Accueil - Archiv otevřený HAL
↑ Abraham Waksman, Optimální řešení problému synchronizace popravčí čety . Informace a kontrola, 1966, sv. 9, s. 66-78 DOI
↑ 1 2 3 4 Problém popravčí čety
↑ https://www.sciencedirect.com/science/article/pii/S0019995868903094
↑ 1 2 3 4 Shinahr, Ilka. Problém synchronizace dvou a třírozměrných popravčích čet // Information and Control : deník. - Academic Press, 1974. - Sv. 24 . - S. 163-180 . - doi : 10.1016/S0019-9958(74)80055-0 .
↑ V. I. Varshavsky, V. B. Marachovsky, V. A. Peschansky, “Některé varianty problému synchronizace řetězu automatů”, Probl. peredachi inform., 4:3 (1968), 73-83; Problémy Informujte….

Literatura

Shinahr, Ilka. Problém synchronizace dvou a třírozměrných popravčích čet // Information and Control : deník. - Academic Press, 1974. - Sv. 24 . - S. 163-180 . - doi : 10.1016/S0019-9958(74)80055-0 .

Odkazy

Conwayova hra o život a další buněčné automaty

Konfigurační třídy

Konfigurace

Kluzák
Blok
R-pentomino
pětidekát

Podmínky

Jiná kosmická loď na
dvourozměrné mřížce

Živý	Den a noc Život bez smrti vysoká životnost semena
jiný	model pískové hromady Útočná puška von Neumann Wireworld Ant Langton Zvířata Worms of Paterson

Jednorozměrná kosmická loď

Software a algoritmy

Golly
Mirkova
hashlife

výzkumníci KA