Amortizációs költségelemzés Amennyiben m˝uveleteknek egy M1 , . . . , Mm sorozatának a futási idejét akarjuk meghatározni, akkor egy lehet˝oség, hogy külön-külön minden egyes m˝uvelet futási idejét kifejezzük és összegezzük. Ennél gyakran pontosabb és kedvez˝obb eredményt kapunk, ha helyette a teljes m˝uveletsor összesített költségét számítjuk, de az egyes m˝uveletekét nem. Ekkor a m˝uveletekre átlagolt T (n)/m költséget számítjuk, ezt az m˝uveletek átlagolt költségének nevezzük. (Ez továbbra is lehet legrosszabb eset elemzés, itt az átlag nem az input eloszlásra, hanem a m˝uveletekre vonatkozik.) Az átlagolt költség meghatározására a következ˝o módszereket szokás használni. • Összesítéses módszer. • Könyvelési módszer. • Potenciál módszer. 1. Példa Többszörös VeremBol muvelet. ˝ Vegyünk egy módosított verem adattípust, amelyben a verem adattípus m˝uveletei mellett definiálunk egy TOROL(V,k) m˝uveletet, amely törli a legfels˝o k elemet, ha van k darab elem, egyébként pedig törli a verem összes elemét. Tudjuk, hogy az üres V veremb˝ol kiindulva végrehajtottunk m darab m˝uveletet, amelyek mindegyike a Verembe(V,x), Torol(V),Verembol(V,x), Torol(V,k) valamelyike. Feladat az átlagolt költség meghatározása. Ha egyenként vesszük a m˝uveleteket a Torol(V,k) m˝uvelet futási ideje O(k) a többié konstans, így csak O(k) értéket kapnánk az átlagolt költségre. Látjuk majd, hogy O(1) is teljesül. 2. Példa Bináris számláló növelése. Tekintsük az A[0..k-1] bitvektort, ami egy szám 2-es számrendszerbeli leirása, a tömb i-dik eleme az 2i -es helyiértéken álló szám. A feladat a számláló növelése, kezdetben x = 0, azaz A[i] = 0 minden i-re. Az x := x+1 való növelésre a következ˝o eljárást használjuk. Novel(A) i:=0 while(i<=k-1) and A[i]=1 A[i]:=0 i:=i+1 if i<=k-1 then A[i]:=1 A feladat a 2k darab Novel eljárás átlagolt költségének (bitek változtatásának száma) meghatározása. Egy m˝uvelet költsége legrosszabb esetben O(k). Összesítéses módszer Az összesítéses módszernél a teljes m˝uveletsor futási idejére közvetlenül bizonyítunk fels˝o korlátot. 1. Példa Az összesített költség O(n), mivel legfeljebb n elemet tudunk a verembe berakni, és csak berakott elemen keletkezhet költség a törlésnél vagy kivételnél. 2. Példa Vizsgáljuk meg a 2k darab m˝uvelet teljes költségét. Vizsgáljuk meg az egyes tömbelemek hányszor változnak. Észrevehetjük, hogy A[0] minden m˝uveletnél változik, azaz 2k esetben, A[1] minden második m˝uveletnél változik, 1
k−1 k−i azaz 2k−1 esetben, és így tovább A[i] 2k−1 esetben változik. Következésképpen a teljes költség ∑i=0 2 = 2k+1 − 1, azaz az átlagos költség konstans. Könyvelési módszer
A könyvelési módszer lényege az, hogy más amortizált cˆi költséget könyvelünk el az i m˝uveletre, mint a tényleges költsége. Ez a költség lehet kisebb is, mint a tényleges csak arra kell ügyelni, hogy minden j ≤ m esetén fennálljon a j
j
∑ cˆi ≥ ∑ ci
i=1
i=1
egyenl˝otlenség. Ha az egyenl˝otlenség teljesül használhatjuk az amortizált költséget átlagolt költségnek. 1. Példa A könyvelt költség legyen 2 a Verembe(V,x) m˝uvelet esetén, 0 a TOROL(V), TOROL(V,k), VEREMBOL(V,x) m˝uveletek esetén. Ekkor a kivétel költségét már az elem verembe behelyezésekor elkönyveltük, így az amortizált költségekre követelt feltétel teljesül. 2. Példa A tényleges költség annyi, ahány bitet megváltoztat a m˝uvelet a végrehajtása során. Számítsunk 2 amortizációs költséget, ha egy bitet 1-re állítunk be. Mivel ezt az értékadást minden lépésben egyszer hajtjuk végre, ezért minden lépésben 2 az amortizált költség. Viszont egy bitet csak azt követ˝oen állíthatunk 0-ra, ha el˝otte 1-re állítottuk, így szintén teljesül a megkövetelt egyenl˝otlenség, tehát az átlagolt költség O(1). Potenciál módszer Ennél a módszernél az el˝ore kifizetett költséget nem egy m˝uvelethez rendeljük hozzá, hanem a vizsgált adatszerkezet állapotához rendelt potenciális energiaként tartjuk számon. A kezdeti állapota az adatszerkezetnek, amelyen m m˝uveletet hajtunk végre legyen D0 , az i-edik m˝uvelet végrehajtása utáni állapot legyen Di . Ekkor az amortizált költség cˆi = ci + Φ(Di ) − Φ(Di−1 ). Az m m˝uvelet amortizált költségét számolva m
m
∑ cˆi = ∑ ci + Φ(Dm) − Φ(D0).
i=1
i=1
Következésképpen, ha Φ(Dn ) ≥ Φ(D0 ) (például Φ(D0 ) = 0 és Φ nemnegatív), akkor teljesül az amortizált költségre megkövetelt egyenl˝otlenség. 1. Példa Legyen Φ a veremben lev˝o elemek száma, ez egy nemnegatív függvény, aminek kezdeti értéke 0. Vizsgáljuk az amortizált költségeket. • Verembe(V,x): Φ értéke 1-el n˝o, tényleges költség 1, így az amortizált 2. • Torol(V), Verembol(V,x): Φ értéke 1-el csökken, tényleges költség 1, így az amortizált 0. • Torol(V,k): Legyen r a minimuma k-nak és a veremben lev˝o elemek számának. Ekkor Φ értéke r-el csökken, tényleges költség r, így az amortizált 0.
2
2. Példa Legyen Φ a számlálót leíró tömbben lev˝o egyesek száma, ez egy nemnegatív függvény, aminek kezdeti értéke 0. Vizsgáljuk az amortizált költséget. Tegyük fel, hogy t bit változott, azaz a tényleges költség t. Ekkor a t változtatás közül egy esetben 0 változott 1-re, a többi t − 1 esetben 1 változott 0-ra, így a potenciálfüggvény értéke t-2-vel csökkent, azaz az amortizált költség 2. 8 királyn˝o probléma Helyezzünk el az n × n-es sakktáblán n királyn˝ot, hogy egyik se üsse a másikat! Megoldástér: n darab mez˝o, amiket a koordinátákkal adhatunk meg: {(x1 , y1 ), . . . , (xn , yn )}, 1 ≤ xi , yi ≤ n . A királyn˝ok akkor és csak akkor nem ütik egymást, ha • xi 6= x j , ha i 6= j • yi 6= y j , ha i 6= j • xi + yi 6= x j + y j , ha i 6= j • xi − yi 6= x j − y j , ha i 6= j Az els˝o feltétel alapján feltehetjük, hogy yi = i, így a királyn˝ok elhelyezését egy (x1 , . . . , xn ) 1 ≤ xi ≤ n vektorral írjuk le, ami annak az elhelyezkedésnek felel meg, hogy az i-edik sorban a királyn˝o az x j oszlopban van. • xi 6= x j , ha i 6= j • xi + i 6= x j + j, ha i 6= j • xi − i 6= x j − j, ha i 6= j Megoldástér ábrázolás Ekkor a bejárandó megoldáskezdemények (x1 , . . . , xk ) vektorok 1 ≤ xi ≤ n, k ≤ n. A megoldáskezdemények egy fában ábrázolhatóak, a fát leíró, a bejárásához használható függvények: EFiu(x1 , . . . , xk ) = (x1 , . . . , xk , 1), ha k
Tehát LehetMego(x1 , . . . , xk ) = True, akkor és csak akkor ha minden i 6= j esetén teljesül, hogy xi 6= x j , xi + i 6= x j + j, xi − i 6= x j − j Használunk még egy Megoldas függvényt, amely akkor és csak akkor ad igaz értéket, ha az adott pont lehetséges megoldás. Esetünkben Megoldas(x1 , . . . , xk ) = True, akkor és csak akkor teljesül, ha LehetMego(x1 , . . . , xk ) és k = n. A keretalgoritmus A fenti függvények alapján az alábbi általános keretalgoritmust építjük fel. Egy adott probléma esetén meg kell adni a megoldástér fáját és a problémához tartozó függvényeket. Visszalep(F) If F=Nil Then return //Üres fa If Megoldas(F) Then Print "F" // Megoldas kiiratasa return Else p:=F.Elsofiu While (p!=Nil) // a gyerekeken sorbamenve If LehetMego(p) Then Visszalep(p) p:=p.Testver A fenti változat egyetlen megoldást keres meg, de a harmadik negyedik sor változtatásával könnyen átírható az összes megoldás megkeresésére. A kiiratás helyett a megoldást bele kell tenni egy halmazba, a negyedik "return" sort törölni. Az összes megoldás megkeresése felhasználható optimalizálási feladatok megoldására is. Pénzváltási probléma Az pénzváltási problémában adottak p1 , . . . , pn pénzérmék és egy E összeg, a feladat kiválasztani az érmék egy S halmazát, amelyre teljesül, hogy ∑i∈S pi = E. A megoldástér a pénzérmék összes lehetséges részhalmaza. Egy lehetséges reprezentáció egy n szintb˝ol álló teljes bináris fa, amely a halmaz bitvektorát tárolja. A részhalmazoknak a levelek felelnek meg. A levélhez tartozó halmazt a levélig a gyökérb˝ol vezet˝o út alapján kapjuk meg. Ha az i-dik szinten balra lépünk az i-dik elemet nem választjuk be, ha jobbra, akkor az i-dik elemet beválasztjuk a halmazba. Egy másik reprezentációval a megoldástér pontjait (a pénzek részhalmazát) a pénzek indexeinek az S ⊆ {1, . . . , n} halmazának X = (i1 , . . . , ik ) növekv˝o felsorolásáként reprezentáljuk. Ekkor a bejáráshoz használt függvények EFiu(i1 , . . . , ik ) = (i1 , . . . , ik , ik + 1), ha ik < n és Nil ha ik = n. Testver(i1 , . . . , ik−1 , ik ) = (i1 , . . . , ik−1 , ik + 1), ha ik < n és Nil ha ik = n. Apa(i1 , . . . , ik−1 , ik ) = (i1 , . . . , ik−1 ), ha k ≥ 1 és Nil egyébként. A LehetMego és Megoldás függvényeket a következ˝oképpen kaphatjuk meg. A LehetMego függvény megadja, ha az eddig meghozott döntéseket nem lehet kiegészíteni egy felbontássá, vagy azért mert már nagyobb összeget választottunk, vagy azért mert minden további elemet kiválasztva sem érhetjük el E-t. Tehát LehetMego(i1 , . . . , ik ) = True akkor és csak akkor, ha k
∑
j=1
k
n
pi j ≤ E ∧ ∑ pi j + j=1
∑
p j ≥ E.
j=ik +1
Továbbá Megoldas(i1 , . . . , ik ) = True akkor és csak akkor, ha ∑kj=1 pi j = E Kiskérdések 4
• könyvelési módszer (1 példa) • potenciál módszer (1 példa) • Visszalépéses keresés keretalgoritmusa • n királyn˝o feladat a felhasznált függvények specifikációja • a pénzváltási problémánál felhasznált függvények specifikációja
5
