8. Dynamické programovanie

Na riešenie niektorých úloh, v ktorých hľadáme nejaké optimálne riešenie, môžeme niekedy použiť metódu dynamické programovanie. Idea sa trochu podobá metóde rozdeľuj a panuj, preto si ju pripomeňme:

  1. ak sa ešte dá rozdeľ veľký problém na (disjunktné) podproblémy
  2. (rekurzívne) vyrieš každý z podproblémov
  3. spoj dokopy všetky tieto čiastkové riešenia do riešenia celého problému

Videli sme napr. ako sa táto metóda využila pre merge sort aj quick sort. Uvedomte si, že pri tom sa problém rieši zhora nadol.

Metóda dynamické programovanie postupuje opačne:

  1. vyriešime najjednoduchšie prípady zložitého problému - riešenia si zapamätáme najlepšie v nejakej tabuľke (podproblémy nemusia byť navzájom disjunktné - bolo by dokonca dobré, keby sa navzájom prekrývali)
  2. z týchto jednoduchých riešení postupne skladáme riešenia stále zložitejších a zložitejších prípadov problému a všetko toto zapisujeme do tabuľky
  3. takto pokračujeme, kým sa nedostaneme k riešeniu požadovaného problému

Táto metóda funguje na princípe zdola nahor a väčšinou využíva pomocnú pamäť na pamätanie si čiastkových riešení - často sú to jednorozmerné alebo dvojrozmerné tabuľky (veľkosti O(n) alebo O(n**2)). Vďaka tejto metóde sa niekedy podarí z problému exponenciálnej zložitosti O(2**n) vyrobiť riešenie zložitosti O(n) alebo O(n**2).

Na riešenie úloh pomocou dynamického programovania treba mať veľkú skúsenosť s analýzou problému, rozdelením na podproblémy, vymyslením, ako skladať z riešení malých podproblémov väčšie, ako využívať tabuľky. Ukážeme to na sérii jednoduchých úloh: mnohé z nich sme už veľakrát riešili, ale netušili sme, že za nimi sú skryté princípy dynamického programovania.

Fibonacciho postupnosť

Poznáme rekurzívnu verziu funkcie:

def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

Už vieme, že táto funkcia má exponenciálnu zložitosť.

Ak by sme najprv postupne (bez rekurzie) vypočítali do tabuľky prvých n členov postupnosti a potom n-tý vrátili ako výsledok funkcie, zložitosť tohto zápisu by bola len O(n). Hoci v tomto prípade sme tiež minuli O(n) pomocnej pamäte:

def fib(n):
    tab = [0, 1]
    for i in range(2, n+1):
        tab.append(tab[i-1] + tab[i-2])
    return tab[n]

Toto je najjednoduchší prípad použitia dynamického programovania: veľký problém (zložitosti O(2**n)) sme pomocou postupného zostavovania tabuľky (v nej sme riešili jednoduchšie podproblémy a z nich sme zostavovali stále zložitejšie a zložitejšie riešenia) previedli na úlohu zložitosti O(n). Vidíme tu, že úloha sa rieši metódou zdola nahor, t.j. najprv najjednoduchšie podúlohy a potom stále zložitejšie, ktoré sa blížia k požadovanému problému.

Fibonacciho postupnosť tiež vieme vyriešiť aj bez rekurzie a bez pomocnej tabuľky, napr.

def fib(n):
    f1, f2 = 1, 0
    for i in range(n):
        f1, f2 = f2, f1+f2
    return f2

V tomto riešení sme prepísali rekurzívnu úlohu postupným riešením najprv najjednoduchších podproblémov (postupne pre n=0 a n=1) a z nich zostavujeme zložitejšie riešenia - tu sme tabuľku veľkosti n nahradili len dvomi pomocnými premennými.

Inokedy sa pri riešení iných úloh pomocou dynamického programovania ukáže, že namiesto kompletnej dvojrozmernej tabuľky stačí zostavovať len jej posledný riadok (prípadne posledné dva). Podobne ako nám z jednorozmernej tabuľky pre fibonacciho čísla nakoniec stačili len dve posledné hodnoty.

