Backup

Tym razem będzie o zadaniu z kategorii „fajne i proste”. Tak, są też i takie! Ale obiecuję, że już w kolejnym (no, lub może jeszcze następnym) odcinku pojawi się problemik z serii tych legendarnych. A tymczasem zastanówmy się nad następującym: mając dany ciąg liczb naturalnych a_1, a_2, \ldots, a_n i parametr k \leq \lceil\frac{n}{2}\rceil, chcemy wybrać dokładnie k liczb o najmniejszej możliwej sumie. Aby nie było zupełnie trywialnie, nie wolno nam wybrać dwóch sąsiednich.

Powiedzmy, że na dobry początek wybierzemy sobie k najmniejszych liczb. Jeśli nasz ciąg to na przykład 1,5,2,4,3 i k=3, wybrane w ten sposób liczby nie są sąsiednie, czyli tak naprawdę możemy z czystym sumieniem zakończyć pracę. Jeśli jednak nasz ciąg to 5,1,2,4,3, wybierzemy 1 i 2, które nie mogą (jednocześnie) pojawić się w rozwiązaniu. Czyli lipa.

Musimy więc podejść do sprawy w choć odrobinę bardziej wyrafinowany sposób. Powiedzmy, że a_i to najmniejsza liczba w całym ciągu. Dość kuszące byłoby założenie, że istnieje rozwiązanie optymalne, w którym wybieramy a_i, lecz niestety niekoniecznie musi tak być. Nie jest jednak tak całkiem tragicznie: przyjrzyjmy się sytuacji, w której najlepsze możliwe rozwiązanie S nie zawiera a_i. Jeśli nie zawiera ono ani a_{i-1} ani a_{i+1}, moglibyśmy polepszyć sytuację dorzucając i i wyrzucając dowolne j\in S (no, a dokładniej: nie pogorszyć). Czyli na pewno i-1\in S lub i+1\in S. Jeśli dokładnie jedna z tych liczb pojawia się w S, czyli (ze względu na symetrię jest to jedyny istotny przypadek) i-1\in S oraz i+1\not\in S, możemy zastąpić i-1 przez i. Znów, polepszy to (a przynajmniej nie pogorszy) sytuację. Ostatni możliwy przypadek to i-1,i+1\in S. Chciałoby się powiedzieć, że także wtedy możemy polepszyć sytację, ale… niestety, nie zawsze.

No, ale nie przejmujmy się: przynajmniej udało nam się pokazać, że i\in S lub i-1,i+1\in S, jeśli a_i jest najmniejszym elementem. Nazwijmy to (być może odrobinę na wyrost) lematem. Tak naprawdę lemat pozwala na redukcję oryginalnego problemu do takiego, w którym k i n są choć odrobinę omniejsze. Jak? Wystarczy zastąpić a_{i-1},a_{i},a_{i+1} przez a_{i-1}+a_{i+1}-a_{i}!

Nazwijmy oryginalną instancję P, a zredukowaną P'. Optymalnemu rozwiązaniu P o koszcie C odpowiada (jakieś) rozwiązanie P' o koszcie C-a_i. W drugą stronę, każdemu rozwiązaniu P' o koszcie C odpowiada (jakieś) rozwiązanie P o koszcie C+a_i. Czyli tak naprawdę zamiast szukać rozwiązania P, możemy wyznaczyć koszt optymalnego rozwiązania P', a następnie dodać do niego a_i!

backup

Pozostaje pytanie, jak rozwiązać P'. No.. może tak samo? Czyli znów wybrać najmniejszy element, zastąpić go (wraz z sąsiadami) nowym, i tak dalej. Powtarzając takie rozumowanie prędzej lub później dojdziemy do sytuacji, w której k=0, która nie powinna już przysporzyć nam większych trudności. Pozostaje tylko pytanie, jak efektywnie potrafilibyśmy redukować kolejne instancje.

Przyjrzyjmy się więc co tak naprawdę się tutaj dzieje. Wybieramy najmniejszą liczbę, usuwamy jej sąsiadów, modyfikujemy (a dokładniej, zwiększamy) aktualną wartość. Wystarczy więc przechowywać wszystkie liczby w strukturze danych, która pozwala na dodawanie, usuwanie, i znajdowanie minimum. Może to więc być zwykły kopiec (tudzież kolejka priorytetowa), który umożliwi nam rozwiązanie całego zadania w czasie \mathcal{O}(n\log n).

Jeśli chodzi o samo zadanie, to w zasadzie koniec. Przyjrzyjmy się jednak przez chwilę co tak naprawdę się tutaj wydarzyło. W pewnym sensie zastosowaliśmy strategię zachłanną, jednak zamiast często pojawiającego się w takich rozwiązaniach triku typu „bez straty ogólności istnieje rozwiązanie optymalne, który wybiera dany element”, stworzyliśmy sobie możliwość zmiany decyzji w mniej lub bardziej odległej przyszłości. W jednym z kolejnym odcinków przyjrzyjmy się innemu zadaniu, w którym przydaje się podobna sztuczka, o następującej treści: dla danego ciągu n liczb całkowitych chcemy wybrać co najwyżej k rozłącznych spójnych fragmentów o jak największej sumie. Co dość zaskakujące, taki problem można rozwiązać w czasie… no, zobaczymy już niedługo.

Advertisements

2 myśli nt. „Backup

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