Deterministický problém schůzky - Deterministic rendezvous problem

The deterministický problém schůzky je varianta problém schůzky kde hráči, nebo roboti, se musí najít podle a deterministický sled pokynů. Přestože každý robot dodržuje stejnou posloupnost instrukcí, je pro každý robot použit jedinečný štítek lámání symetrie. Roboti obvykle jednají synchronně, i když existují nesynchronní verze deterministického problému setkání.^[1]

Přehled

V synchronní verzi deterministického problému setkávání jsou oba roboti zpočátku umístěni na libovolném místě uzly v konečném, spojeném, neusměrněném graf. Velikost a struktura grafu není robotům známa.

Robot zná tyto informace:

T, počet časových kroků od aktivace
d, stupeň uzlu aktuálně obsazeného robotem
L, štítek robota (obvykle ve formě bitového řetězce)

K vyřešení problému s deterministickým setkáním musí být oběma robotům dána posloupnost deterministických instrukcí, které robotům umožní použít jejich známé informace k nalezení druhého. Roboti se považují za navzájem nalezené, pokud oba zabírají stejný uzel v grafu během stejného časového kroku.^[1]

Řešení

Řada algoritmů existuje k vyřešení deterministického problému setkání. Některá z řešení jsou uvedena níže:

Dessmark et. al

V roce 2006 Dessmark et al. představil řešení, které řeší deterministický problém setkání v čase úměrném ${ textstyle O left (n ^ {5} { sqrt { tau l}} + n ^ {10} l right)}$ , kde:

n je počet uzlů v grafu
τ je rozdíl v době aktivace mezi dvěma roboty
l je délka kratšího ze štítků robotů

Toto řešení není ideální, protože τ je vstupní parametr deterministického problému schůzky, a proto může být libovolně velký.^[2]

Kowalski a Malinowski

V roce 2008 předložili Kowalski a Malinowski řešení, které problém řeší v roce 2008 ${ textstyle O left (n ^ {15} + l ^ {3} right)}$ čas.^[3] Jedná se o významné zlepšení, protože na této časové složitosti nezávisí τ. Toto řešení má však jednu zásadní nevýhodu. Využívá to ustoupitkde roboti musí sledovat každou hranu, kterou prošli. To je nevýhoda, protože klade předpoklady na strukturu grafu (konkrétně na jeho označení) a na senzorické a paměťové schopnosti robotů.

Ta-Shma a Zwick

Řešení předložené Ta-Shmou a Zwick v roce 2014 řeší problém v ${ textstyle O left (n ^ {5} + l right)}$ čas. Kromě snížené časové složitosti (která se nespoléhá na τ), toto řešení také nepoužívá backtracking. Místo toho používá pojem univerzální traversální sekvence pomoci vyřešit problém.^[1]

Univerzální traversální sekvence je sekvence instrukcí zahrnující a přechod grafu pro všechny běžný graf se stanoveným počtem vrcholů a pro libovolný počáteční vrchol.^[4] Vzhledem k tomu, že roboti nemusí být v běžném grafu, je univerzální traverzová sekvence pro n uzly a stupeň d se používá, kde d je maximální stupeň grafu. Jakékoli pokyny ve zvolené univerzální sekvenci procházení, které určují, že robot cestuje k sousedovi aktuálního uzlu, který neexistuje (tj. Aktuální uzel má stupeň < d) jsou ignorovány. Tímto způsobem všechny uzly v grafu se stupněm menším než d se s nimi zachází jako s dostatečným počtem smyček, aby se jejich celkový stupeň zvýšil na d, což účinně umožňuje považovat graf za běžný pro účely univerzálního procházení.^[1]

Základní myšlenkou řešení Ta-Shmy a Zwicka je, že pokud jeden z robotů dokončí úplný průchod grafu, zatímco druhý robot zůstane nečinný, nebo spočívá, pak se oba roboti zaručeně setkají. Vzhledem k tomu, že velikost grafu není známa, roboti používají univerzální sekvence pro zvýšení hodnoty n, zatímco pravidelně odpočívá. Zda robot odpočívá před nebo po průchodu závisí na hodnotě jeho štítku.^[1]

Například jeden z robotů mohl spustit sekvenci:

{ 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}}} ...}

zatímco druhý robot spouští sekvenci:

{ 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}} ...}