Túto istú úlohu môžeme riešiť pomocou memoizácie (riešili sme to na 2. cvičení v (7) úlohe):

  • je to spôsob, ktorým si funkcia pamätá už raz vypočítané výsledky a keď ju voláme druhýkrát, tak už nič nepočíta, len zapamätanú hodnotu vráti ako svoj výsledok
  • vďaka tomu nemusíme funkciu prerábať na nerekurzívnu verziu s vytváraním tabuľky, ale tabuľka sa vytvára automaticky

Potom fib() vyzerá takto:

mem = {}               # globálna premenná

def fib(n):
    if n in mem:
        return mem[n]
    if n < 2:
        mem[i] = n
        return n
    res = fib(n-1) + fib(n-2)
    mem[n] = res
    return res

alebo s využitím inicializovaného mutable parametra:

def fib(n, mem={}):
    if n in mem:
        return mem[n]
    if n < 2:
        mem[i] = n
        return n
    res = fib(n-1) + fib(n-2)
    mem[n] = res
    return res

Vidíme, že toto riešenie je zhora nadol, ale tiež sa v ňom vytvára tabuľka s riešeniami všetkých podúloh. Hovoríme, že memoizácia je špeciálnym prípadom dynamického programovania. Využije sa hlavne pri jednoduchších úlohách, ktoré vieme zapísať rekurzívne. V Pythone existuje machanizmus, pomocou ktorého sa dá memoizácia zapísať veľmi elegantne (tzv. dekorátory), napr.

import functools

@functools.lru_cache(maxsize=None)          # dekorátor
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)
>>> print(*(fib(n) for n in range(16)))
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

Kombinačné čísla

Kombinačné čísla vieme vypočítať aj pomocou rekurzívneho vzťahu:

komb(n, k) = komb(n-1, k) + komb(n-1, k-1)

Tento vzťah sa dá jednoducho zapísať pomocou rekurzie (pre triviálne prípady k=0 a n=k), pričom zložitosť takejto funkcie je O(2**n):

def komb(n, k):
    if k == 0 or n == k:
        return 1
    return komb(n - 1, k) + komb(n - 1, k - 1)

Zo strednej školy poznáme Pascalov trojuholník, ktorý je poskladaný z hodnôt kombinačných čísel:

            1
          1   1
        1   2   1
      1   3   3   1
    1   4   6   4   1
  1   5  10  10   5   1
1   6  15  20  15   6   1

čo sú:

                        komb(0,0)
                   komb(1,0) komb(1,1)
              komb(2,0) komb(2,1) komb(2,2)
         komb(3,0) komb(3,1) komb(3,2) komb(3,3)
    komb(4,0) komb(4,1) komb(4,2) komb(4,3) komb(4,4)
...

Každé číslo (okrem krajných 1) sa dá vypočítať ako súčet dvoch čísel nad ním (vľavo a vpravo). Takže, ak by sme namiesto rekurzie zostavovali tieto hodnoty do dvojrozmernej tabuľky, použili by sme dynamické programovanie: postupným zapĺňaním tabuľky riešime jednoduchšie podúlohy, pričom využívame riešenia ešte jednoduchších podúloh.

Samozrejme, že aj táto úloha sa dá riešiť memoizáciou: aj v tomto prípade je to dynamické programovanie, ale tabuľku za nás postupne zapĺňa Python pri rekurzívnych volaniach.

Mincovka

Známa úloha o rozmieňaní nejakej sumy na čo najmenší počet mincí. Zrejme musíme poznať, aké druhy mincí máme k dispozícii, napr. ak máme mince [1, 2, 5, 10], tak sumu 6 vieme rozmeniť napr. ako 2+2+2 alebo 1+5 ale aj 1+1+1+1+1+1. V tomto prípade je 1+5 hľadaným riešením, lebo na rozmenenie sme použili najmenší počet mincí (zrejme menej ako dvomi mincami sa to nedá).

Postupne ju vyriešime niekoľkými spôsobmi

Pomocou Greedy metódy

Greedy t.j. pažravý algoritmus označuje:

  • na rozmieňanie sa snažíme použiť čo najväčšiu mincu, ktorou sa to ešte dá
  • túto mincu si zapamätáme, odčítame ju od rozmieňanej sumy a celé to opakujeme, kým je rozmieňaná suma väčšia ako 0
