Problemă de sincronizare a shooterului

Problema sincronizării trăgătorilor este o problemă din domeniul informaticii și al teoriei automatelor celulare .

Propus pentru prima dată de John Myhill în 1957 și publicat (cu soluție) în 1962 de Edward Moore [2] . Numele este asociat cu comportamentul soldaților în timpul execuției sau cu un salut de pușcă - toți soldații trag în același timp la un semnal.

Se formulează astfel: este posibil să se programeze un automat celular unidimensional de lungime finită în așa fel încât din starea inițială G●●…●●● toate celulele trec simultan în starea FFF…FFF, indiferent de lungimea lanțului, dacă regula de tranziție ●●●→● este obligatorie și omologii ei pentru capetele lanțului ⌀●●→●, ●●⌀→●? Într-un limbaj simplu [3] :

$n \geqslant 2$ roboți ( automate finite ) cu pistoale stau la rând. Automatele au cel puțin trei stări ●, G și F — „inițial”, „comandant” și „împușcat”. Pe lângă aceste trei, puteți adăuga câte stări intermediare doriți.
Roboții acționează independent conform unui program și comunică doar în lanț: în funcție de semnalele tobei (sincronizator), în funcție de starea lor în momentul de față și de starea a doi vecini, se mută într-o stare nouă. Excepție fac roboții extremi, care au un singur vecin; au propriile lor programe. $t-1$
Toate cele trei programe, dacă robotul și vecinii săi sunt în starea inițială, nu ar trebui să facă nimic.
Toți roboții stau în starea lor inițială și nu fac nimic. În momentul extremei stângi, ei sunt transferați în starea de „comandant”. $t=0$
Există astfel de trei programe (un set de stări și trei seturi de reguli de tranziție - pentru comandant, remorcă și alți roboți) care oricând simultan (pe o bătaie a tobei) intră în starea „împușcat”? $n$

Deoarece semnalul se propagă de-a lungul liniei cu o viteză de 1 poziție pe ceas (în teoria automatelor celulare, aceasta se numește „viteza luminii”), este evident că timpul de sincronizare va crește odată cu creșterea . $n$

Istorie

problemă matematică deschisă

Există o soluție la problema sincronizării săgeților în cinci stări - pentru orice , nu neapărat optimă în timp? $n$

Prima soluție la această problemă a fost găsită de John McCarthy și Marvin Minsky și publicată în Sequential Machines de Edward Moore.

O soluție care necesită timp minim a fost găsită în 1962 de profesorul Eiichi Goto de la MIT [4] . Folosește câteva mii de stări și necesită exact unități de timp pentru roboți. Este ușor de demonstrat (vezi mai jos) că nu mai există soluții eficiente în timp. $2n-2$ $n$

Soluția optimă, folosind doar șase stări (inclusiv „împușcătura” finală), a fost găsită de Jacques Mazoyer în 1987 [5] . Anterior, Robert Balzer a demonstrat prin enumerare computerizată că nu există soluții cu patru stări de celule [6] . Peter Sanders a aflat ulterior că procedura de căutare a lui Balzer a fost incompletă, dar după ce a corectat procedura, a obținut același rezultat. În anii 2010 s-au obținut prin enumerare evolutivă sute de soluții diferite cu șase stări [7] . Încă nu se știe dacă există o soluție cu cinci stări de celule.

