Ile ścieżek?

Większość z Was na pewno widziała już przynajmniej „kilka” zadań, w których używa się metody dziel-i-zwyciężaj. Mam jednak nadzieję, że nie widzieliście zadania, które jest (aktualnie) moim ulubionym przykładem użycia tej techniki. Wydaje mi się, że najbardziej naturalnym kontekstem, w którym można o niej mówić, są drzewa. Zastanówmy się więc nad następującym pytaniem: jak szybko zliczyć (dla danego drzewa, którego krawędzie mają niekoniecznie całkowite wagi) pary wierzchołków, które są od siebie odległe o dokładnie (znów, niekoniecznie całkowite) D? Skoro ma to być przykład metody dziel-i-zwyciężaj, łatwo się domyśleć, że chcielibyśmy celować w złożoność \mathcal{O}(n\log n), jednak… po drodze pojawi się przynajmniej jedna niespodzianka 🙂

Skoro chcemy skorzystać tutaj z techniki dziel-i-zwyciężaj, musimy umieć zredukować oryginalny problem do kilku mniejszych. Wybierzmy więc dowolny wierzchołek x\in T i.. usuńmy go! W rezultacie uzyskamy kolekcję mniejszych drzew T_1,T_2,\ldots,T_k. Powiedzmy, że umiemy szybko zliczyć dla każdego i pary wierzchołków u,v\in T_i odległych od siebie o dokładnie D. Czy w jakikolwiek sposób pomaga nam to w rozwiązaniu oryginalnego problemu? Trochę tak, a trochę nie: musimy jeszcze zliczyć te u,v\in T, które należą do różnych mniejszych drzew. No i pewnie uwzględnić to, że u albo v (czy nawet obydwa z nich) mogą być tak naprawdę naszym wybranym wierzchołkiem x.