def mincovka1(mince, suma):
    zoznam = []
    mince = sorted(mince)
    while suma > 0:
        i = len(mince)-1
        while i >= 0 and mince[i] > suma:
            i -= 1
        if i < 0:
            return None
        suma -= mince[i]
        zoznam.append(mince[i])
    return zoznam[::-1]

otestujeme:

for suma in range(1, 21):
    print(suma, sorted(mincovka1([1, 2, 5, 10], suma)))

Predchádzajúci algoritmus funguje dobre len pre niektoré sady mincí, napr. pre mince [1, 3, 7, 10] by sumu 14 rozmenil ako 1+3+10 pričom správnym riešením by malo byť 7+7 (teda iba 2 mince). Zrejme je tento algoritmus veľmi rýchly, ale nie vždy funguje optimálne: niekedy nájde nie najlepšie riešenie.

Hrubá sila

Vyriešme túto úlohu hrubou silou, teda pomocou backtrackingu:

def mincovka2(mince, suma):
    if suma in mince:
        return [suma]
    naj = None
    for minca in mince:
        if minca < suma:
            ries = mincovka2(mince, suma-minca) + [minca]
            if naj is None or len(ries) < len(naj):
                naj = ries
    return naj
>>> mincovka2([1, 3, 7, 10], 14)
[7, 7]

Zloťitosť tohto algoritmu je O(2**n)

Memoizácia

Predchádzajúci rekurzívny algoritmus je pre väčšie hodnoty veľmi pomalý (podobne ako rekurzívna fibonacciho funkcia). Môžeme ho výrazne urýchliť pomocou memoizácie:

  • zadefinujeme globálnu premennú mem ako prázdne asociatívne pole a rekurzívna funkcia mincovka3() najprv v tomto poli zistí, či už túto hodnotu nemá vypočítanú a ak áno vráti ju ako výsledok
def mincovka3(mince, suma, mem={}):
    if suma in mem:
        return mem[suma]             # už sme to počítali predtým
    if suma in mince:
        mem[suma] = [suma]
        return [suma]
    naj = None
    for minca in mince:
        if minca < suma:
            ries = mincovka3(mince, suma-minca) + [minca]
            if naj is None or len(ries) < len(naj):
                naj = ries
    mem[suma] = naj
    return naj

Zložitosť tohlo algoritmu je O(mn), ked m je počet mincí a n je samotná rozmieňaná suma.

Vyskúšajte zavolať obe tieto funkcie aj pre väčšie hodnoty, napr.

>>> mincovka2([1, 3, 7, 10, 20], 45)
?
>>> mincovka3([1, 3, 7, 10, 20], 45)
?

Preskúmajme obsah poľa mem po jednom zavolaní mincovka3:

>>> mincovka3([1, 3, 7, 10], 14)
[7, 7]
>>> mincovka3.__defaults__[0]
{10: [10], 7: [7], 3: [3], 1: [1], 4: [3, 1], 2: [1, 1], 5: [3, 1, 1],
 8: [7, 1], 11: [10, 1], 6: [3, 3], 9: [7, 1, 1], 12: [10, 1, 1],
 13: [10, 3], 14: [7, 7]}
>>> sorted(mincovka3.__defaults__[0])
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

Dynamické programovanie

Obsah pomocného poľa mem, ktoré sa využilo pre memoizáciu môže byť inšpiráciou pre riešenie pomocou ozajstného dynamického programovania:

  • funkcia mincovka4() najprv zostaví tabuľku podobnú mem, ale urobí to bez rekurzie metódou zdola nahor: postupne ju bude zapĺňať zľava doprava, t.j. z hodnôt na menších indexoch vypočíta hodnoty na vyšších
  • prvkami tabuľky budú minimálne počty rozmieňania na mince pre dané sumy, t.j. tab[suma] bude minimálny počet mincí, na ktoré sa dá daná suma rozmeniť
  • bude sa pri tom používať podobný cyklus ako v mincovka2(), ktorý hľadal minimálny počet mincí rozmieňaní, ale namiesto rekurzie tu bude vytiahnutie hodnoty z tabuľky tab
