Miejska geografia

Na ponury grudniowy wieczór proponuję zadanie z Ural Sport Programming Championship 2015, którego treść można przedstawić w jednym zdaniu: chcemy znaleźć drzewo spinające o jak najmniejszej różnicy kosztu między najdroższą na najtańszą krawędzią. Brzmi fajnie, prawda?

Oryginalną treść można zobaczyć tutaj tutaj. Patrząc na limity widzimy, że pewnie interesuje nas rozwiązanie o złożoności liniowo-logarytmicznej, choć być może możemy sobie pozwolić na logarytm kwadrat (lub skomplikowane rozwiązanie z dużą stałą; co kto woli!). Graf jest nieskierowany, koszt krawędzi e będziemy oznaczać jako c(e), i jesteśmy proszeni o wypisanie drzewo o najmniejszej możliwej różnicy. Nie przejmujmy się jednak za bardzo tym ostatnim i myślmy o wyliczaniu samej różnicy, przy odrobinie szczęścia odtworzenie odpowiadającego mu drzewa nie będzie masakrą.

Zacznijmy od posortowania krawędzi e_1,e_2,\ldots,e_m tak, żeby c(e_1) \leq c(e_2) \leq \ldots \leq c(e_m). Teraz dla każdego i interesuje nas wyznaczenie najmniejszego możliwego j takiego, że e_i, e_{i+1},\ldots,e_j rozpina cały graf (jeśli i jest zbyt duże, takie j może nie istnieć). Nazwijmy to j=j(i) partnerem i. Dlaczego interesują nas właśnie takie j(i)? Dlatego, że po ich wyliczeniu rozwiązanie całego zadania sprowadza się do wypisania najmniejszej możliwej wartości c(e_{j(i)})-c(e_i) (po wszystkich i, dla których j(i) jest zdefiniowane).

Dość łatwo wyliczyć jedno j(i). Musimy tylko dodawać kolejne krawędzie i,i+1,i+2,\ldots do początkowego grafu tak długo, jak liczba spójnych składowych jest większa niż 1. Dysponując strukturą union-find możemy więc poznać j(i) w czasie prawie liniowym. Ale to przecież za wolno!

Zauważmy jednak, że wyznaczane wartości j(i) są monotoniczne, to znaczy mamy j(1) \leq j(2) \leq \ldots \leq j(m) (dla wygody uznajmy, że nieistniejące j jest równe \infty). Może więc dałoby się jakoś wykorzystać część pracy wykonywanej podczas wyliczania j(i-1) do wyliczenia j(i)? Lub na odwrót?

Dla ustalonego i wyliczenie j(i) to tak naprawdę wyznaczenie najtańszego drzewa spinającego używającego krawędzi e_i,e_{i+1},\ldots,e_m. Powiedzmy więc, że wyznaczamy nie tylko samą wartość j(i), ale też całe drzewo. Wtedy przejście z i do i-1 sprowadza się dorzucenia e_i do aktualnego drzewa, a następnie usunięciu z niego dokładnie jednej krawędzi. Dokładniej, jeśli e_i=(x,y), interesuje nas pozbycie się najdroższej krawędzi na ścieżce między x oraz y w drzewie. Dlaczego? Przypomnijmy, że krawędzie nienależące do MST to dokładnie te krawędzie, które są najcięższe na pewnym cyklu (jest to tak zwana czerwona reguła), czyli krawędzie które nie załapały się do drzewa skonstruowanego dla i nie będą mieć więcej szczęścia dla i-1. Dodatkowo, e_i na pewno należy do nowego drzewa. Ale jak jak znaleźć tę najdroższą krawędź?

miejska1

Wystarczy użyć drzew splay. Można je bowiem wzbogacić tak, aby utrzymywać zbiór drzew, które można przecinać i sklejać, tak aby możliwe było wyliczenie najcięższej krawędzi na ścieżce między dwoma wierzchołkami, a wszystkie operacje zajmowały zamortyzowany czas \mathcal{O}(\log n). Tak wzbogacona strukura nazywa się drzewami link-cut (od obsługiwanych operacji). Ale czy na pewno chcemy dzisiaj implementować drzewa splay?