Zacznijmy od zliczenia wszystkich par postaci \{x,u\}. Wymaga to tylko wyznaczenia dla każdego u odległości od x, co może być wręcz trywialnie wykonane w czasie liniowym za pomocą jednego przeszukiwania w głąb uruchomionego w x. Następnie wypadałoby zliczyć pary \{u,v\}, dla których u\in T_i oraz v\in T_j dla wszystkich możliwych 1\leq i<j\leq k. Jest to tyle kłopotliwe, że k może być dość duże (w szczególności, nawet rzędu n. Na szczęście można dość łatwo pozbyć się tego kłopotu.

Lemat. Oryginalny problem można zredukować w czasie liniowym do zliczania par czerwonych wierzchołków odległych o dokładnie D w drzewie stopnia co najwyżej 3, w którym każdy wierzchołek jest czerwony lub czarny.

Dowód. Będziemy stopniowo przebudowywać T pozbywając się wierzchołków stopnia większego niż 3. Powiedzmy, że mamy u, którego sąsiedzi to v_1,v_2,\ldots,v_k, gdzie k>3. Zastępujemy u ciągiem nowych wierzchołków tak jak na poniższym rysunku, przy czym kolor u' jest taki sam jak oryginalny kolor u, a wszystkie pozostałe nowe wierzchołki są czarne.

ile_redukcja

Dość łatwo uwierzyć, że liczba par czerwonych wierzchołków odległych o dokładnie D nie ulega zmianie, oraz całą procedurę można zaimplementować w czasie liniowym.

Od tego momentu możemy więc zakładać, że k\leq 3, czyli tak naprawdę bez większego problemu możemy rozważyć osobno wszystkie możliwe indeksy i<j. Pozostaje (no, może nie jest to właściwe słowo: jak na razie nie wydarzyło się jeszcze nic ciekawego) więc przyjrzeć się ścieżkom długości D (w oryginalnym T) łączącym czerwone u\in T_i oraz v\in T_j. Powiedzmy, że korzeń r_i każdego T_i to ten z wierzchołków, który w oryginalnym T był sąsiadem x, oraz że d_T(p,q) jest długością (unikalnej) ścieżki łączącej p i q w T. Jeśli d_T(r_i,x)+d_T(x,r_j)=w (tę wartość można łatwo wyznaczyć w czasie stałym, bo przecież jest to po prostu suma długości dwóch krawędzi), tak naprawdę musimy zliczyć ile jest czerwonych u\in T_i oraz v\in T_j, dla których d(u,r_i)+d(v,r_j)=D-w.

W tym momencie możemy tak naprawdę zupełnie zapomnieć o drzewach! Powiedzmy, że utworzymy (posortowaną) listę A zawierającą wszystkie liczby d(u,r_i) dla czerwonych u\in T_i oraz (również posortowaną) listę B zawierającą wszystkie liczby d(v,r_j) dla czerwonych v\in T_j. Wtedy dość łatwo można zliczyć pary liczb x\in A, y\in B, x+y=D-w rozważając kolejne x i dla każdego z nich utrzymując najmniejsze y\geq D-w-x. Po każdym przesunięciu się z x w prawo być może musimy przesunąć się z y w lewo, być może nawet wiele razy, jednak suma wszystkich przesunięć będzie na pewno liniowa. Czyli tak naprawdę najbardziej kosztownym elementem całego zliczania jest posortowanie list, które może być wykonane w czasie \mathcal{O}(n\log n).

No i pięknie: udało nam się zredukować w czasie \mathcal{O}(n\log n) orygialne pytanie dotyczące drzewa T do (w najgorszym przypadku) trzech dotyczących mniejszych drzew T_1,T_2,T3. Mogłoby się wydawać, że możemy być z siebie dumni, lecz niestety lekkomyślny wybór wierzchołka x może spowodowac, że złożoność całego rozwiązania będzie \mathcal{O}(n^2\log n), na przykład jeśli zaczniemy od długiej ścieżki, no i za każdym razem x będzie jednym z końców. A przecież możemy łatwo uzyskać \mathcal{O}(n^2) uruchamiając przeszukiwanie w głąb z każdego wierzchołka. Czyli raczej smuteczek.

A może i nie smuteczek. Przecież x może być wybrane z zachowaniem choć odrobiny zdrowego rozsądku. Można na przykład skorzystać z poniższego lematu, który (podobno) był już znany Jordanowi (temu od krzywych). Co prawda nie udało mi się tego zweryfikowac, ale był to niewątpliwie bardzo mądry gość, więc… niech będzie.

Lemat.Dla dowolnego drzewa T można znaleźć w czasie liniowym wierzchołek x, którego usunięcie powoduje rozpadnięcie się T na mniejsze drzewa, których rozmiary nie przekraczają \frac{1}{2}n.

Dowód. Na dobry początek wybierzmy dowolne x\in T. Jeśli jego usunięcie powoduje, że T rozpada się na dostatecznie małe kawałki, kończymy zabawę. W przeciwnym wypadku wybieramy największy z tych kawałków i zastępujemy x jego sąsiadem, który znajduje się właśnie tam. Precyzyjny dowód poprawności i analizę czasu działania takiej procedury pozostawiam dociekliwemu Czytelnikowi.

Uzbrojeni w powyższy lemat, możemy już skonstruować algorytm, którego czas działania wyrazi się rekurencją:

T(n)=\mathcal{O}(n\log n)+T(n_1)+T(n_2)+T(n_3)

gdzie n_1+n_2+n_3=n-1 oraz n_1,n_2,n_3\leq\frac{1}{2}n. Po chwili zastanowienia i, na przykład, wyobrażeniu sobie drzewka wszystkich wywołań rekurencyjnych, można zauważyć, że T(n)=\mathcal{O}(n\log^2n). Czyli koniec!

Oczywiście tylko żartowałem. Przecież na samym początku zdecydowaliśmy się celować w złożoność \mathcal{O}(n\log n). Gdyby tylko udało nam się pozbyć tego sortowania…

W tym momencie dużo zależy od przyjętego modelu obliczeń. Jeśli na przykład powiemy, że wystarcza nam czas oczekiwany, sortowanie można śmiało zastąpić haszowaniem, i w rezultacie łatwo osiągamy żądany oczekiwany czas \mathcal{O}(n\log n). Jeśli jednak interesuje nas rozwiązanie w pełni deterministyczne, robi się o wiele ciekawiej. Przyjrzyjmy się jeszcze raz pojedynczemu wywołaniu rekurencyjnemu. Wybieramy „środkowy” wierzchołek x, porządkujemy wszystkie (w najgorszym przypadku) wierzchołki względem ich odległości od x, oraz powtarzamy całą operację dla mniejszych drzew uzyskanych po usunięciu x. W każdym z nich ponownie wybieramy „środkowy” wierzchołek, porządkujemy wszystkie wierzchołki względem ich odległości, … Cała sytuacja wygląda więc mniej więcej tak jak na poniższym rysunku.

ile-rekurencja

Powiedzmy, że najpierw wykonamy całą operację dla mniejszych drzew, a dopiero później zabierzemy się za sortowanie wierzchołków względem ich odległości od x. Popatrzmy się na mniejsze drzewo T_1. Wybraliśmy w nim wierzchołek x', po usunięciu którego otrzymaliśmy jeszcze mniejsze drzewa T'_1,T'_2,T'_3. Teraz chcielibyśmy posortować wierzchołki w T_1 względem ich odległości od x, co tak naprawdę sprowadza się do posortowania (dalej względem odległości od x!) wierzchołków w T'_1,T'_2,T'_3. Teraz zauważmy, że w przypadku wierzchołków w T'_2 i T'_3 tak naprawdę równie dobrze moglibyśmy sortować względem odległości od x'! Jest o tyle lepsze, że przecież takie sortowanie wykonaliśmy już w wywołaniu rekurencyjnym. Pozostaje jednak kwestia posortowania wierzchołków w T'_1, dla których co prawda także wykonaliśmy sortowanie względem odległości od x', jednak niekoniecznie pomaga nam to w sortowania względem odległości od x. Jednak przypomnijmy, że w T'_1 wybraliśmy wierzchołek x'', po usunięciu którego otrzymaliśmy (już całkiem mizerne) drzewa T''_1,T''_2,T''_3. Znów, w przypadku wierzchołków w T''_2 i T''_3 zamiast sortować względem odległości od x możemy równie dobrze sortować względem odległości od x'', co tak naprawdę wykonaliśmy już wcześniej. A w przypadku wierzchołków w T''_1… pewnie domyślacie się co dalej. Cały proces można zobaczyć na poniższej ilustracji.

ile-descend

Inaczej mówiąc, zamiast sortować wszystkie wierzchołków względem odległości od x wystarczy połączyć ze sobą \mathcal{O}(\log n) posortowanych list L_1,L_2,\ldots, gdzie |L_i|\leq (\frac{1}{2})^i n. A to jest, w gruncie rzeczy, dość łatwe, i może być wykonane w sumarycznym czasie \mathcal{O}(n), o ile tylko zaczniemy od najkrótszej listy i będziemy stopniowo łączyć kolejne z aktualnym wynikiem.

Czyli pokazaliśmy, że tak naprawdę można uporządkować wszystkie wierzchołki względem ich odległości od x w czasie liniowym. Po takiej modyfikacji rozwiązania rekurencja opisująca sumaryczny czas działania zmienia się na:

T(n)=\mathcal{O}(n)+T(n_1)+T(n_2)+T(n_3)

która, na podstawie podobnego rozumowania jak wcześniej, rozwiązuje się do \mathcal{O}(n\log n).

Pozostaje się zastanowić, czy nie dałoby się lepiej… Jeśli chcemy pozostać w modelu arytmetycznym (czyli, mówiąc w skrócie, dopuszczamy tylko dodawanie/odejmowanie wag krawędzi), dość łatwo jest pokazać, że raczej by się nie dało. Jednak czy na pewno chcemy?

Reklamy

9 myśli nt. „Ile ścieżek?

  1. Hmm, nie da się chyba edytować komentarzy, to napiszę czwarty ;). W ostatnim równaniu rekurencyjnym powinno być O(n) zamiast O(nlogn).

  2. W wersji gdy krawędzie mają małe naturalne długości (np. wszystkie równe 1) da się chyba bez hashowania, używając po prostu listy list : wierzchołek w odległości d od korzenia umieszczamy w d-tej liście. W zasadzie to wystarczy nam zwykła lista intów, na której pamietamy ile jest wierzchołków w danej odległości.

    Zastanawiam się czy wnioskiem z tego Twojego rozwiązania nie jest struktura danych która zużywa O(nlgn) pamięci i pozwala dla dowolnego x wypisać w O(n) wszystkie wierzchołki w kolejności odległości od x. Nie wiem do czego to by miało służyć, ale może do znajdowania najbliższych stacji benzynowych w bajtocji…

  3. Tego z listą list to nie rozumiem, bo przecież nawet jeśli wagi krawędzi są bardzo małe, w którymś momencie będziemy mieli ich sumy, które mogą być nawet n? Chyba, że chodziło Ci o tablicę list?

    W tym pytaniu na samym końcu chodziło mi o coś takiego: powiedzmy, że umiemy sortować inty szybciej niż w O(nlogn) (no bo umiemy), czy można osiągnąć mniej niż O(nlogn) dla całego problemu? (nie wiem)

  4. Jeśli dobrze rozumiem, każda z par jest zliczana ‚na palcach’, tzn. wymaga własnej iteracji. Oznacza to, że jeżeli odpowiedź(ilość par w odległości K) to więcej niż n log n, to złożoność tego algorytmu nie wyniesie O (n log n). Łatwo skonstruować taki przykład, że ilość takich par będzie rzędu n^2.

    Konstrukcja: (n/2-1) wierzchołków łączymy z wierzchołkiem A krawędzią o wadze 1, inne (n/2-1) wierzchołków łączymy w ten sam sposób z wierzchołkiem B(ostatnim nieużytym). Teraz łączymy wierzchołek A z B. Powstaje drzewo podobne do sztangi, w którym każdy z wierzchołków połączonych z A(prócz B) jest w odległości 3 od wierzchołków połączonych z B(bez A). Zatem dla zapytania o ilość par odległych o 3, odpowiedź to: (n/2-1)(n/2-1) co jest rzędu n^2.

    Błąd w uzasadnieniu algorytmu leży chyba tutaj: „Po każdym przesunięciu się z x w prawo być może musimy przesunąć się z y w lewo, być może nawet wiele razy, jednak suma wszystkich przesunięć będzie na pewno liniowa.”.
    Otóż, jeżeli zbiory z x i y będą miały elementy powtarzające się (co bardzo łatwo może się zdarzyć) to samo przesuwanie się nie wystarczy. Konieczne mogą być powroty.

    Można to jednak ominąć i liczyć prawe i lewe takie same elementy(odpowiednio) tworzące tą samą sumę, po czym mnożąc je otrzymać ilość par (nie licząc „na palcach”, tj. inkrementacją).

    Jeśli gdzieś w rozumowaniu jest błąd to proszę o poprawę 🙂

    • Faktycznie nie napisałem tego wprost, ale chciałbym zakładać, że elementy w tych zbiorach nie powtarzają się, czyli kolapsować duplikaty (co chyba sugerujesz). Ewentualnie przesuwać nie jeden palec, a dwa. Jest to już kwestia implementacyjna.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s