Shooter-synkroniseringsproblem

Problemet med synkronisering af skydere er et problem fra området for datalogi og teorien om cellulære automater .

Først foreslået af John Myhill i 1957 og udgivet (med løsning) i 1962 af Edward Moore [2] . Navnet er forbundet med soldaternes adfærd under henrettelse eller en riffelsalut - alle soldater skyder på samme tid på et signal.

Det er formuleret som følger: er det muligt at programmere en endimensionel cellulær automat af endelig længde på en sådan måde, at fra starttilstanden G●●...●●● alle celler samtidig går over til tilstanden FFF...FFF, uanset længden af kæden, hvis overgangsreglen ●●●→● er obligatorisk og dens modstykker for enderne af kæden ⌀●●→●, ●●⌀→●? I almindeligt sprog [3] :

$n \geqslant 2$ robotter ( finite automata ) med kanoner står i kø. Automater har mindst tre tilstande ●, G og F — "initial", "kommandør" og "skud". Ud over disse tre kan du tilføje så mange mellemtilstande, som du vil.
Robotter handler uafhængigt i henhold til et program og kommunikerer kun i en kæde: Ifølge tromlens signaler (synkronisator), afhængigt af deres tilstand i øjeblikket og to naboers tilstand, flytter de til en ny tilstand. Undtagelsen er de ekstreme robotter, som kun har én nabo; de har deres egne programmer. $t-1$
Alle tre programmer, hvis robotten og dens naboer er i den oprindelige tilstand, bør ikke gøre noget.
Alle robotter står i deres oprindelige tilstand og gør ingenting. I det ekstreme venstrefløjs øjeblik bliver de overført til "kommandant"-staten. $t=0$
Findes der sådanne tre programmer (et sæt tilstande og tre sæt overgangsregler - for chefen, traileren og andre robotter), at de på et hvilket som helst tidspunkt samtidig (på et slag på tromlen) går i "skud"-tilstand? $n$

Da signalet forplanter sig langs linjen med en hastighed på 1 position pr. ur (i cellulær automatteori kaldes dette "lysets hastighed"), er det indlysende, at synkroniseringstiden vil stige med stigende . $n$

Historie

åbent matematisk problem

Er der en løsning på problemet med synkronisering af pile i fem tilstande - for enhver , ikke nødvendigvis optimal i tid? $n$

Den første løsning på dette problem blev fundet af John McCarthy og Marvin Minsky og udgivet i Sequential Machines af Edward Moore.

En løsning, der kræver minimal tid, blev fundet i 1962 af professor Eiichi Goto fra MIT [4] . Det bruger flere tusinde tilstande og kræver nøjagtigt tidsenheder for robotterne. Det er nemt at bevise (se nedenfor), at der ikke findes mere tidseffektive løsninger. $2n-2$ $n$

Den optimale løsning, der kun bruger seks tilstande (inklusive det endelige "skud"), blev fundet af Jacques Mazoyer i 1987 [5] . Tidligere beviste Robert Balzer ved computeroptælling, at der ikke findes løsninger med fire celletilstande [6] . Peter Sanders fandt senere ud af, at Balzers eftersøgningsprocedure var ufuldstændig, men efter at have rettet proceduren fik han samme resultat. I 2010'erne blev hundredvis af forskellige løsninger med seks tilstande opnået ved evolutionær opregning [7] . Det er stadig uvist, om der findes en løsning med fem celletilstande.