def mincovka4(mince, suma):
    tab = [0] * (suma+1)
    for s in range(1, suma+1):
        ...
    return tab[suma]

Odhadnime časovú zložitosť algoritmu:

Teraz dopíšeme do funkcie mincovka4() záverečnú časť, ktorá na základe tabuľky tab zrekonštruuje zoznam použitých mincí a funkcia potom namiesto počtu mincí vráti zoznam (pole) použitých mincí. Vypíšme túto tabuľku napr. pre mincovka4([1,3,7,10,20], 19):

[0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 1, 2, 3, 2, 2, 3, 3, 2, 3, 4]

V tejto tabuľke posledná 4 označuje, že suma 19 sa dá rozmeniť 4 mincami, preto musí v tejto tabuľke existovať nižšia suma, ktorá sa dá rozmeniť 3 mincami a od 19 sa líši presne o niektorú z mincí (t.j. treba skontrolovať 19-1, 19-3, 19-7, … a ktorá z týchto súm sa dá rozmeniť 3 mincami, tak tú vyberieme), nech je to napr. minca 7. Zaradíme mincu 7 do zoznamu pre výsledok a pokračujeme v hľadaní ďalšej mince: v tabuľke tab[19-7] má hodnotu 3, preto hľadáme takú mincu, že tab[12-minca]==2, ak je tabuľka skonštruovaná korektne, taká minca bude aspoň jedna. Takto pokračujeme, kým neposkladáme kompletný zoznam mincí

Výsledný program:

def mincovka4(mince, suma):
    tab = [0] + [None] * suma
    for s in range(1, suma+1):
        for m in mince:
            if s >= m and tab[s-m] is not None:
                if tab[s] is None or tab[s] > tab[s-m]+1:
                    tab[s] = tab[s-m]+1
    #print(tab)
    return tab[suma]

napr.

>>> mincovka4([3, 5], 7)
[0, None, None, 1, None, 1, 2, None]

Najdlhšie podpostupnosti

Ďalšou skupinou úloh sú problémy, v ktorých sa v jednorozmernom poli čísel (alebo pre dve jednorozmerné polia, nemusia byť číselné) hľadá:

  1. najdlhšiu súvislú rastúcu podpostupnosť (sekvencia)
    • napr. pre 3, 7, 2, 9, 4, 1, 5, 6, 10, 8, 0 dostaneme 1, 5, 6, 10
  2. najdlhšiu vybranú rastúcu podpostupnosť
    • napr. pre 3, 7, 2, 9, 4, 1, 5, 6, 10, 8, 0 dostaneme, napr. 2, 4, 5, 6, 8 alebo 3, 4, 5, 6, 10
  3. najdlhšiu súvislú spoločnú podpostupnosť dvoch postupností
  4. najdlhšiu vybranú spoločnú podpostupnosť dvoch postupností

Algoritmy všetkých štyroch úloh sú navzájom veľmi podobné a samozrejme, že sa riešia pomocou dynamického programovania. My si ukážeme riešenie 2. úlohy.

Najdlhšia vybraná rastúca podpostupnosť

Rieši sa pomocou dynamického programovania napr. takto:

  • postupne sa zostavuje tabuľka tab, v ktorej i-ty prvok obsahuje dĺžku najdlhšej vybranej rastúcej podpostupnosti, ktorá končí i-tym prvkom, zrejme túto hodnotu budeme počítať len z prvých i-1 prvkov, t.j.
    • tab[0] je zrejme 1, lebo ak berieme prvky poľa len po 0, tak tento je 1-prvkovou postupnosťou
    • tab[1] má byť dĺžkou najdlhšej rastúcej podpostupnosti, ak berieme do úvahy len 0. a 1. prvok poľa a pritom vybraná podpostupnosť končí 1. prvkom: bude tu 1 alebo 2
    • tab[2] je opäť dĺžkou najdlhšej, ak berieme len prvé 3 prvky, pričom nás zaujímajú len podpostupnosti, ktoré končia 3. prvkom: tretí prvok môže nadväzovať buď na postupnosť končiacu v prvom alebo končiacu v druhom prvku (závisí to od toho, či je tretí prvok väčší ako prvý alebo druhý a ktorá z týchto podpostupností je dlhšia)
    • takto postupne vybudujeme celú tabuľku tab
  • dynamicky toto pole tab budete vytvárať budete pre vstupnú postupnosť post takto:
    • pre tab[i] nájdeme najväčšiu hodnotu medzi tab[0:i-1] (na indexe j), pre ktorú je post[j] < post[i] - do tab[i] zapíšeme túto najväčšiu hodnotu zvýšenú o 1
    • ak medzi tab[0:i-1] nie je žiadna, pre ktorú by platilo post[j] < post[i], do tab[i] zapíšeme 1 (zrejme post[i] nie je väčšie ako žiadne z post[0:i-1])
  • z takto zostavenej tabuľky tab vieme zistiť hľadanú dĺžku podpostupnosti (je to maximálna hodnota v tabuľke) a tiež vieme zrekonštruovať hľadanú podpostupnosť:
    • v tab pôjdeme od konca a postupne hľadáme prvý výskyt pozícií s jednotlivými dĺžkami (najprv max, potom max-1, max-2, …, 2, 1)

Riešenie:

def hladaj(post):
    tab = [0] * len(post)
    for i in range(len(post)):
        max = 0
        for j in range(i):
            if post[j] < post[i]:
                if tab[j] > max:
                    max = tab[j]
        tab[i] = max + 1
    print('tabulka:', *tab)
    max_i = 0
    for i in range(len(tab)):
        if tab[i] > tab[max_i]:
            max_i = i
    dlzka = tab[max_i]
    print('naj dlzka =', dlzka)
    vysl = [post[max_i]]
    i = max_i
    for d in reversed(range(1, dlzka)):
        for j in range(i):
            if tab[j] == d and post[j] < post[i]:
                break
        vysl.insert(0, post[j])
        i = j
    print('hladana podpostupnost:', *vysl)
    return vysl
>>> pole = [3, 7, 2, 9, 4, 1, 5, 6, 10, 8, 0]
>>> hladaj(pole)
tabulka: 1 2 1 3 2 1 3 4 5 5 1
naj dlzka = 5
hladana podpostupnost: 3 4 5 6 10
[3, 4, 5, 6, 10]

Cvičenie

L.I.S.T.

kombinačné čísla

  1. Zapíšte a otestujte rekurzívne riešenie komb(n, k) = komb(n-1, k) + komb(n-1, k-1)
    • zistite počet rekurzívnych volaní pre n in (20,21,22,…30): komb(n, k=15)

  1. Zapíšte nerekurzívnu verziu komb1(n, k), ktorá najprv skonštruuje dvojrozmernú tabuľku pre n riadkov a k stĺpcov a na základe nej vráti výsledok

    • funkcia:

      def komb1(n, k):
          # ... vytvorte dvojrozmernú tabuľku veľkosti n x k, kde tab[i][j] = hodnota komb(i, j)
          # ... tabuľku vytvorte metódou zdola nahor, t.j. najprv pre malé i a j
          return tab[n][k]
      
  2. Riešte ako v (2) ale namiesto dvojrozmernej tabuľky pracujte len s jedným riadkom (z i-teho vyrobte (i+1)-ty riadok)

    • funkcia:

      def komb2(n, k):
          ...
      
    • otestujte správnosť, napr.

      for n in range(10):
          for k in range(0, n+1):
              if not komb(n, k) == komb1(n, k) == komb2(n, k):
                  print(n, k, komb(n, k), komb1(n, k), komb2(n, k))
      
  3. Riešte memoizáciou, t.j. do rekurzívneho riešenia pridajte pamätanie si vypočítaných hodnôt a ich neskoršie použitie

    • funkcia:

      def komb3(n, k, mem={}):
          ...
      
    • otestujte

