A „dinamikus programozás” paradigmája

A lényeget a következő dokumentum 1. fejezete tartalmazza.

A dinamikus programozás (DP) rövid lényegét emígyen határozzák meg Rónyai és társai a [Rónyai L.,Ivanyos G.,Szabó R.: „Algoritmusok”, TYPOTEX, 1999] irodalomban: „A dinamikus programozás módszerek gyakran használatos valamilyen numerikus paramétertől függő érték optimumának meghatározására. Lényege, hogy az optimumot (optimális megoldást) alkalmas kisebb részfeladatok optimumából (optimális megoldásából) próbáljuk előállítani. A dinamikus programozást használó algoritmusok vezérlési szerkezete gyakran emlékeztet egy táblázat szisztematikus (pl. sorról sorra haladó) kiszámítására. A táblázat kitöltését általában egy rekurzív összefüggés teszi lehetővé, ami alapján a bejárási sorrend szerint korábbi elemekből meghatározhatók a többiek. A kapott módszer költségét többnyire a kitöltendő táblázat mérete határozza meg. …”

Mit kell tehát tennünk egy feladat dinamikus megoldásának tervezésekor?

1. A megoldás szerkezetének tanulmányozása – részproblémákra bontás megsejtése
2. Részproblémákra és összetevőkre bontás – részproblémák és paramétereik körvonalazása: a rekurzió előkészítése
   1. Az összetevőkre bontás körmentes legyen!
   2. Minden részprobléma megoldása kifejezhető legyen rekurzívan az összetevők megoldásaival!
3. Részproblémák megoldásának kifejezése rekurzívan az összetevők megoldásaiból – formalizálás: függvénydefiníció
4. Részproblémák megoldásának kiszámítása – a táblaszámítás algoritmizálása
   1. Kiszámítási sorrend meghatározása: minden részprobléma minden összetevője előbb szerepeljen a felsorolásban!
   2. „Alulról-felfelé” (helyesebben: a már kiszámoltak felől a még definiálatlanok felé) haladó legyen számítás!
5. A megoldás előállítása az előbbi lépésben előállított táblázat segítségével – a megoldás algoritmizálása, kódolása.

A feladat szövege

Adott N tárgy (értékük F_i, súlyuk S_i). Egy hátizsákba maximum H súlyú tárgyat pakolhatunk. Mennyi a maximális elszállítható érték?
(L. az előadásanyag 19-20. diáin!)

A megoldás

A megoldás szerkezetének tanulmányozása

Tegyük fel, hogy H≥S_i1+S_i2+…+S_im (i₁<i₂<…<i_m) optimális megoldás, azaz F_i1+F_i2+…+F_im maximális!
Ekkor H-S_im≥S_i1+S_i2+…+S_im-1 (i₁<i₂<…<i_m) is optimális, azaz az adott részproblémának megoldása a megoldás megfelelő részlete.

Részproblémákra bontás

A feladatot jól jellemezhetjük két paraméterrel: az X kapacitással (a zsákba még beleférő súllyal), és a legnagyobb i indexszel, amely a tárgyhalmaz még felhasználható elemeinek részhalmazát meghatározza: (X,i).

Részproblémákra úgy kell bontsuk, hogy az „összetevő” részproblémák paraméterei közül legalább egy változzék. Ha a változás mindig csökkenést (vagy valami maximumfelé haladást) jelent, akkor a körmentessége garantált. Jelen esetben a maximális H súlytól indulva, azt csökkentve, illetve a tárgyak N számának csökkentésével származtatjuk a részproblémákat.

Rekurzív összefüggések a részproblémák és megoldásaik között