kde ty_i je univerzální traverzová posloupnost pro graf s i uzly, u_i je počet kroků v této univerzální sekvenci procházení a 0^k představuje k kroky, kde robot spočívá. Sekvenci univerzálního průchodu pro velikost skutečného grafu provede jeden robot, zatímco druhý odpočívá na počet kroků v tomto průchodu. Funguje to však pouze v případě, že jsou oba roboti aktivováni současně.^[1]

Pro pokrytí případu, kdy jsou roboti aktivováni v různých časech, bude sekvence, která se má spustit, zahrnovat doby odpočinku délky u_i po každém kroku (v traverzu a době odpočinku). Jeden z robotů by například spustil sekvenci:

{ 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}}}

kde σ_i je i^th krok U₁ a π_i je i^th krok U₂.^[1]

Aby bylo možné formálně představit sekvenci, kterou bude každý robot spouštět, je zapotřebí další notace. Nechat:

σ^b = 0 pokud b = 0
σ^b = σ pokud b = 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} }$

Za předpokladu, že popisek jednoho robota je 0 a popisek druhého robota je 1, posloupnost, kterou by každý robot spustil, je:

{ 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}}}) ...}

Podsekvence ${ textstyle D_ {u_ {i} -1} ((U_ {i} U_ {i}) ^ {L { bar {L}}})}$ je známý jako blok a lze jej přepsat na ${ textstyle D_ {u_ {i} -1} ((U_ {i} U_ {i}) ^ {L} (U_ {i} U_ {i}) ^ { bar {L}})}$ .

Pokud σ = U_i a m = u_i, blok lze dále zjednodušit na:

{ 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}}}

Oba výše uvedené řádky jsou známé jako kousky. Jeden blok se skládá z univerzální traversální sekvence s prokládanými dobami odpočinku, zatímco druhý blok je dobou odpočinku délky 2m².

Pokud je štítek robota 0, pak se každý spuštěný blok rovná:

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

Pokud je štítek 1, pak se každý blok, který běží, rovná:

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

Analýza

Sekvence výše uvedených pokynů umožní dvěma robotům se štítky 0 a 1 setkat se po O (n^2c) časové kroky.^[1]

Ta-Shma a Zwick ukazují, jak rozšířit toto řešení a umožnit robotům setkat se až po O (n^C) časové kroky a jak zacházet s libovolnými štítky (což prodlužuje dobu, než se roboti setkají s O (n⁵+l) časové kroky).^[1]

Reference

^ ^A ^b ^C ^d ^E ^F ^G ^h ⁱ Ta-Shma, Amnon; Zwick, Uri (Duben 2014). „Deterministické setkání, hledání pokladů a silně univerzální průzkumné sekvence“. Transakce ACM na algoritmech. 10 (3). 12.
^ Dessmark, A .; Fraingnaud, P .; Kowalski, D .; Pelc, A. (2006). „Deterministické setkání v grafech“. Algorithmica. 46 (1): 69–96. doi:10.1007 / s00453-006-0074-2.
^ Kowalski, D .; Malinowski, A. (2008). "Jak se setkat v anonymní síti". Teoretická informatika. 399 (1–2): 144–156. doi:10.1016 / j.tcs.2008.02.010.
^ Aleliunas, R .; Karp, R .; Lipton, R .; Lovász, L .; Rackoff, C. (1979). "Náhodné procházky, univerzální sekvence procházení a složitost problémů s bludištěm". 20. výroční sympozium o základech informatiky (sfcs 1979). doi:10.1109 / SFCS.1979.34.

[Ta-Shma_2014-1] A ^b ^C ^d ^E ^F ^G ^h ⁱ Ta-Shma, Amnon; Zwick, Uri (Duben 2014). „Deterministické setkání, hledání pokladů a silně univerzální průzkumné sekvence“. Transakce ACM na algoritmech. 10 (3). 12.

[2] Dessmark, A .; Fraingnaud, P .; Kowalski, D .; Pelc, A. (2006). „Deterministické setkání v grafech“. Algorithmica. 46 (1): 69–96. doi:10.1007 / s00453-006-0074-2.

[Kowalski_2008-3] Kowalski, D .; Malinowski, A. (2008). "Jak se setkat v anonymní síti". Teoretická informatika. 399 (1–2): 144–156. doi:10.1016 / j.tcs.2008.02.010.

[Aleliunas_1979-4] Aleliunas, R .; Karp, R .; Lipton, R .; Lovász, L .; Rackoff, C. (1979). "Náhodné procházky, univerzální sekvence procházení a složitost problémů s bludištěm". 20. výroční sympozium o základech informatiky (sfcs 1979). doi:10.1109 / SFCS.1979.34.

[1]

[2]

[3]

[4]