Детерминированная проблема рандеву - Deterministic rendezvous problem

В детерминированная задача рандеву это вариант проблема рандеву где игроки, или роботы, должны найти друг друга, следуя детерминированный последовательность инструкций. Хотя каждый робот следует одной и той же последовательности инструкций, уникальная метка, назначенная каждому роботу, используется для нарушение симметрии. Обычно роботы действуют синхронно, хотя существуют и несинхронные версии детерминированной задачи рандеву.^[1]

Обзор

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

Информация, известная роботу, следующая:

• Т, количество шагов по времени с момента его активации
• d, то степень узла, занятого в данный момент роботом
• L, метка робота (обычно в виде битовой строки)

Чтобы решить проблему детерминированного рандеву, обоим роботам должна быть предоставлена ​​последовательность детерминированных инструкций, которые позволяют роботам использовать свою известную информацию для поиска друг друга. Считается, что роботы нашли друг друга, если они оба занимают один и тот же узел на графике в течение одного временного шага.^[1]

Решения

Существует ряд алгоритмов для решения детерминированной задачи рандеву. Некоторые из решений перечислены ниже:

Dessmark et. аль

В 2006 году Дессмарк и др. представили решение, которое решает детерминированную проблему рандеву за время, пропорциональное ${\textstyle O\left(n^{5}{\sqrt {\tau l}}+n^{10}l\right)}$, куда:

• п это количество узлов в графе
• τ разница во времени активации между двумя роботами
• л длина самой короткой из этикеток роботов

Это решение не идеально, так как τ является входным параметром детерминированной задачи рандеву и поэтому может быть сколь угодно большим.^[2]

Ковальский и Малиновский

В 2008 году Ковальский и Малиновски представили решение, которое решает проблему в ${\textstyle O\left(n^{15}+l^{3}\right)}$ время.^[3] Это значительное улучшение, поскольку эта временная сложность не зависит от τ. Однако у этого решения есть один существенный недостаток. Он использует возврат, где роботы должны отслеживать каждое пройденное ребро. Это недостаток, потому что он делает предположения о структуре графа (а именно о том, как он помечен), а также о сенсорных возможностях и памяти роботов.

Та-Шма и Цвик

Решение, представленное Та-Шма и Цвик в 2014 году решает проблему в ${\textstyle O\left(n^{5}+l\right)}$ время. В дополнение к уменьшенной временной сложности (которая не зависит от τ), это решение также не использует отслеживание с возвратом. Вместо этого он использует понятие универсальные последовательности обхода чтобы помочь решить проблему.^[1]

Универсальная последовательность обхода - это последовательность инструкций, содержащих обход графа для любого регулярный график с заданным количеством вершин и для любой начальной вершины.^[4] Поскольку роботы не могут быть в обычном графе, универсальная последовательность обхода для п узлы и степень d используется, где d - максимальная степень графа. Любые инструкции в выбранной универсальной последовательности обхода, которые указывают, что робот перемещается к соседу текущего узла, который не существует (т. Е. Текущий узел имеет степень < d) игнорируются. При этом все узлы в графе со степенью меньше, чем d рассматриваются как имеющие достаточно петель, чтобы довести их общую степень до d, что позволяет рассматривать граф как регулярный для универсальных обходов.^[1]

Основная идея решения Та-Шмы и Цвика состоит в том, что если один из роботов завершает полный обход графа, а другой робот остается в режиме ожидания, или отдыхает, то встреча двух роботов гарантирована. Поскольку размер графа неизвестен, роботы запускают универсальные последовательности обхода для увеличения значений п, при этом периодически отдыхая. Будет ли робот отдыхать до или после обхода, зависит от значения его метки.^[1]

Например, один из роботов может выполнить последовательность:

$${\displaystyle U_{1}0^{u_{1}}U_{2}0^{u_{2}}U_{4}0^{u_{4}}U_{8}0^{u_{8}}...U_{2^{i}}0^{u_{2^{i}}}...}$$

а другой робот выполняет последовательность:

$${\displaystyle 0^{u_{1}}U_{1}0^{u_{2}}U_{2}0^{u_{4}}U_{4}0^{u_{8}}U_{8}...0^{u_{2^{i}}}U_{2^{i}}...}$$

