Shooter-synkroniseringsproblem

Problemet med synkronisering av skyttar är ett problem från området för datavetenskap och teorin om cellulära automater .

Föreslog först av John Myhill 1957 och publicerades (med lösning) 1962 av Edward Moore [2] . Namnet är förknippat med soldaternas beteende under avrättning eller gevärsalut - alla soldater skjuter samtidigt på en signal.

Den är formulerad enligt följande: är det möjligt att programmera en endimensionell cellulär automat med ändlig längd på ett sådant sätt att från starttillståndet G●●...●●● alla celler samtidigt övergår till tillståndet FFF...FFF, oavsett längden på kedjan, om övergångsregeln ●●●→● är obligatorisk och dess motsvarigheter för kedjans ändar ⌀●●→●, ●●⌀→●? I klartext [3] :

$n \geqslant 2$ robotar ( finite automata ) med vapen står i kö. Automater har minst tre tillstånd ●, G och F — "initial", "commander" och "shot". Utöver dessa tre kan du lägga till så många mellanlägen du vill.
Robotar agerar självständigt enligt ett program och kommunicerar endast i en kedja: enligt trummans signaler (synkroniseraren), beroende på deras tillstånd för tillfället och tillståndet hos två grannar, flyttar de till ett nytt tillstånd. Undantaget är de extrema robotarna, som bara har en granne; de har sina egna program. $t-1$
Alla tre programmen, om roboten och dess grannar är i utgångsläget, borde inte göra någonting.
Alla robotar står i sitt ursprungliga tillstånd och gör ingenting. I ögonblicket för extremvänstern överförs de till "befälhavarens" stat. $t=0$
Finns det sådana tre program (en uppsättning tillstånd och tre uppsättningar övergångsregler - för befälhavaren, trailern och andra robotar) att de när som helst samtidigt (på ett slag av trumman) går in i "shot"-tillståndet? $n$

Eftersom signalen fortplantar sig längs linjen med en hastighet av 1 position per klocka (i cellulär automatteori kallas detta "ljushastigheten"), är det uppenbart att synkroniseringstiden kommer att öka med ökande . $n$

Historik

öppet matematiskt problem

Finns det en lösning på problemet med synkronisering av pilar i fem tillstånd - för alla , inte nödvändigtvis optimala i tid? $n$

Den första lösningen på detta problem hittades av John McCarthy och Marvin Minsky och publicerades i Sequential Machines av Edward Moore.

En lösning som kräver minimal tid hittades 1962 av professor Eiichi Goto vid MIT [4] . Den använder flera tusen tillstånd och kräver exakta tidsenheter för robotarna. Det är lätt att bevisa (se nedan) att det inte finns några mer tidseffektiva lösningar. $2n-2$ $n$

Den optimala lösningen, med endast sex tillstånd (inklusive det sista "skottet"), hittades av Jacques Mazoyer 1987 [5] . Tidigare har Robert Balzer bevisat genom datoruppräkning att det inte finns några lösningar med fyra celltillstånd [6] . Peter Sanders fick senare reda på att Balzers sökförfarande var ofullständigt, men efter att ha rättat till proceduren fick han samma resultat. På 2010 -talet erhölls hundratals olika lösningar med sex tillstånd genom evolutionär uppräkning [7] . Det är fortfarande okänt om det finns en lösning med fem celltillstånd.

De försöker också slå rekordet för antalet inblandade övergångsregler (inklusive den obligatoriska men inte använda regeln för befälhavaren ⌀●●→● [7] . Det finns 119 regler i Mazoyers lösning. Det finns en icke-tidsoptimal lösning med sex tillstånd och 78 regler, och den optimala är från den 80:e.

Hitta ofullständiga lösningar med fyra tillstånd - till exempel synkronisering av en rad robotar [1] . $2^{m}$

Den enklaste lösningen

Den enklaste lösningen på problemet beskriver två vågor av tillstånd som fortplantar sig längs en rad av robotar, varav den ena rör sig tre gånger snabbare än den andra. Den snabba vågen reflekteras från den bortre kanten av raden och möter den långsamma vågen i mitten. Därefter delas två vågor i fyra, som rör sig i olika riktningar från centrum. Processen fortsätter, varje gång dubblerar antalet vågor, tills längden på segmenten i raden blir lika med 1. I detta ögonblick skjuter alla robotar. Detta beslut kräver tidsenheter för soldaterna. $3n$ $n$

Lösning som kräver minimal tid

En ganska enkel 16-statslösning som beskrevs av Abraham Waksman 1966 [8] beskrivs här . Befälhavaren skickar signaler med frekvenser till den intilliggande roboten . Signalen studsar från den högra änden av raden och möter signalen (för ) i cellen . När den studsar skapar den också en ny befälhavare i den högra änden. $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}$ $Si}$ $i\geq 2$ $n/2^{i-1}.$ $S_{1}$

Signaler genereras med hjälp av hjälpsignaler som sprider sig till vänster. Vartannat ögonblick genererar den normala signalen en hjälpsignal som fortplantar sig åt vänster. rör sig oberoende med hastighet 1, medan långsammare signaler rör sig endast när de tar emot hjälpsignaler. $Si}$ $S_{1}$

Bevis på minsta tid

Om mellan befälhavaren (initierande av skjutningen) och den närmaste änden av robotarna, kräver synkroniseringen åtminstone steg [9] . $k$ $2n-2-k$

Ett specialfall: om befälhavaren är på kanten, steg då. $2n-2$

Bevis. Låt oss säga att det finns tre program som löser synkroniseringsproblemet, och för vissa , och kommer att kunna skjuta för . Vi tror att befälhavaren är närmare den vänstra änden. $n$ $k$ $t<2n-2-k$

