Chińska komórka

03.10.2009 - Paweł Gawrychowski
TrudnośćTrudność

Nie jest to może moje ulubione zadanie (nie wygrałem dzięki jego rozwiązaniu żadnych zawodów :), ale na pewno jest bardzo fajnym przykładem użycia dość ogólnej techniki, którą warto znać. Także dlatego, że w dość zaskakujący sposób pojawia się w niej geometria obliczeniowa (mam nadzieję, że nie zniechęci to Was to dalszej lektury...), mimo że zadanie na pierwszy (a nawet na drugi) rzut oka nie ma nic wspólnego z geometrią. Ale po kolei...

Zadanie

Treść można zobaczyć na przykład tutaj. Po przedarciu się przez historyjkę problem wygląda następująco: dostajemy ciąg $ n $ liczb $ f_1,\ldots,f_n $, mamy pokroić go na $ k $ kawałków $ f_1,\ldots,f_{m_1} $, $ f_{m_1+1},\ldots,f_{m_2} $, ..., $ f_{m_{k-1}+1},\ldots,f_n $ tak, aby zminimalizować sumę ich kosztów. Kosztem fragmentu $ f_a,\ldots,f_b $ nazywamy $ f_a+2f_{a+1}+3f_{a+2}+\ldots+(b-a+1)f_b $. Autor zadania prosi o podanie zarówno tej minimalnej sumy, jak i optymalnego podziału, jednak my zajmiemy się tylko wyznaczeniem najmniejszego możliwego kosztu.

Pierwszy pomysł

..jest dość oczywisty: możemy użyć programowania dynamicznego. Niech $ T[i,j] $ oznacza koszt pokrojenia sufiksu $ f_i,f_{i+1},\ldots,f_n $ na $ j $ kawałków. Aby podzielić sufiks na $ j $ fragmentów, wystarczy wybrać długość pierwszego z nich, a następnie podzielić pozostałą część na $ j-1 $ kawałków. Czyli wszystkie $ T[i,j] $ można wyznaczyć w następujący sposób:

$$ T[n+1,0] = 0$$
$$ T[i,j] = \min_{i < s} T[s,j-1]+ S[i,s-1] $$
gdzie $ S[a,b]=f_a+2f_{a+1}+3f_{a+2}+\ldots+(b-a+1)f_b $. Musimy jednak poradzić sobie z dwoma problemami:

  1. trzeba efektywnie wyznaczać wartości $ S[a,b] $. Nie jest to bardzo trudne jeśli wcześniej wyliczymy (w czasie $ O(n) $) wartości $ A[i]=f_i+f_{i+1}+\ldots +f_n $ oraz $ B[i]=f_i+2f_{i+1}+\ldots + (n-i+1)f_n $ korzystając z tego, że:
    $$A[n+1]=B[n+1]=0$$
    $$A[i]=f_i+A[i+1]$$
    $$B[i]=A[i]+B[i+1]$$
    i zauważymy, że $ S[a,b]=B[a]-B[b+1]-(b-a+1)A[b+1] $.
  2. mamy do wyznaczenia $ O(nk) $ wartości $ T[i,j] $. Wyliczenie każdej z nich wymaga całkiem sporo pracy rzędu $ n $, co daje nam złożoność $ O(n^2k) $. W oryginalnej wersji $ n $ i $ k $ były bardzo małe, ale nie powinno nas to zniechęcać do zastanowienia się nad lepszym rozwiązaniem...

Drugi pomysł, trochę lepszy

Skoro wyznaczenie pojedynczej wartości $ T[i,j] $ jest tak kosztowne, to może dałoby się wyznaczać kilka takich wartości jednocześnie? Powiedzmy, że mając już wszystkie wartości $ f(i)=T[i,j] $ dla ustalonego $ j $, chcemy policzyć wartości $ g(i)=T[i,j+1] $. Co tak naprawdę musimy wyznaczyć?

$$g(i)= min_{i < j} f(j) + S[i,j-1]$$
$$= min_{i < j} f(j) + B[i]-B[j]-(j-i)A[j]$$
$$= B[i] + min_{i<j} f(j) - B[j] - jA[j] + iA[j]$$
jeśli oznaczymy $ b_j=f(j)-B[j]-jA[j] $, $ a_j=A[j] $ oraz $ t_j(x) = a_j(x)+b_j $ widać, że tak naprawdę interesuje nas wyznaczenie $ min_{i<j} t_j(i) $ dla wszystkich wartości $ i=n,n-1,\ldots,1 $. W tym momencie możemy całkiem zapomnieć o pierwotnym sformułowaniu problem i zająć się tylko i wyłącznie wyznaczaniem takich minimów z funkcji liniowych (no, prawie: przydatne będzie jeszcze to, że współczynniki $ a_j $ są wszystkie dodatnie i coraz większe dla kolejnych wartości $ j $).

Jak minimalizować funkcje liniowe?

Popatrzmy przez chwilę na prostszą wersję problemu: dla danego zbioru funkcji liniowych $ \{t_j\} $ chcemy wyznaczać $ min_{j} t_j(x) $ dla różnych wartości $ x $. Najlepiej nie przeglądając za każdym razem wszystkich funkcji... Rozwiązanie takiego problemu najłatwiej wyobrazić sobie na rysunku:

