Struktura danych dla najkrótszych ścieżek

Niech będzie nieważonym niekierowanym wykresem z wierzchołkami i krawędziami . Czy jest możliwe przetworzenie i utworzenie struktury danych o rozmiarze aby mógł odpowiadać na zapytania o formie „odległość między a ” w czasie O (n)? $G$ $n$ $m$ $G$ $m \cdot \mathrm{polylog}(n)$ $u$ $v$

Problem wydaje się zbyt podstawowy, aby go rozwiązać.

graph-theory graph-algorithms ds.data-structures

— ilyaraz
źródło

W odpowiedzi na twoją ostatnią uwagę na temat „zbyt podstawowy, aby go rozwiązać”: jeśli na pytanie należy odpowiedzieć w stałym czasie, jest ono rzeczywiście dobrze zbadane. Ale chodzi o to, że pozwalasz O (n) na zapytanie (zamiast O (1) lub trywialne O (m)). Chociaż uważam, że jest to interesujące pytanie, nie sądzę, aby miało to fundamentalne znaczenie.

— Tsuyoshi Ito,

@TsuyoshiIto - Nie rozumiem, dlaczego pytanie traci swoje „podstawowe znaczenie”, jeśli pozwala na super-stały, ale subliniowy czas zapytania. Załóżmy na przykład, że mogę rozwiązać powyższy problem z ograniczeniem, że na zapytania dotyczące odległości można odpowiedzieć w czasie dla niektórych , a czas przetwarzania wynosi najwyżej - czy nie dałoby mi to sub-sześciennego algorytmu do obliczania najkrótszych ścieżek? Osobiście uważam, że jest to bardzo interesujące pytanie.

O (n^{1 - ε})

$O(n^{1-\varepsilon})$

ε > 0

$\varepsilon > 0$

O (n^{3 - ε})

$O(n^{3 - \varepsilon})$

— Rachit

Nie wiem, czy istnieje ogólny sposób, czy nie, ale istnieje dobry sposób na ograniczone wykresy szerokości, patrz zapytanie Najkrótsza ścieżka na ograniczonych wykresach szerokości

— Saeed,

Również jeśli możesz stworzyć najkrótsze drzewa ścieżek (zaczynając od każdego węzła), a następnie odpowiedzieć na najkrótszą ścieżkę zapytania (przez powiązany katalog główny) w , lub w podobny sposób możesz zbudować struktura danych o mniejszym rozmiarze pamięci.

m = Ω (n^{2})

$m = \Omega(n^2)$

O (n)

$O(n)$

— Saeed,

Odpowiedzi:

To bardzo interesujące pytanie. Na wysokim poziomie pytasz, czy można wstępnie przetworzyć wykres w taki sposób, aby zapytania o najkrótszą ścieżkę stały się niezależne od gęstości wykresu, bez zajmowania dużo dodatkowej przestrzeni - ciekawe, ale, jak mówisz, nierozwiązane.

Jeśli jesteś zadowolony z przybliżonych odległości, oto sposób na uzyskanie przybliżenia. Niech będzie ważonym niekierowanym wykresem z węzłami i krawędziami . W poniższym artykule pokazano, że w przypadku zapytań o przybliżoną odległość projektowanie struktur danych dla wykresów o krawędziach nie jest trudniejsze niż wykresy, w których każdy węzeł ma stopień ograniczony przez : $2$ $G$ $n$ $m$ $m$ $m/n$

R. Agarwal, PB Godfrey, S. Har-Peled, Przybliżone zapytania odległości i kompaktowe wyznaczanie tras na rzadkich wykresach, INFOCOM 2011

Załóżmy zatem, że jest wykresem ograniczonym do . Próbki węzły losowo jednolite; nazywaj te punkty orientacyjne. Podczas fazy przetwarzania wstępnego zapisz na wykresie odległość od każdego punktu orientacyjnego do każdego innego węzła; wymaga to przestrzeni . Dla każdego węzła zapisz jego najbliższy punkt orientacyjny węzeł . Ponadto przechowuj wykres w strukturze danych, powiedzmy jako listę przylegania. $G$ $m/n$ $\alpha = O(m/n)$ $O(m)$ $u$ $\ell(u)$

W przypadku zapytania o odległość między i , kulki rosną wokół obu węzłów - kulka węzła jest definiowana jako zbiór węzłów, które są bliżej niż do najbliższego punktu orientacyjnego, powiedzmy . Można wykazać, że rozmiar każdej kulki wynosi , zgodnie z oczekiwaniami. Niech , gdzie jest kulą węzła a jest zbiorem sąsiadów węzłów w . Można wykazać, że rozmiar wynosi , w oczekiwaniu. $u$ $v$ $w$ $w$ $\ell(w)$ $O(n^2/m)$ $\Gamma(u) = B(u) \cup N(B(u))$ $B(u)$ $u$ $N(B(u))$ $B(u)$ $\Gamma(u)$ $O(n)$

Odpowiadając na zapytanie: jeśli , zwróć ; w przeciwnym razie, jeśli , zwróć ; w przeciwnym razie zwróć . Łatwo wykazać, że jest to przybliżenie . $\Gamma(u) \cap \Gamma(v) \neq \emptyset$ $\min_{x \in \Gamma(u) \cap \Gamma(v)} \{d(u, x) + d(v, x)\}$ $d(u, \ell(u)) \leq d(v, \ell(v))$ $d(u, \ell(u)) + d(\ell(u), v)$ $d(v, \ell(v)) + d(\ell(v), u)$ $2$

