Vzdálenost věštce - Distance oracle - Wikipedia

v výpočetní, a distanční věštec (DO) je datová struktura pro výpočet vzdáleností mezi vrcholy v a graf.

Úvod

Nechat G(PROTI,E) být neorientovaný vážený graf s n = |PROTI| uzly a m = |E| hrany. Rádi bychom odpověděli na dotazy ve tvaru „jaká je vzdálenost mezi uzly s at?".

Jedním ze způsobů, jak to udělat, je spustit Dijkstrův algoritmus. To vyžaduje čas ${ displaystyle O (m + n log n)}$, a nevyžaduje žádný další prostor (kromě samotného grafu).

Abychom mohli na mnoho dotazů odpovědět efektivněji, můžeme strávit nějaký čas předzpracováním grafu a vytvořením pomocné datové struktury.

Jednoduchá datová struktura, která tohoto cíle dosahuje, je matice který určuje pro každou dvojici uzlů vzdálenost mezi nimi. Tato struktura nám umožňuje odpovídat na dotazy v konstantním čase ${ displaystyle O (1)}$, ale vyžaduje ${ displaystyle O (n ^ {2})}$ extra prostor. Lze jej inicializovat včas ${ displaystyle O (n ^ {3})}$ pomocí algoritmu nejkratších cest všech párů, jako je například Floyd-Warshallův algoritmus.

DO leží mezi těmito dvěma extrémy. Využívá méně než ${ displaystyle O (n ^ {2})}$ místo za účelem odpovědi na dotazy za méně než ${ displaystyle O (m + n log n)}$ čas. Většina DO musí dělat kompromisy ohledně přesnosti, tj. Nevrací přesnou vzdálenost, ale spíše její konstantní faktorovou aproximaci.

Přibližně DO

Thorup a Zwick^[1] popsat více než 10 různých DO. Poté navrhnou nový DO pro každého k, vyžaduje prostor ${ displaystyle O (kn ^ {1 + 1 / k})}$, takže na jakýkoli následný dotaz na vzdálenost lze přibližně včas odpovědět ${ displaystyle O (k)}$. Přibližná vrácená vzdálenost je maximálně natažená ${ displaystyle 2k-1}$, tj. kvocient získaný dělením odhadované vzdálenosti skutečnou vzdáleností leží mezi 1 a ${ displaystyle 2k-1}$. Čas inicializace je ${ displaystyle O (kmn ^ {1 / k})}$.

Některé speciální případy zahrnují:

• Pro ${ displaystyle k = 1}$ dostaneme jednoduchou matici vzdálenosti.
• Pro ${ displaystyle k = 2}$ dostaneme strukturu pomocí ${ displaystyle O (n ^ {1.5})}$ prostor, který odpovídá na každý dotaz v konstantním čase a v přibližném faktoru maximálně 3.
• Pro ${ displaystyle k = lfloor log n rfloor}$, dostaneme strukturu pomocí ${ displaystyle O (n log n)}$ prostor, čas dotazu ${ displaystyle O ( log n)}$a protáhnout se ${ displaystyle O ( log n)}$.

Vyšší hodnoty k nezlepšují prostor ani dobu předzpracování.

DO pro obecné metrické prostory

Věštec je postaven na zmenšující se sbírce k+1 sady vrcholů:

• ${ displaystyle A_ {0} = V}$
• Pro každého ${ displaystyle i = 1, ldots, k-1}$: ${ displaystyle A_ {i}}$ obsahuje každý prvek z ${ displaystyle A_ {i-1}}$, nezávisle, s pravděpodobností ${ displaystyle n ^ {- 1 / k}}$. Všimněte si, že očekávaná velikost ${ displaystyle A_ {i}}$ je ${ displaystyle n ^ {1-i / k}}$. Prvky ${ displaystyle A_ {i}}$ se nazývají i-centra.
• ${ displaystyle A_ {k} = emptyset}$

Pro každý uzel proti, vypočítat jeho vzdálenost z každé z těchto sad:

• Pro každého ${ displaystyle i = 0, ldots, k-1}$: ${ displaystyle d (A_ {i}, v) = min {(d (w, v) | w v A_ {i}}}$ a ${ displaystyle p_ {i} (v) = arg min {(d (w, v) | w v A_ {i}}}$. Tj., ${ displaystyle p_ {i} (v)}$ je i-centrum nejblíže k proti, a ${ displaystyle d (A_ {i}, v)}$ je vzdálenost mezi nimi. Všimněte si, že pro pevné proti, tato vzdálenost se slabě zvyšuje s i. Všimněte si také, že pro každého proti, ${ displaystyle d (A_ {0}, v) = 0}$ a ${ displaystyle p_ {0} (v) = v}$.
• ${ displaystyle d (A_ {k}, v) = infty}$.

Pro každý uzel proti, vypočítat:

• Pro každého ${ displaystyle i = 0, ldots, k-1}$: ${ displaystyle B_ {i} (v) = {w v A_ {i} setminus A_ {i + 1} | d (w, v)$. ${ displaystyle B_ {i} (v)}$ obsahuje všechny vrcholy v ${ displaystyle A_ {i}}$ které jsou striktně blíže proti než všechny vrcholy v ${ displaystyle A_ {i + 1}}$. Částečné odbory ${ displaystyle B_ {i}}$s jsou koule s rostoucím průměrem, které obsahují vrcholy se vzdálenostmi až k prvnímu vrcholu další úrovně.

Pro každého proti, spočítat jeho chomáč:

• ${ displaystyle B (v) = bigcup _ {i = 0} ^ {k-1} B_ {i} (v).}$

Je možné ukázat, že očekávaná velikost ${ displaystyle B (v)}$ je nanejvýš ${ displaystyle kn ^ {1 / k}}$.

Pro každou partu ${ displaystyle B (v)}$, postavte a hash tabulka to platí pro každého ${ displaystyle w v B (V)}$, vzdálenost ${ displaystyle d (w, v)}$.

Celková velikost datové struktury je ${ displaystyle O (kn + Sigma | B (v) |) = O (kn + nkn ^ {1 / k}) = O (kn ^ {1 + 1 / k})}$

Po inicializaci této struktury následující algoritmus najde vzdálenost mezi dvěma uzly, u a proti:

• ${ displaystyle w: = u, i: = 0}$
• zatímco ${ displaystyle w notin B (v)}$:
  • ${ displaystyle i: = i + 1}$
  • ${ displaystyle (u, v): = (v, u)}$ (zaměňte dva vstupní uzly; tím se nezmění vzdálenost mezi nimi, protože graf je neorientovaný).
  • ${ displaystyle w: = p_ {i} (u)}$
• vrátit se ${ displaystyle d (w, u) + d (w, v)}$

Je možné ukázat, že v každé iteraci je vzdálenost ${ displaystyle d (w, u)}$ roste maximálně ${ displaystyle d (v, u)}$. Od té doby ${ displaystyle A_ {k-1} subseteq B (v)}$, existuje nanejvýš k-1 iterace, takže konečně ${ Displaystyle d (w, u) leq (k-1) d (v, u)}$. Nyní u nerovnost trojúhelníku, ${ Displaystyle d (w, proti) leq d (w, u) + d (u, v) leq kd (v, u)}$, takže vrácená vzdálenost je maximálně ${ displaystyle (2k-1) d (u, v)}$.

Vylepšení

Výše uvedený výsledek později vylepšili Patrascu a Roditty^[2] kteří navrhují DO velikosti ${ displaystyle O (n ^ {4/3} m ^ {1/3})}$ který vrací aproximaci faktoru 2.

Redukce z nastaveného křižovatkového věštce

Pokud existuje DO s aproximačním faktorem nejvýše 2, je možné sestavit a nastavit křižovatku věštce (SIO) s časem dotazu ${ displaystyle O (1)}$ a prostorové požadavky ${ displaystyle O (N + n)}$, kde n je počet sad a N součet jejich velikostí; vidět nastavit průnik věštec # Redukce na přibližnou vzdálenost věštec.

Předpokládá se, že problém SIO nemá netriviální řešení. Tj. To vyžaduje ${ displaystyle Omega (n ^ {2})}$ prostor pro včasné zodpovězení dotazů ${ displaystyle O (1)}$, např. pomocí n-podle-n tabulka s průnikem mezi oběma sadami. Pokud je tato domněnka pravdivá, znamená to, že neexistuje DO s aproximačním faktorem menším než 2 a konstantním časem dotazu.^[2]

Reference