Ei încearcă, de asemenea, să doboare recordul pentru numărul de reguli de tranziție implicate (inclusiv regula necesară, dar nefolosită pentru comandant ⌀●●→● [7] . Există 119 reguli în soluția lui Mazoyer. Există o regulă neoptimală de timp. soluție cu șase stări și 78 de reguli, iar cea optimă este din a 80-a.

Găsiți soluții incomplete cu patru stări - de exemplu, sincronizarea unei linii de roboți [1] . $2^{m}$

Cea mai simplă soluție

Cea mai simplă soluție a problemei descrie două valuri de stări care se propagă de-a lungul unei linii de roboți, dintre care unul se mișcă de trei ori mai repede decât celălalt. Valul rapid este reflectat de la marginea îndepărtată a rândului și se întâlnește cu unda lentă în centru. După aceea, două valuri sunt împărțite în patru, mișcându-se în direcții diferite față de centru. Procesul continuă, dublând de fiecare dată numărul de valuri, până când lungimea segmentelor rândului devine egală cu 1. În acest moment, toți roboții trag. Această decizie necesită unități de timp pentru soldați. $3n$ $n$

Soluție care necesită timp minim

O soluție destul de simplă cu 16 stări descrisă de Abraham Waksman în 1966 [8] este descrisă aici . Comandantul trimite semnale cu frecvențe către robotul adiacent . Semnalul sare în capătul drept al rândului și întâlnește semnalul (pentru ) în celulă . Când sare, creează și un nou comandant la capătul drept. $S_{1},~~S_{2},~~S_{3}~~\dots ~~S_{i}\dots$ $1,~{\frac {1}{3)),~{\frac {1}{7)),~\dots ~{\frac {1}{2^{i-1}-1} }\puncte$ $S_{1}$ $Si}$ $i\geq 2$ $n/2^{i-1}.$ $S_{1}$

Semnalele sunt generate folosind semnale auxiliare care se propagă spre stânga. La fiecare secundă de timp, semnalul normal generează un semnal auxiliar care se propagă spre stânga. se deplasează independent la viteza 1, în timp ce semnalele mai lente se mișcă numai atunci când primesc semnale auxiliare. $Si}$ $S_{1}$

Dovada timpului minim

Dacă între comandant (inițiatorul tragerii) și cel mai apropiat capăt al roboților, sincronizarea necesită cel puțin pași [9] . $k$ $2n-2-k$

Un caz special: dacă comandantul este pe margine, atunci face pași. $2n-2$

Dovada. Să presupunem că există trei programe care rezolvă problema de sincronizare, iar pentru unele , și vor putea trage pentru . Credem că comandantul este mai aproape de capătul din stânga. $n$ $k$ $t<2n-2-k$

Orice semnal se deplasează de la robot la robot nu mai repede decât așa-numita „viteză a luminii” - 1 poziție pe pas de timp. Acțiunile primului robot în acest moment depind de primii doi roboți în acest moment , de primii trei în acest moment , …, de toți roboții în acest moment . În acest moment, ultimul robot este încă în starea inițială (semnalul ajunge în acest moment ). $t$ $t-1$ $t-2$ $n$ $t_{1}=t-(n-1)\leqslant n-2-k$ $n-1-k$

Aceasta înseamnă că dacă adăugăm alți roboți la capătul drept , în momentul de față starea primilor roboți va fi aceeași, nu se va schimba nimic pentru primul robot și va trage în același pas . Ultimul th de pe treaptă va rămâne în starea inițială - semnalul nu va avea timp să-l ajungă. Deci acest trio de programe nu este o soluție. Contradicţie. $(n+2)$ $t_{1}$ $n$ $t$ $(2n+2)$ $t$

Cealaltă limită inferioară, trepte, este dovedită în același mod , dar numărul nu este mai mic. $n-1+k$ $2n-2-k$

Notă. Cerințe suplimentare privind și , dacă nu sunt limitate de mai sus, pot da un câștig în numărul de stări, dar nu în timp, și într-adevăr există o generalizare a soluției cu 17 stări a lui Waksman care funcționează pentru oricare și pentru pași [10] . $n$ $k$ $n$ $n$ $k$ $2n-2-k$

Generalizări

Au fost propuse și studiate mai multe formulări mai generale ale problemei, inclusiv serii ordonate arbitrar, inele închise, pătrate, cuburi, grafice Cayley și grafice generale.

Dacă cunoașterea că comandantul se află la marginea formației liniare nu reușește să câștige în timpul de sincronizare, atunci în formația bidimensională din cunoașterea că el este pătrat, va exista un câștig [11] .