De forsøger også at slå rekorden for antallet af involverede overgangsregler (inklusive den påkrævede, men ikke brugte regel for chefen ⌀●●→● [7] . Der er 119 regler i Mazoyers løsning. Der er en ikke-tidsoptimal løsning med seks stater og 78 regler, og den optimale er fra den 80.

Find ufuldstændige løsninger med fire tilstande - for eksempel synkronisering af en række robotter [1] . $2^{m}$

Den enkleste løsning

Den enkleste løsning på problemet beskriver to bølger af tilstande, der forplanter sig langs en række af robotter, hvoraf den ene bevæger sig tre gange hurtigere end den anden. Den hurtige bølge reflekteres fra den fjerneste kant af rækken og møder den langsomme bølge i midten. Derefter er to bølger opdelt i fire, der bevæger sig i forskellige retninger fra midten. Processen fortsætter, hver gang antallet af bølger fordobles, indtil længden af rækkens segmenter bliver lig med 1. I dette øjeblik skyder alle robotter. Denne beslutning kræver tidsenheder for soldaterne. $3n$ $n$

Løsning, der kræver minimal tid

En ret simpel 16-statsløsning beskrevet af Abraham Waksman i 1966 [8] er beskrevet her . Fartøjschefen sender signaler med frekvenser til den tilstødende robot . Signalet hopper af i højre ende af rækken og støder på signalet (for ) i cellen . Når det hopper, opretter det også en ny chef i højre ende. $S_{1},~~S_{2},~~S_{3}~~\dots ~~S_{i}\dots$ $1,~{\frac {1}{3)),~{\frac {1}{7)),~\dots ~{\frac {1}{2^{i-1}-1} }\dots$ $S_{1}$ $S_{i}$ $i\geq 2$ $n/2^{i-1}.$ $S_{1}$

Signaler genereres ved hjælp af hjælpesignaler, der forplanter sig til venstre. Hvert andet øjeblik genererer det normale signal et hjælpesignal, der forplanter sig til venstre. bevæger sig uafhængigt med hastighed 1, mens langsommere signaler kun bevæger sig, når de modtager hjælpesignaler. $S_{i}$ $S_{1}$

Bevis for minimumstid

Hvis mellem chefen (initiator af skydning) og den nærmeste ende af robotterne, kræver synkronisering mindst trin [9] . $k$ $2n-2-k$

Et særligt tilfælde: hvis kommandanten er på kanten, så skridt. $2n-2$

Bevis. Lad os sige, at der er tre programmer, der løser synkroniseringsproblemet, og for nogle , og vil være i stand til at skyde for . Vi mener, at chefen er tættere på venstre ende. $n$ $k$ $t<2n-2-k$

Ethvert signal går fra robot til robot ikke hurtigere end den såkaldte "lyshastighed" - 1 position pr. tidstrin. Handlingen af den første robot i øjeblikket afhænger af de første to robotter i øjeblikket , af de første tre i øjeblikket , …, af alle robotter i øjeblikket . I dette øjeblik er den sidste robot stadig i sin oprindelige tilstand (signalet ankommer i øjeblikket ). $t$ $t-1$ $t-2$ $n$ $t_{1}=t-(n-1)\leqslant n-2-k$ $n-1-k$

Det betyder, at hvis vi tilføjer flere robotter til den højre ende , i øjeblikket vil tilstanden af de første robotter være den samme, intet vil ændre sig for den første robot, og den vil skyde i samme trin . Den sidste th på trinnet forbliver i sin oprindelige tilstand - signalet har ikke tid til at nå det. Så denne trio af programmer er ikke en løsning. Modsigelse. $(n+2)$ $t_{1}$ $n$ $t$ $(2n+2)$ $t$

Den anden nedre grænse, trin, er bevist på samme måde , men antallet er ikke mindre. $n-1+k$ $2n-2-k$

Bemærk. Yderligere krav om og , hvis ikke begrænset ovenfra, kan give en gevinst i antallet af stater, men ikke i tid, og der er faktisk en generalisering af Waksmans 17-statsløsning, der virker for alle og for trin [10] . $n$ $k$ $n$ $n$ $k$ $2n-2-k$

Generaliseringer

Adskillige mere generelle formuleringer af problemet er blevet foreslået og undersøgt, herunder vilkårligt ordnede serier, lukkede ringe, firkanter, terninger, Cayley-grafer og generelle grafer.

Hvis viden om, at chefen er på kanten af den lineære formation, ikke opnår i synkroniseringstid, så vil der i den todimensionelle formation fra viden om, at han er firkantet, være en gevinst [11] .

Det var muligt at finde eksistensen af en løsning til et lineært system, hvis hver robot skal give et signal ure før skuddet, kender robotten maksimum og sit eget , og programmeres derefter [12] . Den enkleste løsning er at give robotterne yderligere tilstande og det samme antal cyklusser at synkronisere, men du kan undvære denne forsinkelse, hvis formationen er lang nok. Kompleksiteten af hvert enkelt program (faktisk husker det robottens tilstand fra den klassiske opgave). $\tau _{i}$ $\tau _{i}$ ${\displaystyle \max \tau _{i))$ $a^{2\max \tau _{i}+1}$ $2\max \tau _{i}+1$

Den nøjagtige minimumssynkroniseringstid på forskellige skalaer
(en løsning blev fundet, og det blev bevist, at det ikke kunne være hurtigere)

Handlingsform	Minimum tid
Linje, mellem chefen og den nærmeste kant af robotterne $k$	$2n-2-k$ [9]
Ring	$n-1$ [9]
Ring med envejsformidling af information	$2n-2$ [9]
Kare med kommandanten på hjørnet $m\ gange n$	$m+n+\operatørnavn {max} \{m,n\}-3$ [elleve]
Firkantet med kommandøren på hjørnet $n\ gange n$	$2n-2$ [elleve]
Terning med en kommandør øverst $n\ gange n\ gange n$	$3n-3$ [elleve]

Noter

↑ 1 2 https://www.researchgate.net/publication/220977377_About_4-States_Solutions_to_the_Firing_Squad_Synchronization_Problem
↑ FR Moore, GG Langdon, Et generaliseret skydeværnsproblem . Information og kontrol, bind 12, hæfte 3, marts 1968, side 212-220. DOI
↑ [Konfetti] synkroniseringsproblem med skydestyrken - YouTube
↑ Gå til E. En minimal tidsløsning af skydestyrkeproblemet. Ditto kursusnotater for anvendt matematik, vol. 298, s. 52-59. Harvard University, Cambridge (1962)
↑ Jacques Mazoyer, En seks-stats minimal tidsløsning på skydestyrkens synkroniseringsproblem . Teoretisk datalogi, 1987, vol. 50 s. 183-238 DOI
↑ Robert Balzer, en 8-stats minimal tidsløsning på synkroniseringsproblemet i skydegruppen . Information og kontrol, 1967, bind 10, s.22-42 DOI
↑ 1 2 Accueil - Arkiv ouverte HAL
↑ Abraham Waksman, en optimal løsning på synkroniseringsproblemet med skydestyrken . Information og kontrol, 1966, bind 9, s. 66-78 DOI
↑ 1 2 3 4 Skydetropsproblemet
↑ https://www.sciencedirect.com/science/article/pii/S0019995868903094
↑ 1 2 3 4 Shinahr, Ilka. To- og tredimensionelt skydeholdssynkroniseringsproblem // Information og kontrol : journal. - Academic Press, 1974. - Vol. 24 . - S. 163-180 . - doi : 10.1016/S0019-9958(74)80055-0 .
↑ V. I. Varshavsky, V. B. Marakhovsky, V. A. Peschansky, "Some variants of the problem of automaton chain synchronization", Probl. peredachi inform., 4:3 (1968), 73-83; Oplys om problemer….

Litteratur

Shinahr, Ilka. To- og tredimensionelt skydeholdssynkroniseringsproblem // Information og kontrol : journal. - Academic Press, 1974. - Vol. 24 . - S. 163-180 . - doi : 10.1016/S0019-9958(74)80055-0 .

Links

Conways Game of Life og andre cellulære automater

Konfigurationsklasser

Konfigurationer

Svævefly
Blok
R-pentomino
Pentadecatlon

Vilkår

Andre rumfartøjer på et
todimensionelt gitter

Livsagtig	Dag og nat Liv uden død vildt liv frø
Andet	sandbunke model Von Neumann kampgevær Wireworld Ant Langton Critters Worms of Paterson

Et-dimensionelt rumfartøj

Software og algoritmer

Golly
Mireks
hashlife

KA-forskere