Русская Википедия:Задача синхронизации стрелков
Зада́ча синхрониза́ции стрелко́в — задача из области информатики и теории клеточных автоматов.
Впервые предложена Джоном Майхиллом в 1957 году и опубликована (с решением) в 1962 году Эдвардом Муром[2]. Название связано с поведением солдат при расстреле или ружейном салюте — все солдаты стреляют одновременно по сигналу.
Формулируется следующим образом[1]: можно ли так запрограммировать одномерный клеточный автомат конечной длины, чтобы из стартового состояния G●●…●●● все клетки одновременно перешли в состояние FFF…FFF, независимо от длины цепочки, если обязательно правило перехода ●●●→● и его аналоги для концов цепочки ⌀●●→●, ●●⌀→●? Простым языком[3]:
- <math>n \geqslant 2</math> роботов (конечных автоматов) с ружьями стоят шеренгой. У автоматов как минимум три состояния ●, G и F — «исходное», «командир» и «выстрел». Помимо этих трёх, можно добавить сколько угодно промежуточных состояний.
- Роботы действуют независимо по одной программе и общаются только по цепочке: по сигналам барабана (синхронизатора) в зависимости от своего состояния в момент <math>t - 1</math> и состояния двух соседей переходят в новое состояние. Исключение — крайние роботы, у которых только один сосед; у них собственные программы.
- Все три программы, если робот и его соседи в исходном состоянии, ничего не должны делать.
- Все роботы стоят в исходном состоянии и ничего не делают. В момент <math>t=0</math> крайнего левого переводят в состояние «командир».
- Существуют ли такие три программы (набор состояний и три комплекта правил перехода — для командира, замыкающего и остальных роботов), чтобы при любом <math>n</math> они передали по цепочке приказ командира и одновременно (на одном ударе барабана) перешли в состояние «выстрел»?
Поскольку сигнал распространяется по шеренге со скоростью 1 позиция за такт (в теории клеточных автоматов это называется «скорость света»), очевидно, время синхронизации будет возрастать с возрастанием <math>n</math>.
История
Шаблон:Кратное изображение Шаблон:Врезка Первое решение этой задачи было найдено Джоном Маккарти и Марвином Мински и было опубликовано в Sequential Machines Эдвардом Муром.
Решение, требующее минимальное время, было найдено в 1962 профессором Эйити Гото из МТИ[4]. Оно использует несколько тысяч состояний и требует ровно <math>2 n - 2</math> единиц времени для <math>n</math> роботов. Легко доказывается (см. ниже), что более эффективных по времени решений не существует.
Оптимальное решение, использующее всего шесть состояний (включая конечное «выстрел»), было найдено Жаком Мазойером в 1987 году[5]. Ранее Роберт Бальцер компьютерным перебором доказал, что решений с четырьмя состояниями клеток не существует[6]. Питер Сандерс позднее выяснил, что поисковая процедура Бальцера была неполной, однако исправив процедуру, получил тот же результат. В 2010-е эволюционным перебором получены сотни разных решений с шестью состояниями[7]. До сих пор неизвестно, существует ли решение с пятью состояниями клеток.
Также пытаются побить рекорд по количеству задействованных правил перехода (включая требуемое, но неиспользуемое правило для командира ⌀●●→●[7]. В решении Мазойера 119 правил. Существует неоптимальное по времени решение с шестью состояниями и 78-ю правилами, и оптимальное — с 80-ю.
Находят неполные решения с четырьмя состояниями — например, синхронизирующие шеренгу из <math>2^m</math> роботов[1].
Простейшее решение
Простейшее решение задачи описывает две волны состояний, распространяющиеся по шеренге роботов, одна из которых движется в три раза быстрее другой. Быстрая волна отражается от дальнего края ряда и встречается с медленной в центре. После этого две волны разделяются на четыре, движущиеся в разные стороны от центра. Процесс продолжается, каждый раз удваивая число волн, пока длина отрезков ряда не станет равной 1. В этот момент все роботы стреляют. Это решение требует <math>3n</math> единиц времени для <math>n</math> солдат.
Решение, требующее минимального времени
Здесь описано достаточно простое решение из 16 состояний, описанное Абрахамом Ваксманом в 1966 году[8]. Командир посылает соседнему роботу сигналы <math>S_1,~~S_2,~~S_3~~ \dots ~~ S_i \dots</math> с частотами <math>1,~ \frac {1}{3},~ \frac {1} {7},~ \dots~ \frac {1} {2^{i - 1} - 1}\dots</math> Сигнал <math>S_1</math> отражается от правого края ряда и встречает сигнал <math>S_i</math> (для <math>i \ge 2</math>) в ячейке <math>n/2^{i - 1}.</math> Когда <math>S_1</math> отражается, он также создает нового командира на правом конце.
Сигналы <math>S_i</math> генерируются с использованием вспомогательных сигналов, распространяющихся влево. Каждый второй момент времени обычный сигнал генерирует вспомогательный сигнал, распространяющийся влево. <math>S_1</math> движется самостоятельно со скоростью 1, тогда как более медленные сигналы движутся только при получении вспомогательных сигналов.
Доказательство минимального времени
Доказательство. Допустим, существует тройка программ, которая решает задачу синхронизации, и для некоторых <math>n</math> и <math>k</math> сумеет выстрелить за <math>t < 2n - 2 - k</math>. Считаем, что командир ближе к левому концу.
Любой сигнал проходит от робота к роботу не быстрее, чем с так называемой «скоростью света» — 1 позиция за шаг времени. Действия первого робота в момент <math>t</math> зависят от первых двух роботов на момент <math>t - 1</math>, от первых трёх на момент <math>t - 2</math>, …, от всех <math>n</math> роботов на момент <math>t_1 = t - (n - 1) \leqslant n - 2 - k</math>. В этот момент последний робот всё ещё в исходном состоянии (сигнал к нему приходит к моменту <math>n - 1 - k</math>).
А значит, если добавить к правому концу ещё <math>(n+2)</math>-х роботов, в момент <math>t_1</math> состояние первых <math>n</math> роботов будет таким же, для первого робота ничего не изменится, и он выстрелит на том же шаге <math>t</math>. Последний <math>(2n+2)</math>-й на шаге <math>t</math> останется в исходном состоянии — до него сигнал не успеет дойти. Так что данная тройка программ — не решение. Противоречие.
Точно так же доказывается и другая нижняя грань, <math>n - 1 + k</math> шагов, но число <math>2n-2-k</math> не меньше.
Примечание. Дополнительные требования к <math>n</math> и <math>k</math>, если <math>n</math> не ограничено сверху, могут дать выигрыш по количеству состояний, но не по времени, и действительно существует обобщение решения Ваксмана из 17 состояний, работающее для любых <math>n</math> и <math>k</math> за <math>2n-2-k</math> шагов[9].
Обобщения
Было предложено и изучено несколько более общих формулировок задачи, включая ряды с произвольным расположением командира, замкнутые кольца, квадраты, кубы, графы Кэли и графы общего вида.
Удалось найти существование решения для линейного строя, если каждый робот должен дать сигнал за <math>\tau_i</math> тактов до выстрела, робот знает максимальное и своё <math>\tau_i</math>, и соответственно программируется, при этом роботы с одинаковой задержкой будут иметь одинаковые программы[10]. Простейшее решение — дать роботам <math>\max\tau_i</math> дополнительных состояний и столько же тактов на синхронизацию, но можно обойтись и без этой задержки, если строй достаточно длинный. Сложность каждой отдельной программы <math>a^{2\max\tau_i + 1}</math> (по сути, он помнит состояние <math>2\max\tau_i + 1</math> робота из классической задачи).
Разновидность задачи византийских генералов, когда все исправные процессоры должны синхронизироваться в отсутствие сигналов точного времени, независимо от работы процессоров-вредителей, обозвали «византийской задачей синхронизации стрелков»[11].
| Форма строя | Минимальное время |
|---|---|
| Шеренга, между командиром и ближним краем <math>k</math> роботов | <math>2n-2-k</math>[12] |
| Кольцо | <math>n-1</math>[12] |
| Кольцо с односторонним распространением информации | <math>2n-2</math>[12] |
| Каре <math>m \times n</math> с командиром на углу | <math>m + n + \operatorname{max}\{m,n\} - 3</math>[13] |
| Квадрат <math>n \times n</math> с командиром на углу | <math>2n - 2</math>[13] |
| Куб <math>n \times n \times n</math> с командиром в вершине | <math>3n - 3</math>[13] |
Примечания
Литература
Ссылки
- «Firing Squad Problem»
- «On Formulations of Firing Squad Synchronization Problems»
- «Firing squad synchronization»
- ↑ 1,0 1,1 1,2 Шаблон:Cite web
- ↑ F. R. Moore, G. G. Langdon, A generalized firing squad problem. Information and Control, Volume 12, Issue 3, March 1968, Pages 212—220. DOI
- ↑ Confetti — Firing Squad synchronization problem — YouTube Шаблон:Wayback
- ↑ Goto E. A minimal time solution of the firing squad problem. Dittoed course notes for Applied Mathematics, vol.298,pp.52-59. Harvard University, Cambridge(1962)
- ↑ Jacques Mazoyer, A six-state minimal time solution to the firing squad synchronization problem. Theoretical Computer Science, 1987, vol. 50 pp 183—238 DOI
- ↑ Robert Balzer, An 8-state Minimal Time Solution to the Firing Squad Synchronization Problem. Information and Control, 1967, vol.10, pp.22—42 DOI
- ↑ 7,0 7,1 Шаблон:Cite web
- ↑ Abraham Waksman, An Optimum Solution to the Firing Squad Synchronization Problem. Information and Control, 1966, vol.9, pp.66—78 DOI
- ↑ Шаблон:Cite web
- ↑ В. И. Варшавский, В. Б. Мараховский, В. А. Песчанский, «Некоторые варианты задачи о синхронизации цепи автоматов», Пробл. передачи информ., 4:3 (1968), 73-83; Problems Inform….
- ↑ https://groups.csail.mit.edu/tds/papers/Lynch/MIT-LCS-TM-275.pdf
- ↑ 12,0 12,1 12,2 Ошибка цитирования Неверный тег
<ref>; для сносокstanfordне указан текст - ↑ 13,0 13,1 13,2 Шаблон:Статья
