Laboratórium 11 Dynamické programovanie dátových štruktúr a algoritmov (séria 1AB)
Používateľské nástroje
Nástroje webu
Bočný panel
obsah
1 Laboratórne ciele
2 Dynamické programovanie
2.1 Prehľad
Dynamické programovanie spočíva v riešení problému jeho rozdelením na čiastkové problémy a ich riešení. Na rozdiel od divide et impera nie sú podprogramy disjunktné, ale prekrývajú sa.
Aby sa zabránilo prepočtu prekrývajúcich sa častí, robí sa riešenie od najmenších podprogramov a pomocou nášho výsledku vypočítame bezprostredne väčší čiastkový problém. Najmenšie podproblémy sa nazývajú unitárne podproblémy, ktoré je možné vyriešiť v konštantnej zložitosti, napríklad najväčšia postupnosť v súbore jedného prvku.
2.2 Implementácia
2.3 Typické problémy vyriešené týmto algoritmom
2.3.1 Problém s batohom
Riešenie je konštruované dynamickým programovaním, D [i] [j] = najlepšia cena získaná pre prvé objekty i s maximálnou hmotnosťou j.
Vzťah rekurencie je nasledovný: D [i] [j] = maximum (D [i-1] [j], D [i-1] [jG [i]] + C [i]), kde G [i] = váha objektu i a C [i] = cena objektu.
Myšlienka je táto: K súčasnému riešeniu buď nepridávame vôbec objekt i, a zostaneme na cene pre objekty i-1, alebo pridáme objekt i, v takom prípade pripočítame jeho cenu k cene získanej pre prvé objekty i-1 a váhu j-G [i].
2.3.2 Určenie najdlhšieho stúpajúceho radu
Príklad: pre reťazec 24,12,15,8,19 je odpoveďou reťazec 12,15,19.
Začíname tým, že pre každý prvok určíme dĺžku najdlhšieho striktne vzostupného reťazca, ktorý začína prvým prvkom a končí týmto prvkom. Túto hodnotu nazveme najlepšia a rekurzívny vzorec použijeme najlepšie i = 1 + max (najlepšie j), s jn potom môžeme prepísať P (n) = ∏ (Cn, k X k), kde k = 0,1,2, ... n.
Nech koef (P, k) = koeficient X k v polynóme P. Potom môžeme napísať nasledujúce 2 vlastnosti:
Spojenie medzi koeficientmi polynómov typu P (n) môžeme odvodiť, ak napíšeme P (n + 1) = (X + 1) P (n) = X P (n) + P (n).
Ale coef (P (n), k) = C (n, k), takže sme dostali rekurenciu, ktorá používa iba jeden doplnok.
Cvičenia
3. Laboratórne cvičenia (Linux)
Pre toto laboratórium si môžete stiahnuť kostru kódu tu. Stiahnite si archív a rozbaľte ho.
Linux
Môžete použiť nástroj wget na stiahnutie a nástroj na rozbalenie na rozbalenie.