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ść).

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.

5 myśli nt. „Ochotnicy”

Jakub Łopuszański pisze:

2013/08/22 o 9:34 pm

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.

Odpowiedz
gawry1 pisze:

2013/08/23 o 10:37 am

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?

Odpowiedz
Jakub Łopuszański pisze:

2013/08/23 o 6:10 pm

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.

Odpowiedz
Jakub Łopuszański pisze:

2013/08/24 o 2:09 pm

spoiler alert: a może program dualny rozwiązać dijkstrą?

Odpowiedz
gawry1 pisze:

2013/08/27 o 12:58 pm

Noo program dualny.. zawsze warto rozwiązać 🙂

Odpowiedz