Kolejna darmowa porcja wiedzy z dziedziny algorytmiki 📖! Pochylimy się teraz nad jedną z potężnych technik do wyznaczania rozwiązania przybliżonego (której notabene, użyliśmy do rozwiązania dyskretnego problemu plecakowego 😄!). Jest nią programowanie dynamiczne 🧨! Podejście do szukania rozwiązania polega na siatce "podproblemów" 🧠. A co to takiego i jak się to wyznacza, dowiesz się już w środku ❤️!
PROGRAMOWANIE DYNAMICZNE Z DZIELENIEM "ZA PAN BRAT"
Technika którą opisuję, została opracowana w 1953 roku przez Richarda Bellmana, także istnieje w nauce już spory kawał czasu 😅! Odnosi się ona do rozwiązywania zagadnień optymalizacyjnych wykorzystując cechę zachłanności i radzi sobie doskonale przy wyznaczaniu rozwiązań aproksymacyjnych 💪.
Sama nazwa posiada ciekawą historię 😉. W latach .50, fraza "programowanie" wcale nie odnosiła się do programowania jakie znamy dzisiaj, czyli do "klepania kodu" 😁, a raczej do planowania działań (zwłaszcza militarnych 🫡). Autor pracował nad projektami wspieranymi finansowo przez amerykańską armię 🇺🇸 i otrzymał ważne zadanie wyznaczenia najlepszej metody działania 💯. Ponadto, miał do czynienia z Sekretarzem Obrony, który miał dostawać "piany na pysku" na pojęcie "research" (w kontekście matematyki) 😄. Richard Bellman postanowił połączyć pojęcie "programowanie" z przymiotnikiem "dynamiczne", działając w ten sposób troszeczkę marketingowo, aby utrzymać dofinansowanie 💵.
NA CZYM POLEGA PROGRAMOWANIE DYNAMICZNE?
Jednym zdaniem: stosuje podział na "podproblemy" i rejestruje rozwiązania częściowe (lokalnie optymalne rozwiązania) w tabeli lub siatce 🤩. Ujmując programistycznie, w tablicy dwuwymiarowej 😊. Poprzez podział na "podproblemy" i konsekwentne ich rozwiązywanie krok po kroku, programowanie dynamiczne pozwala na uzyskanie bardzo dobrych wyników przy problemach, które mają nieakceptowalną złożoność czasową (wykładniczą) ✅. Konkretniej, chodzi o 👇:
- problemy NP-trudne,
- problemy NP-zupełne.
Wyznaczanie rozwiązania przy tej technice polega na tym, że dla każdego wiersza i kolumny nakładamy zmienną (w ujęciu matematycznym, nie programistycznym), a w każdej komórce wpisujemy wartość stanowiącą rozwiązanie "podproblemu", na podstawie tych dwóch stanów (zmiennych) 💥. Zmienna stanu, to nic innego jak parametr "biorący udział" w dzieleniu "podproblemu", którego stan ulega zmianie co iterację ℹ️.
Cierpliwie krok po kroku wypełniamy naszą siatkę (albo tabelę 🙂), aż we wszystkich polach znajdzie się wartość ✅. Kiedy wszystkie pola zostaną wypełnione, wystarczy odczytać spośród nich wartość maksymalną - to będzie nasze rozwiązanie ostateczne 💙! Zapamiętywanie raz wyznaczonych rozwiązań "podproblemów" określa się "memoizacją" (ang. memoisation) 🧠.
W tym miejscu należy podkreślić to, że rozwiązanie ostateczne, czyli maksymalne, nie musi być komórką w ostatnim wierszu i kolumnie ⚠️. Tak jest dla przykładu przy dyskretnym problemie plecakowym, natomiast już w odległości Levenshteina, wartość maksymalna może znaleźć się w dowolnej innej komórce tabeli, niekoniecznie w prawym dolnym rogu ℹ️. To nie jest żadna reguła programowania dynamicznego, że bierzemy wartość tylko z prawego dolnego rogu i to jest rozwiązanie ostateczne ❌! Patrz na wartość, a nie pozycję 🫵!
ZALETY PROGRAMOWANIA DYNAMICZNEGO
Są 2 ogromne zalety stosowania programowania dynamicznego 👍:
- uniwersalność,
- redukcja do złożoności wielomianowej.
Pierwsza zaleta: możliwość skorzystania z tej techniki dla problemu dowolnej kategorii 🏆. Nie ma znaczenia, czy dotyczy ustalenia które przedmioty włożyć do plecaka (dyskretny problem plecakowy), jaką wartość posiada ciąg Fibonacciego dla zadanego wyrazu ciągu czy wyznaczamy najkrótszą ścieżkę w grafie używając algorytmu Dijkstry 😊. Wszystkie te zagadnienia, są rozwiązywalne liniowo przy pomocy programowania dynamicznego ❤️! Jedynym uwarunkowaniem jest, żeby problem cechował się niejaką "własnością optymalnej podstruktury" 🤯. Na ludzki język, problem musi się dać podzielić na "podproblemy", a uzyskane optymalne rozwiązanie ostateczne musi "pochodzić" od lokalnie optymalnych rozwiązań (rozwiązań częściowych) ✅.
Druga zaleta: efektywne redukowanie złożoności czasowej do postaci wielomianowej 🏆. W wyniku "chomikowania" otrzymywanych rozwiązań częściowych, algorytm w kolejnych iteracjach posługuje się poprzednio zapisanymi wynikami, co skutecznie skraca cały koszt w ujęciu czasowym 👍. Ponieważ siatka składa się z wierszy i kolumn (przyjmując formę tablicy dwuwymiarowej), ograniczamy się do postaci liniowej przez co złożoność czasowa "spada" do poziomu pseudowielomianowego, który jest dużo lepszy, niż postać wykładnicza 💥!
 |
Programowanie dynamiczne to technika skutecznego wyznaczania rozwiązań problemów o wysokiej złożoności czasowej przy użyciu siatki do notowania rozwiązań częściowych (lokalnie optymalnych rozwiązań).
Wszystko 😁! Metoda skuteczna, przyjemna i ciekawa 🚀. Jeżeli kiedykolwiek staniesz przed problemem algorytmicznym o wykładniczej złożoności czasowej, rozważ programowanie dynamiczne i poćwiartowanie problemu na "podproblemy" 🔪. To nie będzie dla niego bolesne 😏.