class: center, middle, inverse, title-slide # Optymalizacja dyskretna <br>(w tym algorytmy heurystyczne) ## Podziel i ogranicz ### Jakub Nowosad <br><a href="https://jakubnowosad.com/" class="uri">https://jakubnowosad.com/</a> --- # Branch and bound - Podziel i ogranicz - Algorytm dokładny (nieheurystyczny) - wyszukiwanie optymalnego rozwiązania bez konieczności sprawdzania wszystkich rozwiązań - Często wolny algorytm - W najgorszym przypadku wykładniczy wzrost czasu wykonywania algorytmu wraz ze wzrostem rozmiaru danych wejściowych --- # Branch and bound - Polega ona na przeszukaniu drzewa reprezentującego przestrzeń rozwiązań problemu - Dwie procedury: - **Podział** - dzielenie zbioru rozwiązań na rozłączne podzbiory - **Ograniczanie** - pomijanie w przeszukiwaniu gałęzi, o których wiemy że nie zawierają optymalnego rozwiązania. Ograniczenia mogą być dolne (lower bound) lub górne (upper bound) --- # Brute force (dla porównania) <div class="figure" style="text-align: center"> <img src="images/bf.jpg" alt="https://www.geeksforgeeks.org/0-1-knapsack-using-branch-and-bound/" width="1019" /> <p class="caption">https://www.geeksforgeeks.org/0-1-knapsack-using-branch-and-bound/</p> </div> --- # Branch and bound <div class="figure" style="text-align: center"> <img src="images/bab1.jpg" alt="https://www.geeksforgeeks.org/branch-and-bound-algorithm/" width="816" /> <p class="caption">https://www.geeksforgeeks.org/branch-and-bound-algorithm/</p> </div> --- # Branch and bound Ignorujemy rozwiązania, które: 1. Są niemożliwe (mają sumę wag większą niż nasza pojemność) 2. Są gorsze niż obecne najlepsze pełne rozwiązanie --- # Branch and bound Kolejność? Wstępna heurystyka -- Strategie: - Wyliczamy gęstość (relację wartości do wagi) - Sortujemy -- Ograniczanie: - Wkładamy do plecaka posortowane elementy of najcenniejszego aż do zapełnienia plecaka - Ostatni element może być włożony częściowo - Np. plecak ma ograniczenie wagi (W) równe 5. Dwa posortowane elementy ważą razem 4 (2 + 2) i mają wartość 10 (6 + 4). Trzeci z posortowanych elementów waży 2 i ma wartość 2. Czyli suma wartości wynosi 6 + 4 + (1/2 * 2) = 11. - W ten sposób określamy górne ograniczenie (ang. *upper bound*) - plecak nie będzie bardziej wartościowy niż te kilka najcenniejszych elementów --- # Branch and bound <div class="figure" style="text-align: center"> <img src="images/bab2.jpg" alt="https://www.geeksforgeeks.org/implementation-of-0-1-knapsack-using-branch-and-bound/" width="80%" /> <p class="caption">https://www.geeksforgeeks.org/implementation-of-0-1-knapsack-using-branch-and-bound/</p> </div> --- # Branch and bound <!-- Implementacja: --> <!-- https://www.geeksforgeeks.org/implementation-of-0-1-knapsack-using-branch-and-bound/ --> <!-- https://medium.com/@leenancyparmar1999/knapsack-problem-branch-and-bound-approach-1fdab6d9a241 --> Algorytm: 1. Sortuj wszystkie pozycje w kolejności malejącego stosunku wartości do wagi. W ten sposób używając algorytmu zachłannego możemy wyznaczyć górne ograniczenie. 2. Zainicjuj maksymalny zysk, `maxProfit = 0` 3. Stwórz pustą kolejkę, `Q`. 4. Stwórz węzeł drzewa decyzyjnego i umieść go w kolejce `Q`. Zysk i waga węzła wynoszą 0. 5. Gdy `Q `nie jest pusty: - Wyciągnij element z `Q`, nazwijmy go `u`. - Oblicz zysk węzła następnego poziomu. Jeśli zysk jest większy niż `maxProfit`, to zaktualizuj `maxProfit`. - Oblicz granicę węzła następnego poziomu. Jeśli wartość graniczna jest większa niż maxProfit, to dodaj węzeł następnego poziomu do Q. - Rozważ przypadek, gdy węzeł następnego poziomu nie jest uważany za część rozwiązania i dodaj węzeł do kolejki z poziomem jako następnym, ale wagą i zyskiem bez uwzględnienia węzłów następnego poziomu. --- # Branch and bound - Implementacja I - https://en.wikipedia.org/wiki/Branch_and_bound#Pseudocode - Implementacja II - https://www.geeksforgeeks.org/implementation-of-0-1-knapsack-using-branch-and-bound/ --- class: inverse, left, bottom # Przykłady --- # Problem komiwojażera I http://www.cs.put.poznan.pl/mkasprzak/zp/ZP-wyklad5.pdf .lc[ <table> <thead> <tr> <th style="text-align:left;"> </th> <th style="text-align:right;"> A </th> <th style="text-align:right;"> B </th> <th style="text-align:right;"> C </th> <th style="text-align:right;"> D </th> <th style="text-align:right;"> E </th> </tr> </thead> <tbody> <tr> <td style="text-align:left;"> A </td> <td style="text-align:right;"> 0 </td> <td style="text-align:right;"> 31 </td> <td style="text-align:right;"> 32 </td> <td style="text-align:right;"> 11 </td> <td style="text-align:right;"> 18 </td> </tr> <tr> <td style="text-align:left;"> B </td> <td style="text-align:right;"> 31 </td> <td style="text-align:right;"> 0 </td> <td style="text-align:right;"> 59 </td> <td style="text-align:right;"> 23 </td> <td style="text-align:right;"> 46 </td> </tr> <tr> <td style="text-align:left;"> C </td> <td style="text-align:right;"> 32 </td> <td style="text-align:right;"> 59 </td> <td style="text-align:right;"> 0 </td> <td style="text-align:right;"> 40 </td> <td style="text-align:right;"> 15 </td> </tr> <tr> <td style="text-align:left;"> D </td> <td style="text-align:right;"> 11 </td> <td style="text-align:right;"> 23 </td> <td style="text-align:right;"> 40 </td> <td style="text-align:right;"> 0 </td> <td style="text-align:right;"> 27 </td> </tr> <tr> <td style="text-align:left;"> E </td> <td style="text-align:right;"> 18 </td> <td style="text-align:right;"> 46 </td> <td style="text-align:right;"> 15 </td> <td style="text-align:right;"> 27 </td> <td style="text-align:right;"> 0 </td> </tr> </tbody> </table> ] .rc[ <div id="htmlwidget-a32e616bc16550004729" style="width:504px;height:504px;" class="grViz html-widget"></div> <script type="application/json" data-for="htmlwidget-a32e616bc16550004729">{"x":{"diagram":"digraph {\n\ngraph [layout = \"dot\",\n rankdir = \"TB\",\n outputorder = \"edgesfirst\",\n bgcolor = \"white\"]\n\nnode [fontname = \"Helvetica\",\n fontsize = \"10\",\n shape = \"circle\",\n fixedsize = \"true\",\n width = \"0.5\",\n style = \"filled\",\n fillcolor = \"aliceblue\",\n color = \"gray70\",\n fontcolor = \"gray50\"]\n\nedge [fontname = \"Helvetica\",\n fontsize = \"8\",\n len = \"1.5\",\n color = \"gray80\",\n arrowsize = \"0.5\"]\n\n \"1\" [label = \"A\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"2\" [label = \"B\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"3\" [label = \"C\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"4\" [label = \"D\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"5\" [label = \"E\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"6\" [label = \"C\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"7\" [label = \"D\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"8\" [label = \"E\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"9\" [label = \"B\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"10\" [label = \"B\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"11\" [label = \"D\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"12\" [label = \"D\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"13\" [label = \"E\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"14\" [label = \"C\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"15\" [label = \"E\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"16\" [label = \"D\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"17\" [label = \"E\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"18\" [label = \"C\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"19\" [label = \"E\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"20\" [label = \"C\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"21\" [label = \"E\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"22\" [label = \"D\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"23\" [label = \"E\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"24\" [label = \"C\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"25\" [label = \"E\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"26\" [label = \"E\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"27\" [label = \"C\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"28\" [label = \"B\", fillcolor = \"#F0F8FF\", fontcolor = \"#000000\"] \n \"1\"->\"2\" \n \"1\"->\"3\" \n \"1\"->\"4\" \n \"1\"->\"5\" \n \"2\"->\"6\" \n \"2\"->\"7\" \n \"2\"->\"8\" \n \"3\"->\"9\" \n \"4\"->\"10\" \n \"5\"->\"11\" \n \"6\"->\"12\" \n \"6\"->\"13\" \n \"7\"->\"14\" \n \"7\"->\"15\" \n \"9\"->\"16\" \n \"9\"->\"17\" \n \"10\"->\"18\" \n \"10\"->\"19\" \n \"11\"->\"20\" \n \"12\"->\"21\" \n \"13\"->\"22\" \n \"14\"->\"23\" \n \"15\"->\"24\" \n \"16\"->\"25\" \n \"18\"->\"26\" \n \"19\"->\"27\" \n \"20\"->\"28\" \n}","config":{"engine":"dot","options":null}},"evals":[],"jsHooks":[]}</script> ] --- # Problem komiwojażera II <div class="figure" style="text-align: center"> <img src="images/bab_tspe.gif" alt="http://lcm.csa.iisc.ernet.in/dsa/node187.html" width="80%" /> <p class="caption">http://lcm.csa.iisc.ernet.in/dsa/node187.html</p> </div> --- # Problem komiwojażera II - Podejście - z jednej strony musi być dany odcinek, a z drugiej danego odcinka nie może być <div class="figure" style="text-align: center"> <img src="images/bab_tsp1.gif" alt="http://lcm.csa.iisc.ernet.in/dsa/node187.html" width="80%" /> <p class="caption">http://lcm.csa.iisc.ernet.in/dsa/node187.html</p> </div> --- # Problem komiwojażera II Ignorujemy (przycinamy) cząstkowe rozwiązania, które: 1. Są dłuższe niż obecne najkrótsze pełne rozwiązanie Sortujemy: 1. Np. według najkrótszych pojedynczych odcinków --- # Problem komiwojażera II <div class="figure" style="text-align: center"> <img src="images/bab_tsp2.gif" alt="http://lcm.csa.iisc.ernet.in/dsa/node187.html" width="74%" /> <p class="caption">http://lcm.csa.iisc.ernet.in/dsa/node187.html</p> </div> <!-- https://www.geeksforgeeks.org/traveling-salesman-problem-using-branch-and-bound-2/ --> --- class: inverse, left, bottom # Inne materiały --- # Inne materiały - https://tarakc02.github.io/branch-and-bound/ - http://web.tecnico.ulisboa.pt/mcasquilho/compute/_linpro/TaylorB_module_c.pdf - https://www.geeksforgeeks.org/8-puzzle-problem-using-branch-and-bound/ - https://www.geeksforgeeks.org/job-assignment-problem-using-branch-and-bound/ - https://www.geeksforgeeks.org/n-queen-problem-using-branch-and-bound/ - https://towardsdatascience.com/the-branch-and-bound-algorithm-a7ae4d227a69