Jelöljük E(X,i)-vel a legnagyobb elszállítható értéket, amely az első i tárgyból egy X kapacítású zsákba bepakolható!
Ekkor az E(X,i) így definiálandó:

  E:Súly×Index→Érték,   Súly,Index,Érték=N
  
  E(X,i):=F1                          , ha i=1 ∧ S1≤X    (1)
  E(X,i):=0                           , ha i=1 ∧ S1>X    (2)
  E(X,i):=E(X,i-1)                    , ha i>1 ∧ Si>X    (3)
  E(X,i):=max(E(X,i-1),Fi+E(X-Si,i-1) , egyébként        (4)

A feladat megoldását az E(H,N) jelenti.

Rekurzív megoldás algoritmusa

Ez legyen házi feladat, gyakorlásként, és hogy lássuk mennyi rekurzív hívást kíván!
Ha kíváncsi az én megoldásomra: töltse le! … és két bemeneti fájl: 4.be, 20.be hozzá.

Dinamikus programozásos logikájú megoldás algoritmusa₁

A rekurziót kell feloldani: egy táblázat megfelelő sorrendű kiszámításával. A táblázatról:

1. A táblázat most 2-indexes, azaz mátrix, mivel a rekurzív E függvény 2-paraméteres.
2. A táblázat 1. indexe (a sorindex) fut a „kapacitásokon” (0..H), a 2. indexe (az oszlopindexe) a tárgysorszámokon (1..N).
3. Az E függvény rekurzív definícióját megnézve, látjuk, hogy mindkét paraméter kisebb vagy egyenlő paraméterértékekre hivatkozik a rekurzív ágakon.
   A (3) ág definíciója miatt az előző oszlopra (előző tárgy választásának esetére utalva), a (4) ág definíciója miatt pedig az előző oszlop valamely előző vagy azonos sorbeli értékére (mivel a súly>0).
   Ennek fontos következménye, hogy az E függvénynek megfeleltetett mátrix feltöltése felülről→lefelé / balról→jobbra irányú kell legyen!

[Programparaméterek – ábrázolás --------------------------------------------------------]

Konstans
  MaxN:Egész(???) [a tárgyak maximális száma]
  MaxH:Egész(???) [a zsák kapacitásának maximális értéke]
Típus [a feladatbeli S és F tömbök „egyesített” megfelelőjénet típusa:]
  TTárgy=Rekord(súly,érték:Egész)
  TTárgyak=Tömb(1..MaxN:TTárgy)
  TTab=Tömb(0..MaxH,1..MaxN:Egész) [a dinamikus programozás táblázata]
Változó
  Tárgyak:TTárgyak [a feladatbeli S, F tömbök megfelelője; globálisan elérhető]
  …
  
[A lényegi függvény – implementálás ----------------------------------------------------]

Függvény MaxÉrték(Konstans h,n:Egész):Egész
  Változó
    i,x:Egész
    E:TTab
  [Az 1. oszlop kiszámolása --------------------------------------------]
  E(0..Tárgyak(1).súly-1,1):=0                            [⇐(2)]
  E(Tárgyak(1).súly..h,1):=Tárgyak(1).érték               [⇐(1)]
  [Az i=2..n. oszlop kiszámolása ---------------------------------------]
  Ciklus i=2-től n-ig
    Ciklus x=0-tól h-ig
      E(x,i):=E(x,i-1)                                    [⇐(3)]
      Ha Tárgyak(i).súly≤x és E(x,i)<Tárgyak(i).érték+E(x-Tárgyak(i).súly,i-1) akkor
        E(x,i):=Tárgyak(i).érték+E(x-Tárgyak(i).súly,i-1) [⇐(4)]
      Elágazás vége
    Ciklus vége
  Ciklus vége
  [♥]
  MaxÉrték:=E[h,n]
Eljárás vége.

Figyelje meg az alábbi példamátrixot!

A 4.be bemeneti fájl mellett kitöltött E mátrix.


… és készülés közben: a fenti algoritmus [♥] jelölt pontján kiírva az E állapotát.

A megoldás, azaz a programparaméterek és a főprogram:

…
Változó
  [Bemenet:]
  N,H:Egész
  Tárgyak:TTárgyak [a definícióbeli S, F tömbök megfelelője; globálisan elérhető]
  [Kimenet:]
  Érték:Egész

  … [adat-beolvasás]	
  Érték:=MaxÉrték(H,N)
  … [eredmény-kiírás]

Ha kíváncsi az én megoldásomra: töltse le! … és két bemeneti fájl: 4.be, 20.be hozzá.

Kérdés: mi van akkor, ha a súly (és az érték) nem egész, hanem valós szám?

1. A megfelelő típusok átírása után változatlanul helyesen működik-e a rekurzív program?
   A válasz…
   Gond nélkül!
2. A dinamikus programozású logikájú program alapja egy táblázat, a konkrét feladat esetében: egy mátrix léte.
   Probléma: a konkrét feladatban a súly lehetséges értékei (0..H) a mátrix sor-indexei. Ez valós nem lehet! Hogy lehet e problémát feloldani?
   A válasz…
   Legyenek az eddig egész értékű paraméterek Q/R alakú (Q,R∈N) racionális számok: S_i:=Q_i/R_i (i=1..N), H:=Q/R!
   
   1. Válasszunk egy alkalmas új egységet: ε∈R, ε>0!
   2. Minden fenti paramétert helyettesítsünk az ε egység egész számszorosával:
      S_i → s_i∈N (i=1..N), H → h∈N, mégpedig így:
      S_i = s_i*ε (i=1..N), H = h*ε!
   3. Az ε választása: ε:=1/LKKT(R₁…R_N,R), ahol LKKT a legkisebb közös többszörös függvénye.
   4. Tehát
      S_i = Q_i/R_i = s_i*ε ⇒ s_i = Q_i/R_i*1/ε = S_i*1/ε és
      H = Q/R = H*ε ⇒ h = Q/R*1/ε = H*1/ε.
      Az s_i, h értékeivel már indexelhető a mátrix.

A feladat szövege

Adott N tárgy (értékük F_i, súlyuk S_i). Egy hátizsákba maximum H súlyú tárgyat pakolhatunk. Mennyi a maximális elszállítható érték, mely tárgyakat pakoljuk a zsákba?
(L. az előadásanyag 19-22. diáin!)

A megoldás₁

A megoldás szerkezetének tanulmányozása₁

L. előző megoldásnál!

Részproblémákra bontás₁

L. előző megoldásnál!

Rekurzív összefüggések a részproblémák és megoldásaik között₁

Ennél a megoldásnál követjük az előbbi, alapfeladat megoldásánál alkalmazott gondolatmenetet. Erre fogunk építkezni.
L. előző megoldásnál!

Dinamikus programozásos logikájú megoldás algoritmusa₁

A feladat megoldását részben (ti. a maximális értéket) az E(H,N) mátrix tartalmazza.
L. előző megoldásnál!

Emellett azonban össze kell szedni a megoldásban szereplő tárgyakat is. Ez elvégezhető az E mátrix segítségével: az E(H,N)-ből kiindulva visszafelé lépdelve, és követve a választott tárgy súlyát, a még rendelkezésre álló kapacítást, és az össz értéket.

Figyelje meg az alábbi példamátrixot!

A 4.be bemeneti fájl mellett kitöltött E mátrix.
A bepakolandó tárgyak felderítésének módja, animációval bemutatva.

[Programparaméterek – ábrázolás --------------------------------------------------------]

Konstans
  MaxN:Egész(???) [a tárgyak maximális száma]
  MaxH:Egész(???) [a zsák kapacitásának maximális értéke]
Típus
  TTárgy=Rekord(súly,érték:Egész)
  TTárgyak=Tömb(1..MaxN:TTárgy)
  TTab=Tömb(1..MaxH,1..MaxN:Egész) [a dinamikus programozás táblázata]
  TSorszámok=Tömb(1..MaxN:Egész)
  
[A lényegi függvény – implementálás ----------------------------------------------------]

Eljárás Hátizsák(Konstans h,n:Egész, 
                 Változó db:Egész, zstk:TSorszámok, érték:Egész):
  Változó
    i,x:Egész
    E:TTab
  [Az 1. oszlop kiszámolása --------------------------------------------]
  E(0..Tárgyak(1).súly-1,1):=0; E(Tárgyak(1).súly..h,1):=Tárgyak(1).érték
  [Az i=2..n. oszlop kiszámolása ---------------------------------------]
  Ciklus i=2-től n-ig
    Ciklus x=0-tól h-ig
      E(X,i):=E(x,i-1)
      Ha Tárgyak(i).súly≤x és E(x,i)<Tárgyak(i).érték+E(x-Tárgyak(i).súly,i-1) akkor
        E(x,i):=Tárgyak(i).érték+E(x-Tárgyak(i).súly,i-1)
      Elágazás vége
    Ciklus vége
  Ciklus vége
  Összegyűjt(h,n,E,db,zstk,érték)
Eljárás vége.

… és a plusz eredményparamétereket összeszedő eljárás:

Eljárás Összegűjt(Konstans h,n:Egész, E:TTab,
                  Változó db:Egész, zstk:TSorszámok, érték:Egész):
  Változó
    x,i:Egész
  i:=n; x:=h; db:=0; érték:=0
  Ciklus i>0 [≡van még tárgy] és E(x,i)>0 [≡van még hely]
    Ciklus amíg i>1 és E(x,i)=E(x,i-1) [≡az i. nincs felhasználva]
      i:-1
    Ciklus vége
    db:+1; zstk(db):=i [az i. a következő felhasznált]
    x:=x-Tárgyak(i).súly [már csak x súly fér a zsákba]
    érték:+Tárgyak(i).érték [az eddigi összérték]
    i:-1
  Ciklus vége
Eljárás vége.

Ha kíváncsi az én megoldásomra: töltse le! … és két bemeneti fájl: 4.be, 20.be hozzá.

A feladat szövege

Egy szóba minimálisan hány karaktert kell beszúrni, hogy tükörszó legyen belőle (azaz ugyanaz legyen balról jobbra és jobbról balra olvasva is)! Egy szót tükörszónak nevezünk, ha balról és jobbról kiolvasva betűről betűre megegyezik. (Tehát minden egybetűs szó tükörszó.) Minden szó felbontható részekre úgy, hogy minden rész tükörszó legyen. Minimálisnak nevezzük az olyan felbontást, amely egy szót a lehető legkevesebb tükörszóra szed szét. Írjon programot a minimális tükörszó partíciók számának meghatározására.

Példa:

A megoldás

Ha kíváncsi az én megoldásomra: töltse le!

1. Mohó Marci malacperselyben gyűjti a pénzét. Csak fémpénzeket rakott a perselybe, de nem jegyezte föl, hogy milyeneket. Felírta azonban az üres persely súlyát, így meg tudja állapítani a perselyben levő pénzek összsúlyát. Ismeri továbbá az egyes pénzérmék egyedi súlyát és értékét. Szeretné kiszámítani, hogy mennyi az a legkisebb összeg, amelyet a perselye biztosan tartalmaz. Egy adott típusú pénzérméből –természetesen– több is lehet a perselyben. Adjuk meg a címletezést is!
2. Egy N×M-es téglalap alakú területen egy járművel szedhetjük össze az elrejtett kincseket. A terep keletre és észak felé lejt, azaz a jármű csak kelet, ill. észak felé haladhat. Bizonyos helyeken akadályok vannak, ahova nem léphet! Adja meg, hogy maximum hány kincset gyűjthet be!