Varje signal går från robot till robot inte snabbare än den så kallade "ljushastigheten" - 1 position per tidssteg. Den första robotens agerande för tillfället beror på de två första robotarna för tillfället , på de tre första för tillfället , ... på alla robotar för tillfället . I detta ögonblick är den sista roboten fortfarande i sitt initiala tillstånd (signalen kommer i ögonblicket ). $t$ $t-1$ $t-2$ $n$ $t_{1}=t-(n-1)\leqslant n-2-k$ $n-1-k$

Det betyder att om vi lägger till fler robotar i den högra änden , för tillfället kommer tillståndet för de första robotarna att vara detsamma, ingenting kommer att förändras för den första roboten, och den kommer att skjuta i samma steg . Den sista th på steget kommer att förbli i sitt ursprungliga tillstånd - signalen kommer inte att ha tid att nå den. Så denna trio av program är ingen lösning. Motsägelse. $(n+2)$ $t_{1}$ $n$ $t$ $(2n+2)$ $t$

Den andra nedre gränsen, steg, bevisas på samma sätt , men antalet är inte mindre. $n-1+k$ $2n-2-k$

Notera. Ytterligare krav på och , om de inte begränsas från ovan, kan ge en vinst i antalet stater, men inte i tid, och det finns faktiskt en generalisering av Waksmans 17-statslösning som fungerar för alla och för steg [10] . $n$ $k$ $n$ $n$ $k$ $2n-2-k$

Generaliseringar

Flera mer allmänna formuleringar av problemet har föreslagits och studerats, inklusive godtyckligt ordnade serier, slutna ringar, rutor, kuber, Cayley-grafer och allmänna grafer.

Om vetskapen om att befälhavaren är på kanten av den linjära formationen misslyckas med att vinna i synkroniseringstid, kommer det att finnas en vinst i den tvådimensionella formationen från vetskapen om att han är kvadratisk [11] .

Det var möjligt att hitta existensen av en lösning för ett linjärt system, om varje robot måste ge en signal klockor innan skottet, roboten vet max och sin egen , och programmeras därefter [12] . Den enklaste lösningen är att ge robotarna ytterligare tillstånd och samma antal cykler att synkronisera, men du klarar dig utan denna fördröjning om formationen är tillräckligt lång. Komplexiteten för varje enskilt program (det kommer faktiskt ihåg robotens tillstånd från den klassiska uppgiften). ${\displaystyle \tau _{i))$ ${\displaystyle \tau _{i))$ $\max \tau _{i}$ $a^{2\max \tau _{i}+1}$ $2\max \tau _{i}+1$

Den exakta minsta synkroniseringstiden på olika skalor
(en lösning hittades och det bevisades att det inte kunde vara snabbare)

Handlingsform	Minsta tid
Linje, mellan befälhavaren och robotarnas närmaste kant $k$	$2n-2-k$ [9]
Ringa	$n-1$ [9]
Ring med enkelriktad spridning av information	$2n-2$ [9]
Kare med befälhavaren på hörnet $m\ gånger n$	$m+n+\operatörsnamn {max} \{m,n\}-3$ [elva]
Fyrkant med befälhavaren på hörnet $n\ gånger n$	$2n-2$ [elva]
Kub med en befälhavare överst $n\ gånger n\ gånger n$	$3n-3$ [elva]

Anteckningar

↑ 1 2 https://www.researchgate.net/publication/220977377_About_4-States_Solutions_to_the_Firing_Squad_Synchronization_Problem
↑ FR Moore, GG Langdon, Ett generaliserat skjutningsgruppsproblem . Information och kontroll, volym 12, nummer 3, mars 1968, sid 212-220. DOI
↑ [Konfetti] Synkroniseringsproblem med skjutningsgruppen - YouTube
↑ Gå till E. En minimal tidslösning av skjutgruppsproblemet. Ditoed course notes for Applied Mathematics, vol.298,pp.52-59. Harvard University, Cambridge (1962)
↑ Jacques Mazoyer, En sextillståndslösning med minimal tid på synkroniseringsproblemet med skjutgrupp . Teoretisk datavetenskap, 1987, vol. 50 sid 183-238 DOI
↑ Robert Balzer, en 8-tillståndslösning med minimal tid till synkroniseringsproblemet med skjutningsgruppen . Information and Control, 1967, vol.10, s.22-42 DOI
↑ 1 2 Accueil - Arkiv ouverte HAL
↑ Abraham Waksman, en optimal lösning på synkroniseringsproblemet med skjutgrupp . Information and Control, 1966, vol. 9, sid. 66-78 DOI
↑ 1 2 3 4 Skjutgruppsproblemet
↑ https://www.sciencedirect.com/science/article/pii/S0019995868903094
↑ 1 2 3 4 Shinahr, Ilka. Två- och tredimensionellt problem med synkronisering av skjutlag // Information och kontroll : 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; Problem Informera….

Litteratur

Shinahr, Ilka. Två- och tredimensionellt problem med synkronisering av skjutlag // Information och kontroll : journal. - Academic Press, 1974. - Vol. 24 . - S. 163-180 . - doi : 10.1016/S0019-9958(74)80055-0 .

Länkar

Conways Game of Life och andra cellulära automater

Konfigurationsklasser

Konfigurationer

Villkor

Andra rymdskepp på ett
tvådimensionellt gitter

Levande	Dag och natt Livet utan död högt liv frön
Övrig	sandhög modell Von Neumann automatgevär Wireworld Ant Langton Småkryp Worms of Paterson

Endimensionell rymdfarkost

Programvara och algoritmer

Golly
Mireks
hashlife

KA-forskare