где ты_я - универсальная последовательность обхода графа с я узлы, u_я - количество шагов в этой универсальной последовательности обхода, а 0^k представляет k ступеньки, на которых отдыхает робот. Универсальная последовательность обхода для размера фактического графа будет выполняться одним роботом, в то время как другой будет выполняться для количества шагов в этом обходе. Однако это работает только в том случае, если два робота активированы одновременно.^[1]

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

$${\displaystyle \sigma _{1}0^{u_{1}-1}\sigma _{2}0^{u_{1}-1}\sigma _{3}0^{u_{1}-1}...\sigma _{u_{1}}0^{u_{1}-1}0^{2u_{1}}\pi _{1}0^{u_{2}-1}\pi _{2}0^{u_{2}-1}\pi _{3}0^{u_{2}-1}...\pi _{u_{2}}0^{u_{2}-1}0^{2u_{2}}}$$

где σ_я это я^th шаг U₁ и π_я это я^th шаг U₂.^[1]

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

• σ^б = 0, если б = 0
• σ^б = σ, если б = 1
• ${\displaystyle {\bar {L}}=1-L}$
• ${\displaystyle \sigma ^{m_{1}..m_{k}}=\sigma _{1}^{m}...\sigma _{k}^{m}}$
• ${\displaystyle D_{k}(\sigma _{1}...\sigma _{m})=\sigma _{1}0^{k}...\sigma _{m}0^{k}}$

Предполагая, что метка одного робота равна 0, а метка другого робота равна 1, каждый робот будет запускать следующую последовательность:

$${\displaystyle D_{u_{1}-1}((U_{1}U_{1})^{L{\bar {L}}})D_{u_{2}-1}((U_{2}U_{2})^{L{\bar {L}}})...D_{u_{2^{k}}-1}((U_{2^{k}}U_{2^{k}})^{L{\bar {L}}})...}$$

Подпоследовательность ${\textstyle D_{u_{i}-1}((U_{i}U_{i})^{L{\bar {L}}})}$ известен как блокировать и может быть переписан как ${\textstyle D_{u_{i}-1}((U_{i}U_{i})^{L}(U_{i}U_{i})^{\bar {L}})}$.

Если σ = U_я и m = u_я, блок можно дополнительно упростить до:

$${\displaystyle (\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1})^{L}}$$

$${\displaystyle (\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1})^{\bar {L}}}$$

Обе приведенные выше строки известны как куски. Один блок состоит из универсальной последовательности обхода с чередующимися периодами отдыха, а другой блок представляет собой период отдыха длиной 2.м².

Если метка робота равна 0, то каждый блок, который он запускает, равен:

$${\displaystyle 0^{2m^{2}}\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}}$$

Если метка равна 1, то каждый запускаемый блок равен:

$${\displaystyle \sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}0^{2m^{2}}}$$

Анализ

Последовательность приведенных выше инструкций позволит двум роботам с метками 0 и 1 встретиться после O (п^2c) временные шаги.^[1]

Та-Шма и Цвик показывают, как расширить это решение, чтобы позволить роботам встречаться только через O (п^c) временные шаги и способы работы с произвольными метками (что увеличивает время до встречи роботов до O (п⁵+л) временные шаги).^[1]

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

1. Та-Шма, Амнон; Цвик, Ури (Апрель 2014 г.). «Детерминированные встречи, поиски сокровищ и строго универсальные последовательности исследований». ACM-транзакции на алгоритмах. 10 (3). 12.
2. Дессмарк, А .; Fraingnaud, P .; Ковальски, Д .; Пелц, А. (2006). «Детерминированное рандеву в графах». Алгоритмика. 46 (1): 69–96. Дои:10.1007 / s00453-006-0074-2.
3. Ковальский, Д .; Малиновский, А. (2008). «Как познакомиться в анонимной сети». Теоретическая информатика. 399 (1–2): 144–156. Дои:10.1016 / j.tcs.2008.02.010.
4. Алелиунас, Р .; Karp, R .; Lipton, R .; Lovász, L .; Ракофф, К. (1979). «Случайные блуждания, универсальные последовательности обходов и сложность задач лабиринта». 20-й ежегодный симпозиум по основам компьютерных наук (sfcs 1979). Дои:10.1109 / SFCS.1979.34.