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