class: center, middle, inverse, title-slide .title[ # Optymalizacja dyskretna
(w tym algorytmy heurystyczne) ] .subtitle[ ## Programowanie dynamiczne ] .author[ ### Jakub Nowosad
https://jakubnowosad.com/
] --- <!-- http://web.sgh.waw.pl/~jg23234/do/DO2016/Wyk%C5%82ad%209%20-%20Zasada%20Bellmana.pdf --> <!-- http://www.cs.put.poznan.pl/arybarczyk/TeoriaAiSD3.pdf --> # Programowanie dynamiczne - **Dynamic programming** - Algorytm dokładny (nieheurystyczny) - wyszukiwanie optymalnego rozwiązania bez konieczności sprawdzania wszystkich rozwiązań - Stosowane do wieloetapowych procesów decyzyjnych - Programowanie dynamiczne opiera się na podziale rozwiązywanego problemu na podproblemy względem kilku parametrów - Zasada optymalności Bellmana - decyzja optymalna podjęta w kroku `i` jest nadal optymalną w kroku `i+1` i kolejnych. (Nie możemy się cofać) - Programowanie dynamiczne sprowadza się do rozbicia problemu optymalizacyjnego na prostsze podproblemy i zapisania rozwiązania każdego podproblemu tak, aby każdy podproblem został rozwiązany tylko raz <!-- Klucz do zaprojektowania algorytmu tą techniką leży w znalezieniu równania rekurencyjnego opisującego optymalną wartość funkcji celu dla danego problemu jako funkcji optymalnych wartości funkcji celu dla podproblemów o mniejszych rozmiarach. --> --- # Programowanie dynamiczne - W programowaniu dynamicznym skracamy czas obliczeń kosztem zajmowanej przestrzeni (np. w pamięci) - https://www.quora.com/How-should-I-explain-dynamic-programming-to-a-4-year-old/answer/Jonathan-Paulson: > *writes down "1+1+1+1+1+1+1+1 =" on a sheet of paper* <br> "What's that equal to?" <br> *counting* "Eight!" <br> *writes down another "1+" on the left* <br> "What about that?" <br> *quickly* "Nine!" <br> "How'd you know it was nine so fast?" <br> "You just added one more" <br> "So you didn't need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say 'remembering stuff to save time later'" --- # Programowanie dynamiczne <!-- http://sipi.usc.edu/~ortega/RD_Examples/boxDP.html --> Dwa wymagania: 1. **Optymalna podstruktura** - rozwiązanie problemu optymalizacyjnego można określić poprzez optymalnie rozwiązanie jego podproblemów. 2. **Nakładające się podproblemy** - każdy rekurencyjny algorytm rozwiązujący problem powinien rozwiązywać te same podproblemy w kółko, a nie generować nowe podproblemy. W odróżnieniu od techniki dziel i zwyciężaj (ang. *divide and conquer*) podproblemy w programowaniu dynamicznym nie są rozłączne, ale musi je cechować własność optymalnej podstruktury. <!-- Przykład https://www.youtube.com/watch?v=B_SpfyPl5XA min32 --> --- # Programowanie dynamiczne - Aby rozwiązać dany problem należy rozwiązać wszystkie problemy cząstkowe - Tworzymy w ten sposób drzewo zależności (a nie regularne drzewo) [Dwa podejścia](https://media.geeksforgeeks.org/wp-content/cdn-uploads/Tabulation-vs-Memoization-1.png): - **Bottom-up** - rozwiązanie problemu rekurencyjnie poprzez rozwiązywanie najmniejszych podproblemów (**tabulation**) - **Top-down** - by uniknąć wielokrotnego rozwiązywania identycznych problemów cząstkowych przechowujemy ich wyniki (redukujemy złożoność obliczeniową) (**memoization**, nie *memorization*!) --- # Bottom-up Dynamic Programming - Rozwiązujemy najpierw najmniejsze podproblemy - Wykorzystujemy je rozwiązania do zbudowania i znalezienia rozwiązań dla większych podproblemów --- # Top-down Dynamic Programming - Zapamiętujemy rozwiązania do podproblemów - Za każdym razem, gdy próbujemy rozwiązać nowy podproblem, najpierw sprawdzamy tabelę, czy jest już rozwiązany - Jeśli rozwiązanie zostało zapisane, możemy użyć go bezpośrednio, w przeciwnym razie rozwiążemy podproblemy i dodamy ich rozwiązanie do tabeli --- # Rekurencja .pull-left[ <img src="images/serpiente.jpg" style="display: block; margin: auto;" /> ] .pull-right[ - *Recursion* - technika wykorzystywana w programowaniu polegająca do odwoływaniu się funkcji do samej siebie - "To understand recursion, you must understand recursion." - Przykład - wyliczanie silni: ``` unsigned int factorial(unsigned int n) { if (n == 0) { return 1; } else { return n * factorial(n - 1); } } ``` ] --- # Rekurencja <div class="figure" style="text-align: center"> <img src="images/recursion.jpg" alt="https://www.smbc-comics.com/comic/recursion" width="60%" /> <p class="caption">https://www.smbc-comics.com/comic/recursion</p> </div> --- # Ciąg Fibonacciego .pull-left[ - Taki ciąg liczb naturalnych, gdzie każdy kolejny wyraz jest sumą dwóch poprzednich, zaczynając od 0 i 1 - https://www.youtube.com/watch?v=SjSHVDfXHQ4, https://www.youtube.com/watch?v=kkGeOWYOFoA - Przykład $$ 0, 1, 1, 2, 3, 5, 8, ... $$ <img src="images/fibonacci-spiral.png" width="80%" style="display: block; margin: auto;" /> - Dla uproszczenia - nie zajmujemy się pierwszym 0 i 1 ] -- .pull-right[ <img src="images/fib.png" width="70%" style="display: block; margin: auto;" /> - Drzewo zależności - Potwierdza ono, że jest to problem pasujący do programowania dynamicznego ] --- # Ciąg Fibonacciego https://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence Rekurencyjna funkcja do wyliczania wartości ciągu Fibonacciego: ``` function fib(n) if n <= 1 return n return fib(n − 1) + fib(n − 2) ``` Określenie wartości ciągu Fibonacciego: 1. `fib(5)` 2. `fib(4) + fib(3)` 3. `(fib(3) + fib(2)) + (fib(2) + fib(1))` 4. `((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))` 5. `(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))` -- Jaki tutaj istnieje problem? -- - **Część obliczeń jest wykonywanych wielokrotnie.** - **Złożoność wykładnicza (O(2<sup>n</sup>))** --- # Ciąg Fibonacciego Podejście **bottom-up**: ``` function fib(n) if n = 0 return 0 else var previousFib := 0, currentFib := 1 repeat n − 1 times // loop is skipped if n = 1 var newFib := previousFib + currentFib previousFib := currentFib currentFib := newFib return currentFib ``` - Zaczynamy od wyliczenia najmniejszej wartości `fib`, a dopiero następnie coraz to wyższych wartości z tej wcześniej uzyskanej - Złożoność liniowa (O(n)) --- # Ciąg Fibonacciego Podejście **top-down**: ``` var m := map(0 → 0, 1 → 1) function fib(n) if key n is not in map m m[n] := fib(n − 1) + fib(n − 2) return m[n] ``` - **Memoization** - przechowujemy wartości już wykonanych obliczeń - Złożoność liniowa (O(n)) --- # Problem wydawania reszty https://www.cs.usfca.edu/~galles/visualization/DPChange.html <div class="figure" style="text-align: center"> <img src="images/reszta.gif" alt="http://algorytmy.ency.pl/artykul/programowanie_dynamiczne" width="58%" /> <p class="caption">http://algorytmy.ency.pl/artykul/programowanie_dynamiczne</p> </div> --- # Schemat działania 1. **Określ czy problem można rozwiązać używając programowania dynamicznego** 2. **Ustal jak przedstawić stan używając jak najmniejszej liczby parametrów** 3. **Sformułuj relacje pomiędzy stanami** 4. **Użyj tabulacji lub memoizacji** Inne podejście: - https://www.quora.com/What-are-some-good-ways-to-approach-a-dynamic-programming-question/answer/Paul-Baltescu --- # Schemat działania 1) **Określ czy problem można rozwiązać używając programowania dynamicznego** - Zazwyczaj problemy, które wymagają zmaksymalizowania lub zminimalizowania pewnych ilości lub problemy z liczeniem, które mówią o wyliczaniu rozmieszczeń pod pewnymi warunkami mogą być rozwiązane za pomocą programowania dynamicznego --- # Schemat działania 2) **Ustal jak przedstawić stan używając jak najmniejszej liczby parametrów** - Problemy programowania dynamicznego dotyczą stanu i jego przejścia - Stan - można zdefiniować jako zbiór parametrów, które w unikalny sposób identyfikują konkretną pozycję lub położenie w danym problemie. Ten zestaw parametrów powinien być jak najmniejszy, aby zmniejszyć przestrzeń stanu - W problemie plecakowym tymi parametrami mogą być indeks i waga --- # Schemat działania 3) **Sformułuj relacje pomiędzy stanami** - Przykład - https://www.geeksforgeeks.org/solve-dynamic-programming-problem/ --- # Schemat działania 4) **Użyj tabulacji lub memoizacji** - Przykład - https://www.geeksforgeeks.org/solve-dynamic-programming-problem/ --- # Zastosowanie - https://www.geeksforgeeks.org/dynamic-programming/ - https://blog.usejournal.com/top-50-dynamic-programming-practice-problems-4208fed71aa3 --- class: inverse, left, bottom # Przykłady <!-- Proces alokacyjny http://www.cs.put.poznan.pl/arybarczyk/TeoriaAiSD3.pdf - Jednowymiarowy proces alokacyjny - Pierwszy wiersz przedstawia koszt (ile zasobu musimy wydać) - Kolejne wiersze przedstawiają zyski dla różnych działalności - Cel: podzielenie `M = 8` jednostek zasobu na `N = 3` działalności, tak aby maksymalizować zyski <table> <tbody> <tr> <td style="text-align:left;"> koszt </td> <td style="text-align:right;"> 0 </td> <td style="text-align:right;"> 1 </td> <td style="text-align:right;"> 2 </td> <td style="text-align:right;"> 3 </td> <td style="text-align:right;"> 4 </td> <td style="text-align:right;"> 5 </td> <td style="text-align:right;"> 6 </td> <td style="text-align:right;"> 7 </td> <td style="text-align:right;"> 8 </td> </tr> <tr> <td style="text-align:left;"> dzialalnosc1 </td> <td style="text-align:right;"> 0 </td> <td style="text-align:right;"> 5 </td> <td style="text-align:right;"> 15 </td> <td style="text-align:right;"> 40 </td> <td style="text-align:right;"> 80 </td> <td style="text-align:right;"> 90 </td> <td style="text-align:right;"> 95 </td> <td style="text-align:right;"> 98 </td> <td style="text-align:right;"> 100 </td> </tr> <tr> <td style="text-align:left;"> dzialalnosc2 </td> <td style="text-align:right;"> 0 </td> <td style="text-align:right;"> 5 </td> <td style="text-align:right;"> 15 </td> <td style="text-align:right;"> 40 </td> <td style="text-align:right;"> 60 </td> <td style="text-align:right;"> 70 </td> <td style="text-align:right;"> 73 </td> <td style="text-align:right;"> 74 </td> <td style="text-align:right;"> 75 </td> </tr> <tr> <td style="text-align:left;"> dzialalnosc3 </td> <td style="text-align:right;"> 0 </td> <td style="text-align:right;"> 4 </td> <td style="text-align:right;"> 26 </td> <td style="text-align:right;"> 40 </td> <td style="text-align:right;"> 45 </td> <td style="text-align:right;"> 50 </td> <td style="text-align:right;"> 51 </td> <td style="text-align:right;"> 52 </td> <td style="text-align:right;"> 53 </td> </tr> </tbody> </table> Proces alokacyjny <table> <tbody> <tr> <td style="text-align:left;"> koszt </td> <td style="text-align:right;"> 0 </td> <td style="text-align:right;"> 1 </td> <td style="text-align:right;"> 2 </td> <td style="text-align:right;"> 3 </td> <td style="text-align:right;"> 4 </td> <td style="text-align:right;"> 5 </td> <td style="text-align:right;"> 6 </td> <td style="text-align:right;"> 7 </td> <td style="text-align:right;"> 8 </td> </tr> <tr> <td style="text-align:left;"> dzialalnosc1 </td> <td style="text-align:right;"> 0 </td> <td style="text-align:right;"> 5 </td> <td style="text-align:right;"> 15 </td> <td style="text-align:right;"> 40 </td> <td style="text-align:right;"> 80 </td> <td style="text-align:right;"> 90 </td> <td style="text-align:right;"> 95 </td> <td style="text-align:right;"> 98 </td> <td style="text-align:right;"> 100 </td> </tr> <tr> <td style="text-align:left;"> dzialalnosc2 </td> <td style="text-align:right;"> 0 </td> <td style="text-align:right;"> 5 </td> <td style="text-align:right;"> 15 </td> <td style="text-align:right;"> 40 </td> <td style="text-align:right;"> 60 </td> <td style="text-align:right;"> 70 </td> <td style="text-align:right;"> 73 </td> <td style="text-align:right;"> 74 </td> <td style="text-align:right;"> 75 </td> </tr> <tr> <td style="text-align:left;"> dzialalnosc3 </td> <td style="text-align:right;"> 0 </td> <td style="text-align:right;"> 4 </td> <td style="text-align:right;"> 26 </td> <td style="text-align:right;"> 40 </td> <td style="text-align:right;"> 45 </td> <td style="text-align:right;"> 50 </td> <td style="text-align:right;"> 51 </td> <td style="text-align:right;"> 52 </td> <td style="text-align:right;"> 53 </td> </tr> </tbody> </table> - Co by było gdyby... Zaczynając od ostatniej decyzji (zajmujemy się ostatnią działalnością do wyboru) <table> <tbody> <tr> <td style="text-align:left;"> pozostaly_zasob </td> <td style="text-align:left;"> 0 </td> <td style="text-align:left;"> 1 </td> <td style="text-align:left;"> 2 </td> <td style="text-align:left;"> 3 </td> <td style="text-align:left;"> 4 </td> <td style="text-align:left;"> 5 </td> <td style="text-align:left;"> 6 </td> <td style="text-align:left;"> 7 </td> <td style="text-align:left;"> 8 </td> </tr> <tr> <td style="text-align:left;"> zysk3 </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> </tr> <tr> <td style="text-align:left;"> koszt3 </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> </tr> <tr> <td style="text-align:left;"> zysk2 </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> </tr> <tr> <td style="text-align:left;"> koszt2 </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> </tr> <tr> <td style="text-align:left;"> zysk1 </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> </tr> <tr> <td style="text-align:left;"> koszt1 </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> </tr> </tbody> </table> Proces alokacyjny <table> <tbody> <tr> <td style="text-align:left;"> koszt </td> <td style="text-align:right;"> 0 </td> <td style="text-align:right;"> 1 </td> <td style="text-align:right;"> 2 </td> <td style="text-align:right;"> 3 </td> <td style="text-align:right;"> 4 </td> <td style="text-align:right;"> 5 </td> <td style="text-align:right;"> 6 </td> <td style="text-align:right;"> 7 </td> <td style="text-align:right;"> 8 </td> </tr> <tr> <td style="text-align:left;"> dzialalnosc1 </td> <td style="text-align:right;"> 0 </td> <td style="text-align:right;"> 5 </td> <td style="text-align:right;"> 15 </td> <td style="text-align:right;"> 40 </td> <td style="text-align:right;"> 80 </td> <td style="text-align:right;"> 90 </td> <td style="text-align:right;"> 95 </td> <td style="text-align:right;"> 98 </td> <td style="text-align:right;"> 100 </td> </tr> <tr> <td style="text-align:left;"> dzialalnosc2 </td> <td style="text-align:right;"> 0 </td> <td style="text-align:right;"> 5 </td> <td style="text-align:right;"> 15 </td> <td style="text-align:right;"> 40 </td> <td style="text-align:right;"> 60 </td> <td style="text-align:right;"> 70 </td> <td style="text-align:right;"> 73 </td> <td style="text-align:right;"> 74 </td> <td style="text-align:right;"> 75 </td> </tr> <tr> <td style="text-align:left;"> dzialalnosc3 </td> <td style="text-align:right;"> 0 </td> <td style="text-align:right;"> 4 </td> <td style="text-align:right;"> 26 </td> <td style="text-align:right;"> 40 </td> <td style="text-align:right;"> 45 </td> <td style="text-align:right;"> 50 </td> <td style="text-align:right;"> 51 </td> <td style="text-align:right;"> 52 </td> <td style="text-align:right;"> 53 </td> </tr> </tbody> </table> - Co by było gdyby... Zaczynając od ostatniej decyzji (zajmujemy się ostatnią działalnością do wyboru) <table> <tbody> <tr> <td style="text-align:left;"> pozostaly_zasob </td> <td style="text-align:left;"> 0 </td> <td style="text-align:left;"> 1 </td> <td style="text-align:left;"> 2 </td> <td style="text-align:left;"> 3 </td> <td style="text-align:left;"> 4 </td> <td style="text-align:left;"> 5 </td> <td style="text-align:left;"> 6 </td> <td style="text-align:left;"> 7 </td> <td style="text-align:left;"> 8 </td> </tr> <tr> <td style="text-align:left;"> zysk3 </td> <td style="text-align:left;"> 0 </td> <td style="text-align:left;"> 4 </td> <td style="text-align:left;"> 26 </td> <td style="text-align:left;"> 40 </td> <td style="text-align:left;"> 45 </td> <td style="text-align:left;"> 50 </td> <td style="text-align:left;"> 51 </td> <td style="text-align:left;"> 52 </td> <td style="text-align:left;"> 53 </td> </tr> <tr> <td style="text-align:left;"> koszt3 </td> <td style="text-align:left;"> 0 </td> <td style="text-align:left;"> 1 </td> <td style="text-align:left;"> 2 </td> <td style="text-align:left;"> 3 </td> <td style="text-align:left;"> 4 </td> <td style="text-align:left;"> 5 </td> <td style="text-align:left;"> 6 </td> <td style="text-align:left;"> 7 </td> <td style="text-align:left;"> 8 </td> </tr> <tr> <td style="text-align:left;"> zysk2 </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> </tr> <tr> <td style="text-align:left;"> koszt2 </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> </tr> <tr> <td style="text-align:left;"> zysk1 </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> </tr> <tr> <td style="text-align:left;"> koszt1 </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> <td style="text-align:left;"> </td> </tr> </tbody> </table> --> --- # Problem plecakowy I - http://www.cs.put.poznan.pl/mkasprzak/zp/ZP-wyklad5.pdf - `\(I = 5\)`, `\(W = 10\)`, `\(c_i = [3, 4, 2, 6, 1]\)`, `\(w_i = [5, 3, 2, 4, 3]\)` -- Tablica programowania dynamicznego:
--- # Problem plecakowy I - http://www.cs.put.poznan.pl/mkasprzak/zp/ZP-wyklad5.pdf - `\(I = 5\)`, `\(W = 10\)`, `\(c_i = [3, 4, 2, 6, 1]\)`, `\(w_i = [5, 3, 2, 4, 3]\)` - Rozwiązanie odczytujemy od końca, cofając się z pola `\((I,W)\)` po kolei do pól, z których wyprowadzone zostały wartości składające się na optymalną ścieżkę. Kończymy na wartości 0. --
- **Rozwiązanie:** {2, 3, 4} --- # Problem plecakowy II <!-- https://stackoverflow.com/a/40223136 --> - https://www.hackerearth.com/practice/notes/the-knapsack-problem/ - https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/ --- # Problem komiwojażera - https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm - https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/ - https://towardsdatascience.com/solving-tsp-using-dynamic-programming-2c77da86610d --- class: inverse, left, bottom # Inne materiały --- # Inne materiały - https://www.youtube.com/watch?v=B_SpfyPl5XA - https://cran.r-project.org/web/packages/RcppDynProg/vignettes/Segmentation.html - https://www.geeksforgeeks.org/dynamic-programming/ - https://github.com/llSourcell/dynamic_programming/blob/master/Dynamic%20Programming.ipynb - https://www.hackerearth.com/practice/notes/dynamic-programming-i-1/ - https://blog.usejournal.com/top-50-dynamic-programming-practice-problems-4208fed71aa3 - https://medium.com/basecs/speeding-up-the-traveling-salesman-using-dynamic-programming-b76d7552e8dd - https://dev.to/victoria/knapsack-problem-algorithms-for-my-real-life-carry-on-knapsack-33jj - Błażewicz, Jacek (1983) Badania operacyjne dla informatyków, Wydaw. Nauk.-Techn., Warszawa - http://www.micsymposium.org/mics_2005/papers/paper102.pdf