Ochotnicy

Wakacje powoli się kończą, więc tym razem będzie trochę bardziej na serio: rozwiążemy sobie chińskie zadanie o przydziale zadań w (chińskiej) fabryce. Co prawda w treści niby jest coś o Szwecji i ochotnikach, ale kto by się tam dał nabrać. Zadanie jest o tyle fajne, że na pierwszy (a nawet i na drugi) rzut oka wydaje się być na tyle bliskie rzeczywistości, że pewnie (NP-)trudne. Ale, o dziwo, nie jest!

Treść można zobaczyć tutaj. Chcemy zaplanować pracę w ciągu n kolejnych dni. Wiemy, że w i-tym z nich potrzebnych jest przynajmniej a_i pracowników. Pracownicy są podzieleni na m typów, pracownik i-tego typu zaczyna pracę dnia s_i i pracuje aż do dnia t_i, lecz niestety musimy mu za to zapłacić c_i RMB. Możemy zatrudnić dowolnie wiele pracowników każdego typu, ważne jest tylko spełnienie wszystkich żądań i zminimalizowanie sumarycznego kosztu. Aha, n\leq 1000 i m\leq 10000 i autor wydaje się sugerować, że a_i mogą być spore, więc rozwiązanie pewnie musi mieć raczej małą złożoność.

Dość często w zadaniach dotyczących szeregowania zadań, alokacji zasobów, …, dobrym pomysłem jest sformułowanie problemu jako (ważonego lub nie) przepływu w grafie. Czasami jest to bardzo łatwe (jak choćby w sytuacji, w której przydzielamy zadania pracownikom tak, żeby każdy dostał dokładnie jedno zadanie, które potrafi wykonać, i każde zadanie zostało przydzielone dokładnie jednemu pracownikowi), ale w tym przypadku chyba nie jest oczywiste. Mamy sporo parametrów i nie jest jasne, jak przetłumaczyć je wszystkie na język przepływów. Co zrobić?

Jak zwykle warto zacząć od trochę prostszej wersji. W tym przypadku dość naturalnym uproszczeniem jest założenie, że w i-tym dniu chcemy dysponować dokładnie a_i pracownikami. Tak, żeby żaden z nich nie mógł się obijać.

Taką uproszczoną wersję dość łatwo przedstawić jako najtańszy maksymalny przepływ. Wystarczy tylko popatrzeć na różnice b(i)=a(i)-a(i-1) (dla wygody ustalmy, że a(0)=a(n+1)=0). Jeśli b(i)>0, musimy mieć b(i) pracowników, którzy zaczynają pracę w dniu i. Jeśli zaś b(i)<0, musimy mieć -b(i) pracowników, którzy kończą wtedy pracę. Teraz można myśleć o tym tak, że w pewnym sensie chcemy sparować ze sobą żądania tych dwóch typów używając do tego pracowników. Na przykład jeśli b(1)=1 oraz b(2)=-1, pracownik pracujący tylko pierwszego dnia pozwala nam na zredukowanie b(1) i b(2) do zera. W ogólnej sytuacji cała sprawa jest trochę bardziej skomplikowana, i pewnie lepiej jest o tym myśleć w kategoriach sieci przepływowej, w której mamy jeden wierzchołek v_i dla każdego dnia i=1,2,\ldots,n. Dla każdego typu pracownika, który zaczyna pracę w dniu s_i, kończy t_i, i oczekuje pensji w wysokości c_i RMB, dorzucamy krawędź z v_{s_i} do v_{t_i+1} o koszcie c_i i nieskończonej przepustowości. Dodatkowo tworzymy źródło połączone krawędzią o koszcie 0 i przepustowości b_i z każdym wierzchołkiem v_i, dla którego b_i > 0, oraz ujście połączone krawędzią o koszcie 0 i przepustowości -b_i z każdym wierzchołkiem v_i, dla którego b_i<0. Prosty i tendencyjny przykład z treści znajduje się na poniższej ilustracji. Każda z krawędzi jest opisana jako (koszt, przepustowość).

ochotnicy

