Macie ode mnie następną porcję wiedzy z dziedziny algorytmiki. Pochylimy się nad programowaniem dynamicznym, które zostało pobieżnie opisane w artykule o dyskretnym problemie plecakowym, a teraz opiszę samą technikę bez podstawiania do jakiejkolwiek potrzeby. Programowanie dynamiczne bardzo mi się podoba jako samo podejście do szukania rozwiązania i Tobie też może się spodobać ;)!
| Tweet |
PROGRAMOWANIE DYNAMICZNE Z DZIELENIEM "ZA PAN BRAT"
Tytułowy termin odnosi się do metody projektowania algorytmów stosując zasadę zachłanności. Autor tej techniki, Richard Bellman, opracował sposób na rozwiązywanie zagadnień optymalizacyjnych, w której najważniejszą rolę odgrywa podział problemu na mniejsze "podproblemy". Te podproblemy zostają nałożone na siatkę (czy pisząc językiem informatycznym, na tablicę dwuwymiarową) i w każdej kratce wprowadza się wartość definiującą lokalnie optymalne rozwiązanie (rozwiązanie częściowe). Dla każdego wiersza i kolumny nakłada się odpowiednie ograniczenie, a każda pojedyncza kratka będzie oznaczać wartość maksymalną przestrzegającą ograniczeń w danym rzędzie i kolumnie. Wraz z wypełnianiem tabelki wartościami które chcemy optymalizować, dochodzimy do rozwiązywania większych fragmentów podproblemów, aż wreszcie dojdziemy do samego końca.
Ogromną zaletą tej techniki jest uniwersalność - ograniczenia nie sprowadzają się do jakiejś konkretnej kategorii problemów, a wystarczy odpowiednio je określić dla wierszy i kolumn (co samo w sobie może być jednak dużym wyzwaniem dla niestandardowych problemów). Po wypełnieniu całej tabelki wartościami, wystarczy odczytać najwyższą wartość i to będzie rozwiązanie aproksymacyjne. Czyli widzicie już drugi plus - redukowanie złożoności obliczeniowej w wyniku "chomikowania" otrzymywanych po drodze wyników częściowych, co trzeba się też liczyć z pewnym możliwym marginesem błędu w porównaniu do algorytmów dokładnych (nic za darmo, "buddy" :D ). Może tak być, ale nie musi.
Przykładów znowu może być od groma. Na dyskretnym problemie plecakowym starałem się Państwu zaprezentować możliwość wydobycia rozwiązania zamieniając "brute-force" na programowanie dynamiczne. Co jeszcze muszę przekazać to to, że nie zawsze globalnie optymalne rozwiązanie jest komórką w ostatnim wierszu i kolumnie. Tak było dla problemu plecakowego, ale są takie przypadki jak choćby odległość Levenshteina, w których nie uwzględnia się ostatniej komórki w tabeli, tylko tę dysponującą najwyższą wartością i to ona zostałaby zwrócona na wyjściu jako globalnie optymalne rozwiązanie. Słowem klucz jakim się charakteryzuje programowanie dynamiczne jest maksymalizacja (językiem matematycznym). Trzeba też dorzucić informację taką, że to stosuje się jedynie do podproblemów dyskretnych, czyli takich które są od siebie niezależne.
Wszystko! Metoda bardzo ciekawa i przyjemna dla oka. Jeżeli kiedykolwiek staniecie przed problemem algorytmicznym o charakterze matematyki dyskretnej, możecie spokojnie chwycić za programowanie dynamiczne i poćwiartować problem na "podproblemy". To nie będzie dla niego bolesne ;).