Algorytmy zachłanne vs. dynamiczne
Strategia zachłanna
Wróćmy na moment do zadania z poprzedniej lekcji:
Na \(n\) stosach ustawionych w rzędzie leży pewna liczba monet: na pierwszym stosie \(a_1\), na drugim \(a_1\) , ..., na \(n\)-tym \(a_n\). Wolno nam zabrać niektóre z tych stosów, ale nie wolno ruszyć dwóch sąsiednich. Jaka jest największa liczba monet, które można uzyskać?
Spróbujmy następującej prostej strategii: policzmy, ile jest monet na nieparzystych stosach (\(a_1 + a_3 + \ldots\)), a ile na parzystych (\(a_2 + a_4 + \ldots\)) i weźmy większą z tych liczb. Czy ta strategia zawsze daje najlepszy możliwy wynik? Niestety, nie zawsze: dla ciągu "3 0 0 3" można zabrać 6 monet, a uda nam się tylko 3.
To może mądrzejsza strategia: weźmy największy stosik, potem największy taki, który jeszcze możemy (nie sąsiaduje z już wziętym), potem kolejny największy...czy ten pomysł jest lepszy? Niestety, dalej nie. Zastanówmy się, jak zepsuć taki algorytm i sprawić, aby nie osiągał najlepszego wyniku. Wiemy, że zaczyna od wzięcia największej liczby w ciągu, ale jednocześnie rezygnuje z dwóch sąsiednich – sprawmy zatem, żeby strata tych dwóch stosów była bardzo kosztowna (ale pamiętajmy, żeby były mniejsze od największego). Dopilnujmy przy tym, aby po wzięciu największego stosu algorytm nie miał już żadnej rozsądnej opcji. Odpowiedni przykład może zatem wyglądać na przykład tak: 0 5 8 5 0. Największym stosem jest 8, ale potem zostają już tylko zera, podczas gdy wzięcie obu piątek dałoby lepszy wynik 10. Zestaw danych wejściowych, dla którego algorytm daje błędny lub nieoptymalny wynik, nazywa się popularnie kontrprzykładem.
Algorytmy, które nie "planują naprzód", ale wybierają co, co wydaje się najlepsze w danym momencie, przyjęło się nazywać zachłannymi. Strategie zachłanne często są pierwszymi, które przychodzą go głowy. Często dają dość dobre wyniki, ale relatywnie rzadko zdarza się, aby dawały zawsze wynik optymalny.
Problem plecakowy
Często zdarza się, że łatwa strategia zachłanna jest alternatywą do nieco trudniejszej dynamicznej. Na przykład bardzo znany problem plecakowy formułowany jest następująco:
Wybieramy spośród \(n\) przedmiotów – przedmiot numer \(i\) ma swoją wagę \(s_i\) oraz wartość \(v_i\). Mamy plecak, który pomieści przedmioty o łącznej wadze \(p\). Jaka jest największa wartość przedmiotów, które możemy uzyskać?
Znowu, przeanalizujmy kilka strategii.
Można oczywiście zabierać przedmioty od tych najbardziej wartościowych – tutaj kontrprzykład znaleźć bardzo łatwo, jeden wartościowy przedmiot zajmujący cały plecak może zablokować dwa nieco mniejsze, z których każdy zajmuje pół plecaka. Znacznie sprytniejszą strategią jest uszeregowanie przedmiotów względem wartości przypadającej na jednostkę, według ilorazu \(\frac{v_i}{s_i}\), i zabieranie przedmiotów kolejno od tych, które "najbardziej efektywnie" wypełniają przestrzeń w plecaku. Tutaj jest nieco trudniej znaleźć odpowiedni kontrprzykład – pozostawimy skonstruowanie go jako ćwiczenie dla Czytelnika, nadmieniając tylko, że do takiej konstrukcji mogą się przydać "złośliwe" przedmioty, zostawiające w plecaku sporo miejsca, w które jednak żaden inny przedmiot się nie zmieści.
Ale jak właściwie prawidłowo rozwiązać problem plecakowy? Wyobraźmy sobie na chwilę, że mamy tylko jeden przedmiot, o przykładowej wadze 4 i wartości 6. Weźmy plecak o pojemności – na przykład – 10, ale policzmy nieco więcej informacji, niż potrzebujemy: obliczmy, ile byśmy zarobili, gdyby nasz plecak miał pojemność kolejno 0, 1, 2, ...., 10, wpisując te liczby do tablicy \(A\), w komórki \(A[0]\), \(A[1]\), ..., \(A[10]\):
| Pojemność (t): | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Zysk (A[t]): | 0 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
Są to dość oczywiste rachunki: jeśli dysponujemy pojemnością 4, możemy zabrać nasz jedyny przedmiot, jeśli mniejszą – nie możemy. Nieco ciekawiej robi się, jeśli teraz dołożymy drugi przedmiot, o wadze 3 i wartości 5:
| Pojemność (t): | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Zysk (A[t]): | 0 | 0 | 0 | 5 | 6 | 6 | 6 | 11 | 11 | 11 | 11 |
Do pojemności 2 włącznie nie możemy zabrać nic, przy pojemności 3 tylko drugi przedmiot, przy 4 – tylko pierwszy, zaś przy 7 i większej – obydwa. Jak łatwo się domyślić, będziemy teraz starali się dołożyć trzeci przedmiot i poprawić wszystkie pola w tej tablicy. Niech trzeci przedmiot ma wagę 2 i wartość 4. Rozważmy na chwilę plecak mający pojemność \(k\) i zastanówmy się, co może nam dać nowy przedmiot. Możemy go zignorować – a wtedy nasz wynik dla pojemności \(k\) będzie taki, jak był przy dwóch dotychczasowych przedmiotach (czyli \(A[k]\)). Jeśli zaś go zabierzemy, od razu zyskamy 4, ale pozostanie nam mniejszy plecak o wielkości \(k-2\), w który będziemy się starali zmieścić dwa poprzednie przedmioty (z zyskiem \(A[k-2]\)). Są to jedyne dwie opcje postępowania, z których oczywiście wybieramy lepszą. Nowa wartość (dla trzech przedmiotów) komórki \(A[k]\) (nazwijmy ją \(A'[k]\)) wynosi:
\(A'[k] = \max(A[k], 4 + A[k-2])\)
Jeśli teraz dokładamy przedmiot numer \(i\), o wadze \(s[i]\) i wartości \(v[i]\), nowa wartość \(A'[k]\) wynosi:
\(A'[k] = \max(A[k], v[i] + A[k-s[i]])\)
Oczywiście, tak liczymy tylko dla \(k \geq s[i]\) – dla mniejszych \(k\) nie mamy możliwości wzięcia \(i\)-tego przedmiotu.
W ten sposób możemy obliczyć całą tablicę \(A'\). Kiedy to zrobimy, zastępujemy nią tablicę \(A\) – w tym momencie mamy już prawidłowe wyniki dla każdej pojemności plecaka, przy dokładnie \(i\) przedmiotach – po czym dodajemy kolejny, \((i+1)\)-szy przedmiot. Po dodaniu wszystkich przedmiotów, w komórce \(A[p]\) znajdzie się dokładnie wartość, której szukamy: najlepszy zysk dla plecaka o pojemności \(p\), po uwzględnieniu wszystkich \(n\) przedmiotów.
Działający algorytm zachłanny
Bywają sytuacje, w których strategia zachłanna działa. Przykładem takiej sytuacji jest następujący problem:
Mamy do wynajęcia salę wykładową. Może się w niej odbyć \(n\) wykładów, z których \(i\)-ty zaczyna się o czasie\(a[i]\) i kończy o czasie \(b[i]\). Należy wybrać możliwie wiele wykładów tak, aby żadne dwa się nie nakładały – ich przedziały czasowe nie mogą mieć wspólnego punktu.
Posortujmy wykłady względem ich końca, czyli tak, aby \(b[1] \leq b[2] \leq \ldots \leq b[n]\). Okazuje się, że teraz opłaca się wybrać wykład 1, pominąć te, które się z nim nakładają, po czym wybrać pierwszy taki, który wybrać można, potem kolejny nie nakładający się z pierwszymi dwoma, i tak dalej. Dlaczego akurat w tym wypadku tak prosty algorytm wystarcza?
Otóż wyobraźmy sobie na chwilę, że ktoś inny wybrał optymalny, największy zbiór wykładów. Jaki jest pierwszy wykład w jego rozwiązaniu? Jeśli nie jest nim 1 tylko na przykład 3, możemy zastąpić w rozwiązaniu wykład 3 przez wykład 1, pozostawiając pozostałe bez zmian. Skoro bowiem wykład 3 nie nakładał się z żadnym z pozostałych (późniejszych!), to tym bardziej nie może tego robić 1.
Co właściwie to oznacza? Pokazaliśmy, że możemy w każdym dobrym rozwiązaniu wybrać na początku wykład 1 i nie "zepsuć" przez to rozwiązania. Innymi słowy, możemy szukając rozwiązania wziąć na pewno, bezpiecznie, wykład numer 1. Skoro go wzięliśmy, możemy pominąć te nakładające się na niego, i powtórzyć całe rozumowanie – z pozostałych wykładów ten najwcześniej się kończący będzie na pewno bezpieczny.
Wzięcie największego stosu monet nie jest zatem najbardziej opłacalne, ale wzięcie najwcześniej kończącego się wykładu – jest. Na czym polega różnica? Potrafiliśmy zaargumentować, że najwcześniejszy wykład może być wzięty tak, byśmy nie stracili nic z optymalności rozwiązania. Nie umiemy takiego dowodu powtórzyć w wypadku monet. W wyborze "algorytm zachłanny czy dynamiczny" najważniejsze jest – jak często bywa w algorytmice i programowaniu – aby porządnie zastanowić się, zanim zaczniemy pisać program. Algorytmy zachłanne są na ogół łatwiejsze do napisania i szybciej działają, ale raczej nie należy stawiać na nie, zanim nie spróbujemy poszukać kontrprzykładu.