Programozási módszertan Dinamikus programozás: Nyomtatási feladat A leghosszabb közös részsorozat ´ Werner Agnes ´ oki ¨ es ´ Informaci ´ os ´ Rendszerek Tanszek ´ Villamosmern
e-mail:
[email protected]
PM-04 – p. 1/18
´ jellemzoi ˝ Dinamikus programozas Egy dinamikus programozási algoritmus kifejlesztése 4 lépésre bontható fel: 1. Jellemezzük az optimális megoldás szerkezetét. 2. Rekurzív módon definiáljuk az optimális megoldás értékét. 3. Kiszámítjuk az optimális megoldás értékét alulról felfelé történo˝ módon. 4. A kiszámított információk alapján megszerkesztünk egy optimális megoldást.
PM-04 – p. 2/18
´ feladat Nyomtatasi Feladat az s1 , s2 , . . . , sn szavakból álló bekezdés kinyomtatása. ˝ állnak. A szavak rendre l1 , l2 , . . . , ln karakterekbol A nyomtató egy sorba összesen M karaktert tud elhelyezni. Tegyük fel, hogy li ≤ M ∀ 1 ≤ i ≤ n esetén. ˝ sj -ig terjedo˝ szavakat tartalmazza, akkor a Ha egy sor az si -tol szavak között mindig egy szóköz van, míg a sor végén további M −j+i−
j X
lm
m=i
extra szóköz (nem negatív!). Adjunk meg egy hatékony algoritmust, amely a "legszebben" nyomtatja ki a bekezdést, azaz minimalizálja az utolsó sor kivételével a sorok végén található extra szóközök számának köbeinek összegét!
PM-04 – p. 3/18
´ dinamikus programozassal ´ Megoldas ∀1 ≤ i ≤ j ≤ n esetén legyen e[i, j] = M − j + i −
j X
lm
m=i
˝ sj -ig terjedo˝ szavakat tartalmazó sor végén lévo˝ extra (az si -tol szóközök száma) ∀1 ≤ i ≤ j ≤ n esetén legyen ∞, ha e[i, j] < 0, k[i, j] = ´ e[i, j] ≥ 0, 0, ha j = n es ¨ e[i, j]3 , kul ¨ onben
PM-04 – p. 4/18
´ dinamikus programozassal ´ Megoldas Tekintsük az s1 , s2 , . . . , sj szavak egy optimális elrendezését. ˝ Tegyük fel, hogy ebben az utolsó sor az si szóval kezdodik. ˝ sorig terjedo˝ rész az Vegyük észre, hogy ekkor az utolsó elotti s1 , s2 , . . . , si−1 szavak egy optimális elrendezése. Ha nem így lenne, akkor ezt a részt lecserélve az s1 , s2 , . . . , si−1 szavak egy optimális elrendezésére az s1 , s2 , . . . , sj szavak egy "szebb" elrendezéséhez jutnánk, ami ellentmondás. Jelölje c[j] az s1 , s2 , . . . , sj szavak optimális elrendezésének soraihoz rendelt k értékek összegét.
c[j] =
(
0, ha j = 0, min{c[i − 1] + k[i, j] | 1 ≤ i ≤ j}, ha j > 0.
∀ 1 ≤ i ≤ j estén legyen p[j] annak az si szónak az indexe, ˝ amellyel az utolsó sor kezdodik az s1 , s2 , . . . , sj szavak optimális elrendezésénél. PM-04 – p. 5/18
Program 1. Nyomtatás(l,n,M) 2. for i = 1 to n do 3. e[i, i] = M − l[i] 4. for j = i + 1 to n do 5. e[i, j] = e[i, j − 1] − l[j] − 1 6. for i = 1 to n do 7. for j = i to n do 8. if e[i, j] < 0 9. then k[i, j] = ∞ 10. else 11. if j = n and e[i, j] ≥ 0 12. then k[i, j] = 0 13. else k[i, j] = e[i, j]3 14. c[0] = 0 15. for j = 1 to n do 16. c[j] = ∞ 17. for i = 1 to j do 18. if c[i − 1] + k[i, j] < c[j] then 19. c[j] = c[i − 1] + k[i, j]; p[j] = i 21. return c, p PM-04 – p. 6/18
¨ ´ Tordel es 1. 2. 3. 4. 5. 6. 7.
Tördelés(p,j) i = p[j] if i = 1 then h = 1 else h = T rdels(p, i − 1) + 1 print (h, i, j) return h
Az eljárás az optimálisan tördelt bekezdés sorainak számával tér vissza. A kinyomtatott (h, i, j) hármasok azt mutatják, hogy a h-adik sor ˝ sj -ig terjedo˝ szavakat tartalmazza (h = 1, 2, . . .). az si -tol A Nyomtatás eljárás költsége O(n2 ), a Tördelés eljárás költsége O(n).
PM-04 – p. 7/18
´ Bevezetes Biológiai alkalmazásokban gyakran össze kell hasonlítani pl. két ˝ vagy több élolény DNS-ét. A DNS-t bizonyos, bázisnak nevezett molekulák szekvenciái alkotják. A lehetséges bázisok: adenin, guanin, citozin és timin. ˝ ujükkel A bázisokat a kezdobet ˝ jelöljük. A DNS szerkezete leírható a véges [A, C, G, T] halmazon vett sztringgel. ˝ Pl. az egyik élolény DNS-e S1 = ACCGGT CGAGT GCGCGGAAGCCGGCCGAA ˝ a másik élolény DNS-e S2 = GT CGT T CGGAAT GCCGT T GCT CT GT AAA ˝ Két élolény DNS-ét pl. abból a célból hasonlíthatjuk össze, hogy megállapítsuk, hogy mennyire hasonlóak. (valamilyen mérték szerint a két lény mennyire közel áll egymáshoz) PM-04 – p. 8/18
¨ ´ Osszehasonl´ ıtas A hasonlóságot több féle képpen definiálhatjuk: • két DNS szekvencia hasonló, ha az egyik a másiknak
részsztringje, • két szekvencia hasonló, ha kevés változtatással vihetok ˝ át
egymásba, • keresünk egy olyan S3 szekvenciát, amelyik olyan
bázisokból áll, amelyek ugyanabban a sorrendben, de nem feltétlenül egymás után fordulnak elo˝ mind S1 -ben, mind S2 -ben; minél hosszabb, annál nagyobb a hasonlóság. A példában: a leghosszabb S3 szekvencia S1 = ACCGGT CGAGT GCGCGGAAGCCGGCCGAA S2 = GT CGT T CGGAAT GCCGT T GCT CT GT AAA S3 = GT CGT CGGAAGCCGGCCGAA
PM-04 – p. 9/18
´ ¨ osr ¨ eszsorozat ´ Reszsorozat, koz Egy sorozat részsorozata egy olyan sorozat, amit az adott sorozatból néhány elem elhagyásával nyerünk. Formálisan: Ha az adott X = (x1 , x2 , . . . , xm ), akkor egy másik sorozat Z = (z1 , z2 , . . . , zk ) sorozat akkor részsorozata X -nek, ha létezik X indexeinek egy szigorúan növo˝ (i1 , i2 , . . . , ik ) sorozata, hogy minden j = 1, 2, . . . , k esetén xij = zj . Adott két sorozat, X és Y . Azt mondjuk, hogy egy Z sorozat közös részsorozatuk, ha Z részsorozata X -nek is és Y -nak is.
PM-04 – p. 10/18
¨ os ¨ reszsorozat=LKR ´ A leghosszabb koz 1. lépés: A leghosszabb közös részsorozat jellemzése A feladat megoldásának egyik módszere leszámolni X összes ˝ részsorozatát és mindegyiket ellenorizni, hogy részsorozata-e Y -nak és tárolnunk kell a megtalált leghosszabb részsorozatot. X mindegyik részsorozata az 1, 2, . . . , m indexhalmaz egy részhalmazának felel meg. ˝ Mivel X -nek 2m részsorozata van, az eljárás exponenciális idot igényel. ⇓
Az algoritmus használhatatlan. Ez a probléma azonban rendelkezik az optimális részstruktúra tulajdonsággal.
PM-04 – p. 11/18
´ reszstrukt ´ ´ Az LKR optimalis ur ´ aja Az X = (x1 , x2 , . . . , xm ) sorozat i-edik prefixe Xi = (x1 , x2 , . . . , xi ) (i = 0, 1, . . . , m). Tétel: (Az LKR optimális részstruktúrája.) Legyen X = (x1 , x2 , . . . , xm ) és Y = (y1 , y2 , . . . , yn ) két sorozat és Z = (z1 , z2 , . . . , zk ) ezek egy LKR-je. Ekkor igazak a következo˝ állítások: 1. Ha xm = yn , akkor zk = xm = yn és Zk−1 az Xm−1 és Yn−1 egy LKR-je. 2. Ha xm 6= yn , akkor zk 6= xm esetén Z az Xm−1 és Y egy LKR-je. 3. Ha xm 6= yn , akkor zk 6= yn és Z az X és Yn−1 egy LKR-je.
PM-04 – p. 12/18
´ reszstrukt ´ ´ Az LKR optimalis ur ´ aja Bizonyítás: 1. Ha zk 6= xm , akkor az xm = yn elemet hozzátehetnénk Z-hez, és így X és Y egy k + 1 hosszú közös részsorozatát kapnánk, ez ellentmond Z választásának. Ezért zk = xm = yn . Most a Zk−1 prefix hossza k − 1 és közös részsorozata Xm−1 -nek és Yn−1 -nek. Meg kell mutatni, hogy ezek egy LKR-je is. Ha W egy legalább k hosszú közös részsorozata Xm−1 -nek és Yn−1 -nek, akkor ehhez hozzáfuzve ˝ az xm = yn elemet, X és Y k-nál hosszabb közös részsorozatát kapjuk, ami ellentmond Z választásának. 2. Ha zk 6= xm , akkor Z közös részsorozata Xm−1 -nek és Y -nak. Ha ezeknek volna egy W közös részsorozata, mely hosszabb, mint k, akkor ez közös részsorozata volna Xm -nek és Y -nak, ami ismét ellentmond Z választásának. 3. A bizonyítás hasonlóan történik, mint 2-nél.
PM-04 – p. 13/18
´ es: ´ reszfeladatok ´ ´ 2. lep rekurz´ıv megoldasa •
A tétel azt mondja, hogy csak egy vagy ketto˝ részfeladat van, amit meg kell vizsgálni X = (x1 , x2 , . . . , xm ) és Y = (y1 , y2 , . . . , yn ) LKR-jének megkeresésekor.
•
Ha xm = yn , akkor Xm−1 és Yn−1 LKR-jét kell megkeresni, amelyhez csatolva az xm = yn elemet kapjuk X és Y LKR-jét.
•
Ha xm 6= yn , akkor két részfeladatot kell megoldanunk: Xm−1 és Y , illetve X és Yn−1 LKR-jét kell megkeresni.
• •
Akármelyik is a hosszabb, az az X és Y LKR-je.
• •
˝ Látható, hogy az LKR problémában a részfeladatok átfedok.
•
Ezek közös részfeladata Xm−1 és Yn−1 LKR-jének meghatározása.
˝ Mivel ezek az esetek kimerítik az összes lehetoséget, tudjuk, hogy egy részfeladat megoldása benne van X és Y LKR-jében.
X és Y LKR-jének megkeresésekor szükségünk lehet X és Yn−1 , illetve Xm−1 és Y LKR-jének megkeresésére.
PM-04 – p. 14/18
¨ ´ Rekurz´ıv osszef ugg ¨ es Meghatározható egy rekurzív összefüggés: Legyen c[i, j] Xi és Yj LKR-jének hossza. Ha akár i, akár j nulla, azaz a sorozatok legalább egyikének hossza 0, akkor természetesen az LKR hossza is 0. Az LKR optimális részstruktúra tulajdonságából a következo˝ rekurzív képletet kapjuk: 0, ha i = 0 vagyj = 0, c[i, j] = ´ xi = yj c[i − 1, j − 1] + 1, ha i, j > 0 es ´ xi 6= yj max(c[i, j − 1], c[i − 1, j]), ha i, j > 0 es
PM-04 – p. 15/18
´ es: ´ LKR hosszanak ´ ´ ıtasa ´ 3. lep kiszam´ Használhatjuk a dinamikus programozást. LKR-hossza(X, Y ) 1. m := hossz[X] 2. n := hossz[Y ] 3. for i := 1 to m do c[i, 0] := 0 4. for j := 1 to n do c[0, j] := 0 5. for i := 1 to m 6.
do for j := 1 to n
7.
do if xi = yj
8. 9.
then c[i, j] := c[i − 1, j − 1] + 1 b[i, j] := ”h”
10.
else if c[i − 1, j] ≥ c[i, j − 1]
11.
then c[i, j] := c[i − 1, j]
b[i, j] := ” ↑ ”
12.
else c[i, j] := c[i, j − 1]
b[i, j] := ” ← ”
13. return c és b Az eljárás futási ideje O(m ∗ n), mivel minden tömbelem kiszámításának ideje O(1). PM-04 – p. 16/18
´ matrix ´ Eredmeny
PM-04 – p. 17/18
´ es: ´ Egy LKR megszerkesztese ´ 4.lep Az alábbi eljárás X és Y LKR-jének elemeit a helyes, eredeti sorrendben nyomtatja ki. LKR-nyomtat(b, X, i, j) 1. if i = 0 vagy j = 0 2.
then return
3. if b[i, j] = ”h” 4. 5.
then LKR-nyomtat(b, X, i − 1, j − 1) print xi
6. else if b[i, j] = ” ↑ ” 7.
then LKR-nyomtat(b, X, i − 1, j)
8.
else LKR-nyomtat(b, X, i, j − 1)
PM-04 – p. 18/18