Krzywą zaznaczoną na czerwono będziemy nazywali górną otoczką funkcji $ \{t_j\} $. Dla każdej funkcji mamy co najwyżej jeden przedział, na którym jest ona najlepszym możliwym wyborem. Jeżeli wyznaczymy wcześniej te przedziały i posortujemy według początków, znalezienie $ min_{j} t_j(x) $ sprowadzi się do znalezienia największego początku nie przekraczającego $ x $. Czyli do wyszukiwania binarnego...

No dobrze, ale w naszym problemie zbiór funkcji liniowych nie był podany z góry: dla kolejnych wartości $ j $ trzeba dokładać kolejne funkcje. Musimy więc umieć sprytnie aktualizować aktualną górną otoczkę. Popatrzmy więc jak może się ona zmienić po dodaniu nowej funkcji $ t(x) $:

w powyższej sytuacji trzeba zastąpić zielony fragment przedziałem, na którym optymalna jest niebieski fragment nowej funkcji. Jeżeli kolejno dodawane funkcje mają coraz większe współczynniki przy $ a $, zastępowany fragment będzie zawsze prefiksem aktualnej otoczki (czyli rysunek wcale nie był tak tendencyjny, jak mogłoby się wydawać). Znacząco ułatwia to implementację aktualizacji, o ile przechowujemy opis aktualnej otoczki na stosie tak, aby odcinek najbardziej na lewo był na szczycie. Po dodaniu nowej funkcji wystarczy wtedy zdejmować ze szczytu stosu odcinki tak długo, jak znajdują się na lewo od nowej prostej. W momencie, gdy napotkamy odcinek, który ją przecina, trzeba "skrócić" go do punktu przecięcia.

Zastanówmy się chwilę nad kosztem takiej aktualizacji. Może się zdarzyć, że dodanie nowej funkcji spowoduje konieczność usunięcia wielu odcinków, jednak powoduje utworzenie tylko jednego nowego. Z drugiej strony ciężko usunąć coś czego nie ma, a więc (wszystkich) usunięć nie będzie więcej niż $ n $. Czyli zamortyzowany koszt aktualizacji to tylko $ O(1) $.

Oprócz aktualizacji musimy jednak również znaleźć przedział, w którym znajduje się bieżąca wartość $ i $. Użycie wyszukiwania binarnego dałoby nam złożoność $ O(\log n) $, co wydaje się trochę kiepskie, skoro mamy aktualizację w czasie stałym. Ale przecież tak naprawdę wcale nie potrzebujemy tego wyszukiwania binarnego! Szukamy coraz mniejszych wartości $ i $, czyli kolejne poszukiwania możemy zaczynać w miejscu, w którym poprzednio skończyliśmy, co daje (również zamortyzowany) koszt $ O(1) $ na wyznaczenie pojedynczej wartości. A tak naprawdę możemy zrobić jeszcze prościej: każdy odcinek otoczki, który leży całkiem na prawo od prostej $ x=i $, na pewno już nam się nie przyda, możemy się więc go pozbyć. Czyli zamiast na stosie, otoczkę powinniśmy przechowywać w strukturze, która pozwala na dodawanie i usuwanie elementów z obydwu końców. Może to być lista dwukierunkowa lub (dla programujących w C++) deque.

Cała implementacja nie jest bardzo skomplikowana, o ile umiemy wyliczać przecięcia dwóch odcinków/prostych. Tego typu "prymitywy" geometryczne (jak przecięcie, sprawdzanie po której stronie prostej leży punkt, liczenie odległości od prostej, znajdowanie okręgu przechodzącego przez dane punkty, itd) warto:

  1. napisać,
  2. porządnie przetestować,
  3. przeklejać :)

Czy to już koniec?

W zasadzie tak: umiemy już wyznaczyć optymalny koszt. Autor zadania prosi nas też o wyznaczenie najlepszego podziału (a nawet jest bardziej wybredny i wymaga, żeby był on najmniejszy leksykograficznie), jednak podany wyżej pomysł można łatwo wzbogacić o znajdowanie nie tylko najmniejszego kosztu, ale także funkcji, dla której jest on osiągany. Cały algorytm będzie miał złożoność $ O(nk) $. Jeżeli chcesz spróbować zaimplementować takie rozwiązanie, tutaj można zobaczyć i rozwiązać problemik, który ma co prawda zupełnie inną treść, ale sprowadza się do tego samego.

Co jeszcze?

Co prawda nie ma to żadnego związku z minimalizacją funkcji liniowych, ale wszystkim, którym podobało się użycie otoczki do rozwiązania problemu, który wydawał się nie mieć nic wspólnego z geometrią, polecam następujące zadanie:

Mamy dane trzy substancje chemiczne A,B i C (Czytelnik może zastąpić litery swoimi ulubionymi pierwiastkami). Dysponujemy $ n $ roztworami, w których te substancje występują w proporcjach $ a_i : b_i : c_i $. Chcielibyśmy zmieszać (niektóre, być może wszystkie) je tak, aby otrzymać roztwór o proporcjach $ x:y:z $. Czy jest to możliwe?

oraz zastanowienie się nad warunkami, które musi spełniać funkcja kosztu, aby znajdowanie optymalnego podziału na fragmenty można było przyspieszyć tak, jak w przypadku zadaniu o komórce.

4.75
Twoja ocena: Brak Ocena: 4.8 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com