KREDIT
VADÁSZ

Dinamikus programozás segédlet

2007.12.16 00:16:24
Szerző: Fekete Gábor
Cimkék: dinamikus programozás, algoritmus elmélet, ordo, optimalitás elve, algoritmusok

Dinamikus programozás segédlet

A feladatok megoldásáról:
A dinamikus programozás során a rekurziónál fellépő fölösleges számításokat spóroljuk meg úgy, hogy egy (vagy több) tömbben tároljuk a megfelelő értékeket, és minden lehetséges elemet csak egyszer számítunk ki.
Általános lépések (adott feladat esetében):

• Rekurziós összefüggés felírása
• Az összefüggés elemzése. Ha lehetséges, akkor tömbre átírás (a változók diszkrétek, korlátozottak)
• A tömbben a kitöltési irány meghatározása (minden elem esetén definiált legyen az összes olyan elem értéke, amit használ
• Végső megoldás helyének megadása
• Ha kell, optimális megoldás visszakeresése
• Ellenkező esetben memóriaigény csökkentése (ha lehet)

7.1 Hányféleképpen lehet egy n lépcsőfokot tartalmazó lépcsö tetejére felmenni, ha egyet, vagy kettőt tudunk lépni?
Rekurzív öf:
lepcso(1)=1
lepcso(2)=2
lepcso(n)=lepcso(n-1)+lepcso(n-2)
Adott n esetén pontosan n értéket kell kiszámolnunk (lepcso(1)-tol lepcso(n)-ig), igy ez elfér egy n méretű tömbben (T).
Az öszefüggések egyszerűen átírhatóak:
T[1]=1
T[2]=2
T[i]=T[i-1]+T[i-2]
Mivel az i. elem az (i-1). és (i-2). elemektől függ, a tömböt a kis indexektől a nagy indexekig kitöltve helyes eredményt kapunk, a megoldás T[n]-ben lesz.

7.11 Mint 7.1, de némely fok el van korhadva.
Mint az előző feladat, de ha egy fok el van korhadva, akkor ott az érték 0 legyen, egyébként teljesül az összefüggés. (az alapesetek is az első két fok állapotától függenek triviális módon)

7.2 Hányféleképpen tudunk egy nxk méretű sakktábla bal alsó sarkából a jobb felsőbe jutni? (egyet fel, vagy egyet jobbra tudunk lépni)
Az összefüggések (egyből egy R tömbbe írva):
R[i][j]=1, ha i=1 vagy j=1
R[i][j]=R[i-1][j]+R[i][j-1] egyébként
pl.:

1	4	10	20	35
1	3	6	10	15
1	2	3	4	5
1	1	1	1	1

Minden nem szélső elem a tőle "balra" és az alatta lévő elemtől függ, azaz a tömböt sorfolytonosan lentről felfelé haladva kitölthetjük.
Vizsgáljuk meg a kitöltés közben a tömböt:

1	3	?
1	2	3	4	5
1	1	1	1	1

A kitöltésben a ?-lel jelölt elem következik, ha megigyeljük a táblát, észrevehetjük, hogy egyik még ki nem töltött elemhez nem szükséges a piros háttérrel jelölt elemek ismerete, azaz ezeket felesleges tárolni. Általánosan elmondható, hogy elég az épp aktuális sort letárolni, illetve az az alatt lévő sorét, azaz mindössze két sort.
Ha jobban megfigyeljük többet is észrevehetünk:

1	3	?
1	2	3	4	5
1	1	1	1	1

A pirossal jelölt elemekre nincsen (és nem is lesz) szükség, csak a zölddel jelöltek kiszámítottak és szükségesek, ezeket egy sorban tárolhatjuk (világosszürke háttérrel a következőleg kiszűmolandó elem):

1

3

3

4

5

A világosszürke elem új értékének kiszámításához tudnunk kell, hogy ebben az egy sorban hol helyezkedik el az eredeti iömbben alatta lévő, illetve a tőle balra lévő. A balra lévő itt is a tőle balra lévő, az eredetileg alatta lévő pedig pont az ő helyén van, azaz ezt a kettőt összegezve megkapjuk az új eredményt:

1

3

6

4

5

7.17Adott egy nxk méretű sakktábla, minden mezőn van egy bizonyos értékű kincs, maximum mennyi összértéket tudunk gyűjteni, ha a bal alsó sarokból indulunk, a jobb felsőbe érkezünk, és csak egyet jobbra, vagy egyet fel tudunk lépni?
A mezőkön lévő értékeket tárolja egy C tömb. pl.:

C=	1 2 1 6 10 5 4 1 2 3 7 5 1 3 4 10

A rekurzív összefügések, egyből egy T tömbre átírva:
T[1][1]=C[1][1]
T[i][1]=C[i][1]+T[i-1][1], ha i>1 (az alatta lévő mezőig összegyűjtöttünk valamennyit, majd lépünk fel, és felvesszük, ami ott van)
T[1][j]=C[1][j]+T[1][j-1], ha j>1 (hasonlóan)
T[i][j]=max{T[i-1][j],T[i][j-1]}+C[i][j], ha i>1 és j>1 (vagy lentről, vagy balról lépünk ide, és felvesszük a kincset)
A megoldás T[k][n]-ben lesz
Ez alapján a példára:

T=	14 20 23 30 13 18 23 24 3 7 15 23 1 4 8 18

Azaz összesen 30 értékű kincsünk lehet a legjobb esetben.
A következő feladat: adjunk meg egy ilyen útvonalat.
Ehhez vegyünk fel egy F segédtömböt, amiben letároljuk, hogy az aktuális mezőnél T kiszámítása közben melyik volt optimálisabb, lentről, vagy balról jönni (azaz T[i-1][j], vagy T[i][j-1] volt nagyobb a max fv. számolásakor). Legyen: 'l', ha lentről, 'b', ha balról, és '0' a kiindulómezőn.
Az előző példára:

F=	l l l l l b b l l l l l 0 b b b

Könnyedén vissza tudjuk keresni az utat, tudjuk, hogy jobbfelülre érkeztünk, látjuk, hogy oda lentről léptünk, tehát az utolsó lépés F (Fel) volt. Látjuk, hogy eggyel lejjebbre is lenről jöttünk, tehát az a lépés is F volt. Így visszalépkedve (addig folytatva az iterációt, amíg a kiinduló mezőre nem lépünk) meghatározható az útvonal:
JJJFFF

1	2	1	6
10	5	4	1
2	3	7	5
1	3	4	10

Másik lehetőség, hogy F nélkül mindig újra kiszámoljuk, honnan léphettünk oda, tehát tudjuk, hogy a jobbfelsőbe érkeztünk, megnézzük, hogy tőle balra 23-at gyűjthettünk, alatta pedig 24-et, tehát lentről kellett jönnünk (hiszen optimális az eredmény). Ezt folytatva amig a balalsóba nem érünk megkapjuk ugyanezt az útvonalat.


7.16Adjuk meg, hogy hány betűt kell minimum beszúrni egy szóba, hogy tükörszó legyen.
Legyen a szó n hosszú, vegyünk egy nxn-es T tömböt. T[i][j] tartalmazza, hogy minimálisan hány betűt kell beszúrni a szó i-edik karaktertől a j-edik karakterig tartó részszavába, hogy az tükörszó legyen. (j>=i)
A megoldást T[1][n]-ben kell majd keresnünk. A következő összefüggések állnak fenn:
T[i][i]=0, hiszen definíció szerint minden egybetűs szó tükörszó
T[i][i+1]=0, ha a két betű megyegyezik, hiszen ekkor ez tükörszó
T[i][i+1]=1, ha a két betű nem egyezik meg, hiszen ekkor be kell szúrnunk egy betűt

Pl.: Legyen a szó: aababba
Ekkor pl. T[5][5] az 5. karaktertől az 5. karakterig tartó résszóval foglalkozik, ami: b, ez tükörszó
T[5][6]-nál a szó bb, ami szintén tükörszó, nem kell beszúrnunk semmit
T[2][3]-nál a szó ab, ami nem tükörszó, de ha beszúrunk egy betűt, akkor az lesz: bab

T[i][j]=T[i+1][j-1], ha j>i+1, és az i. és j. karakterek megyegyeznek
pl. T[2][6] -nál a szó: ababba, mivel az első és az utolsó karakter megegyezik, a betűket csak közéjük kell beszúrni, úgy, hogy a köztük lévő szó is tükörszó legyen, azaz babb-nek kell tükörszónak lennie, ami a 3.-tól az 5.-ig lévő részszó, azaz T[3][5] karaktert kell hozzá beszúrni

T[i][j]=min{T[i+1][j],T[i][j-1]}+1 egyébként

Legyen a példa T[1][6], ez megadja, hány karaktert kell beszúrni aababb-be. Mivel a két szélső betű nem egyezik meg, két lehetőségünk van:
Vagy az első betűt beszúrjuk az utolsó után: aababba, ekkor hasonlóan az előző esethez csak azzal a szóval kell tovább foglalkozni, ami a két ugyanolyan szélső között van, azaz ababb-vel, amibe pontosan T[2][6] betűt kell beszúrni.
A másik lehetőség, hogy az utolsót szúrjuk be az első elé: baababb, innentöl hasonló indokokkal, mint elöbb T[1][5] betűt kell beszúrni.
Mivel a kérdés, hogy minimum mennyit kell, kiválasztjuk azt, amelyik optimálisabb eredményt hoz, illetve hozzáadjuk a +1 beszúrt betűt az eredményhez.

A kérdés, hogy miyen sorrenben töltsük ki a tömböt. Az összefüggéseket megvizsgálva látható, hogy minden cella legfeljebb az eggyel felette lévőt, illetve az eggyel balra lévőt használja, illetve a tőle balrafenn lévőt. Az alapeseteket pedig könnyedén kitölthetjük:

						0
					0	1
				0	0
			0	1
		0	1
	0	1
0	0					?

Látható, hogy eztán csak a következő átlót tudjuk kitölteni, aztán az azutánit, és így tovább:

0 0 1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 ?

0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 ?

0 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 2 0 0 1 1 2 ?

0 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 2 1 0 0 1 1 2 3 ?

0 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 2 1 0 0 1 1 2 3 2

Továbbá észrevehető, hogy bármelyik átlót számolva csak a felette lévő két átlóra van szükség, azaz elég lenne mindig csak 3-at letárolni, a két uloljára kiszámítottat, valamint az aktuálisan számítottat (sőt, elég 2 is, megfelelő elemeket felülírva).
Ha viszont ara is kíváncsiak vagyunk, hogy hova kell beszúrni, és miket, akkor egy segédtömbben le kell tárolni, hogy az aktuális T[i][j] számítása során hova és mit szúrtunk be.
Ez vagy az i-1-edik karakter után a j-edik karakter, vagy a j-edik után az i-edik karakter, vagy nincsen beszúrás.
Ezen a segédtömbön visszafelé haladva megkapjuk az összes beszúrandó betűt (hogy hova szúrunk be, és mit, az egyértelműen meghatározza, hogy melyik résszóval foglalkozunk tovább, tehát melyik tömbelemre "ugrunk").

Hozzászólások

... 00 11.05-3 2008/2009-1 4. 5.előadás andragógia aszalós lászló atkinson biotermékek economic policy elosztás éptöri erdeiné török zsuzsa esszék felvilágosodás gazdaság gazdinfo géptan hla ipar jogképesség katalízis kérdések és válaszok kidolgozott tétel koncentráció középkor közig közigtöri laskai gábor magyarország geográfiája marketing növénynemesítés olasz őstörténet peter behrens political science pszichológia reklámelmélet és gyakorlat rushdie stilisztika számvitel szimbólum szociálpszichológia szte-btk dr. simon józsef tb nemzetközi vállalatgazdaságtan vegyipari vektor villamos gépek