0/1 Nahrbtnik

0/1 Nahrbtnik

Avtor: Matija Lokar

Osnovna ideja

  • Problem razbijemo na več enostavnejših, med seboj povezanih, podproblemov, običajno iste vrste.
  • Podprobleme rešujemo ločeno in med njimi prenašamo rešitve.
  • Dinamično programiranje:

    • reševanje problema od spodaj navzgor
    • iz rešitev enostavnih podproblemov sestavljamo rešitev težjih problemov.
  • Rešitve enostavnejših problemov shranjujemo in jih pri kasnejših klicih kompleksnejših problemov uporabimo.

Dinamično programiranje

  • sistematično pregledovanje možnih poti v reševanju problema

    • zato tudi pride do optimalne rešitve
  • potencialne rešitve na tekočem koraku določamo na osnovi potencialnih rešitev iz prejšnjega koraka
  • Poznamo dva pristopa za reševanje:

    • pristop naprej
    • pristop nazaj
(slika1.png)

Dinamično programiranje

  • Vse delne rešitve, ki sestavljajo optimalno rešitev, morajo biti tudi optimalne (pravilo optimalnosti).
  • ker je iskanje optimalnih rešitev majhnih problemov lahko, najprej poiščemo vse mogoče delne rešitve podproblemov, ki bi lahko nastopili, ter jih shranimo.
  • iz njih tvorimo rešitve nekoliko zahtevnejših problemov (ni nam treba upoštevati morebitnih neoptimalnih možnosti, ker smo jih izločili že prej).
  • postopek nadaljujemo, dokler ne najdemo končne rešitve problema.
  • praviloma bomo pripravili rešitve mnogih manjših problemov, ki jih ne bomo uporabili v končni rešitvi, vendar bomo zaradi njih pri reševanju morali preizkusiti manj možnosti.

Pravilo optimalnosti

  • Vsako podzaporedje zaporedja odločitev, ki generira optimalno rešitev, mora biti tudi optimalno
  • Matrično verižno množenje

    • Zadnja odločitev:

      • (A*…*A)*(A*…*A)
      • Tako podproblem A*…*A kot podproblem A*…*A moramo rešiti optimalno
      • Zakaj?

Dinamično programiranje

  • Reševanje optimizacijskih problemov – vsaka rešitev ima vrednost, iščemo rešitev z min/max vrednostjo.
  • Običajen potek reševanja naloge z dinamičnim programiranjem.

    • Razbijemo reševanje originalnega problema na podprobleme in preverimo pravilo optimalnosti (podrešitev optimalne rešitve je optimalna rešitev podproblema).
    • Nastavimo rekurzivno enačbo.
    • Izračunaj vrednost optimalne rešitve = rešimo rekurzivno enačbo (memoizacija – pomnjenje prejšnjih rešitev).
    • Konstruiraj optimalno rešitev iz informacije, ki smo si jo shranili med računanjem.

Nekaj povezav

0/1 Nahrbtnik

  • majhen nahrbtnik volumna V, veliko predmetov
  • velikost predmeta v
  • Cena (vrednost) predmeta c
  • iščemo x ki nam pove, kaj se zgodi z i-tim predmetom
(slika2.png)
(slika3.png) (slika4.png)

0/1 Nahrbtnik

  • predmete jemljemo le cele
  • iščemo x {, }‚ ki nam pove, če vzamemo i-ti predmet
(slika5.png)
(slika3.png) (slika4.png)

Preprosti problem nahrbtnika

  • predpostavka: predmete lahko režemo
  • iščemo x med in ‚ ki nam pove, koliko vzamemo i-tega elementa
(slika3.png) (slika4.png)

Preprosti problem nahrbtnika

  • prava strategija: glede na vrednost c/v
  • Dokaz: Kozak str. 220

0/1 nahrbtnik

  • Požrešna metoda nas NE pripelje (nujno) do rešitve
  • Protiprimer

    • c = (57, 57, 105, 113, 100, 108)
    • v = (30, 27, 35, 40, 50, 51)
    • V = 60
    • Požrešna metoda

      • c/v = (1.9, 2.1, 3, 2.8, 2, 2.1)
      • x = (0, 0, 1, 0, 0, 0)
      • C = 105
    • Boljša

      • x = (1, 1, 0, 0, 0, 0)
      • C = 114
(slika6.png)

Strategija

  • Pri požrešni metodi smo vedno vedeli, katera pot nas vodi k rešitvi
  • Pri 0/1 nahrbtniku načeloma ne vemo, ali je smiselno predmet vzeti ali ne
  • Vodimo več potencialnih rešitev

    • Preverimo in zavržemo, če ne pelje k rešitvi
    • Pravila za zavračanje
    • Dinamično programiranje: pravilo optimalnosti

(slika1.jpg)

Pravilo optimalnosti pri O/1 nahrbtniku

  • X naj bo optimalna rešitev za P(V, 1, n)
  • X = 0 – potem mora biti X optimalna rešitev za P(V, 2, n)

    • Zakaj?
  • X = 1 - potem mora biti X optimalna rešitev za P(V, 2, n)

    • Zakaj?
  • Torej ne glede na to, kako se odločimo za 1. predmet – ostale odločitve morajo biti optimalne, da bomo prišli do optimalne rešitve

Bellmanova enačba

  • G(i,W) = vrednost optimalne rešitve s predmeti z indeksi 1, ..., i in prostorom W
  • Iščemo G(n, V)
  • Odločitev za predmet i: vzamemo/ne vzamemo
  • Če ga ne vzamemo:

    • že prej (s predmeti 1 .. i-1) smo sestavili optimalno rešitev za ta volumen: G(i-1,W)
  • Če ga vzamemo:

    • zraven bomo dobili ci,
    • prej (s predmeti 1 .. i-1) smo morali poznati optimum za nahrbtnik z vi manjšim volumnom: G(i-1, W) G(i,W) = max{G(i-1,W), G(i-1, W) + c)}

