Зада́ча синхрониза́ции стрелко́в — задача из области информатики и теории клеточных автоматов .

Впервые предложена Джоном Майхиллом в 1957 году и опубликована (с решением) в 1962 году Эдвардом Муром . Название связано с поведением солдат при расстреле или ружейном салюте — все солдаты стреляют одновременно по сигналу.

Формулируется следующим образом : можно ли так запрограммировать одномерный клеточный автомат конечной длины, чтобы из стартового состояния G●●…●●● все клетки одновременно перешли в состояние FFF…FFF, независимо от длины цепочки, если обязательно правило перехода ●●●→● и его аналоги для концов цепочки ⌀●●→●, ●●⌀→●? Простым языком :

• ${\displaystyle n\geqslant 2}$ роботов ( конечных автоматов ) с ружьями стоят шеренгой. У автоматов как минимум три состояния ●, G и F — «исходное», «командир» и «выстрел». Помимо этих трёх, можно добавить сколько угодно промежуточных состояний.
• Роботы действуют независимо по одной программе и общаются только по цепочке: по сигналам барабана (синхронизатора) в зависимости от своего состояния в момент ${\displaystyle t-1}$ и состояния двух соседей переходят в новое состояние. Исключение — крайние роботы, у которых только один сосед; у них собственные программы.
• Все три программы, если робот и его соседи в исходном состоянии, ничего не должны делать.
• Все роботы стоят в исходном состоянии и ничего не делают. В момент ${\displaystyle t=0}$ крайнего левого переводят в состояние «командир».
• Существуют ли такие три программы (набор состояний и три комплекта правил перехода — для командира, замыкающего и остальных роботов), чтобы при любом ${\displaystyle n}$ они передали по цепочке приказ командира и одновременно (на одном ударе барабана) перешли в состояние «выстрел»?

Поскольку сигнал распространяется по шеренге со скоростью 1 позиция за такт (в теории клеточных автоматов это называется «скорость света»), очевидно, время синхронизации будет возрастать с возрастанием ${\displaystyle n}$ .

История

Первое решение этой задачи было найдено Джоном Маккарти и Марвином Мински и было опубликовано в Sequential Machines Эдвардом Муром.

Решение, требующее минимальное время, было найдено в 1962 профессором Эйити Гото из МТИ . Оно использует несколько тысяч состояний и требует ровно ${\displaystyle 2n-2}$ единиц времени для ${\displaystyle n}$ роботов. Легко доказывается (см. ниже), что более эффективных по времени решений не существует.

Оптимальное решение, использующее всего шесть состояний (включая конечное «выстрел»), было найдено Жаком Мазойером в 1987 году . Ранее Роберт Бальцер компьютерным перебором доказал, что решений с четырьмя состояниями клеток не существует . Питер Сандерс позднее выяснил, что поисковая процедура Бальцера была неполной, однако исправив процедуру, получил тот же результат. В 2010-е эволюционным перебором получены сотни разных решений с шестью состояниями . До сих пор неизвестно, существует ли решение с пятью состояниями клеток.

