Проблема с синхронизацией расстрельной команды
Проблема синхронизации расстрельного отряда — это проблема в области информатики и клеточных автоматов , цель которой состоит в том, чтобы спроектировать клеточный автомат , который, начиная с одной активной ячейки, в конечном итоге достигает состояния, в котором все ячейки активны одновременно. Впервые он был предложен Джоном Майхиллом в 1957 году и опубликован (с решением Джона Маккарти и Марвина Мински ) в 1962 году Эдвардом Ф. Муром .
Постановка задачи
[ редактировать ]Название задачи происходит от аналогии с реальными расстрельными командами : цель состоит в том, чтобы разработать систему правил, согласно которой офицер может приказать расстрельной части открыть огонь так, чтобы ее члены стреляли из винтовок одновременно.
Более формально, проблема касается клеточных автоматов , массивов конечных автоматов, называемых «ячейками», расположенных в линию, так что на каждом временном шаге каждый автомат переходит в новое состояние в зависимости от своего предыдущего состояния и состояний двух своих соседей. в линии. В задаче о расстреле линия состоит из конечного числа ячеек, и правило, согласно которому каждая машина переходит в следующее состояние, должно быть одинаковым для всех ячеек внутри линии, но функции перехода двух конечные точки линии могут различаться, поскольку в каждой из этих двух ячеек отсутствует сосед на одной из двух сторон.
Состояния каждой ячейки включают три различных состояния: «активное», «неподвижное» и «активное», а функция перехода должна быть такой, чтобы ячейка, которая находится в состоянии покоя и соседи которой находятся в состоянии покоя, оставалась неподвижной. Первоначально, в момент времени t = 0 , все состояния находятся в состоянии покоя, за исключением крайней левой ячейки (общей), которая является активной. Цель состоит в том, чтобы разработать набор состояний и функцию перехода так, чтобы независимо от длины линии ячеек существовал момент времени t , при котором каждая ячейка переходит в состояние срабатывания в момент времени t , и такой, что ни одна ячейка не принадлежит в состояние срабатывания до момента времени t .
Решения
[ редактировать ]Первое решение FSSP было найдено Джоном Маккарти и Марвином Мински и опубликовано Муром в Machines журнале Sequential . Их решение заключается в распространении двух волн вдоль линии солдат: быстрой волны и медленной волны, движущейся в три раза медленнее. Быстрая волна отскакивает от другого конца линии и встречает медленную волну в центре. Затем две волны разделились на четыре волны: быструю и медленную, движущуюся в любом направлении от центра, фактически разделив линию на две равные части. Этот процесс продолжается, шеренга разделяется до тех пор, пока длина каждого деления не станет равной 1. В этот момент каждый солдат стреляет. Это решение требует 3 n единиц времени для n солдат.
Решение, использующее минимальное количество времени (что составляет 2 n - 2 единицы времени для n солдат), было впервые найдено Эйити Гото ( 1962 ), но в его решении использовались тысячи состояний. Ваксман (1966) увеличил это число до 16 штатов, а Бальцер (1967) еще больше улучшил его до восьми штатов, утверждая при этом, что доказал, что не существует решения с четырьмя штатами. Позже Питер Сандерс обнаружил, что процедура поиска Бальцера была неполной, но сумел подтвердить результат несуществования четырех состояний с помощью исправленной процедуры поиска. Лучшее известное в настоящее время решение, использующее шесть штатов, было предложено Жаком Мазойером ( 1987 ). До сих пор неизвестно, существует ли решение с участием пяти государств.
В решениях с минимальным временем генерал посылает вправо сигналы S 1 , S 2 , S 3 , ..., на Si скоростях 1, 1/3, 1/7, ..., 1/(2 я -1 − 1) . Сигнал S1 Si отражается на правом конце линии и встречает сигнал ( ) для i ≥ 2 в ячейке n /2. я -1 . Когда S 1 отражается, он также создает нового генерала на правом конце. Сигналы S i строятся с использованием вспомогательных сигналов, которые распространяются влево. Каждый второй раз, когда сигнал перемещается (вправо), он посылает вспомогательный сигнал влево. S 1 движется самостоятельно со скоростью 1, в то время как каждый из более медленных сигналов движется только тогда, когда получает вспомогательный сигнал.
Обобщения
[ редактировать ]Проблема синхронизации расстрельной команды была обобщена на многие другие типы клеточных автоматов, включая многомерные массивы ячеек ( Shinahr 1974 ). Также рассматривались варианты задачи с разными начальными условиями ( Kobayashi & Goldstein 2005 ).
Решения проблемы расстрела можно адаптировать и к другим проблемам. Например, Патрик Фишер ( 1965 ) разработал клеточный автоматный алгоритм для генерации простых чисел на основе более раннего решения проблемы синхронизации расстрельных отрядов.
Ссылки
[ редактировать ]- Бальцер, Роберт (1967), «Минимальное по времени решение проблемы синхронизации расстрельной команды с 8 состояниями», Information and Control , 10 (1): 22–42, doi : 10.1016/S0019-9958(67)90032-0 .
- Фишер, Патрик К. (1965), «Генерация простых чисел с помощью одномерного итерационного массива в реальном времени», Journal of the ACM , 12 (3): 388–394, doi : 10.1145/321281.321290 .
- Гото, Эйичи (1962), Решение проблемы расстрела за минимальное время , То же самое, конспекты курса по прикладной математике 298, Кембридж, Массачусетс: Гарвардский университет, стр. 52–59 . Цитируется Ваксманом (1966) .
- Кобаяши, Кодзиро; Гольдштейн, Дарин (2005), «О формулировках проблем синхронизации расстрелов», Нетрадиционные вычисления (PDF) , Конспекты лекций по информатике, том. 3699, Springer-Verlag, стр. 157–168, doi : 10.1007/11560319_15 .
- Мазойе, Жак (1987), «Решение проблемы синхронизации расстрельного отряда с шестью состояниями за минимальное время», Theoretical Computer Science , 50 (2): 183–238, doi : 10.1016/0304-3975(87)90124-1 .
- Мур, Франция; Лэнгдон, Г.Г. (1968), «Общая проблема расстрела», Information and Control , 12 (3): 212–220, doi : 10.1016/S0019-9958(68)90309-4 .
- Шинахр, Илька (1974), «Двух- и трехмерная проблема синхронизации расстрельного отряда», Information and Control , 24 (2): 163–180, doi : 10.1016/S0019-9958(74)80055-0 .
- Ваксман, Абрахам (1966), «Оптимальное решение проблемы синхронизации расстрельной команды», Information and Control , 9 (1): 66–78, doi : 10.1016/S0019-9958(66)90110-0 .