Bellmanova enačba

  • Pozor, potrebujemo celotni predpis G(i,W) za vse W in ne le za V
  • G(0, W) = 0, W >= 0 (nimamo predmetov, nahrbtnik pa)
  • G(0, W) = -∞, W < 0 (nimamo predmetov, nahrbtnika pa tudi ne)
  • Z izbiro -∞ pri negativnem volumnu preprečimo, da bi vzeli predmete, ki ne gredo noter, ker "neskončno pokvarijo" vrednost
  • S tem maksimum ne bo nikoli napačen!

Implementacija

  • Prva ideja: rekurzija

    O_1Nahrbtnik(i, W) {
      if (i = 0)
        if (W >= 0) return 0;
        else return -∞;
      neVzamem = O_1Nahrbtnik(i-1,W);
      vzamem = O_1Nahrbtnik(i-1,W-v[i])+c[i];
      return max(neVzamem, vzamem);
    }

    Klic: O_1Nahrbtnik(n,V);

Rekurzivna rešitev

  • Rekurzivni algoritem: čas. zahtevnost O(2)
  • Neučinkovito, ker veliko vozlišč izračunamo večkrat ali celo odveč
  • Primer:

    • n=5, V=10, w=[2, 2, 6, 5, 4], c=[6, 3, 5, 4, 6]

(slika2.jpg)

G(1, W)

  • Narišimo
(graf1.jpg)

G(2, W)

  • G(2,w) = max{G(1,W), G(1,W)+c}
  • Narišimo (v = (2, 3), c = (4,1))
(graf2.jpg)

G(2, W)

  • Maksimum
(graf3.jpg)

G(2, W)

  • W < 2: 0(0, 0)
  • 2 ≤ W < 5: 4(1, 0)
  • 5 ≤ W: 5(1, 1)
(graf3.jpg)

G(2, W) – še en zgled

  • Narišimo (v = (2, 3), c = (4,5))
  • G(2,w) = max{G(1,W), G(1,W)+c}
(slike26.jpg)

G(2, W)

  • Maksimum
(slide27.jpg)

G(2, W)

  • W < 2: 0(0, 0)
  • 2 ≤ W < 3: 4(1, 0)
  • 3 ≤ W < 5: 5(0, 1)
  • 5 ≤ W: 9(1, 1)
(slide28.jpg)

Ideja

  • G(j,W) je odsekoma konstantna funkcija
  • Zapomniti si moramo le točke skokov
  • S = { množica parov (W,C), ki opisuje G(i,W)}
  • S = {(0,0)}
  • Z = {množica parov(W,C): (W,C) S}
  • S – zlitje(maksimum!) S in Z

Primer

  • V = (4, 2, 4, 6)
  • C = (5, 3, 7, 8)
  • Zaradi zlivanja uredimo nepadajoče po v
  • V = (2, 4, 4, 6)
  • C = (3, 5, 7, 8)

Primer

  • S = {(0,0)}
  • Z = {(0+2, 0+3)} = {(2, 3)}
  • S = {(0,0), (2,3)}
  • Z = {(0+4, 0+5), (2+4,3+5)} = {(4, 5), (6,8)}
  • S = {(0,0), (2,3), (4, 5), (6,8)}
  • Z = S (4,7) = {(4,7), (6,10), (8, 12), (10,15)}
  • S = {(0,0), (2,3), (4, 7), (6,10), (8, 12), (10,15)}
  • V = (2, 4, 4, 6)
  • C = (3, 5, 7, 8)

Primer

  • S = {(0,0), (2,3), (4, 7), (6,10), (8, 12), (10,15)}
  • Z = S (6,8) = {(6,8), (8,11), (10, 15), (12,18), (14, 20), (16,23)}
  • S = {(0,0), (2,3), (4, 7), (6,10), (8, 12), (10,15), (12,18), (14, 20), (16,23)}
  • Če iščemo rešitev pri V = 9

    • Optimum je 12 (zasedemo 8 prostora)
    • V = 13: optimalna vrednost 18
  • V = (2, 4, 4, 6)
  • C = (3, 5, 7, 8)

Kako do x

  • Že prej: pare vodimo le dokler ne presežejo V
  • (W*,C*) zadnji par v S, kjer W* ≤ V
  • Gledamo, kje je (W*,C*)

    • S & Z x = 0 ali x = 1 (dve optimalni rešitvi)
    • S & ni v Z x = 0
    • ni S je v Z x = 1
  • Ko poznamo x, nadaljujemo enako z x.

    • Če x = 0, gledamo par (W*,C*) v S
    • Če x = 1, gledamo par (W,C) v S
  • Če v primeru izberemo S & Z vedno x = 0, potrebujemo le S

Kako do x - zgled

  • V = 9
  • v = (2, 4, 4, 6)
  • c = (3, 5, 7, 8)

Kako do x - zgled

  • S = {(0,0)}
  • S = {(0,0), (2,3)}
  • S = {(0,0), (2,3), (4, 5), (6,8)}
  • S = {(0,0), (2,3), (4, 7), (6,10), (8, 12}
  • S = {(0,0), (2,3), (4, 7), (6,10), (8, 12)}
  • Vzamemo zadnjega v S : (8,12)
  • Ker (8,12) S x = 0
  • (8,12) ni S x = 1 : (8,12) – (4,7)
  • (4,5) ni S x = 1 : (4, 5) – (4, 5)
  • (0,0) S x = 0
  • Rešitev (0, 1, 1, 0)

V = (2, 4, 4, 6)
C = (3, 5, 7, 8)

0%
0%