Programowanie dynamiczne to koncepcja opracowana przez Richarda Bellmana, matematyka i ekonomistę.
W tym czasie Bellman szukał sposobu na rozwiązanie złożonych problemów optymalizacyjnych. Problemy z optymalizacją wymagają wybrania najlepszego rozwiązania z zestawu opcji.
Przykładem problemu optymalizacyjnego jest problem komiwojażera. Celem jest znalezienie najkrótszej trasy, aby sprzedawca mógł odwiedzić każde miasto dokładnie raz i wrócić do miasta startowego.
Podejście Bellmana do tych problemów polegało na podzieleniu ich na mniejsze podproblemy i rozwiązaniu podproblemów od najmniejszego do największego. Następnie zapisał wyniki podproblemów i ponownie wykorzystał je do rozwiązania większych podproblemów. To jest główna idea programowania dynamicznego.
Spis treści:
Co to jest programowanie dynamiczne?
Programowanie dynamiczne rozwiązuje problemy optymalizacyjne, dzieląc je na mniejsze podproblemy, rozwiązując każdy podproblem jeden raz i przechowując ich rozwiązania, aby można je było ponownie wykorzystać i połączyć w celu rozwiązania większego problemu. Problemy są rozwiązywane od najmniejszego do największego, co pozwala na ponowne wykorzystanie rozwiązań.
Jak działa programowanie dynamiczne?
Rozwiązanie problemu za pomocą programowania dynamicznego obejmuje następujące kroki:
Aby zobaczyć to w działaniu, obliczamy szóstą liczbę Fibonacciego, F(6), korzystając z tego procesu.
Najpierw zdefiniuj podproblemy, które należy rozwiązać.
F(n) = F(n-1) + F(n-2) dla n > 1
Dlatego: F(6) = F(5) + F(4)
fa(5) = fa(4) + fa(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
fa(2) = fa(1) + fa(0)
F(1) = 1
F(0) = 0
Drugi krok obejmuje rozwiązanie każdego podproblemu za pomocą funkcji rekurencyjnej lub procesu iteracyjnego. Rozwiązujemy podproblemy od najmniejszego do największego, ponownie wykorzystując wyniki z mniejszych podproblemów. Daje nam to:
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
Gdy rozwiązujemy każdy z podproblemów, przechowujemy rozwiązania w tablicy lub tabeli, aby można je było ponownie wykorzystać w rozwiązywaniu większych podproblemów, takich jak:
Po rozwiązaniu wszystkich podproblemów używamy rozwiązań do skonstruowania rozwiązania pierwotnego problemu.
W tym przypadku rozwiązaniem pierwotnego problemu jest szósta liczba Fibonacciego, którą można znaleźć, sumując wyniki F(5) i F(4), podproblemów zidentyfikowanych na podstawie największego problemu. Wynik daje nam 8.
Gdzie i dlaczego stosuje się programowanie dynamiczne?
Programowanie dynamiczne stosuje się w obszarach, w których mamy problemy, które można podzielić na mniejsze podproblemy, a ich rozwiązania służą do rozwiązywania większych problemów.
Obszary te obejmują informatykę, ekonomię, matematykę i inżynierię. W informatyce służy do rozwiązywania problemów związanych z sekwencjami, wykresami i wartościami całkowitymi oraz w programowaniu konkurencyjnym.
W ekonomii służy do rozwiązywania problemów optymalizacyjnych w finansach, produkcji i alokacji zasobów. W matematyce programowanie dynamiczne jest wykorzystywane w teorii gier, statystyce i prawdopodobieństwie, gdzie służy do rozwiązywania problemów optymalizacyjnych.
W inżynierii służy do rozwiązywania problemów związanych z alokacją zasobów, planowaniem, produkcją, komunikacją i systemami sterowania.
Korzystanie z programowania dynamicznego do rozwiązywania problemów optymalizacyjnych ma kilka zalet:
Jeśli chodzi o rozwiązywanie problemów optymalizacyjnych, programowanie dynamiczne jest bardzo przydatnym narzędziem zapewniającym efektywność rozwiązań.
Podejścia stosowane w programowaniu dynamicznym
W programowaniu dynamicznym stosuje się dwa podejścia do rozwiązywania problemów optymalizacyjnych. Są to podejście odgórne i podejście oddolne.
Podejście odgórne
To podejście jest również znane jako zapamiętywanie. Zapamiętywanie to technika optymalizacji używana głównie do przyspieszania programów komputerowych poprzez przechowywanie wyników wywołań funkcji w pamięci podręcznej i zwracanie wyników z pamięci podręcznej następnym razem, gdy są potrzebne, zamiast ich ponownego obliczania.
Podejście odgórne obejmuje rekurencję i buforowanie. Rekurencja obejmuje funkcję wywołującą samą siebie z prostszymi wersjami problemu jako argumentem. Rekurencja służy do rozbijania problemu na mniejsze podproblemy i rozwiązywania podproblemów.
Po rozwiązaniu problemu podrzędnego jego wynik jest zapisywany w pamięci podręcznej i ponownie wykorzystywany za każdym razem, gdy wystąpi podobny problem. Odgórne podejście jest łatwe do zrozumienia i wdrożenia, a podproblem rozwiązuje tylko raz. Wadą jest jednak to, że zajmuje dużo pamięci z powodu rekurencji. Może to prowadzić do błędu przepełnienia stosu.
Podejście oddolne
Podejście oddolne, znane również jako tabulacja, eliminuje rekursję, zastępując ją iteracją, unikając w ten sposób błędów przepełnienia stosu.
W tym podejściu duży problem jest dzielony na mniejsze podproblemy, a rozwiązania podproblemów są wykorzystywane do rozwiązania większego problemu.
Mniejsze podproblemy są najpierw rozwiązywane od największego do najmniejszego, a ich wyniki są przechowywane w macierzy, tablicy lub tabeli, stąd nazwa tabulacja.
Zapisane wyniki rozwiązują większe problemy, które zależą od podproblemów. Wynik pierwotnego problemu jest następnie znajdowany przez rozwiązanie największego podproblemu przy użyciu wcześniej obliczonych wartości.
Takie podejście ma tę zaletę, że jest wydajne pod względem pamięci i czasu dzięki wyeliminowaniu rekurencji.
Przykłady problemów, które można rozwiązać za pomocą programowania dynamicznego
Poniżej przedstawiono niektóre problemy programistyczne, które można rozwiązać za pomocą programowania dynamicznego:
# 1. Problem z plecakiem
Źródło: Wikipedia
Plecak to torba wykonana z płótna, nylonu lub skóry, zwykle zapinana na plecach i używana przez żołnierzy i turystów do przenoszenia zapasów.
W problemie plecakowym masz plecak, a biorąc pod uwagę jego nośność, musisz wybrać przedmioty, z których każdy ma swoją wartość. Twój wybór powinien być taki, aby uzyskać maksymalną łączną wartość wybranych przedmiotów, a waga przedmiotów była mniejsza lub równa pojemności plecaka.
Przykład problemu plecakowego podano poniżej:
Wyobraź sobie, że wybierasz się na pieszą wycieczkę i masz plecak o pojemności 15 kilogramów. Masz listę przedmiotów, które możesz ze sobą zabrać, wraz z ich wartością i wagą, jak pokazano w poniższej tabeli:
PozycjaWartośćWagaNamiot2003Śpiwór1502Piec501Jedzenie1002Bidon100,5Apteczka251
Wybierz podzbiór przedmiotów do przyniesienia w taki sposób, aby całkowita wartość przedmiotów była zmaksymalizowana, a łączna waga była mniejsza lub równa pojemności plecaka, która wynosi 15 kilogramów.
Rzeczywiste zastosowania problemu plecakowego polegają na wyborze papierów wartościowych, które mają zostać dodane do portfela w celu zminimalizowania ryzyka i maksymalizacji zysku oraz znalezienia najmniej marnotrawnych sposobów na ograniczenie surowców.
#2. Problem z harmonogramem
Problem planowania to problem optymalizacyjny, w którym celem jest optymalne przypisanie zadań do zestawu zasobów. Zasobami mogą być maszyny, personel lub inne zasoby wykorzystywane do wykonania zadań.
Poniżej przedstawiono przykład problemu z harmonogramem:
Wyobraź sobie, że jesteś kierownikiem projektu odpowiedzialnym za zaplanowanie zestawu zadań, które muszą zostać wykonane przez zespół pracowników. Każde zadanie ma czas rozpoczęcia, czas zakończenia oraz listę pracowników, którzy są uprawnieni do jego wykonania.
Oto tabela opisująca zadania i ich charakterystykę:
ZadanieCzas rozpoczęciaCzas zakończeniaWykwalifikowani pracownicyT1911A, B, CT21012A, CT31113B, CT41214A, B
Przydziel każde zadanie pracownikowi, aby zminimalizować całkowity czas realizacji.
Problem harmonogramowania można napotkać w przemyśle wytwórczym, próbując zoptymalizować alokację zasobów, takich jak maszyny, materiały, narzędzia i robocizna.
Można go również spotkać w służbie zdrowia przy optymalizacji wykorzystania łóżek, personelu i środków medycznych. Inne branże, w których może wystąpić ten problem, to zarządzanie projektami, zarządzanie łańcuchem dostaw i edukacja.
#3. Problem komiwojażera
Źródło: Wikipedia
Jest to jeden z najczęściej badanych problemów optymalizacyjnych, który można rozwiązać za pomocą programowania dynamicznego.
Problem komiwojażera zawiera listę miast i odległości między każdą parą miast. Musisz znaleźć najkrótszą możliwą trasę, która odwiedza każde miasto dokładnie raz i wraca do miasta początkowego.
Przykład problemu komiwojażera podano poniżej:
Wyobraź sobie, że jesteś sprzedawcą, który musi odwiedzić kilka miast w jak najkrótszym czasie. Masz listę miast, które musisz odwiedzić, oraz odległości między każdą parą miast, jak pokazano w poniższej tabeli:
MiastoABCDEA010152030B100352515C153503020D202530010E301520100
Z problemem komiwojażera można spotkać się między innymi w branży rekreacyjnej przy próbie planowania tras dla turystów, logistyce przy planowaniu wysyłki towarów, transporcie przy planowaniu tras autobusowych oraz w branży sprzedaży.
Oczywiście programowanie dynamiczne ma wiele zastosowań w świecie rzeczywistym, co pomaga dowiedzieć się o nim więcej.
Skorzystaj z poniższych zasobów, aby poszerzyć swoją wiedzę na temat programowania dynamicznego.
Zasoby
Programowanie dynamiczne Richarda Bellmana
Programowanie dynamiczne to książka Richarda Bellmana, który wymyślił programowanie dynamiczne i rozwinął je we wczesnych stadiach.
Książka jest napisana w łatwy do zrozumienia sposób, który wymaga jedynie podstawowej znajomości matematyki i rachunku różniczkowego, aby zrozumieć tekst. W książce Bellman przedstawia matematyczną teorię wieloetapowego procesu decyzyjnego, który jest kluczowy w programowaniu dynamicznym.
Następnie książka analizuje problemy wąskich gardeł w wieloetapowych procesach produkcyjnych, twierdzenia o istnieniu i wyjątkowości oraz optymalne równanie zapasów.
Najlepsze w tej książce jest to, że Bellman podaje przykłady wielu złożonych problemów z dziedzin takich jak logistyka, teoria planowania, teoria komunikacji, ekonomia matematyczna i procesy sterowania oraz pokazuje, jak programowanie dynamiczne może rozwiązać te problemy.
Książka jest dostępna w wersji Kindle, twardej i miękkiej oprawie.
Kurs mistrzowski algorytmów programowania dynamicznego
Ten kurs mistrzowski dotyczący algorytmów programowania dynamicznego firmy Udemy jest oferowany przez Apaara Kamala, inżyniera oprogramowania w Google, oraz Prateeka Naranga, który również współpracował z Google.
Kurs jest zoptymalizowany, aby pomóc uczniom osiągnąć sukces w konkursie programistycznym, który zawiera wiele problemów wymagających programowania dynamicznego.
Oprócz zawodników programistycznych, kurs jest idealny dla programistów, którzy chcą poprawić swoje zrozumienie algorytmów oraz osób przygotowujących się do wywiadów programistycznych i rund kodowania online.
Kurs, który trwa ponad 40 godzin, obejmuje dogłębne programowanie dynamiczne. Kurs najpierw oferuje odświeżenie pojęć, takich jak rekurencja i cofanie się.
Następnie obejmuje programowanie dynamiczne w teorii gier, łańcuchy, drzewa i grafy, potęgowanie macierzy, maski bitowe, kombinatorykę i podsekwencje, problemy z partycjami i wielowymiarowe programowanie dynamiczne, a także wiele innych koncepcji.
Podstawy programowania konkurencyjnego, główne algorytmy
Udemy oferuje kurs podstaw programowania w trybie rywalizacji, prowadzony przez Prateeka Naranga i Amala Kamaara, który obejmuje programowanie dynamiczne, matematykę, teorię liczb oraz zaawansowane struktury danych i algorytmy w sposób przydatny i odpowiedni dla programistów uczestniczących w zawodach.
Kurs oferuje odświeżenie struktur danych i algorytmów przed zagłębieniem się w bardziej złożone algorytmy i techniki przydatne w programowaniu konkurencyjnym.
Kurs obejmuje programowanie dynamiczne, matematykę, teorię gier, dopasowywanie wzorców, maskowanie bitów i mnóstwo zaawansowanych algorytmów używanych i testowanych w konkursach programistycznych.
Kurs Udemy jest podzielony na 10 modułów i 42 sekcje, a po każdej sekcji znajduje się wiele praktycznych pytań. Ten bestsellerowy kurs to pozycja obowiązkowa dla każdego, kto interesuje się programowaniem konkurencyjnym.
Ostatnie słowa
Programowanie dynamiczne to korzystna umiejętność dla każdego programisty, dzięki której nauczy się udoskonalać rozwiązywanie rzeczywistych problemów. Dlatego programiści powinni rozważyć przejrzenie sugerowanych zasobów, aby dodać to kluczowe narzędzie do swojego zestawu narzędzi.
Następnie możesz sprawdzić języki programowania do wykorzystania w nauce o danych.