Programozási módszertan Dinamikus programozás: szerel˝oszalag ütemezése Mátrixok véges sorozatainak szorzása ´ Werner Agnes ´ oki ¨ es ´ Informaci ´ os ´ Rendszerek Tanszek ´ Villamosmern
e-mail:
[email protected]
PM-06 – p. 1/28
´ 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. A 1-3. lépések jelentik az alapját annak, ahogy a dinamikus programozás meg tud oldani egy feladatot.
PM-06 – p. 2/28
Szerel˝oszalag ütemezése
PM-06 – p. 3/28
Feladat ˝ Egy autógyár autókat állít elo˝ az egyik gyárában, amelynek két szereloszalagja van. ˝ Mindkét szereloszalag elején egy alváz jelenik meg, melyhez adott számú állomáson hozzászerelik az alkatrészeket, majd a szalag végén távozik a kész autó. Mindegyik szalagnak n állomása van, melyek indexei j = 1, 2, . . . , n. Sij jelöli az i-edik (i = 1 vagy 2) szalag j-edik állomását. Az elso˝ szalag j-edik állomása (S1j ) ugyanazt a funkciót látja el, mint a második szalag j-edik állomása (S2j ). ˝ A szalagokat különbözo˝ idopontokban különbözo˝ technológiával építették, ezért ˝ ˝ kell elofordulhat, hogy a két szalag azonos állomásán a terméknek különbözo˝ idot ˝ aij jelöli. eltöltenie. Az Sij állomáson a muveleti ˝ idot
PM-06 – p. 4/28
˝ ´ -Pelda ´ Szereloszalag utemez ese ¨
A teljes leszámlálás számítási ideje Ω(2n). Ez nagy n mellett elfogadhatatlan.
PM-06 – p. 5/28
´ es: ´ a legrovidebb ¨ ´ asi ´ ut 1. lep gyart ´ szerkezete Tekintsük a lehetséges legrövidebb utat, ahogy egy alváz a ˝ túljut az S1j állomáson. kiindulási helyzetbol ˝ Ha j = 1, akkor csak egy lehetoség van, és így könnyu˝ ˝ meghatározni a szükséges idot. ˝ j = 2, . . . , n esetén két lehetoség van: • Az alváz érkezhet közvetlenül az S1,j−1 állomásról, amikor
ugyanannak a szalagnak a (j − 1)-edik állomásáról a j -edik állomására való átszállítás ideje elhanyagolható. • Az alváz S2,j−1 felol ˝ érkezik, az átszállítás ideje t2,j−1 .
Tegyük fel, hogy az S1 j állomáson való túljutás leggyorsabb ˝ érkezünk. módja az, hogy oda az S1,j−1 felol Az alváznak a legrövidebb módon kell túljutnia az S1,j−1 állomáson, mert ha volna egy gyorsabb mód, hogy az alváz túljusson a S1,j−1 állomáson, akkor ezt használva magán S1,j -n is hamarabb jutna túl, ami ellentmondás. PM-06 – p. 6/28
´ es: ´ a legrovidebb ¨ ´ asi ´ ut 1. lep gyart ´ szerkezete Általánosabban fogalmazva azt mondhatjuk, hogy a ˝ szereloszalag ütemezésének (hogy megtaláljuk a legrövidebb módot az Sij állomáson való túljutásra) optimális megoldása tartalmazza egy részfeladat (vagy az S1,j−1 vagy az S2,j−1 állomáson való leggyorsabb áthaladás) optimális megoldását. Erre a tulajdonságra optimális részstruktúraként fogunk hivatkozni. Azaz részfeladatok optimális megoldásaiból megszerkesztheto˝ a feladat optimális megoldása.
PM-06 – p. 7/28
´ es: ´ a rekurz´ıv megoldas ´ 2. lep Az optimális megoldás értékét a részfeladatok optimális ˝ rekurzívan fejezzük ki. értékeibol A részfeladatok legyenek mindkét szalag j -edik állomásán való leggyorsabb áthaladás megkeresésének a feladatai j = 1, . . . , n mellett. ˝ ami alatt az alváz túl tud jutni Jelölje fi [j] azt a legrövidebb idot, az Sij állomáson. ˝ Célunk annak a legrövidebb idonek a meghatározása, ami alatt az alváz az egész üzemen keresztül tud haladni. ˝ f ∗ jelöli. Ezt az idot f ∗ = min{f1 [n] + x1 , f2 [n] + x2 } f1 [1] = e1 + a11 f2 [1] = e2 + a21 PM-06 – p. 8/28
´ es: ´ a rekurz´ıv megoldas ´ 2. lep Hogyan kell kiszámolni az fi [j]-t esetén?
j = 2, . . . , n és i = 1, 2
f1 [j] = min{f1 [j − 1]+ a1j , f2 [j − 1]+ t2,j−1 + a1j }, ha j = 2, . . . , n. f2 [j] = min{f2 [j − 1]+ a2j , f1 [j − 1]+ t1,j−1 + a2j }, ha j = 2, . . . , n.
A következo˝ rekurzív egyenletet kapjuk: ( e1 + a11 , ha j = 1, f1 [j] = min{f1 [j − 1] + a1j , f2 [j − 1] + t2,j−1 + a1j }, ha j ≥ 2 ( e2 + a21 , ha j = 1, f2 [j] = min{f2 [j − 1] + a2j , f1 [j − 1] + t1,j−1 + a2j }, ha j ≥ 2
PM-06 – p. 9/28
´ es: ´ a rekurz´ıv megoldas ´ 2. lep Az fi [j] mennyiségek a részfeladatok optimális érékei. Annak érdekében, hogy vissza tudjuk keresni a legrövidebb utat, ˝ definiáljuk li [j]-t mint azt a szereloszalagot, amelyiknek a j − 1-edik állomását használtuk az Sij -n való leggyorsabb keresztülhaladáskor. Itt i = 1, 2 és j = 2, . . . , n. ˝ (Nem definiáljuk li [1]-et, mert Si1 -t egyik szalagon sem elozi meg másik állomás.) Az l∗ szalag definíció szerint az, amelyiknek az utolsó állomását használjuk az egész üzemen való áthaladáskor. Az li [j] értékek segítségével lehet nyomon követni a legrövidebb utat.
PM-06 – p. 10/28
´ es: ´ a legrovidebb ¨ ´ ´ ido˝ kiszam´ ´ ıtasa ´ 3. lep atfut asi Sokkal jobban járunk, ha az fi [j] értékeket más sorrend szerint ˝ adódik. számoljuk, mint az a rekurzív módszerbol ˝ és Vegyük észre, hogy j ≥ 2 esetén fi [j] csak f1 [j − 1] -tol ˝ függ. f2 [j − 1] -tol Ha az fi [j] értékeket az állomások j indexének növekvo˝ sorrendjében számoljuk, akkor a legrövidebb átfutási ido˝ meghatározása Θ(n) ideig tart.
PM-06 – p. 11/28
´ es: ´ a legrovidebb ¨ ´ ´ ido˝ kiszam´ ´ ıtasa ´ 3. lep atfut asi ALGORITMUS1(a,t,e,x,n) 1. f1 [1] := e1 + a11 2. 3.
f2 [1] := e2 + a21
for j := 2 to n do if f1 [j − 1] + a1j ≤ f2 [j − 1] + t2,j−1 + a1j
4.
then f1 [j] := f1 [j − 1] + a1j
l1 [j] := 1
5.
else f1 [j] := f2 [j − 1] + t2,j−1 + a1j
6.
if f2 [j − 1] + a2j ≤ f1 [j − 1] + t1,j−1 + a2j
7.
then f2 [j] := f2 [j − 1] + a2j
8.
else f2 [j] := f1 [j − 1] + t1,j−1 + a2j
9.
if f1 [n] + x1 ≤ f2 [n] + x2
10.
then f ∗ = f1 [n] + x1
11.
else f ∗ = f2 [n] + x2
l1 [j] := 2
l2 [j] := 2 l2 [j] := 1
l∗ = 1 l∗ = 2 PM-06 – p. 12/28
´ es: ´ a legrovidebb ¨ ´ ´ ideju˝ ut 4. lep atfut asi ´ ˝ meg kell szerkeszteni fi [j], f ∗ , li [j] és l∗ kiszámítását követoen az üzemen való legrövidebb áthaladást biztosító utat. Az eljárás az út állomásait az indexek csökkeno˝ sorrendjében nyomtatja ki. ALGORITMUS2(l,n) 1. i := l∗ 2. print i"-edik szalag" n"-edik állomás" 3. for j := n downto 2 4. do i := li [j] 5. print i"-edik szalag (" j − 1")-edik állomás"
PM-06 – p. 13/28
Mátrixok véges sorozatainak szorzása
PM-06 – p. 14/28
Feladat Feladat: Legyenek A1 , A2 , . . . , An adott mátrixok. Számítsuk ki a mátrixok A1 A2 . . . An szorzatát. Definíció: Mátrixok egy szorzata teljesen zárójelezett, ha • vagy egyetlen mátrix, • vagy két zárójelbe tett teljesen zárójelezett mátrixszorzat
szorzata. Megjegyzés: A mátrixok szorzása asszociatív muvelet. ˝
PM-06 – p. 15/28
´ Algoritmus-Kod Két mátrix összeszorzásának algoritmusa (pszeudokód): MÁTRIXSZORZÁS(A,B) 1. if oszlop[A] 6= sor[B] 2.
then error "nem összeillo˝ dimenzió"
3.
else for i ← 1 to sor[A]
4. 5. 6. 7. 8.
do for j ← 1tooszlop[B] do C[i, j] ← 0 for k ← 1 to oszlop[A] do C[i, j] ← C[i, j] + A[i, kB[k, j] return C
Szorzatmátrix mérete: Apxq ∗ Bqxr = Cpxr
˝ pqr Számítási ido: PM-06 – p. 16/28
´ ´ ¨ ´ anak ´ ´ aja ´ Veges sok matrix osszeszorz as problem Legyen (A1 , . . . , An ) mátrixok egy adott véges sorozata, ahol az Ai mátrix mérete pi−1 × pi (i = 1, . . . , n). Keressük az A1 A2 . . . An sorozat azon teljes zárójelezését, mely minimalizálja a szorzat kiszámításához szükséges skalár szorzások számát. Cél: a szorzás optimális sorrendjének megállapítása, a szorzást nem végezzük el.
PM-06 – p. 17/28
´ ojelez ´ ´ ´ Zar esek vizsgalata Zárójelezések száma: Legyen P (n) az n mátrix zárójelezéseinek száma. P (1) = 1 Tegyük fel, hogy ha n ≥ 2, akkor a sorozatot a k -dik és a k + 1-dik eleme között szétvágva a két részsorozatra a zárójelezések száma egymástól függetlenül meghatározható (k = 1, . . . , n − 1) Rekurzív formula: ( 1, ha n = 1, Pn−1 P (n) = k=1 P (k)P (n − k), ha n ≥ 2
A megoldás nagyságrendje: Ω(2n ) ˝ Az összes lehetséges zárójelezés megvizsgálása ("nyers ero" módszerrel) nem hatékony!
PM-06 – p. 18/28
´ zar ´ ojelez ´ ´ szerkezete 1. Az optimalis es Optimális megoldás a részfeladatok optimális megoldásából: Keressük azt az alkalmas optimális részstruktúrát, mely felhasználható a probléma optimális megoldásának létrehozásához a részproblémák optimális megoldásaiból. Az optimális zárójelezés szerkezete: Jelölje Ai··j az Ai Ai+1 . . . Aj szorzat eredményét. Ha i < j , akkor az optimális zárójelezés két részre vágja a sorozatot valamely Ak és Ak+1 mátrix között (i ≤ k < j) Az Ai..j mátrixot megkapjuk, ha összeszorozzuk az Ai..k és Ak+1..j mátrixokat; koltseg(Ai..j ) = koltseg(Ai..k ) + koltseg(Ak+1..j ) + koltseg(Ai..k Ak+1..j ) Megjegyzés: Az optimális zárójelezésben az Ai..k és Ak+1..j részsorozatok zárójelezésének is optimálisnak kell lennie! PM-06 – p. 19/28
´ 2. Rekurz´ıv megoldas Részprobléma: Ai Ai+1 . . . Aj szorzat optimális zárójelezése, ahol 1 ≤ i ≤ j ≤ n. Legyen m[i, j] az Ai..j mátrix számításához szükséges skalár szorzások minimális száma. Az Ai..k Ak+1..j szorzat számításának költsége a korábbiak alapján: pi−1 pk pj m[i, j] számítása: ( 0, ha i = j, m[i, j] = mini≤k<j {m[i, k] + m[k + 1, j] + pi−1 pk pj }, ha i < j Megjegyzés: A k értékét ugyan nem ismerjük, de csak j − i féle ˝ választjuk a legjobbat. lehet: k = i, i + 1, . . . , j − 1, ezekbol
PM-06 – p. 20/28
´ kolts ¨ eg ´ szam´ ´ ıtasa ´ Optimalis ˝ A rekurzív algoritmus idoigénye exponenciális, nem jobb, mint az összes zárójelezés vizsgálata, viszont a részfeladatok száma alacsony: ⇒ ahány i, j pár kielégíti az 1 ≤ i ≤ j ≤ n feltételt: n(n + 1)/2 = Θ(n2) (az algoritmus egy-egy részfeladattal többször is foglalkozhat a rekurziós fa különbözo˝ ágaiban)
PM-06 – p. 21/28
´ felfele´ tort ¨ en ´ o¨ megkozel´ ¨ ıtes: ´ 3. Alulrol A táblázat kitöltésénél fontos a sorrend: j − i + 1 db mátrix m[i, j] összeszorzási költségének számításához csak j − i + 1-nél rövidebb szorzatokat használunk: k = i, i + 1, . . . , j − 1 esetén • Ai..k mátrix k − i + 1 < j − i + 1 mátrix szorzata, • Ak+1..j mátrix j − k < j − i + 1 mátrix szorzata.
⇒ az m tömböt a szorzatok növekvo˝ hossza szerint kell kitölteni. Legyen s[i, j] az a k index, melynél az optimális zárójelezés az Ai..j szorzatot kettévágja.
PM-06 – p. 22/28
´ Algoritmus (pszeudokod) MÁTRIX-SZORZÁS-SORREND(p) 1. n ← hossz[p] − 1 2. for i ← 1 to n 3.
do m[i, i] ← 0
4. for l ← 2 to n 5.
do for i ← 1 to n − l + 1
6.
do j ← i + l − 1
7.
m[i, j] ← ∞
8.
for k ← i to j − 1
9. 10.
do q ← m[i, k] + m[k + 1, j] + pi−1 pk pj if q < m[i, j]
11.
then m[i, j] ← q
12.
s[i, j] ← k
13. return m és s Input: p =< p0 , p1 , . . . , pn >, rendre a pi−1 × pi dimenziójú Ai mátrixok méretei (i = 1, 2, . . . , n) hossz[p] = n + 1 PM-06 – p. 23/28
´ ´ Vegrehat as • eloször ˝ az m[i, i] = 0 (i = 1, 2, . . . , n) hozzárendelés
végrehajtása, azaz az 1 hosszú sorozatok számítása, • majd az m[i, j] -re vonatkozó rekurzív egyenlet segítségével
az m[i, i + 1] (i = 1, 2, . . . , n − 1) értékek meghatározása, azaz az l = 2 hosszú sorozatok számítása, • az m[i, i + 2] (i = 1, 2, . . . , n − 2) értékek meghatározása,
azaz az l = 3 hosszú sorozatok számítása, • stb.
m[i, j] csak a korábban már meghatározott m[i, k] és m[k + 1, j] ˝ függ. elemektol ˝ O(n3 ), mert l, i, k ciklusváltozók mindegyike Futásido: legfeljebb n értéket vehet fel. (valójában Ω(n3 ))
PM-06 – p. 24/28
´ megoldas ´ elo˝ all´ ´ ıtasa ´ Az optimalis Az s tömb felhasználásával: s[i, j] az a k index, amely után az Ai..j sorozatot vágjuk. Algoritmus (pszeudokód): OPTIMÁLIS-ZÁRÓJELEZÉS-NYOMTATÁSA(s, i, j) 1. if j = i 2.
then print ”A”i
3.
else print ”(”
4. 5. 6.
OPTIMÁLIS-ZÁRÓJELEZÉS-NYOMTATÁSA(s, i, s[i, j]) OPTIMÁLIS-ZÁRÓJELEZÉSNYOMTATÁSA(s, s[i, j] + 1, j) print ”)”
Kezdeti hívás: OPTIMÁLIS-ZÁRÓJELEZÉS-NYOMTATÁSA(s, 1, n) PM-06 – p. 25/28
´ Pelda
Pl.: A2..5 részsorozat optimális összeszorzása: p0 = 30, p1 = 35, p2 = 15, p3 = 5, p4 = 10, p5 = 20, p6 = 25
m[2, 5]
=
m[2, 2] + m[3, 5] + p1 p2 p5 = 0 + 2500 + 35 × 15 × 20 = 13000 min m[2, 3] + m[4, 5] + p1 p3 p5 = 2625 + 1000 + 35 × 5 × 20 = 7125 m[2, 4] + m[4, 5] + p1 p4 p5 = 4375 + 0 + 35 × 10 × 20 = 11375
A hat mátrix összeszorzásához minimálisan m[1, 6] = 15125 skalár szorzás kell.
PM-06 – p. 26/28
´ ojelez ´ ´ meghataroz ´ ´ rekurz´ıvan A zar es asa A zárójelezés meghatározása rekurzívan az s tömb segítségével
PM-06 – p. 27/28
´ kiszam´ ´ ıtasa ´ Az A1..n szorzat optimalis Az utolsó mátrixszorzás: A1..s[1,n] As[1,n]+1..n
A korábbi mátrixszorzások számítása rekurzívan: • A1..s[1,n] számításakor vágás s[1, s[1, n]] mögött • As[1,n]+1..n számításakor vágás s[s[1, n] + 1, n] elott ˝
Rekurzív hívások sorrendje: [1, 6] ⇒ ([1, 3]([1, 1] → A1 → [2, 3]([2, 2] → A2 → [3, 3] → A3 →)) [4, 6]([4, 5]([4, 4] → A4 → [5, 5] → A5 →)[6, 6] → A6 →)) Optimális zárójelezés: ((A1(A2A3))((A4A5)A6))
PM-06 – p. 28/28
