Задача синхронізації стрільців

Задача синхронізації стрільців — завдання з області інформатики і клітинних автоматів, уперше запропонована Джоном Мейгіллом в 1957 році і опубліковане (з рішенням) в 1962 році Едвардом Муром[1]. Формулюється таким чином:

Розглянемо кінцеве, але довільне число кінцевих автоматів (стрільців), розташованих в ряд. У момент часу t = 0 кожен солдат перебуває у вихідному стані, за винятком найлівішого солдата (командира). Стан кожного солдата у момент часу t > 0 залежить від стану його самого і двох його сусідів у момент часу t − 1(за винятком самих крайніх солдатів, у яких лише один сусід). Якщо солдат і його сусіди знаходяться в початковому стані, то в цьому ж стані вони і залишаються в наступні моменти часу. Завдання полягає в тому, щоб знайти кінцевий набір станів і правил переходу між ними, які допускали б одночасний перехід усіх солдатів в необхідний стан (вогонь).

Історія

Перше рішення цієї задачі було знайдене Джоном Маккарті і Марвіном Мінскі і було опубліковано в Sequential Machines Едвардом Муром. Краще з відомих рішень, що використовуює шість станів, було знайдено Жаком Мазойером в 1987 році[2]. Раніше Роберт Бальцер довів, що рішень з чотирма станами не існує[3]. (Пітер Сандерс згодом з'ясував, що пошукова процедура Бальцера була неповною, проте виправивши процедуру, отримав той же результат.) Досі невідомо, чи існує рішення з п'ятьма станами.

Рішення, що вимагає мінімальний час, було знайдене професором Е. Гото з МТІ[4]. Воно використовує декілька тисяч станів і вимагає рівно 2n − 2 одиниць часу для n солдатів. Доведено, що ефективніших за часом рішень не існує.

Загальне рішення

Загальне рішення задачі описує дві хвилі станів, що поширюються по ряду солдатів, одна з яких рухається втричі швидше за іншу. Швидка хвиля відбивається від далекого краю ряду і зустрічається з повільною в центрі. Після цього дві хвилі розділяються на чотири, що рухаються в різні боки від центру. Процес триває, кожного разу подвоюючи число хвиль, поки довжина відрізків ряду не стане рівною  1. У цей момент усі солдати стріляють. Це рішення вимагає 3n одиниць часу для n солдатів.

Рішення, що вимагає мінімального часу

Оптимальне за часом рішення уперше було описане в статті Waksman, 1966[5]. Командир посилає крайньому солдатові сигнали S1, S2, S3, ., Si з частотами 1, 1/3, 1/7, ., 1/(2 i− 1 − 1). Сигнал S1 відбивається від правого краю ряду і зустрічає сигнал Si (для i ≥ 2) в осередку n/2 i− 1. Коли S1 відбивається, він також створює нового командира на правому кінці.

Сигнали Si генеруються з використанням допоміжних сигналів, що поширюються вліво. Кожен другий момент часу звичайний сигнал генерує допоміжний сигнал, що поширюється вліво. S1 рухається самостійно із швидкістю 1, тоді як повільніші сигнали рухаються тільки при отриманні допоміжних сигналів.

Узагальнення

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

Джерела

Література

  • Shinahr, Ilka (1974). Two- and three-dimensional firing-squad synchronization problem. Information and Control. Academic Press. 24: 163—180. doi:10.1016/S0019-9958(74)80055-0. {{cite journal}}: Проігноровано невідомий параметр |address= (можливо, |location=?) (довідка)

Ресурси Інтернету

Примітки

  1. ↑ F.R. Moore, G.G. Langdon, A generalized firing squad problem. Information and Control, Volume 12, Issue 3, March 1968, Pages 212—220. - 9958(68) 90309-4 DOI
  2. ↑ Jacques Mazoyer, A six-state minimal time solution to the firing squad synchronization problem. Theoretical Computer Science, 1987, vol. 50 pp 183—238 90124-1 DOI
  3. ↑ Robert Balzer, An 8-state Minimal Time Solution to the Firing Squad Synchronization Problem. Information and Control, 1967, vol.10, pp. 22-42 - 9958(67) 90032-0 DOI
  4. ↑ 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)
  5. ↑ Abraham Waksman, An Optimum Solution to the Firing Squad Synchronization Problem. Information and Control, 1966, vol. 9, pp.66-78 - 9958(66) 90110-0 DOI