Koncepcja programowania dynamicznego jest zasługą Richarda Bellmana, wybitnego matematyka i ekonomisty.
W tamtym okresie Bellman poszukiwał metod skutecznego rozwiązywania skomplikowanych zadań optymalizacyjnych. Problemy optymalizacji sprowadzają się do wyboru najlepszego wariantu z szerokiego spektrum możliwości.
Klasycznym przykładem takiego problemu jest zagadnienie komiwojażera. Istotą jest znalezienie najkrótszej trasy, która umożliwi przedstawicielowi handlowemu odwiedzenie każdego miasta tylko raz, a na koniec powrót do punktu wyjścia.
Bellman podszedł do tych wyzwań, dzieląc je na mniejsze, łatwiejsze do opanowania fragmenty, i rozpoczynając rozwiązywanie od najprostszych. Wyniki tych obliczeń były zapisywane i wykorzystywane przy rozwiązywaniu większych podproblemów. To sedno idei programowania dynamicznego.
Na czym polega programowanie dynamiczne?
Programowanie dynamiczne to podejście do rozwiązywania problemów optymalizacyjnych poprzez rozbicie ich na mniejsze części, jednorazowe rozwiązanie każdej z nich oraz zapisanie wyników, aby móc je ponownie wykorzystać do skonstruowania rozwiązania całego zadania. Kluczowe jest rozwiązywanie problemów od najmniejszych do największych, co umożliwia efektywne korzystanie z wcześniejszych wyników.
Jak działa programowanie dynamiczne?
Proces rozwiązywania problemu za pomocą programowania dynamicznego składa się z kilku etapów:
- Identyfikacja podproblemów: Duży problem jest rozkładany na mniejsze, bardziej przystępne fragmenty.
- Rozwiązanie podproblemów: Każdy z zidentyfikowanych podproblemów jest rozwiązywany, często za pomocą rekurencji lub iteracji.
- Zapisywanie rozwiązań: Wyniki rozwiązania podproblemów są przechowywane, co umożliwia ich ponowne wykorzystanie.
- Konstruowanie rozwiązania wyjściowego: Rozwiązanie głównego problemu jest tworzone poprzez łączenie rozwiązań jego składowych podproblemów.
Aby lepiej zobrazować ten proces, przeanalizujemy, jak obliczyć szóstą liczbę Fibonacciego, F(6), stosując to podejście.
Zaczynamy od zdefiniowania podproblemów.
Wzór: F(n) = F(n-1) + F(n-2) dla n > 1
Zatem: F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
F(1) = 1
F(0) = 0
Drugi krok to rozwiązanie każdego z tych podproblemów, stosując funkcję rekurencyjną lub iterację. Rozpoczynamy od najmniejszych, wykorzystując wyniki mniejszych podproblemów do rozwiązania większych. Uzyskujemy w ten sposób:
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
W miarę rozwiązywania kolejnych podproblemów, wyniki są zapisywane, np. w tablicy, umożliwiając ich ponowne wykorzystanie w większych podproblemach.
Gdy wszystkie podproblemy zostaną rozwiązane, wykorzystujemy te wyniki do skonstruowania rozwiązania oryginalnego problemu.
W tym przypadku rozwiązaniem problemu jest szósty element ciągu Fibonacciego, który uzyskujemy przez zsumowanie F(5) i F(4) czyli podproblemów, na które rozbiliśmy pierwotne zadanie. Otrzymany wynik to 8.
Gdzie i dlaczego używa się programowania dynamicznego?
Programowanie dynamiczne znajduje zastosowanie w obszarach, gdzie mamy do czynienia z problemami, które można rozłożyć na mniejsze podproblemy, a ich rozwiązania służą jako fundament do budowania rozwiązania głównego zadania.
Technika ta jest wykorzystywana w informatyce, ekonomii, matematyce i inżynierii. W informatyce pomaga w rozwiązywaniu zadań związanych z sekwencjami, grafami, wartościami całkowitymi, jak również w programowaniu konkursowym.
W ekonomii jest wykorzystywana do rozwiązywania problemów optymalizacyjnych w finansach, produkcji oraz przy alokacji zasobów. W matematyce znajduje zastosowanie w teorii gier, statystyce i rachunku prawdopodobieństwa, wspomagając rozwiązywanie problemów optymalizacyjnych.
W inżynierii pomaga w problemach związanych z alokacją zasobów, planowaniem, produkcją, komunikacją i systemami sterowania.
Zastosowanie programowania dynamicznego do rozwiązywania problemów optymalizacyjnych niesie ze sobą szereg zalet:
- Wydajność: Programowanie dynamiczne może być bardziej efektywne od innych algorytmów optymalizacyjnych, ponieważ unika wielokrotnego rozwiązywania tych samych podproblemów.
- Rozwiązywanie dużych problemów: Programowanie dynamiczne doskonale sprawdza się w przypadku dużych problemów optymalizacyjnych, które innymi metodami byłyby trudne do rozwiązania. Dzięki podziałowi problemu na mniejsze części, zmniejsza się jego złożoność.
- Optymalne rozwiązania: Algorytmy programowania dynamicznego, przy właściwej definicji podproblemów i celów, są w stanie znaleźć optymalne rozwiązanie danego problemu.
- Prostota: Algorytmy programowania dynamicznego są stosunkowo łatwe do wdrożenia i zrozumienia, zwłaszcza jeśli problem można przedstawić w uporządkowany sposób.
- Skalowalność: Algorytmy programowania dynamicznego można stosunkowo łatwo rozszerzać, aby rozwiązywać bardziej złożone problemy, dodając nowe podproblemy lub modyfikując cele.
Podsumowując, programowanie dynamiczne jest niezwykle użytecznym narzędziem w rozwiązywaniu problemów optymalizacyjnych, gwarantując efektywność i wysoką jakość uzyskiwanych wyników.
Podejścia w programowaniu dynamicznym
W programowaniu dynamicznym istnieją dwa główne podejścia do rozwiązywania problemów optymalizacyjnych: odgórne i oddolne.
Podejście odgórne
Podejście to jest również znane jako „zapamiętywanie”. Zapamiętywanie to technika optymalizacyjna, która przyspiesza programy poprzez przechowywanie wyników wywołań funkcji w pamięci podręcznej. Kiedy te same argumenty są potrzebne ponownie, zamiast powtarzać obliczenia, wyniki są pobierane z pamięci podręcznej.
Podejście odgórne opiera się na rekurencji i buforowaniu wyników. Rekurencja polega na wywoływaniu przez funkcję samej siebie, z prostszymi wersjami problemu jako argumentami. Służy do rozkładania problemu na mniejsze podproblemy i ich rozwiązywania.
Gdy podproblem jest rozwiązany, jego wynik jest zapisywany w pamięci podręcznej i ponownie wykorzystywany za każdym razem, gdy wystąpi ten sam podproblem. Podejście odgórne jest łatwe w zrozumieniu i implementacji, a każdy podproblem jest rozwiązywany tylko raz. Jego wadą jest jednak większe zapotrzebowanie na pamięć z powodu rekurencji, co w skrajnych przypadkach może prowadzić do błędu przepełnienia stosu.
Podejście oddolne
Podejście oddolne, zwane również tabulacją, eliminuje rekurencję, zastępując ją iteracją, co pozwala uniknąć błędów przepełnienia stosu.
W tym podejściu duży problem jest rozbijany na mniejsze, a rozwiązania tych mniejszych podproblemów są wykorzystywane do rozwiązania głównego problemu.
Podproblemy są rozwiązywane od najmniejszych do największych, a ich wyniki zapisywane są w macierzy, tablicy lub tabeli, stąd nazwa „tabulacja”.
Zapisane wyniki umożliwiają rozwiązanie większych problemów, które są od nich zależne. Ostateczny wynik jest uzyskiwany poprzez rozwiązanie największego podproblemu przy użyciu wcześniej wyliczonych wartości.
Zaletą tego podejścia jest efektywność pod względem zużycia pamięci i czasu, ze względu na eliminację rekurencji.
Przykłady problemów rozwiązywanych programowaniem dynamicznym
Poniżej przedstawiamy kilka przykładów problemów programistycznych, które można rozwiązać za pomocą programowania dynamicznego:
# 1. Problem plecakowy
Źródło: Wikipedia
Plecak to torba, zwykle z płótna, nylonu lub skóry, noszona na plecach, często wykorzystywana przez żołnierzy i turystów do przenoszenia zapasów.
W problemie plecakowym chodzi o to, by mając plecak o określonej pojemności, wybrać z dostępnych przedmiotów te, które łącznie mają największą wartość, nie przekraczając przy tym jego pojemności. Każdy przedmiot ma przypisaną wagę i wartość.
Przykładowy problem plecakowy:
Wyobraź sobie, że wybierasz się na wędrówkę i masz plecak o pojemności 15 kilogramów. Dostępna jest lista przedmiotów, z których każdy ma określoną wagę i wartość. Jak przedstawia poniższa tabela:
PrzedmiotWartośćWagaNamiot2003Śpiwór1502Kuchenka501Jedzenie1002Butelka z wodą1000,5Apteczka251
Należy wybrać taki podzbiór przedmiotów, by ich łączna wartość była maksymalna, a waga nie przekraczała 15 kilogramów.
Praktyczne zastosowania problemu plecakowego to np. wybór papierów wartościowych do portfela w celu zminimalizowania ryzyka i maksymalizacji zysku, a także szukanie najbardziej efektywnych metod wykorzystania surowców.
#2. Problem planowania zadań
Problem planowania to problem optymalizacyjny, gdzie zadaniem jest przydzielenie zadań do zestawu zasobów w optymalny sposób. Zasoby mogą obejmować maszyny, personel czy inne środki niezbędne do realizacji zadań.
Przykład problemu planowania:
Wyobraź sobie, że jako kierownik projektu musisz zaplanować zadania do wykonania przez zespół. Każde zadanie ma swój czas rozpoczęcia i zakończenia, a także listę pracowników uprawnionych do jego wykonania.
Tabela opisująca zadania i ich parametry:
ZadanieCzas rozpoczęciaCzas zakończeniaKwalifikowani pracownicyT1911A, B, CT21012A, CT31113B, CT41214A, B
Należy przypisać każde zadanie do odpowiedniego pracownika tak, aby zminimalizować całkowity czas wykonania wszystkich zadań.
Problem planowania pojawia się w przemyśle wytwórczym przy optymalizacji wykorzystania zasobów takich jak maszyny, materiały, narzędzia i robocizna. Może też być spotykany w opiece zdrowotnej, gdzie optymalizuje się wykorzystanie łóżek, personelu i środków medycznych. Inne branże, w których ten problem jest istotny, to zarządzanie projektami, łańcuch dostaw i edukacja.
#3. Problem komiwojażera
Źródło: Wikipedia
To jeden z najczęściej badanych problemów optymalizacyjnych, który można rozwiązać przy użyciu programowania dynamicznego.
Problem komiwojażera polega na znalezieniu najkrótszej trasy, która przechodzi przez każde miasto z danej listy tylko raz i wraca do miasta początkowego.
Przykład problemu komiwojażera:
Wyobraź sobie, że jesteś sprzedawcą, który musi odwiedzić kilka miast w jak najkrótszym czasie. Masz listę miast i odległości między nimi, jak przedstawia poniższa tabela:
MiastoABCDEA010152030B100352515C153503020D202530010E301520100
Problem komiwojażera znajduje zastosowanie między innymi w planowaniu tras wycieczek, logistyce przy planowaniu dostaw, transporcie przy optymalizacji tras autobusowych, czy w branży sprzedażowej.
Jak widać, programowanie dynamiczne ma szerokie zastosowanie w rzeczywistym świecie, co czyni je wartościowym obszarem do zgłębiania wiedzy.
Zachęcamy do skorzystania z poniższych źródeł, aby poszerzyć swoją wiedzę w zakresie programowania dynamicznego.
Zasoby
Programowanie dynamiczne Richarda Bellmana
To książka autorstwa Richarda Bellmana, twórcy koncepcji programowania dynamicznego.
Książka jest napisana przystępnym językiem, wymagającym jedynie podstawowej znajomości matematyki i analizy matematycznej. Bellman prezentuje matematyczną teorię wieloetapowego procesu decyzyjnego, która jest fundamentem programowania dynamicznego.
Następnie analizuje problem wąskich gardeł w procesach produkcyjnych, twierdzenia o istnieniu i jednoznaczności oraz optymalne strategie zarządzania zapasami.
Książka prezentuje liczne przykłady złożonych problemów z dziedzin takich jak logistyka, planowanie, teoria komunikacji, ekonomia matematyczna czy procesy sterowania, pokazując jak programowanie dynamiczne może je rozwiązać.
Książka dostępna jest w wersji elektronicznej (Kindle), w twardej i miękkiej oprawie.
Kurs mistrzowski algorytmów programowania dynamicznego
Ten kurs mistrzowski dotyczący programowania dynamicznego, oferowany na platformie Udemy, prowadzony jest przez inżyniera oprogramowania Google, Apaara Kamala i Prateeka Naranga.
Kurs jest zoptymalizowany pod kątem wsparcia uczestników w konkursach programistycznych, gdzie programowanie dynamiczne jest szeroko stosowane.
Oprócz zawodników programistycznych, kurs jest wartościowy dla programistów, którzy chcą poszerzyć wiedzę o algorytmach, a także dla osób przygotowujących się do rozmów kwalifikacyjnych i testów kodowania.
Kurs, trwający ponad 40 godzin, omawia programowanie dynamiczne w sposób szczegółowy. Zaczyna od przypomnienia koncepcji rekurencji i cofania, a następnie przechodzi do programowania dynamicznego w kontekście teorii gier, łańcuchów, drzew i grafów, potęgowania macierzy, masek bitowych, kombinatoryki, podsekwencji, problemów partycji i wielowymiarowego programowania dynamicznego oraz wielu innych tematów.
Podstawy programowania konkurencyjnego, główne algorytmy
Kurs na Udemy, prowadzony przez Prateeka Naranga i Amala Kamaara, wprowadza w podstawy programowania konkurencyjnego, obejmując programowanie dynamiczne, matematykę, teorię liczb oraz zaawansowane struktury danych i algorytmy, w sposób przydatny i odpowiedni dla programistów biorących udział w konkursach.
Kurs zaczyna od przypomnienia struktur danych i algorytmów, a następnie omawia bardziej zaawansowane techniki stosowane w programowaniu konkurencyjnym.
Kurs obejmuje programowanie dynamiczne, matematykę, teorię gier, dopasowywanie wzorców, maskowanie bitowe i wiele zaawansowanych algorytmów przetestowanych w konkursach programistycznych.
Kurs na Udemy jest podzielony na 10 modułów i 42 sekcje, a po każdej sekcji znajduje się wiele zadań do samodzielnego rozwiązania. Ten bestsellerowy kurs jest obowiązkowy dla wszystkich zainteresowanych programowaniem konkurencyjnym.
Podsumowanie
Programowanie dynamiczne jest bardzo przydatną umiejętnością dla każdego programisty, pomagając w ulepszaniu sposobów rozwiązywania realnych problemów. Dlatego zachęcamy do zapoznania się z proponowanymi zasobami, by dodać to kluczowe narzędzie do swojego warsztatu pracy.
Następnie warto zapoznać się z językami programowania przydatnymi w obszarze analizy danych.