+ - 0:00:00
Notes for current slide
Notes for next slide

Optymalizacja dyskretna
(w tym algorytmy heurystyczne)

Podziel i ogranicz

Jakub Nowosad
https://jakubnowosad.com/

1 / 18

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
2 / 18

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)
3 / 18

Brute force (dla porównania)

https://www.geeksforgeeks.org/0-1-knapsack-using-branch-and-bound/

https://www.geeksforgeeks.org/0-1-knapsack-using-branch-and-bound/

4 / 18

Branch and bound

https://www.geeksforgeeks.org/branch-and-bound-algorithm/

https://www.geeksforgeeks.org/branch-and-bound-algorithm/

5 / 18

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
6 / 18

Branch and bound

Kolejność? Wstępna heurystyka

7 / 18

Branch and bound

Kolejność? Wstępna heurystyka

Strategie:

  • Wyliczamy gęstość (relację wartości do wagi)
  • Sortujemy
7 / 18

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
7 / 18

Branch and bound

https://www.geeksforgeeks.org/implementation-of-0-1-knapsack-using-branch-and-bound/

https://www.geeksforgeeks.org/implementation-of-0-1-knapsack-using-branch-and-bound/

8 / 18

Branch and bound

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 Qnie 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.
9 / 18

Przykłady

11 / 18

Problem komiwojażera I

http://www.cs.put.poznan.pl/mkasprzak/zp/ZP-wyklad5.pdf

A B C D E
A 0 31 32 11 18
B 31 0 59 23 46
C 32 59 0 40 15
D 11 23 40 0 27
E 18 46 15 27 0
%0 1->2 1->3 1->4 1->5 2->6 2->7 2->8 3->9 4->10 5->11 6->12 6->13 7->14 7->15 9->16 9->17 10->18 10->19 11->20 12->21 13->22 14->23 15->24 16->25 18->26 19->27 20->28 1 A 2 B 3 C 4 D 5 E 6 C 7 D 8 E 9 B 10 B 11 D 12 D 13 E 14 C 15 E 16 D 17 E 18 C 19 E 20 C 21 E 22 D 23 E 24 C 25 E 26 E 27 C 28 B
12 / 18

Problem komiwojażera II

http://lcm.csa.iisc.ernet.in/dsa/node187.html

http://lcm.csa.iisc.ernet.in/dsa/node187.html

13 / 18

Problem komiwojażera II

  • Podejście - z jednej strony musi być dany odcinek, a z drugiej danego odcinka nie może być
http://lcm.csa.iisc.ernet.in/dsa/node187.html

http://lcm.csa.iisc.ernet.in/dsa/node187.html

14 / 18

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
15 / 18

Problem komiwojażera II

http://lcm.csa.iisc.ernet.in/dsa/node187.html

http://lcm.csa.iisc.ernet.in/dsa/node187.html

16 / 18

Inne materiały

17 / 18

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
2 / 18
Paused

Help

Keyboard shortcuts

, , Pg Up, k Go to previous slide
, , Pg Dn, Space, j Go to next slide
Home Go to first slide
End Go to last slide
Number + Return Go to specific slide
b / m / f Toggle blackout / mirrored / fullscreen mode
c Clone slideshow
p Toggle presenter mode
t Restart the presentation timer
?, h Toggle this help
Esc Back to slideshow