Niekoniecznie. Spójrzmy więc na całą sytuację bardziej globalnie. Aby znaleźć partnera dla każdej krawędzi e_1,e_2,\ldots,e_m, odpalmy się rekurencyjnie dla krawędzi e_1,e_2,\ldots,e_{m/2} oraz dla krawędzi e_{m/2+1},e_{m/2+2},\ldots,e_m. W ten sposób na pewno poprawnie wyznaczymy wszystkie j(i) dla i\geq m/2+1, jednak być może stwierdzimy, że j(i)=\infty dla pewnych i\leq m/2, podczas gdy tak naprawdę j(i) jest z zakresu [m/2+1,m]. Jak temu zaradzić?

Podobnie, to jest rekurencyjnie. Napiszmy procedurę, która przyjmuje dwa zakresy oryginalnych krawędzi e_a,e_{a+1},\ldots,e_b oraz e_c,e_{c+1},\ldots,e_d dla b<c o takiej własności, że partner każdej krawędzi z tego pierwszego zbioru należy do tego drugiego. Wybierzmy t=\frac{a+b}{2} i naiwnie wyliczmy partnera e_t (za pomocą struktury union-find). Z monotoniczności wynika, że do naprawienia partnerów krawędzi e_a,e_{a+1},\ldots,e_{t-1} wystarczy uruchomić się dla zakresów e_a,e_{a+1},\ldots,e_{t-1} wraz z e_c,e_{c+1},\ldots,e_{j(t)}. Trochę gorzej jeśli chodzi o naprawę partnerów krawędzi e_{t+1},e_{t+2},\ldots,e_b. Wiemy, że dla każdego z nich odpowiedź to co najmniej t, ale czy naiwne wywołanie rekurencyjne nie będzie zbyt wolne?

Pewnie będzie. Skoro jednak wiemy, że dla każdego z nich odpowiedź to co najmniej t, możemy na sztywno dorzucić krawędzie e_c,e_{c+1},\ldots,e_{t} do każdego z rozpatrywanych rozwiązań. A to tak naprawdę sprowadza się do utożsamienia ich końców. Tak naprawdę nasza procedura przyjmuje więc nie dwa zakresy oryginalnych krawędzi, a po prostu pewien graf (niekoniecznie też podany na wejściu), którego krawędzie są podzielone na dwa zbiory (tańszy i droższy; zakładamy, że partner każdej tańszej krawędzi jest jedną z tych droższych). Pierwsze wywołanie rekurencyjne dostaje ten sam zbiór wierzchołków, lecz mniejszy zbiór krawędzi. W drugim wywołaniu rekurencyjnym traktujemy każdą spójną składową złożoną ze „sztywnych” krawędzi jako nowy wierzchołek (i dodatkowo usuwamy niektóre krawędzie). Do skonstruowania argumentów tych dwóch wywołań musimy tylko wyliczyć partnera środkowej krawędzi z pierwszego zbioru używając struktury union-find. Ale dlaczego miałoby to szybko działać?

Oznaczmy rozmiary zbiorów przez n_1 oraz n_2. Wtedy czas działania naszej procedury naprawiającej to z grubsza T(n_1,n_2)=\mathcal{O}(n_1+n_2)+T(n_1/2,x)+T(n_1/2,n_2-x), gdzie x może być w zasadzie dowolne (i gdzie uznaliśmy, że union-find działa w czasie stałym na operację). Czyli mamy co najwyżej \log n_1 poziomów rekurencji, a rozmiary wszystkich podproblemów na tej samej głębokości w drzewie wywołań sumują się do n_1+n_2. Czyli koszt naprawy to \mathcal{O}((n_1+n_2)\log n_1).

A jaki jest całkowity czas działania? T(n)=2T(n/2)+\mathcal{O}(n\log n), co rozwiązuje się do \mathcal{O}(n\log^2 n). Odrobinę wolniej niż przy użyciu drzew splay, ale może umiecie to jakoś naprawić?

Reklamy

2 myśli nt. „Miejska geografia

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