Dość oczywiste jest, że poprawnemu wyborowi pracowników odpowiada przepływ (o takim samym koszcie) wysycający wszystkie krawędzie wychodzące ze źródła (a więc także te wchodzące do ujścia, bo \sum_i b_i = 0) w tak utworzonej sieci. Może trochę mniej oczywiste (ale dalej prawdziwe) jest to, że każdemu takiemu przepływowi odpowiada poprawny wybór pracowników (o takim samym koszcie!). Wynika to z faktu, że zawsze możemy wybrać tak zmodyfikować przepływ, żeby był całkowitoliczbowy, czyli przesyłał po każdej krawędzi całkowitą liczbę jednostek.

Tyle jeśli chodzi o uproszczoną wersję. Jak pozbyć się założenia, że w i-tym dniu chcemy dysponować dokładnie a_i pracownikami, a nie przynajmniej tyloma? Okazuje się to wręcz zaskakująco proste. Wystarczy tylko dodać krawędzie o koszcie 0 i nieskończonej przepustowości z każdego v_{i+1} do v_{i} (nazwijmy je sobie krawędziami wstecznymi; nie mylić z krawędziami w tył, które są czymś zupełnie innym).

Ale właściwie niby dlaczego miałoby to działać? Pomysł jest o tyle naturalny, że po takiej modyfikacji pracownika, który wcześniej zaczynał pracę w dniu s_i, a kończył w t_i, teraz tak naprawdę zaczyna pracę w dniu s_i lub później, a kończy w t_i lub wcześniej, czyli dodanie krawędzi wstecznych pozwala nam na ewentualnie utrudnienie sobie życia, czyli jakby zwiększenie niektórych a_i. No, pewnie nie jest to super przekonujące, spróbujmy więc podejść do kwestii w trochę bardziej systematyczny sposób.

Chcemy tak zwiększyć niektóre (lub być może wszystkie) a_i, aby koszt przepływu wysycającego wszystkie krawędzie wychodzące ze źródła w "starej" sieci (tej bez krawędzi wstecznych) był jak najmniejszy. Warto zwrócić uwagę na to, że taki przepływ może nie istnieć! Powiedzmy, że zwiększymy a_i o \delta_i\geq 0, czyli tak naprawdę zmienimy b_i o \Delta_i=\delta_i-\delta_{i-1} (które może być dodatnie lub ujemne; a nawet równe zeru). Fajnie byłoby teraz pokazać, że można skonstruować przepływ o dokładnie takim samym koszcie, który wysyca wszystkie krawędzie wychodzące ze źródła w „nowej” sieci z krawędziami wstecznymi skontruoowanej dla oryginalnych a_i.

Skorzystamy w tym celu dość oczywistej metody, mianowicie zmodyfikujemy przepływ, który już mamy. Musimy tylko jakoś poradzić sobie z tym, że zmieniliśmy przepustowości niektórych krawędzi (tych wychodzących ze źródła i tych wchodzących do ujścia). Trzeba więc przekierować te nadmiarowe jednostki. Mówiąc bardziej precyzyjnie, w każdym v_i mamy -\Delta_i nadmiarowych jednostek jeśli \Delta_i < 0, lub brakuje nam tam \Delta_i jednostek jeśli \Delta_i > 0. Teraz zauważmy, że \sum_i \Delta_i = 0, więc może dałoby się jakoś sparować te nadmiarowe jednostki z brakującymi używając darmowych krawędzi wstecznych? Brzmi nawet spoko, należy jednak sprawdzić, że do sparowania faktycznie wystarczy takie przesyłanie wstecz.

Popatrzmy na krawędź wstecz z v_{i+1} do v_i. Możemy jej użyć do sparowania nadmiarowych jednostek po prawej z brakującymi jednostkami po lewej, na pewno trzeba więc sprawdzić, że po lewej nie mamy nadmiaru. Całkowity bilans po lewej to po prostu \sum_{j\leq i} \Delta_j = \delta_i \geq 0, czyli rzeczywiście jedyne co może się zdarzyć to sytuacja, w której po lewej brakuje nam pewnej liczby jednostek. Tak naprawdę oznacza to, że możemy sparować nadmiarowe jednostki z brakującymi: wystarczy tylko przesłać \delta_i jednostek krawędzią wstecz łączącą v_{i+1} z v_i. Co pokazuje, że możemy skonstruować przepływ o dokładnie takim samym koszcie w nowej sieci.

