Cvičenie 7 – DP

Ciele cvičení:

  • rozumieť princípu techniky „dynamické programovanie“ na príklade niektorých úloh využívajúcich túto techniku
    • vedieť charakterizovať problém
    • vedieť skonštruovať riešenie problému z riešení „menších“ problémov
    • vedieť ako aplikovaním prístupu zdola-nahor (ako náhrada memoizácie) vypočítať požadované riešenie
    • vedieť nájsť a interpretovať riešenie

Krátka sumarizácia

„Objavenie“ dynamického programovania (od rozdeľuj a panuj, cez rekurzívnu implementáciu s memoizáciou, po dynamické programovanie):

  • nájdenie rekurzívneho vzorca, ktoré charakterizuje optimálne riešenie pomocou optimálnych riešení menších problémov (pre každú úlohu jedinečný problém)
  • priamy prepis rekurzívneho vzorca do rekurzívneho algoritmu vedie k neefektívnemu riešeniu
    • Nakreslite strom výpočtu pre Fibonacciho číslo Fib(5). Všimnite si, že strom výpočtu Fib(3) sa nachádza v strome aj ako podproblém pre Fib(5), aj ako podproblém pre Fib(4).
    • Riešenie: neopakovať výpočet rovnakej hodnoty. Pri každom výpočte si každý výsledok uložíme v poli výsledkov. Ak vznikne volanie metódy na výpočet, pozrieme sa najprv do poľa výsledkov, či už náhodou výsledok nemáme vypočítaný a uložený
  • namiesto ukladania medzivýsledkov sa rovno systematicky vypočíta pole s medzivýsledkami
  • Pri nerekurzívnom výpočte Fibonacciho čísla sa systematicky vyplní pole – vždy ako súčet 2 predchádzajúcich prvkov poľa

Nájdite riešenia nasledujúcich úloh využijúc techniku „dynamické programovanie“, riešenia implementujte.

Najdlhšia vybraná rastúca podpostupnosť

Daná je postupnosť N čísel: P[0], P[1], ..., P[N-1]. Nájdite takú podpostupnosť (nemusí byť súvislá), aby všetky hodnoty vybranej podpostupnosti tvorili rastúcu postupnosť hodnôt a vybraná postupnosť bola najdlhšia možná.

Môžete využiť „bonusové“ slajdy k 7. prednáške

Problém zaplatenia nákupu

V peňaženke máme celkom N platidiel (mincí resp. bankoviek) s hodnotami P[0], P[1], ..., P[N-1]. Predpokladajme, že hodnoty platidiel sú celé čísla (pre náročnejších: ako by sme riešili úlohu, keby sme pripustili aj halierové, resp. centové mince?). Cena nákupu je C (opäť celé číslo).

Otázka: vieme platidlami v peňaženke zaplatiť za nákup tak, aby nám nebol vrátený žiaden výdavok, t.j. vieme z platidiel v peňaženke presne vyskladať sumu C? V prípade kladnej odpovede vypíšte, aké platidlá treba použiť.

Aplikácia: Vedeli by ste podobným prístupom riešiť úlohu o spravodlivom rozdelení lupu medzi dvoch zlodejov?

Záhradkárska úloha

Záhrada, ktorá má tvar obdĺžnika, sa skladá z M x N políčok. Na každom políčku je jabloň s hojnou úrodou jabĺk. Nech na políčku [x, y] je úroda jablone U[x, y]. Vstup do záhrady je na políčku [0, 0] a výstup na políčku [M-1, N-1]. Aby návštevníci záhradu okamžite nevyplienili, rozhodol sa správca zaviesť nasledovné pravidlá pre pohyb návštevníkov:

  • Návštevník môže z políčka [x, y] prejsť len na políčko [x, y+1] a [x+1, y]. Zaujímavé pozorovanie, ktoré ale nesúvisí s riešením úlohy: vďaka týmto pravidlám každý návštevník prejde vždy tou najkratšou možnou cestou a tým strávi v záhrade minimálny možný čas (prechody po uhlopriečke neuvažujeme)
  • Návštevník si môže zobrať jablká z jabloní na tých políčkach, ktorými prejde počas svojej cesty záhradou

Nájdite takú cestu záhradou, pri ktorej vyzbierate maximálny možný počet jabĺk.

Nápoveda:

  • Najprv skúsme vypočítať, koľko najviac jabĺk vieme nazbierať.
  • Označme si výrazom Z[x, y] maximálny možný počet jabĺk, ktoré vieme vyzbierať pri ceste z políčka [0, 0] do políčka [x, y].
  • Zrejme maximálny počet jabĺk, ktoré vieme celkovo pri prechode záhradou nazbierať je rovný Z[M-1, N-1].
  • Dôležité pozorovanie: do políčka [x, y] vieme povolenými cestami prísť len z 2 možných susedných políčok

Najdlhšia spoločná podpostupnosť

Dané sú 2 reťazce. Nájdite najdlhšiu podpostupnosť, ktorá je vybranou podpostupnosťou oboch reťazcov.

Môžete využiť „bonusové“ slajdy k 7. prednáške

Problém batoha (pre pokročilých)

  • Navrhnite a implementujte algoritmus využivajúci dynamické programovanie pre problém batoha, ktorý bol odprednášaný na prednáške o backtracku.

Na trati Bratislava Košice a späť

Nie každý má vlaky zadarmo. Vtedy tu mame alternatívy, ktoré poskytuje moderná zdieľaná ekonomika ako „shareovane auta“. Ľudia, ktorí majú v aute miesto pre ďalšieho pasažiera a idú autom medzi dvojicou miest zadajú túto informáciu na stránku spolu s cenou. Takto vieme ušetriť napríklad na trase Košice – Bratislava. Ale ak túto trasu poskladáme z kratších trás tak možno ušetrime ešte viac.
Zoberme trasu Košice – Bratislava zapísanú ako postupnosť okresných miest: KE-PO-LE-PP-LM-ZA-TN-NM-PH-TT-BA.V okresných mestách máme cenové ponuky na prepravu medzi nimi:



1
2
3
4
5
6
7
8
9
10
11
12
13
14
KE-PO 0

KE-PP 3.0

KE-ZA 3.5

KE-TT 15

KE-BA 15

PO-PP 0

PO-PH 10

PP-ZA 5.5

LE-BA 10

ZA-TN 0

TN-TT 4

TN-BA 6

NM-TT 5

TT-BA 1

Za akú najnižšiu cenu sa vieme dopraviť do Bratislavy?

  • Navrhnite a implementujte algoritmus využívajúci dynamické programovanie, ktorý nájde cenu najlacnejšej cesty.
  • Upravte algoritmus nech vypíše túto cestu.
  • Upravte algoritmus aby ak má viacero ciest rovnakú cenu aby vybral tú, kde je menej prestupov.

Poznámky spracované Matejom Perejdom (verifikoval Marián Opiela):