Также пытаются побить рекорд по количеству задействованных правил перехода (включая требуемое, но неиспользуемое правило для командира ⌀●●→● . В решении Мазойера 119 правил. Существует неоптимальное по времени решение с шестью состояниями и 78-ю правилами, и оптимальное — с 80-ю.

Находят неполные решения с четырьмя состояниями — например, синхронизирующие шеренгу из ${\displaystyle 2^{m}}$ роботов .

Простейшее решение

Простейшее решение задачи описывает две волны состояний, распространяющиеся по шеренге роботов, одна из которых движется в три раза быстрее другой. Быстрая волна отражается от дальнего края ряда и встречается с медленной в центре. После этого две волны разделяются на четыре, движущиеся в разные стороны от центра. Процесс продолжается, каждый раз удваивая число волн, пока длина отрезков ряда не станет равной 1. В этот момент все роботы стреляют. Это решение требует ${\displaystyle 3n}$ единиц времени для ${\displaystyle n}$ солдат.

Решение, требующее минимального времени

Здесь описано достаточно простое решение из 16 состояний, описанное Абрахамом Ваксманом в 1966 году . Командир посылает соседнему роботу сигналы ${\displaystyle S_{1},~~S_{2},~~S_{3}~~\dots ~~S_{i}\dots }$ с частотами ${\displaystyle 1,~{\frac {1}{3}},~{\frac {1}{7}},~\dots ~{\frac {1}{2^{i-1}-1}}\dots }$ Сигнал ${\displaystyle S_{1}}$ отражается от правого края ряда и встречает сигнал ${\displaystyle S_{i}}$ (для ${\displaystyle i\geq 2}$ ) в ячейке ${\displaystyle n/2^{i-1}.}$ Когда ${\displaystyle S_{1}}$ отражается, он также создает нового командира на правом конце.

Сигналы ${\displaystyle S_{i}}$ генерируются с использованием вспомогательных сигналов, распространяющихся влево. Каждый второй момент времени обычный сигнал генерирует вспомогательный сигнал, распространяющийся влево. ${\displaystyle S_{1}}$ движется самостоятельно со скоростью 1, тогда как более медленные сигналы движутся только при получении вспомогательных сигналов.

Доказательство минимального времени

Если между командиром (инициатором стрельбы) и ближайшим концом ${\displaystyle k}$ роботов, на синхронизацию нужно не менее ${\displaystyle 2n-2-k}$ шагов .

Частный случай: если командир на краю — то ${\displaystyle 2n-2}$ шага.

Доказательство. Допустим, существует тройка программ, которая решает задачу синхронизации, и для некоторых ${\displaystyle n}$ и ${\displaystyle k}$ сумеет выстрелить за ${\displaystyle t<2n-2-k}$ . Считаем, что командир ближе к левому концу.

Любой сигнал проходит от робота к роботу не быстрее, чем с так называемой «скоростью света» — 1 позиция за шаг времени. Действия первого робота в момент ${\displaystyle t}$ зависят от первых двух роботов на момент ${\displaystyle t-1}$ , от первых трёх на момент ${\displaystyle t-2}$ , …, от всех ${\displaystyle n}$ роботов на момент ${\displaystyle t_{1}=t-(n-1)\leqslant n-2-k}$ . В этот момент последний робот всё ещё в исходном состоянии (сигнал к нему приходит к моменту ${\displaystyle n-1-k}$ ).

А значит, если добавить к правому концу ещё ${\displaystyle (n+2)}$ -х роботов, в момент ${\displaystyle t_{1}}$ состояние первых ${\displaystyle n}$ роботов будет таким же, для первого робота ничего не изменится, и он выстрелит на том же шаге ${\displaystyle t}$ . Последний ${\displaystyle (2n+2)}$ -й на шаге ${\displaystyle t}$ останется в исходном состоянии — до него сигнал не успеет дойти. Так что данная тройка программ — не решение. Противоречие.

Точно так же доказывается и другая нижняя грань, ${\displaystyle n-1+k}$ шагов, но число ${\displaystyle 2n-2-k}$ не меньше.

Примечание. Дополнительные требования к ${\displaystyle n}$ и ${\displaystyle k}$ , если ${\displaystyle n}$ не ограничено сверху, могут дать выигрыш по количеству состояний, но не по времени, и действительно существует обобщение решения Ваксмана из 17 состояний, работающее для любых ${\displaystyle n}$ и ${\displaystyle k}$ за ${\displaystyle 2n-2-k}$ шагов .

Обобщения

Было предложено и изучено несколько более общих формулировок задачи, включая ряды с произвольным расположением командира, замкнутые кольца, квадраты, кубы, графы Кэли и графы общего вида.

Удалось найти существование решения для линейного строя, если каждый робот должен дать сигнал за ${\displaystyle \tau _{i}}$ тактов до выстрела, робот знает максимальное и своё ${\displaystyle \tau _{i}}$ , и соответственно программируется, при этом роботы с одинаковой задержкой будут иметь одинаковые программы . Простейшее решение — дать роботам ${\displaystyle \max \tau _{i}}$ дополнительных состояний и столько же тактов на синхронизацию, но можно обойтись и без этой задержки, если строй достаточно длинный. Сложность каждой отдельной программы ${\displaystyle a^{2\max \tau _{i}+1}}$ (по сути, он помнит состояние ${\displaystyle 2\max \tau _{i}+1}$ робота из классической задачи).

Разновидность задачи византийских генералов , когда все исправные процессоры должны синхронизироваться в отсутствие сигналов точного времени, независимо от работы процессоров-вредителей, обозвали «византийской задачей синхронизации стрелков» .

Точное минимальное время синхронизации на разных строях
(найдено решение и доказано, что быстрее не бывает)

Форма строя	Минимальное время
Шеренга, между командиром и ближним краем ${\displaystyle k}$ роботов	${\displaystyle 2n-2-k}$
Кольцо	${\displaystyle n-1}$
Кольцо с односторонним распространением информации	${\displaystyle 2n-2}$
Каре ${\displaystyle m\times n}$ с командиром на углу	${\displaystyle m+n+\operatorname {max} \{m,n\}-3}$
Квадрат ${\displaystyle n\times n}$ с командиром на углу	${\displaystyle 2n-2}$
Куб ${\displaystyle n\times n\times n}$ с командиром в вершине	${\displaystyle 3n-3}$

Примечания

Литература

• Shinahr, Ilka. Two- and three-dimensional firing-squad synchronization problem (англ.) // (англ.) ( : journal. — Academic Press, 1974. — Vol. 24 . — P. 163—180 . — doi : .

Ссылки