No i fajnie. Teraz trzeba by jeszcze pokazać, że mając przepływ wysycający wszystkie krawędzie wychodzące ze źródła w nowej sieci, możemy w cwany sposób zmodyfikować niektóre a_i i skonstruować przepływ o takim samym koszcie, który wysyca wszystkie krawędzie wychodzące ze źródła w starej sieci (z nowymi a_i). W zasadzie działa to samo rozumowanie, którego użyliśmy przed chwilą: jeśli oznaczymy przepływ z v_{i+1} do v_i jako \delta_i \geq 0, należy zwiększyć a_i o \delta_i. Dość łatwo w to uwierzyć wyobrażając sobie, że chcemy pozbyć się jednej jednostki płynącej Z v_{i+1} do v_i. W tym celu zwiększamy a_i o jeden, wtedy b_i także wzrasta o jeden, a b_{i+1} maleje (też o jeden), i zmniejszamy (o jeden) przepływ z v_{i+1} do v_i. Sumaryczna zmiana przeływu wchodzącego i wychodzącego do v_i i v_{i+1} nie ulegnie zmianie po takiej operacji.

Czyli pokazaliśmy (choć może niezbyt formalnie), że rzeczywiście wystarczy znaleźć najtańszy przepływ, który wysyca wszystkie krawędzie wychodzące ze źródła w nowej sieci (warto zauważyć, że taki przepływ zawsze istnieje; wynika to ze sposobu konstrukcji sieci). Ale jak go znaleźć?

Pewnie można użyć napisanego wcześniej ogólnego algorytmu, który znajduje najtańszy maksymalny przepływ. Jest to na tyle znany problem, że większość z Was pewnie ma go w swojej biblioteczce. W tym konkretnym przypadku sieć przepływowa jest dość duża, konieczne jest więc skorzystanie z w miarę efektywnej implementacji. Co nawet bardziej niepokojące, dość duże mogą być a_i, lepiej więc nie powiększać aktualnego przepływu tylko o jeden w każdym kroku. Przypomnijmy sobie, że najtańszego maksymalnego przepływu zwykle szuka się przepychając przez sieć kolejne jednostki, za każdym razem wybierając najtańszą ścieżkę w sieci residualnej. Możemy więc wybrać na takiej ścieżce krawędź o najmniejszej przepustowości (residualnej) c, a następnie przepuścić ścieżką całe c jednostek na raz. Wystarcza to do rozwiązania zadania, ale nie jest zbyt podniecające jeśli chodzi o analizę czasu działania. Może dałoby się jakoś mądrzej?

Dałoby się! Ale o tym przy innej okazji.

Reklamy

5 myśli nt. „Ochotnicy

  1. Tak na nietrzeźwo, to mam taki pomysł, żeby iśc od lewej do prawej i dla danego momentu t patrzeć na wszystkie oferty pracy przecinające moment t : skreślamy te oferty które są zdominowane przez inne oferty (tj. kończą się później i są tańsze, niż inne) a z tych co zostaną bierzemy najtańszą (czyli najkrótszą) a pozostałe zamieniamy na „przyrostówki”, tzn na takie pseudo oferty reprezentujące fakt, że zamiast osoby A możemy zatrudnić osobę B, co da nam dodatkowych X dni, ale musimy za to zapłacić dodatkowo Y. Te przyrostówki dorzucamy do zasobu już wcześniej zdefiniowanych ofert i jedziemy dalej, tj. rozważamy t+1.

    Niestety nie mam pojęcia jaką to ma złożoność, ale impreza w Antidotum była spoko.

  2. No niby można, choć nie widzę dwóch szczegółów: 1) raczej nie jest tak, że te pozostałe zamieniasz, raczej duplikujesz i robisz z kopii takie „przyrostówki” (no bo być może okaże się, że jakoś tam później nie możesz już wybrać osoby A, a przydałaby Ci się B), co grozi jakimś wykładniczym puchnięciem 2) w tej zamianie na „przyrostówki” trzeba uważać, żeby nie zamienić dwukrotnie tej samej osoby A, a to chyba nie jest łatwe?

  3. Racja. Przez moment miałem nadzieję, że liczba możliwych przyrostówek jest ograniczona przez n^2 (no bo niby odpowiada zamienieniu osoby X na Y), ale to jest nie takie łatwe, bo musimy też gdzieś zakodować informację, że jak już zamienimy X na Y to np. nie możemy potem na Z, bo Z zaczyna pracę później niż t…no i robi się ów wykładniczy klops. No może nie wykładniczy bo pewnie wystarczyłaby trójka (t,X,Y) by opisać przyrostówkę, więc to jakieś n*n*m.

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