Programozási módszertan Dinamikus programozás: A leghosszabb közös részsorozat ´ Werner Agnes ´ oki ¨ es ´ Informaci ´ os ´ Rendszerek Tanszek ´ Villamosmern
e-mail:
[email protected]
PM-07 – p. 1/13
´ 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-07 – p. 2/13
´ 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-07 – p. 3/13
¨ ´ 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-07 – p. 4/13
´ ¨ 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-07 – p. 5/13
¨ 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-07 – p. 6/13
´ 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-07 – p. 7/13
´ 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-07 – p. 8/13
´ 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-07 – p. 9/13
¨ ´ Rekurz´ıv osszef ugg ¨ es Meghatározható egy rekurzív összefüggés: Legyen c[i, j] Xi és Yi 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-07 – p. 10/13
´ 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 m 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-07 – p. 11/13
´ matrix ´ Eredmeny
PM-07 – p. 12/13
´ 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-07 – p. 13/13