A fost posibil să se constate existența unei soluții pentru un sistem liniar, dacă fiecare robot trebuie să dea un semnal de ceas înainte de împușcare, robotul cunoaște maximul și propriul său , și este programat corespunzător [12] . Cea mai simplă soluție este să dai roboților stări suplimentare și același număr de cicluri de sincronizat, dar poți face fără această întârziere dacă formarea este suficient de lungă. Complexitatea fiecărui program individual (de fapt, își amintește starea robotului din sarcina clasică). $\tau _{i)$ $\tau _{i)$ $\max \tau _{i)$ $a^{2\max \tau _{i}+1}$ $2\max \tau _{i}+1$

Timpul minim exact de sincronizare pe diferite scale
(a fost găsită o soluție și s-a dovedit că nu poate fi mai rapid)

Forma de acțiune	Timp minim
Linie, între comandant și marginea apropiată a roboților $k$	$2n-2-k$ [9]
Inel	$n-1$ [9]
Ring cu propagare unidirecțională a informațiilor	$2n-2$ [9]
Kare cu comandantul la colt $m\ori n$	$m+n+\operatorname {max} \{m,n\}-3$ [unsprezece]
Pătrat cu comandantul pe colț $n\ ori n$	$2n-2$ [unsprezece]
Cub cu un comandant în partea de sus $n\times n\times n$	$3n-3$ [unsprezece]

Note

↑ 1 2 https://www.researchgate.net/publication/220977377_About_4-States_Solutions_to_the_Firing_Squad_Synchronization_Problem
↑ FR Moore, GG Langdon, O problemă generalizată a plutonului de execuție . Informații și control, volumul 12, numărul 3, martie 1968, paginile 212-220. DOI
↑ [Confetti] Problemă de sincronizare a trupei de execuție - YouTube
↑ Treceți la E. O soluție în timp minim a problemei plutonului de execuție. Idem note de curs pentru Matematică Aplicată, vol.298,pp.52-59. Universitatea Harvard, Cambridge (1962)
↑ Jacques Mazoyer, O soluție de timp minim în șase stări la problema de sincronizare a plutonului de execuție . Informatica teoretica, 1987, voi. 50 p. 183-238 DOI
↑ Robert Balzer, O soluție de timp minim în 8 stări pentru problema de sincronizare a trupei de execuție . Informare și control, 1967, vol.10, pp.22-42 DOI
↑ 1 2 Accueil - Archive ouverte HAL
↑ Abraham Waksman, O soluție optimă pentru problema de sincronizare a trupei de execuție . Informare și control, 1966, vol.9, pp.66-78 DOI
↑ 1 2 3 4 Problema plutonului de execuție
↑ https://www.sciencedirect.com/science/article/pii/S0019995868903094
↑ 1 2 3 4 Shinahr, Ilka. Problemă de sincronizare a plutonului de execuție în două și trei dimensiuni // Informații și control : jurnal. - Presa Academică, 1974. - Vol. 24 . - P. 163-180 . - doi : 10.1016/S0019-9958(74)80055-0 .
↑ V. I. Varshavsky, V. B. Marakhovsky, V. A. Peschansky, „Unele variante ale problemei sincronizarii lanțului automatelor”, Probl. peredachi inform., 4:3 (1968), 73-83; Probleme informează...

Literatură

Shinahr, Ilka. Problemă de sincronizare a plutonului de execuție în două și trei dimensiuni // Informații și control : jurnal. - Presa Academică, 1974. - Vol. 24 . - P. 163-180 . - doi : 10.1016/S0019-9958(74)80055-0 .

Link -uri

Conway’s Game of Life și alte automate celulare

Clasele de configurare

Configurații

Planor
bloc
R-pentomino
Pentadecatlon

Termeni

O altă navă spațială pe o
rețea bidimensională

Realistic	Zi și noapte Viață fără moarte viata la nivel inalt semințe
Alte	model de grămadă de nisip pușcă de asalt Von Neumann Wireworld Ant Langton Creaturi Viermii lui Paterson

Nave spațiale unidimensionale

Software și algoritmi

Golly
Celebrarea lui
hashlife

Cercetătorii KA