funkcia P

  1. Funkcia P(i, j) pre nezáporné i a j je zadaná takto:

    • ak j=0, výsledkom je 0
    • ak i=0, výsledkom je 1
    • inak výsledkom je (P(i-1, j) + P(i, j-1))/2

    Ručne vytvorte tabuľku veľkosti 4x4 pre hodnoty z range(4)

  1. Zapíšte rekurzívnu funkciu
    • skontrolujte správnosť vašej ručnej tabuľky z (5)
    • zistite počet rekurzívnych volaní pre i in (10,11,12,…20) a j=10
    • odhadnite zložitosť

  1. Vyriešte memoizáciou

  1. Vyriešte vytvorením dvojrozmernej tabuľky veľkosti i x j, ktorú vyplníte po riadkoch bez rekurzie
    • skontrolujte správnosť vašej ručnej tabuľky z (5)
    • odhadnite zložitosť tejto verzie

najdlhšia vybraná podpostupnosť

  1. Na základe algoritmu z prednášky pre „najdlhšia vybraná rastúca podpostupnosť“ najprv

    • ručne bez počítača vytvorte tabuľku dĺžok pre danú postupnosť:

      post = [5, 4, 2, 4, 1, 1, 3, 4, 3, 4, 4, 1, 1, 2, 3, 3, 5, 4, 2, 2]
      
    • z tejto tabuľky dĺžok zrekonštruujte hľadanú vybranú podpostupnosť (úloha môže mať viac riešení)

    • tabuľku aj výsledok skontrolujte spustením programu z prednášky

  1. Upravte funkciu hladaj() z prednášky tak, aby hľadal najdlhšiu vybranú neklesajúcu podpostupnosť (z predchádzajucej postupnosti post vie takto vybrať podpostupnosť dĺžky 8)

    • teraz pre postupnosť:

      >>> post = [5, 4, 2, 4, 1, 1, 3, 4, 3, 4, 4, 1, 1, 2, 3, 3, 5, 4, 2, 2]
      >>> len(hladaj_neklesajucu(post))
      8
      
  2. Algoritmus z prednášky najprv vytvára tabuľku maximálnych dĺžok podpostupností, potom v tejto tabuľke nájde maximálny prvok a na koniec z nej zrekonštruuje hľadanú podpostupnosť. Úloha by sa dala vyriešiť aj trochu inak:

    • tabuľka sa vytvára rovnakým postupom, ale zapisujú sa do nej nie dĺžky ale nájdené maximálne podpostupnosti
    • z tejto tabuľky potom stačí vyhľadať ľubovoľnú podpostupnosť maximálnej dĺžky
    • naprogramujte túto ideu a skontrolujte s výsledkami úloh v (9) a (10) - mali by ste dostať rovnaké výsledky
    • odhadnite pamäťovú zložitosť oboch algoritmov (zaujíma nás použitá pamäť v najhoršom prípade)
      • z porovnania pamäťovej zložitosti týchto dvoch algoritmov by mohlo byť jasné, prečo sa použil variant z prednášky

najdlhšia súvislá rastúca podpostupnosť

  1. Riešenie tejto úlohy sa veľmi podobá predchádzajúcemu algoritmu z prednášky pre vybranú podpostupnosť:

    • najprv sa vytvorí tabuľka maximálnych dĺžok súvislých podpostupností, ktoré končia na danom indexe:

      • ak je post[i-1] < post[i], potom tab[i] = tab[i-1] + 1, inak tab[i] = 1
    • potom sa v tejto tabuľke nájde maximálny prvok - to je dĺžka maximálnej podpostupnosti a index vyjadruje index posledného prvku z tejto podpostupnosti

    • spätne sa vytvorí hľadaná súvislá podpostupnosť

    • ručne vytvorte tabuľku pre

      pole = [3, 7, 2, 9, 4, 1, 5, 6, 10, 8, 0]
      
    • zapíšte algoritmus a skontrolujte vytvorenú tabuľku

  1. Úloha sa dá riešiť aj bez použitia tabuľky: stačí si pamätať doteraz najlepšiu dĺžku a index, kde končí táto podpostupnosť
    • zapíšte algoritmus bez použitia tabuľky (pamäťová zložitosť bude teraz O(1))
    • skontrolujte výsledky porovnaním s algoritmom, ktorý pracuje s tabuľkou
© Copyright 2017, Andrej Blaho.
Naposledy aktualizované 04. sep. 2018.
Vytvorené pomocou Sphinx 1.7.8.

Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License.