Проблема синхронизации расстрельной команды - Firing squad synchronization problem

Одно решение FSSP с использованием 15 состояний и 3n единиц времени. Время увеличивается сверху вниз.
Решение, использующее 2n-2 единицы времени. Время увеличивается снизу вверх.

В проблема синхронизации расстрельной команды проблема в Информатика и клеточные автоматы в котором цель состоит в том, чтобы разработать клеточный автомат это, начиная с одной активной ячейки, в конечном итоге достигает состояния, в котором все ячейки одновременно активны. Впервые это было предложено Джон Майхилл в 1957 г. и опубликованы (с решением Джон Маккарти и Марвин Мински ) в 1962 г. Эдвард Мур.

Постановка задачи

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

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

Состояния каждой ячейки включают три различных состояния: «активное», «неподвижное» и «срабатывающее», а функция перехода должна быть такой, чтобы ячейка, которая находится в состоянии покоя и чьи соседи находятся в неподвижном состоянии, оставалась неподвижной. Первоначально во время т = 0, все состояния неподвижны, за исключением крайней левой ячейки (общая), которая активна. Цель состоит в том, чтобы разработать набор состояний и функцию перехода таким образом, чтобы независимо от длины линии ячеек существовал момент времени. т так что каждая ячейка переходит в состояние запуска в момент времени т, и такая, что ни одна ячейка не принадлежит состоянию срабатывания до времени т.

Решения

Первое решение FSSP было найдено Джон Маккарти и Марвин Мински и был опубликован в Последовательные машины к Мур. Их решение включает распространение двух волн по строю солдат: быстрой и медленной, которые движутся в три раза медленнее. Быстрая волна отскакивает от другого конца линии и встречает медленную волну в центре. Затем две волны разделяются на четыре волны, быстрая и медленная волна движется в любом направлении от центра, эффективно разделяя линию на две равные части. Этот процесс продолжается, разделяя линию до тех пор, пока каждая часть не станет длиной 1. В этот момент стреляет каждый солдат. Для этого решения требуется 3п единиц времени для п солдаты.

Решение, использующее минимальное количество времени (т.е. 2п − 2 единиц времени для п солдат), впервые была найдена Эйити Гото  (1962 ), но в его решении использовались тысячи состояний. Ваксман (1966) улучшил это до 16 состояний и Бальцер (1967) далее улучшил его до восьми состояний, заявив, что доказывает, что решения с четырьмя состояниями не существует. Питер Сандерс позже обнаружил, что процедура поиска Бальцера была неполной, но сумела подтвердить результат отсутствия четырех состояний с помощью исправленной процедуры поиска. Лучшее известное в настоящее время решение, использующее шесть состояний, было предложено Жаком Мазойе (1987 ). Пока неизвестно, существует ли решение с пятью государствами.

В решениях за минимальное время генерал посылает правильные сигналы S1, S2, S3, ..., Sя на скоростях 1, 1/3, 1/7, ..., 1/(2 я−1 − 1). Сигнал S1 отражается на правом конце линии и встречает сигнал Sя (за я ≥ 2) в ячейке п/2 я−1. Когда S1 отражает, это также создает нового генерала в правом конце. Сигналы Sя строятся с помощью вспомогательных сигналов, распространяющихся влево. Каждый раз, когда сигнал перемещается (вправо), он отправляет вспомогательный сигнал влево. S1 движется самостоятельно со скоростью 1, в то время как каждый из более медленных сигналов перемещается только тогда, когда он получает вспомогательный сигнал.

Обобщения

Проблема синхронизации расстрельной команды была обобщена на многие другие типы клеточных автоматов, включая многомерные массивы ячеек (Шинахр 1974 ). Также были рассмотрены варианты задачи с разными начальными условиями (Кобаяши и Гольдштейн 2005 ).

Решения проблемы расстрела также могут быть адаптированы к другим задачам. Например, Патрик Фишер  (1965 ) разработал алгоритм клеточного автомата для генерации простые числа основан на более раннем решении проблемы синхронизации расстрельной команды.

Рекомендации

  • Бальцер, Роберт (1967), "Решение задачи синхронизации расстрельной команды с 8 состояниями с минимальным временем", Информация и контроль, 10 (1): 22–42, Дои:10.1016 / S0019-9958 (67) 90032-0.
  • Фишер, Патрик С. (1965), «Генерация простых чисел с помощью одномерного итеративного массива в реальном времени», Журнал ACM, 12 (3): 388–394, Дои:10.1145/321281.321290.
  • Гото, Эйити (1962), Решение задачи о расстреле за минимальное время, Аналогичные заметки по курсу прикладной математики 298, Кембридж, Массачусетс: Гарвардский университет, стр. 52–59.. Как цитирует Ваксман (1966).
  • Кобаяси, Кодзиро; Гольдштейн, Дарин (2005), "О постановках задач синхронизации расстрельной команды", Нетрадиционные вычисления (PDF), Конспект лекций по информатике, 3699, Springer-Verlag, стр. 157–168, Дои:10.1007/11560319_15.
  • Mazoyer, Jacques (1987), "Решение задачи синхронизации расстрельной команды с минимальным временем для шести состояний", Теоретическая информатика, 50 (2): 183–238, Дои:10.1016/0304-3975(87)90124-1.
  • Мур, Ф. Р .; Лэнгдон, Г. Г. (1968), "Обобщенная проблема расстрела", Информация и контроль, 12 (3): 212–220, Дои:10.1016 / S0019-9958 (68) 90309-4.
  • Шинахр, Илька (1974), "Двумерная и трехмерная задача синхронизации расстрельной команды", Информация и контроль, 24 (2): 163–180, Дои:10.1016 / S0019-9958 (74) 80055-0.
  • Ваксман, Абрахам (1966), "Оптимальное решение проблемы синхронизации расстрельной команды", Информация и контроль, 9 (1): 66–78, Дои:10.1016 / S0019-9958 (66) 90110-0.
  • Вольфрам, Стивен (2002), «Синхронизация расстрельной команды», Новый вид науки, Wolfram Media, стр.1035, ISBN  1-57955-008-8.

внешняя ссылка