Форум Статьи Контакты
Строительство — возведение зданий и сооружений, а также их капитальный и текущий ремонт, реконструкция, реставрация и реновация.

Задача синхронизации стрелков

Дата: 11-01-2023, 09:00 » Раздел: Статьи  » 

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обобщения

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

Если от знания, что командир находится на краю линейного строя, не удаётся выиграть во времени синхронизации, то в двухмерном строю от знания, что он квадратный, будет выигрыш.

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


(голосов:0)

Пожожие новости
Комментарии

Ваше Имя:   

Ваш E-Mail: