Piaskownice Cheopsa

Po długiej przerwie proponuję zadanie z Wielkiej Przesmyckiej 2014 (która była główną choć nie jedyną przyczyną tejże przerwy). Zadanie jest o piaskownicach, kopalniach, i mamie Cheopsa. Wydaje mi się w miarę fajne, ale pewnie nie jestem w tej kwestii tak całkiem wiarygodny.

Treść (zadania D, bardzo fajną) można zobaczyć tutaj (wspomniana pani mama Cheopsa jest Wam pewnie dobrze znana). Dostajemy graf dwudzielny, w którym należy znaleźć maksymalny przepływ o jak najmniejszym koszcie. Przepustowości wszystkich wierzchołków i krawędzi są równe 1, więc na maksymalny przepływ można patrzeć jak na rozwiązanie następującego układu nierówności:

\begin{array}{cc} &\max \sum_{i,j} f_{i,j}\\ \forall_{i,j} & f_{i,j}\in[0,e_{i,j}]\\ \forall_{i} & \sum_j f_j \leq 1\\ \forall_j &\sum_i f_i \leq 1\\ \end{array}

gdzie e_{i,j}=0 jeśli i-ty lewy wierzchołek nie jest połączony z j-tym prawym wierzchołkiem, no i e_{i,j}=1 w przeciwnym wypadku. Dodatkowo interesuje nas najtańszy z takich maksymalnych przepływów. Koszt przepływu definiuje się zwykle tak, że jeśli krawędzią o koszcie c przesyłamy f jednostek, zwiększa to sumaryczny koszt o c\cdot f. W tym przypadku jest jednak zupełnie inaczej. Jeśli z i-tego lewego wierzchołka wypływa sumarycznie f_i=\sum_j f_{i,j} jednostek, zwiększa to sumaryczny koszt o c_i f_i^2. W wersji basic mamy zawsze c_i=1.

No dobrze, znalezienie maksymalnego przepływu pewnie nie jest żadnym problemem. Problemem nie jest też znalezienie najtańszego maksymalnego przepływu, o ile koszt jest zdefiniowany w standardowy sposób. Jeśli jednak koszty są funkcjami kwadratowymi, łatwo zauważyć, że nawet gdy wszystkie przepustowości są całkowite, wcale nie muszą takie być przepływy przez poszczególne krawędzie w optymalnym rozwiązaniu! Na przykład, jeśli mamy dwa lewe wierzchołki połączone z jednym prawym, oraz c_1=1 i c_2=2, maksymalny przepływ przesyła tylko jedną jednostkę. Dokładniej, przesyła x z pierwszego lewego wierzchołka, no i 1-x z drugiego. Czyli całkowity koszt to po prostu x^2+2(1-x)^2=3x^2-4x+2, więc minimalizując go dostajemy x=\frac{2}{3}. Chyba robi się ciekawie.

Warto zacząć od zastanowienia się nad jednym lub dwoma prostymi przypadkami. Jeśli nasz graf dwudzielny to K_{p,q}, czyli każdy z p lewych wierzchołków jest połączony z każdym z q prawych wierzchołków, oraz wszystkie c_i są takie same, oczywiście maksymalny przepływ to \min(p,q). Jeśli p\leq q, nie musimy się starać, bo wszystkie maksymalne przepływy mają takie same koszty. Jeśli jednak p > q, wybór najlepszego z nich nie jest taki oczywisty. Jednak nie jest też super trudny, wystarczy bowiem zminimalizować \sum_i f^2_i, gdzie \sum_i f_i=q. Ponieważ funkcja f(x)=x^2 jest wypukła, najlepszym wyborem jest ustalenie f_i=\frac{q}{p}. Można wysnuć stąd (słuszny) wniosek, że w pewnym sensie chodzi nam o wybranie maksymalnego przepływu, który jest możliwie zbalansowany. W pewnym sensie.

Co prawda w zadaniu mamy graf dwudzielny, ale nie okazuje się to szczególnie pomocne w dalszym myśleniu o problemie. Sformułujmy problem w nieco bardziej ogólny sposób. Mamy dany skierowany graf z wyróżnionym źródłem s i ujściem t, w którym każda krawędź u\rightarrow v ma określoną (całkowitą) przepustowość e(u,v). Dodatkowo, krawędzie wychodzące ze źródła s mają określone współczynniki c(s,v). Interesuje nas maksymalny przepływ z s do t o najmniejszym możliwym koszcie. Płacimy tylko i wyłącznie za przepływy na krawędziach wychodzących z s, oraz jeśli taką krawędzią przesłane zostało f jednostek, gdzie f niekoniecznie jest całkowite, zwiększa to sumaryczny koszt do c(s,v)f^2. Znalezienie maksymalnego przepływu nawet w tej ogólnej wersji nie przysparza żadnego problemu. Wystarczy użyć, na przykład, algorytmu Edmondsa-Karpa. Dołożenie warunku, że przepływ ma dodatkowo być najtańszy, dość drastycznie zmienia sytuację, pokażemy jednak, że przy odrobinie sprytu można zredukować problem do serii starannie skonstruowanych instancji problemu, w którym pytamy się o istnienie przepływu wysycającego wszystkie krawędzie wychodzące ze źródła.

Zajmijmy się najpierw wersją basic, czyli załóżmy, że c(s,v)=1 dla każdego v. W dalszym rozumowaniu pomocna będzie następująca konstrukcja: każdą krawędź s\rightarrow v o przepustowości e(s,v) zastępujemy wieloma mniejszymi. Dokładniej, ustalamy parametr x i tworzymy e(s,v)\cdot x nowych krawędzi. Przepustowość i-tej z nich to dokładnie \frac{1}{x}, a koszt to [g(\frac{i}{x})-g(\frac{i-1}{x})]x, gdzie g(z)=z^{2}. Otrzymujemy w ten sposób nowy graf, w którym koszt przepływu jest zdefiniowany w „normalny” sposób. Teraz okazuje się, że koszty przepływów w obu grafach są całkiem podobne.

  1. Jeśli umiemy przesłać f jednostek w nowym grafie płacąc c, to umiemy przesłać f\frac{x-1}{x} jednostek w oryginalnym grafie płacąc też c. Dlaczego? Popatrzmy na najtańszy maksymalny przepływ w nowym grafie. Na pewno nie zdarzy się, że przesyłamy coś i-tą z krawędzi odpowiadających oryginalnemu e(s,v) (w skrócie: i-krawędzią), ale nie przesyłamy niczego (i-1)-tą z nich. Czyli całkowicie wysycamy i najtańszych krawędzi odpowiadających oryginalnemu e(s,v), i być może częściowo wysycamy i+1-tą. Za przesłanie \frac{i}{x} jednostek tymi całkowicie wysyconymi krawędziami płacimy g(\frac{i}{x})x w nowym grafie, czyli równie dobrze możemy je przesłać płacąc g(\frac{i}{x}), czyli dokładnie tyle samo, w oryginalnym grafie. Tracimy przy tym co najwyżej jedną x-tą przepływu na każdej krawędzi wychodzącej ze źródła.
  2. Jeśli umiemy przesłać f jednostek w oryginalnym grafie płacąc c, to umiemy przesłać f\frac{x-1}{x} jednostek w nowym grafie płacąc też c. Wystarczy bowiem zaokrąglić w dół przepływ na każdej krawędzi wychodzącej ze źródła do wielokrotności \frac{1}{x}.

Teraz pewnie łatwo uwierzyć, że wybierając olbrzymie x dostaniemy, że koszt maksymalnego przepływu w obydwu grafach jest bardzo podobny (jasne jest, że maksymalne przepływy w obydwu grafach przesyłają tyle samo, gdyż dzieląc krawędzie na mniejsze zachowaliśmy ich sumaryczną przepustowość). Sformalizowanie tej wiary pewnie wymaga modyfikacji powyższego rozumowania tak, aby powiedzieć coś o kosztach przesłania dokładnie f jednostek w obydwu grafach. Darujemy sobie. Tak czy inaczej, zwiększając x możemy dowolnie dobrze aproksymować odpowiedź, a w granicy dostaniemy dokładny wynik.

Przyjrzyjmy się teraz, jak będzie wyglądało uruchomienie algorytmu wyznaczającego najtańszy przepływ (w nowym grafie). Taki algorytm wybiera za każdym razem najtańszą ścieżkę powiększającą. Ponieważ koszty są zdefiniowane tylko krawędziach wychodzących ze źródła, tak naprawdę algorytm rozważa te krawędzie zaczynając od najtańszej, no i każdą kolejną stara się przepchnąć tyle, ile się da. Zmodyfikujmy to postępowanie tak, aby w przypadku, w którym nie da się całkowicie wysycić kolejnej krawędzi, nie przesyłać nią niczego (zauważmy, że nie psuje to obserwacji, że na pewno nie wystąpi sytuacja, w której przesyłamy coś i-tą z krawędzi odpowiadających oryginalnemu c(s,v), ale nie przesyłamy niczego (i-1)-tą z nich). Być może zwiększy to koszt optymalnego przepływu, ale podobnie jak wcześniej, zwiększanie x zbliża nas dowolnie blisko do prawidłowej odpowiedzi (tak naprawdę sytuacja jest odrobinę bardziej skomplikowana, bowiem taka modyfikacja może zmniejszyć maksymalny przepływ, ale mimo to w granicy otrzymamy dokładny wynik).

Teraz możemy już skonstruować finalny algorytm, który wygląda w następujący sposób: dla ustalonego x rozważamy kolejno i=1,2,\ldots. Dla każdego i wyznaczamy maksymalną liczbę i-krawędzi, które mogą być jednocześnie nasycone (przypomnijmy, że i-krawedź to i-ta krawędź utworzonych dla oryginalnego e(s,v)), nazwijmy tę liczbę \ell. Zauważmy, że \ell jest nierosnąca dla kolejnych i. Dzięki temu zamiast ustalać konkretną wartość x możemy symulować działanie finalnego algorytmu dla bardzo dużego (wręcz nieskończonego) x w następujący sposób: dla kolejnych \ell=n,n-1,\ldots wyznacz maksymalną wartość \epsilon, dla której da się jednocześnie przesłać dodatkowe \epsilon jednostek dokładnie \ell krawędziami wychodzącymi ze źródła. Lub, mówiąc inaczej, powtarzaj następującą operację: wyznacz maksymalną wartość \epsilon, dla której da się jednocześnie przesłać dodatkowe \epsilon jednostek wszystkimi krawędziami wychodzącymi ze źródła, z których da się jeszcze trafić (w sieci residualnej) do ujścia.

I koniec. No, koniec części basic. Mamy bowiem n iteracji, w każdej z nich szukamy jak największego \epsilon stosując wyszukiwanie binarne, wewnątrz którego pytamy się o istnienie przepływu, który wysyca wszystkie krawędzie wychodzące ze źródła. Dokładniej, dla każdej krawędzi, z której da się jeszcze trafić (w sieci residualnej) do ujścia, tymczasowo podmieniamy przepustowość na równą \epsilon, a następnie uruchamiamy jakiś w miarę rozsądny algorytm, który znajduje maksymalny (nieważony) przepływ. Jeśli znaleziony przepływ to \ell \cdot \epsilon, nasze \epsilon było OK, a jeśli nie to nie.

Teraz zastanówmy się nad przypadkiem, w którym c(s,v) są być może różne dla różnych v. Wtedy i-krawędzie niekoniecznie mają takie same koszty, a więc niekoniecznie można rozważać je jednocześnie, a w zasadzie na tym opierało się nasze rozwiązanie. Możemy jednak zmodyfikować ich definicję w następujący sposób: przepustowość i-krawędzi odpowiadającej s\rightarrow v o przepustowości e(s,v) to \frac{1}{c(s,v)x}, a jej koszt to [g(\frac{i}{c(s,v)x})-g(\frac{i-1}{c(s,v)x})]c^2(s,v)x. Musimy zadbać o zachowanie sumarycznej przepustowości, czyli tworzymy e(s,v)\cdot c(s,v)x nowych krawędzi. Teraz koszt wszystkich i-krawędzi jest dalej taki sam, lecz różne są ich przepustowości. Możemy jednak zmodyfikować nasze rozwiązanie w następujący sposób: tak długo jak jest to możliwe wyznaczaj maksymalną wartość \epsilon, dla której da się jednocześnie przesłać dodatkowe \frac{\epsilon}{c(s,v)} jednostek każdą krawędzią s\rightarrow v, z której da się jeszcze trafić (w sieci residualnej) do ujścia. Czyli po prostu im droższa krawędź tym mniej chętnie używamy jej do powiększenia przepływu.

W wersji professional dalej mamy n iteracji, w których używamy wyszukiwania binarnego. W tej wersji do zmieszczenia się w limitach czasowych koniecznie było jednak użycie czegoś nieco lepszego ni algorytm Edmondsa-Karpa do sprawdzania, czy możliwe jest wysycenie wszystkich krawędzi wychodzących ze źródłach. Można było użyć na przykład algorytmu Dinica. Konieczna jest też odrobina ostrożności, aby nie potknąć się na przypadku c(s,v)=0 (w powyższym rozumowaniu niejawnie założyliśmy, ze c(s,v)>0 wykonując dzielenie). Nie jest to jednak duży problem: wystarczy zaczać od znalezienia maksymalnego przepływu używającego tylko takich krawędzi wychodzących ze źródła.

Ciekawe może być zastanowienie się, czy rzeczywiście konieczne jest to wyszukiwanie binarne. Mam wrażenie, że powinno dać się jakoś sprytniej, ale niestety nie wiem jak. Dlaczego może to być ciekawe? Otóż fajnie mieć algorytm w pełni wielomianowy, to znaczy taki, którego czas działania zależy od wielkości grafu, ale nie od wielkości liczb, które pojawiają się jako przepustowości (czy koszty). Wyszukiwanie binarne sprawia, że nasz czas działania niestety trochę zależy od żądanej dokładności i c(s,v). Na tym kończę dzisiejszą transmisję z pociągu Berlin-Warszawa-Express i zapraszam za dwa tygodnie: rozwiążemy sobie zadanie z algorytmów tekstowych. Też w miarę ciekawe!

Advertisements

3 myśli nt. „Piaskownice Cheopsa

  1. Szalone. Spodziewałem się raczej jakiejś adaptacji algorytmu Newtona: mając jakieś rozwiązanie, zauważamy, że pochodna jest funkcją liniową, a więc mamy jakiś residualny graf w którym szukamy zwykłego najtańszego przepływu gdzie każda krawędź ma koszt odpowiadający pochodnej … i że po iluśtam iteracjach to gdzieśtam zbiega.

    • Zbiegać to pewnie i zbiega, ale ja bym nie był taki pewny, że zbiega szybko. Mieliśmy rozwiązanie, które robiło coś w stylu steepest descent (czyli chyba to o co Ci chodzi) + cycle cancelling do szukania min cost max flow, no i potrzebowało naprawdę sporo iteracji. Ale może da się to jakoś prosto naprawić, nie wiem.

  2. Ahaaa, zapomniałem tam na końcu napisać, że nie umiem zrobić jakoś szybko wersji, w której funkcja kosztu jest na przykład c_i (x^2+x^3), tzn wypukła, ale nie postaci c_i x^k 🙂

Skomentuj

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

Logo WordPress.com

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

Zdjęcie z Twittera

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

Facebook photo

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

Google+ photo

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

Connecting to %s