Wioślarze

Przez ostatni miesiąc byłem niestety trochę zajęty i nie udało mi się dokończyć żadnego z zaległych wpisów, ale kilka dni temu dostałem linka (dzięki!) do zadania, obok którego nie mogę przejść obojętnie. Jest o grafie (fajnie!) z wagami (jeszcze lepiej!), a w opisie rozwiązania pojawi się pojęcie schematu prymalno-dualnego (nie wiem jak Wy, ale ja już nie mogę się doczekać!). Treść jest tutaj, ale można ją przekazać w jednym zdaniu wielokrotnie złożonym: mamy dany nieskierowany graf (na n\leq 500 wierzchołkach) z wagami na krawędziach (niestety, wszystkimi takimi samymi i równymi k, czyli jakby trochę nudno), każdemu wierzchołkowi v chcemy przyporządkować cenę w(v) tak, aby dla każdej krawędzi (u,v) o wadze k było w(u)+w(v)\geq k. No, hm, i żeby zminimalizować sumaryczny koszt \sum_v w(v). A więc… właśnie, co?

…może przepływ? Mamy graf, wagi, chcemy przyporządkować coś do czegoś, n nie jest super duże. W tej sytuacji doświadczony zawodnik pewnie od razu pomyśli sobie, że być chodzi tutaj o jakiś przepływ. Nie jest jednak oczywiste, jak miałaby wyglądać sieć przepływowa. Skoro chcemy coś minimalizować, pewnie powinien być to najtańszy przepływ. Z drugiej strony, przepływy są zwykle całkowitoliczbowe, a w przykładzie z treści zadanie odpowiedzi nijak takie nie są. Więc…

No dobra, to może jednak nie przepływ. Ciężko powiedzieć. Może spróbujmy zacząć od jakiejś specjalnej wersji zadania? Na przykład takiej, w której k=1.

Niestety, nie wydaje się to jakoś istotnie prostsze. No to może graf powinien być jakiś specjalny? Moglibyśmy zacząć drzewa, ale to byłoby zbyt nudne. Popatrzmy więc na przypadek, w którym graf jest dwudzielny. Dlaczego właśnie dwudzielny? Cóż, często jest tak, że problem, który jest NP-trudny dla dowolnych grafów, można rozwiązać w czasie wielomianowym dla grafów dwudzielnych. Powód dobry jak każdy inny.

Czyli mamy dany graf dwudzielny. Każdemu z wierzchołków chcemy przyporządkować koszt tak, aby dla dowolnej krawędzi (u,v) było w(u)+w(v)\geq 1. Od razu widać, że nie ma sensu wybierać w(u) > 1 (no, ani w(u)<0). Czyli w(u)\in [0,1], w szczególności w(u) może być równe 0 lub 1. Zastanówmy się, czy kiedykolwiek opłaca się wybrać coś pomiędzy, czyli na przykład w(u)=0.73? Okazuje się, że nie! Weźmy bowiem takie u, że w(u)\in (0,1) i popatrzmy się na podgraf złożony tylko z tych krawędzi (u,v), dla których w(u)+w(v)=1 (powiedzmy, że są one niebezpieczne), tak jak na poniższej ilustracji.

wioslarze

Niech S_1 i S_2 będą odpowiednio lewą i prawą częścią spójnej składowej tego podgrafu, w której znajduje się u. Teraz wyobraźmy sobie, że zwiększamy wszystkie w(v) dla v\in S_1 o \epsilon oraz (jednocześnie) zmniejszamy w(v) dla v\in S_2 o taki sam \epsilon. O ile tylko nasz \epsilon będzie dostatecznie mizerny, taka podmiana nie popsuje tego, że w(u)+w(v)\geq 1 dla każdej krawędzi! Co więcej, jeśli |S_1| < |S_2|, podmiana nie dość, że nie zmieni tego, że mamy prawidłowe rozwiązanie, to jeszcze zmniejszy jego sumaryczny koszt. Gdy |S_1| > |S_2|, możemy wykonać symetryczną sztuczkę. Gdy zaś |S_1|=|S_2|… no, w zasadzie też (co prawda nie mamy gwarancji, że zmniejszymy koszt rozwiązania, ale można powiedzieć, że w przypadku remisu interesuje nas to, które jest najmniejsze leksykograficznie; są to nudne szczegóły).

No i pięknie. Pokazaliśmy, że (w przypadku grafów dwudzielnych i k=1) interesują nas tylko rozwiązania całkowitoliczbowe. Teraz wystarczy tylko przypomnieć sobie, że kwestia wybrania jak najmniej wierzchołków tak, aby przynajmniej jeden z końców każdej krawędzi został wybrany, to nic innego jak pokrycie wierzchołkowe! No i wiedzieć, że moc najmniejszego pokrycia wierzchołkowego to nic innego jak moc największego skojarzenia. Ten wesoły fakt jest znany jako twierdzenie Königa. Czyli tak naprawdę w naszym szczególnym przypadku wystarczy tylko policzyc matching, a to umiemy robić dość szybko. Powiedzmy, że w czasie \mathcal{O}(n^3) (choć, rzecz jasna, umiemy lepiej).

No to może spróbujmy pozbyć się założenia, że k=1? Spróbujmy!

Okazuje się to być wręcz trywialne. Mianowicie wystarczy przeskalować wszystkie wagi i ceny dzieląc je przez k! W rezultacie dostaniemy graf, w którym k=1, a z takim już umiemy sobie poradzić. Następnie po prostu mnożymy wynik przez k.

Trochę gorzej wygląda kwestia pozbycia się założenia, że graf jest dwudzielny. Tym niemniej łatwo zauważyć, że powyższy trik z normalizacją wag zupełnie nie zależał od struktury grafu, a więc musimy tylko poradzić sobie z przypadkiem, gdy graf niekoniecznie jest dwudzielny, ale na pewno k=1. Sytuacja staje się o tyle niezręczna, że (na przykład) dla cyklu długości 3 optymalne rozwiązanie koniecznie wybiera w(u)=0.5, czyli nie możemy ograniczyć się do rozwiązań całkowitoliczbowych.

Okazuje się jednak, że możemy zredukować sytuację do takiej, w której graf jest dwudzielny. Mianowicie dla każdego wierzchołka u oryginalnego grafu tworzymy dwie kopie u_1 i u_2. Podobnie, dla każdej krawędzi (u,v) tworzymy dwie kopie (u_1,v_2) i (v_1,u_2). Otrzymany graf jest oczywiście dwudzielny. Popatrzmy się teraz na rozwiązanie problemu (tego oryginalnego, ale z k=1) w oryginalnym grafie. Wybierając w(u_1)=w(u_2)=w(u) możemy skonstruować rozwiązanie problemu w nowym grafie, którego koszt jest dokładnie dwukrotnie większy! W drugą stronę, popatrzmy się na rozwiązanie problemu (ciągle z k=1) w nowym grafie. Wybierając w(u)=\frac{w(u_1)+w(u_2)}{2} skonstruujemy rozwiązanie problemu w oryginalnym grafie, którego koszt dokładnie dwukrotnie mniejszy! No, być może nie do końca oczywiste jest to, że faktycznie otrzymamy prawidłowe rozwiązanie. Popatrzmy się więc na dowolną krawędź (u,v) i policzmy:

w(u)+w(v)=\frac{w(u_1)+w(u_2)}{2}+\frac{w(v_1)+w(v_2)}{2}=\frac{w(u_1)+w(v_2)}{2}+\frac{w(v_1)+w(u_2)}{2} \geq \frac{1+1}{2}=1

czyli jest całkiem spoko. Otrzymaliśmy, że koszty optymalnych rozwiązań w obydwu grafach różnią się dokładnie dwukrotnie. Co więcej, zamiast rozważać oryginalny graf, możemy rozwiązać problem dla nowego grafu, który jest dwudzielny (czyli potrafimy już sobie z nim poradzić; i to szybko!), a następnie wrócić z optymalnym rozwiązaniem do punktu startu.

I to w zasadzie byłby koniec całej historii, o ile interesowałby nas tylko koszt optymalnego rozwiązania. Niestety, autor postanowił być trochę bardziej wymagający (co, swoją drogą, jest dość typowe dla zadań z tego regionu), i zażądał wypisania cen wierzchołków (w jakimś optymalnym rozwiązaniu). Jeśli popatrzymy się na powyższe rozumowanie, tak naprawdę wymaga to od nas algorytmicznie efektywnego dowodu twierdzenia Königa. Na szczęście taki jest nawet dowód podany na wikipedii (choć wydaje mi się, że brakuje w nim założenia, że graf jest spójny?).

Ale gdzie obiecany schemat prymalno-dualny? W przejściu z pokrycia wierzchołkami do najliczniejszego skojarzenia. Otóż przypomnijmy sobie, że skorzystaliśmy z tego, że moc najmniejszego pokrycia wierzchołkowego jest dokładnie równa mocy największego skojarzenia. Można więc powiedzieć, że te dwa problemy są do siebie dualne. Staje się to o wiele bardziej przydatne, gdy rozważymy ciekawszą wersję zadania, w której wagi krawędzi są niekoniecznie wszystkie takie same. Powiedzmy, że najpierw przyjrzymy się sytuacji, w której graf jest dwudzielny, czyli chcemy znaleźć wartościowanie wszystkich wierzchołków, dla którego w(u)+w(v) \leq c(u,v), gdzie c(u,v) jest wagą krawędzi (u,v). Teraz okazuje się, że jeśli popatrzymy się na koszt dowolnego skojarzenia (w tym samym grafie), nie może ono przekroczyć kosztu dowolnego poprawnego wartościowania! Faktycznie, koszt skojarzenia M może być ograniczony z góry przez sumę w(u) po wszystkich u będących końcem jakiejś krawędzi z M. Taka suma nie może zaś przekroczyć sumy wszystkich w(u), czyli kosztu najtańszego możliwego wartościowania! OK, ale czy oznacza to, że koszt najdroższego skojarzenia musi być dokładnie równy kosztowi najtańszego wartościowania? Byłoby to o tyle przyjemne, że umiemy (efektywnie) wyznaczać ten pierwszy koszt.

Okazuje się, że faktycznie musi tak być, choć dowód nie jest trywialny. Właśnie na tym opiera się tak zwany algorytm węgierski, za pomocą którego można szybko wyznaczać najdroższe pełne skojarzenie w grafie dwudzielnym. Mówiąc w bardzo dużym skrócie, jego działanie polega na jednoczesnym utrzymywaniu zarówno prawidłowego wartościowania, jak i (niekoniecznie pełnego) skojarzenia. W każdej iteracji choć trochę zbliża się on do pożądanej sytuacji, w której ich koszty są takie same. I to własnie jest zwykle nazywane schematem prymalno-dualnym!

Reklamy

4 myśli nt. „Wioślarze

  1. Programy liniowe są wszędzie, ale często (tak jak tutaj) można je rozwiązywać sprytniej niż simplexem 😉 Wydaje mi się, że gdyby limity były 2-3 razy mniejsze to dałoby się zaakceptować simplexem, ale pewnie dlatego właśnie takie są.

  2. A jak trudno jest skonstruować przykład, dla którego simplex działa ponadwielomianowo? Wiem tylko, że jest to możliwe, ale jakoś nigdy.. nie wnikałem..

  3. Simplex to tak naprawdę „schemat algorytmu”, bo dużo zależy od kolejności wykonywanych pivotów. Im wymyślniejsza strategia tym ciężej dobrać przykład 😉 Ale dla wszystkich standardowych metod działa chyba jeden przykład, nie aż tak skomplikowany.
    Dla problemów tego typu, simplex działa bardzo sprawnie 😉

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