Jeśli chodzi o czas zapytania, zwróć uwagę, że rosnące kule wymagają czasu dla wykresu ograniczonego do ; konstruowanie i danych odpowiednich piłkach zajmuje czasu (ponieważ sąsiedzi są zapisani w strukturze danych); i sprawdzenie, czy jest pusta, czy też nie zajmuje czasu. $O(n)$ $m/n$ $\Gamma(u)$ $\Gamma(v)$ $O(n)$ $\Gamma(u) \cap \Gamma(v)$ $O(n)$

Powyższe granice są oczekiwane; Myślę, że łatwo jest odandomizować konstrukcję. Niestety, ta technika nie pozwala uzyskać przybliżenia lepszego niż . To bardzo interesujące pytanie ... $2$

— Rachit
źródło

Powyższa technika nie wykorzystuje faktu, że wykres wejściowy jest nieważony; być może jest coś interesującego, co możesz zrobić, wykorzystując ten fakt, ale nie mogę wymyślić sposobu na uzyskanie dokładnych odległości. Na przykład, możliwe jest skrócenie czasu zapytania do i uzyskanie odległości ograniczonej przez , gdzie jest dokładną odległością i .

O (n^{2} / m)

$O(n^2/m)$

2 d + 1

$2d+1$

d

$d$

u

$u$

v

$v$

— Rachit

Uświadomiłem sobie, że nie rozumiem, dlaczego jest to przybliżenie 2. Thorup-Zwick w tych samych sytuacjach daje 3-ok.

— ilyaraz

@ilyaraz: Zauważ, że schemat Thorup-Zwick nie wymaga sprawdzania (a zatem odpowiada na zapytania w niemal stałym czasie). Zobacz papier, o którym wspomniałem powyżej, na dowód odcinka .

Γ (u) \cap Γ (v)

$\Gamma(u) \cap \Gamma(v)$

2

$2$

— Rachit

To, czego potrzebujesz, nazywa się „wyrocznią na odległość”. Niestety, nie znam się zbytnio na wyroczniach dystansowych, dlatego mogę skierować was tylko do przełomowej pracy z powodu Thorupa i Zwicka:

Mikkel Thorup i Uri Zwick. Wyrocznie w przybliżeniu na odległość. STOC '01, 2001.

Oto fragment streszczenia:

Niech będzie niekierowanym ważonym wykresem z oraz . Niech będzie liczbą całkowitą. Pokazujemy, że można wstępnie przetwarzać w oczekiwanym czasie w , konstruując strukturę danych o rozmiarze , tak aby dowolne kolejne na zapytanie o odległość można odpowiedzieć w przybliżeniu w czasie . Przybliżona zwrócona odległość wynosi co najwyżej , tzn. Iloraz uzyskany przez podzielenie szacunkowej odległości przez rzeczywistą odległość wynosi od 1 do . [...] Wymagane miejsce w naszym algorytmie jest [...] zasadniczo optymalne. $G = (V, E)$ $|V| = n$ $|E| = m$ $k$ $G = (V, E)$ $O(kmn^{1/k})$ $O(kn^{1+1/k})$ $O(k)$ $2k - 1$ $2k - 1$

Zgodnie z ich wynikami, to, o co prosisz, jest w zasadzie wykonalne nawet dla wykresów ważonych: wybranie daje odległość wyroczni o rozmiarze uzyskaną w oczekiwanym czasie , który może odpowiedzieć na twoje najkrótsze zapytania o ścieżkę za pomocą -stretch w czasie ! $k=1$ $O(n^2)$ $O(mn)$ $1$ $O(1)$

Wyrocznie wyrocznie to bardzo dobrze zbadana dziedzina, więc wierzę, że będziesz mógł dalej kopać.

— Gabor Retvari
źródło

Wersja czasopisma: JACM 2005 .

— Tsuyoshi Ito,

Korzystając z przestrzeni można naiwnie przechowywać tablicę przeglądową. Tak więc ten artykuł (o którym wiedziałem) nie ma tutaj znaczenia.

O (n^{2})

$O(n^2)$

— ilyaraz

Słusznie. Wynik najbardziej zbliżony do żądania AFAIK to wykresy o średnim stopniu które dają ścieżki stretch-2 z miejscem w zapytaniu czas. (R. Agarwal, P. Godfrey i S. Har-Peled, „Przybliżone zapytania o odległość i kompaktowe wyznaczanie trasy na rzadkich wykresach”, INFOCOM 2011.)

Θ (\log n)

$\Theta(\log n)$

O (n^{3 / 2})

$O(n^{3/2})$

O (\sqrt{n})

$O(\sqrt{n})$

— Gabor Retvari

Wykorzystując wbudowane metryki Bourgaina w , można wymyślić wyrocznię ze spacją , czasem zapytania i błędem multiplikatywnym .

ℓ_{1}

$\ell_1$

O (n \log^{2} n)

$O(n \log^2 n)$

O (\log^{2} n)

$O(\log^2 n)$

O (\log n)

$O(\log n)$

— ilyaraz