Programoz´as I. 13. el˝ oad´as Moh´ o algoritmusok
Sergy´an Szabolcs
[email protected] ´ Obudai Egyetem Neumann J´ anos Informatikai Kar Alkalmazott Informatikai Int´ ezet
2014. december 1.
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
1 / 46
Tartalom 1
P´enzkifizet´es
2
0-1 h´atizs´ak probl´ema
3
Moh´o algoritmusok a dinamikus programoz´assal szemben
4
Moh´o strat´egia
5
¨ Utemez´ esi feladatok Esem´eny kiv´alaszt´asi probl´ema Esem´eny elk¨ ul¨ on´ıt´esi probl´ema ¨ Utemez´ es k´es´es minimaliz´al´assal
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
2 / 46
Tartalom 1
P´enzkifizet´es
2
0-1 h´atizs´ak probl´ema
3
Moh´o algoritmusok a dinamikus programoz´assal szemben
4
Moh´o strat´egia
5
¨ Utemez´ esi feladatok Esem´eny kiv´alaszt´asi probl´ema Esem´eny elk¨ ul¨ on´ıt´esi probl´ema ¨ Utemez´ es k´es´es minimaliz´al´assal
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
3 / 46
Postai p´enzt´aros Feladat Egy nyugd´ıjas elmegy a post´ara, hogy felvegye 79.845 Ft-os nyugd´ıj´at. Hogyan tudja a postai p´enzt´aros kifizetni neki ezt az ¨ osszeget u ´gy, hogy a kifizet´eshez a lehet˝o legkevesebb darab c´ımletet haszn´alja?
Megjegyz´esek Rendelkez´esre ´all´ o c´ımletek: 20.000, 10.000, 5.000, 2.000, 1.000, 500, 200, 100, 50, 20, 10 ´es 5 Ft-os. Tegy¨ uk fel, hogy minden c´ımletb˝ ol korl´atlan mennyis´eg van a post´an. Az nem tekinthet˝ o megold´asnak, ha a nyugd´ıjasnak vissza kell adnia. (Pl.: a p´enzt´aros ad 80.000 Ft-ot 4 db 20.000 Ft-os c´ımlettel, majd a nyugd´ıjas visszaad 155 Ft-ot.)
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
4 / 46
Postai p´enzt´aros Megold´as A p´enzt´aros az al´abbi c´ımleteket fogja adni: 3 db 20.000 Ft-os = 60.000 Ft 1 db 10.000 Ft-os = 10.000 Ft 1 db 5.000 Ft-os = 5.000 Ft 2 db 2.000 Ft-os = 4.000 Ft 1 db 500 Ft-os = 500 Ft 1 db 200 Ft-os = 200 Ft 1 db 100 Ft-os = 100Ft 2 db 20 Ft-os = 40 Ft 1 db 5 Ft-os = 5 Ft 79.845 Ft Ez ¨osszesen 13 db pap´ır p´enzt, illetve p´enz´erm´et jelent.
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
5 / 46
Postai p´enzt´aros K´erd´es Megoldhat´o a feladat kevesebb c´ımlettel is?
V´alasz Nem. (Ezt nem fogjuk pontosan bizony´ıtani, de az eddigi tapasztalataink alapj´an tudjuk, hogy egy optim´alis megold´ast adtunk meg.)
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
6 / 46
P´enzkifizet´es Pszudok´od Bemenet: x − eg´ esz, c − eg´ esz rendezett t¨ omb, n − eg´ esz Kimenet: db − eg´ esz t¨ omb ´nzkifizete ´s(x, c, n) f¨ uggv´ eny Pe ´trehoz(eg´ db ← Le esz)[n] ciklus i ← 1-t˝ ol n-ig db[i] ← 0 ciklus v´ ege j ←n ciklus am´ıg x > 0 ciklus am´ıg c[j] > x j ←j −1 ciklus v´ ege db[j] ← db[j] + 1 x ← x − c[j] ciklus v´ ege vissza db f¨ uggv´ eny v´ ege Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
7 / 46
Postai p´enzt´aros A bemutatott algoritmus egy moh´ o algoritmus, mert mindig a legnagyobb v´alaszthat´ o c´ımletet v´alasztja ki. A moh´ o algoritmus ebben a p´eld´aban optim´alis megold´ast ad.
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
8 / 46
Lev´elfelad´as Feladat Nyugd´ıjasunk szeretne feladni egy levelet, mely 1400 Ft-ba ker¨ ul. Hogyan lehet ezt megtenni, ha a lehet˝ o legkevesebb sz´am´ u b´elyeget szeretn´enk a bor´ıt´ekra tenni.
Megjegyz´es Rendelkez´esre ´all´ o b´elyegc´ımletek: 3.500 Ft 1.000 Ft 700 Ft 340 Ft 210 Ft 100 Ft 10 Ft Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
9 / 46
Lev´elfelad´as Megold´as Ha a moh´o algoritmust haszn´aljuk oly m´ odon, hogy mindig a lehet˝o legnagyobb c´ımlet˝ u b´elyeget ragasztjuk fel, akkor az al´abbi megold´ast kapjuk: 0 db 3.500 Ft-os = 0 Ft 1 db 1.000 Ft-os = 1.000 Ft 0 db 700 Ft-os = 0 Ft 1 db 340 Ft-os = 340 Ft 0 db 210 Ft-os = 0 Ft 0 db 100 Ft-os = 0 Ft 6 db 10 Ft-os = 60 Ft 1.400 Ft-os Az algoritmus szerint 8 db b´elyegre van sz¨ uks´eg¨ unk.
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
10 / 46
Lev´elfelad´as Megold´as elemz´ese K¨onnyen l´athat´ o, hogy a moh´ o algoritmus ´altal adott megold´as most nem optim´alis. Az optim´alis megold´as 2 db 700 Ft-os b´elyeg v´alaszt´asa lenne.
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
11 / 46
Tartalom 1
P´enzkifizet´es
2
0-1 h´atizs´ak probl´ema
3
Moh´o algoritmusok a dinamikus programoz´assal szemben
4
Moh´o strat´egia
5
¨ Utemez´ esi feladatok Esem´eny kiv´alaszt´asi probl´ema Esem´eny elk¨ ul¨ on´ıt´esi probl´ema ¨ Utemez´ es k´es´es minimaliz´al´assal
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
12 / 46
0-1 h´atizs´ak probl´ema Vizsg´aljuk meg, hogy a dinamikus programoz´asn´al megismert 0-1 h´atizs´ak probl´ema megoldhat´ o-e moh´ o strat´egi´aval.
A probl´ema megfogalmaz´asa Adott n darab t´argy Az i-edik t´argy ´ert´eke: pi Az i-edik t´argy s´ ulya: wi Kiv´alasztand´ o a t´argyak olyan r´eszhalmaza, melyek ´ert´ek´enek ¨osszege a lehet˝o legnagyobb, mik¨ ozben a s´ ulyuk ¨ osszege nem haladja meg a h´atizs´ak c kapacit´as´at.
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
13 / 46
0-1 h´atizs´ak probl´ema Megold´as moh´o algoritmussal Els˝o k¨ orben el kell d¨ onten¨ unk, hogy milyen jellemz˝ o alapj´an akarunk moh´o strat´egi´at folytatni: ´ ek alapj´an Ert´ S´ uly alapj´an ´ ek/s´ Ert´ uly ar´any alapj´an Tekints¨ uk pl. az ´ert´ek/s´ uly ar´any alap´ u megk¨ ozel´ıt´est. Legyenek a t´argyak ´ert´ek/s´ uly ar´any alapj´an cs¨ okken˝ o m´ odon rendezettek, azaz p2 pn p1 ≥ ≥ ... ≥ . w1 w2 wn
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
14 / 46
0-1 h´atizs´ak probl´ema Pszeudok´od Bemenet: p − eg´ esz t¨ omb, w − eg´ esz t¨ omb, n − eg´ esz (t¨ omb m´erete), c − eg´ esz Kimenet: S − eg´ esz halmaz ´ 0-1Ha ´ tizsa ´ k(p, w , n, c) f¨ uggv´ eny Moho S ←∅ i ←1 ciklus am´ıg (c > 0) ∧ (i ≤ n) ha w [i] ≤ c akkor S ← S ∪ {i} c ← c − w [i] el´ agaz´ as v´ ege i ←i +1 ciklus v´ ege vissza S f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
15 / 46
0-1 h´atizs´ak probl´ema Optim´alis megold´ast ad a moh´o strat´egia? Tekints¨ uk az al´abbi p´eld´at: H´arom t´argyunk van: p1 = 60, w1 = 10; p2 = 100, w2 = 20; p3 = 120, w3 = 30. A h´atizs´akunk m´erete c = 50 egys´egnyi. A moh´o strat´egia alapj´an az 1. ´es 2. t´argyat fogjuk kiv´alasztani, ´ıgy tele rakjuk a zs´akot ´es ¨ osszesen 160 ´ert´ek˝ u t´argyat visz¨ unk el. Ha viszont a 2. ´es 3. vagy ak´ar az 1. ´es 3. v´alasztottuk volna, akkor a zs´akunkba azok is bef´ern´enek, de nagyobb lenne az elvitt ´ert´ek. A moh´o strat´egia itt nem ad optim´alis megold´ast!
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
16 / 46
Tartalom 1
P´enzkifizet´es
2
0-1 h´atizs´ak probl´ema
3
Moh´o algoritmusok a dinamikus programoz´assal szemben
4
Moh´o strat´egia
5
¨ Utemez´ esi feladatok Esem´eny kiv´alaszt´asi probl´ema Esem´eny elk¨ ul¨ on´ıt´esi probl´ema ¨ Utemez´ es k´es´es minimaliz´al´assal
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
17 / 46
Kincsek begy˝ujt´ese Feladat Egy t´eglalap eg´esz koordin´at´aj´ u r´acspontjaiban k¨ ul¨ onb¨oz˝o ´ert´ek˝ u kincsek vannak elhelyezve. Menj¨ unk el a bal als´ o r´acspontb´ ol a jobb fels˝ o r´acspontba u ´gy, hogy k¨ozben a lehet˝o legt¨ obb kincset gy˝ ujtj¨ uk be! Bej´ar´asunk sor´an csak jobbra ´es felfel´e haladhatunk.
Sergy´ an (OE NIK AII)
1
5
3
6
11
2
15
1
6
10
20
9
1
3
4
8
Programoz´ as I.
2014. december 1.
18 / 46
Megold´as dinamikus programoz´assal Egy mez˝oig o¨sszegy˝ujthet˝o kincsek maxim´alis ´ert´eke C [i, j], ha i = 1 ´es j F [i, j − 1] + C [i, j], ha i = 1 ´es j F [i, j] = F [i − 1, j] + C [i, j], ha i ≥ 2 ´es j max {F [i − 1, j], F [i, j − 1]} + C [i, j], ha i ≥ 2 ´es j 1
5
3
6
19
39
55
61
11
2
15
1
18
20
52
53
6
10
20
9
7
17
37
46
1
3
4
8
1
4
8
16
C
Sergy´ an (OE NIK AII)
= 1, ≥ 2, = 1, ≥ 2.
F
Programoz´ as I.
2014. december 1.
19 / 46
¨ Osszegy˝ ujt¨ott kincsek o¨sszege (Dinamikus programoz´as) Pszeudok´od Bemenet: C − eg´ esz t¨ omb, m − eg´ esz (C sorainak sz´ ama), n − eg´ esz (C oszlopainak sz´ ama) Kimenet: F − eg´ esz t¨ omb ¨ f¨ uggv´ eny KincsOsszeg(C , m, n) ´trehoz(eg´ F ← Le esz)[m, n] F [1, 1] = C [1, 1] ciklus j ← 2-t˝ ol n-ig F [1, j] = F [1, j − 1] + C [i, j] ciklus v´ ege ciklus i ← 2-t˝ ol m-ig F [i, 1] = F [i − 1, 1] + C [i, j] ciklus v´ ege ciklus i ← 2-t˝ ol m-ig ciklus j ← 2-t˝ ol n-ig F [i, j] = max (F [i − 1, j], F [i, j − 1]) + C [i, j] ciklus v´ ege ciklus v´ ege vissza F f¨ uggv´ eny v´ ege Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
20 / 46
Bej´ar´asi u´t kiolvas´asa Pszeudok´od Bemenet: F − eg´ esz t¨ omb, m − eg´ esz (F sorainak sz´ ama), n − eg´ esz (F oszlopainak sz´ ama) Kimenet: P − eg´ esz t¨ omb ´ ´ ra ´ siUtKiolvas(F f¨ uggv´ eny Beja , m, n) ´trehoz(eg´ P ← Le esz)[m + n − 1] i ← m; j ← n; k ← m + n − 1 ciklus am´ıg (i ≥ 2) ∧ (j ≥ 2) P[k] ← (i, j); k ← k − 1 ha F [i − 1, j] > F [i, j − 1] akkor i ←i −1 k¨ ul¨ onben j ←j −1 el´ agaz´ as v´ ege ciklus v´ ege ciklus am´ıg i ≥ 2 P[k] ← (i, j); k ← k − 1; i ← i − 1 ciklus v´ ege ciklus am´ıg j ≥ 2 P[k] ← (i, j); k ← k − 1; j ← j − 1 ciklus v´ ege P[1] ← (1, 1) vissza P f¨ uggv´ eny v´ ege Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
21 / 46
Bej´ar´asi u´t Egy optim´alis bej´ar´asi u´t dinamikus programoz´assal 1
5
3
6
19
39
55
61
19
39
55
61
11
2
15
1
18
20
52
53
18
20
52
53
6
10
20
9
7
17
37
46
7
17
37
46
1
3
4
8
1
4
8
16
1
4
8
16
C
Sergy´ an (OE NIK AII)
F
Programoz´ as I.
F
2014. december 1.
22 / 46
Megold´as moh´o algoritmussal ¨ Otlet Elindulunk a bal als´ o sarokb´ ol. Megvizsg´aljuk, hogy a jobb- vagy a fels˝ o szomsz´ed ´ert´eke nagyobb-e, ´es arra megy¨ unk tov´abb.
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
23 / 46
Megold´as moh´o algoritmussal Pszeudok´od Bemenet: C − eg´ esz t¨ omb, m − eg´ esz (C sorainak sz´ ama), n − eg´ esz (C oszlopainak sz´ ama) Kimenet: P − eg´ esz t¨ omb ´ KincsGyu ˝ jte ´s(C , m, n) f¨ uggv´ eny Moho ´trehoz(eg´ P ← Le esz)[m + n − 1] i ← 1; j ← 1; k ← 0 ciklus am´ıg (i < m) ∧ (j < n) k ← k + 1; P[k] ← (i, j) ha C [i + 1, j] > C [i, j + 1] akkor i ←i +1 k¨ ul¨ onben j ←j +1 el´ agaz´ as v´ ege ciklus v´ ege ciklus am´ıg i < m k ← k + 1; P[k] ← (i, j); i ← i + 1 ciklus v´ ege ciklus am´ıg j < n k ← k + 1; P[k] ← (i, j); j ← j + 1 ciklus v´ ege k ← k + 1; P[k] ← (i, j) vissza P f¨ uggv´ eny v´ ege Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
24 / 46
Bej´ar´as moh´o algoritmussal Eredm´eny
Sergy´ an (OE NIK AII)
1
5
3
6
11
2
15
1
6
10
20
9
1
3
4
8
Programoz´ as I.
2014. december 1.
25 / 46
Lehets´eges bej´ar´asi u´tvonalak (1, 1)
(1, 2)
(1, 3)
(1, 4)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 1)
(3, 2)
(3, 3)
(3, 4)
(4, 1)
(4, 2)
(4, 3)
(4, 4)
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
26 / 46
Tartalom 1
P´enzkifizet´es
2
0-1 h´atizs´ak probl´ema
3
Moh´o algoritmusok a dinamikus programoz´assal szemben
4
Moh´o strat´egia
5
¨ Utemez´ esi feladatok Esem´eny kiv´alaszt´asi probl´ema Esem´eny elk¨ ul¨ on´ıt´esi probl´ema ¨ Utemez´ es k´es´es minimaliz´al´assal
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
27 / 46
Moh´o strat´egia A moh´ o algoritmus egy probl´ema optim´alis megold´as´at u ´gy alkotja meg, hogy v´alaszt´asok sorozat´at hajtja v´egre. Minden d¨ ont´esi pontban azt az esetet v´alasztja az algoritmus, mely az adott pillanatban ´eppen optim´alisnak t˝ unik. K´et fontos alkot´ oeleme van az olyan probl´em´aknak, melyek moh´o algoritmussal megoldhat´ ok: Moh´ o-v´ alaszt´ asi tulajdons´ ag Optim´ alis r´eszstrukt´ ur´ ak tulajdons´ ag
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
28 / 46
Moh´o-v´alaszt´asi tulajdons´ag Glob´alis optim´alis tulajdons´ag el´erhet˝ o lok´alis optimum v´alaszt´as´aval Itt van k¨ ul¨ onbs´eg a moh´ o algoritmusok ´es a dinamikus programoz´ as k¨ oz¨ ott Dinamikus programoz´ asn´ al minden l´ep´esben v´ alasztunk, de a v´ alaszt´ as f¨ ugg(het) a r´eszprobl´em´ ak megold´ as´ at´ ol. Moh´ o esetben viszont az adott pillanatban legjobbnak t˝ un˝ o v´ alaszt´ ast hajtjuk v´egre, majd ut´ ana oldjuk meg a v´ alaszt´ as hat´ as´ ara fell´ep˝ o r´eszprobl´em´ akat. A dinamikus programoz´ as alulr´ ol-felfel´e haladva ad megold´ ast, a moh´ o strat´egia viszont fel¨ ulf˝ ol-lefel´e halad, ´ıgy egym´ as ut´ an v´egrehajt moh´ o v´ alaszt´ asokat, melyekkel folyamatosan reduk´ alja a probl´ema m´eret´et.
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
29 / 46
Optim´alis r´eszstrukt´ur´ak tulajdons´ag Egy probl´ema teljes´ıti az optim´alis r´eszstrukt´ ura tulajdons´agot, ha az optim´alis megold´as fel´ep´ıthet˝ o a r´eszprobl´em´ak optim´alis megold´as´ab´ol. Ez az alkot´ oelem kulcsfontoss´ag´ u, mind a dinamikus programoz´as, mind a moh´ o strat´egia alkalmazhat´ os´ag´anak vizsg´alat´an´al.
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
30 / 46
Tartalom 1
P´enzkifizet´es
2
0-1 h´atizs´ak probl´ema
3
Moh´o algoritmusok a dinamikus programoz´assal szemben
4
Moh´o strat´egia
5
¨ Utemez´ esi feladatok Esem´eny kiv´alaszt´asi probl´ema Esem´eny elk¨ ul¨ on´ıt´esi probl´ema ¨ Utemez´ es k´es´es minimaliz´al´assal
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
31 / 46
Tartalom 1
P´enzkifizet´es
2
0-1 h´atizs´ak probl´ema
3
Moh´o algoritmusok a dinamikus programoz´assal szemben
4
Moh´o strat´egia
5
¨ Utemez´ esi feladatok Esem´eny kiv´alaszt´asi probl´ema Esem´eny elk¨ ul¨ on´ıt´esi probl´ema ¨ Utemez´ es k´es´es minimaliz´al´assal
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
32 / 46
Esem´eny kiv´alaszt´asi probl´ema Er˝oforr´as u ¨temez´est szeretn´enk megval´ os´ıtani egym´assal verseng˝o feladatok k¨oz¨ott.
Feladat megfogalmaz´asa Adott esem´enyek egy S = {1, 2, . . . , n} halmaza, amelyek egy k¨oz¨os er˝ oforr´ast k´ıv´annak haszn´alni Minden esem´enyre ismert a kezd˝ o id˝ opontja: si a befejez˝ o id˝ opontja: fi (ahol si ≤ fi )
Ha az i esem´enyt kiv´alasztjuk, az esem´eny az [si , fi [ intervallumot foglalja el Az i ´es j esem´enyek kompatibilisek, ha az [si , fi [ ´es [sj , fj [ intervallumok nem fedik egym´ast, azaz si ≥ fj vagy sj ≥ fi Kiv´alasztand´ o k¨ olcs¨ on¨ osen kompatibilis esem´enyeknek egy legnagyobb elemsz´am´ u halmaza
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
33 / 46
Esem´eny kiv´alaszt´asi probl´ema Megold´as Tegy¨ uk fel, hogy az esem´ enyek a befejez˝ o id˝ opontjaik szerint rendezettek, azaz f1 ≤ f2 ≤ . . . ≤ fn Bemenet: s − id˝ o t¨ omb, f − id˝ o rendezett t¨ omb, n − eg´ esz (t¨ omb¨ ok m´ erete) Kimenet: A − eg´ esz halmaz ´nyKiva ´ laszta ´ s(s, f , n) f¨ uggv´ eny Eseme A ← {1} utols´ o←1 ciklus i ← 2-t˝ ol n-ig ha s[i] ≥ f [utols´ o] akkor A ← A ∪ {i} utols´ o←i el´ agaz´ as v´ ege ciklus v´ ege vissza A f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
34 / 46
Esem´eny kiv´alaszt´asi probl´ema P´elda 1 2 3 4 5 6 7 8 9 10 11 0
1
2
Sergy´ an (OE NIK AII)
3
4
5
6
7 Programoz´ as I.
8
9
10
11
12
13
2014. december 1.
14 35 / 46
Esem´eny kiv´alaszt´asi probl´ema P´elda megold´asa 1 2 3 4 5 6 7 8 9 10 11 0
1
2
Sergy´ an (OE NIK AII)
3
4
5
6
7 Programoz´ as I.
8
9
10
11
12
13
2014. december 1.
14 36 / 46
Esem´eny kiv´alaszt´asi probl´ema Optim´alis megold´ast ad a moh´o algoritmus? 1
A moh´o algoritmus kiv´alasztja az 1 esem´enyt. Ez az esem´eny biztos benne van az optim´alis megold´asban is? Tegy¨ uk fel, hogy A ⊂ S egy optim´ alis megold´ as, ´es legyenek az A-beli esem´enyek a befejez´esi id˝ o szerint rendezettek. Tegy¨ uk fel, hogy A-ban az els˝ o esem´eny k. Ha k = 1, akkor A a moh´ o v´ alaszt´ assal kezd˝ odik. Ha k 6= 1, akkor legyen B = (A \ {k}) ∪ {1}. Mivel f1 ≤ fk , ´ıgy a B-beli esem´enyek nem ´ atfed˝ ok, ´es B ugyanannyi elemet tartalmaz, mint A, ´ıgy B is optim´ alis. Teh´ at mindig l´etezik olyan optim´ alis u ¨temez´es, mely a moh´ o v´ alaszt´ assal kezd˝ odik.
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
37 / 46
Esem´eny kiv´alaszt´asi probl´ema Optim´alis megold´ast ad a moh´o algoritmus? 2
Az 1 esem´eny moh´ o v´alaszt´asa ut´an a probl´ema reduk´al´odik azon esem´eny kiv´alaszt´asi probl´em´ara, amely az S halmaz azon elemeit tartalmazza, amelyek kompatibilisek az 1 esem´ennyel. K´erd´es, hogy A0 = A \ {1} optim´ alis megold´ asa-e az S 0 = {i ∈ S : si ≥ f1 } esem´enyeket tartalmaz´ o probl´em´ anak. Ha tal´ aln´ ank olyan B 0 megold´ as´ at az S 0 probl´em´ anak, amely t¨ obb esem´enyt tartalmazna, mint A0 , akkor az 1 esem´enyt hozz´ aadva B 0 -h¨ oz az S probl´ema olyan B megold´ as´ ahoz jutn´ ank, amely t¨ obb esem´enyt tartalmaz, mint A. Ez viszont ellentmond A optimalit´ as´ anak. Teh´ at minden moh´ o v´ alaszt´ as ut´ an olyan probl´em´ ank marad, mint amilyen az eredeti is volt.
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
38 / 46
Tartalom 1
P´enzkifizet´es
2
0-1 h´atizs´ak probl´ema
3
Moh´o algoritmusok a dinamikus programoz´assal szemben
4
Moh´o strat´egia
5
¨ Utemez´ esi feladatok Esem´eny kiv´alaszt´asi probl´ema Esem´eny elk¨ ul¨ on´ıt´esi probl´ema ¨ Utemez´ es k´es´es minimaliz´al´assal
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
39 / 46
Esem´eny elk¨ul¨on´ıt´esi probl´ema Feladat megfogalmaz´asa Adott n darab esem´eny, melyeknek ismerj¨ uk a kezd´esi ´es befejez´esi id˝opontj´at. (Az i-edik esem´eny kezd˝ o id˝ opontja: si , befejez´esi id˝ opontja pedig: fi .) K¨ ul¨on´ıts¨ uk el az esem´enyeket oly m´ odon el˝ oad´ o termekbe, hogy az egy el˝oad´ o terembe tartoz´ o esem´enyek kompatibilisek legyenek egym´assal, viszont a lehet˝o legkevesebb el˝ oad´ o termet haszn´aljuk.
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
40 / 46
Esem´eny elk¨ul¨on´ıt´esi probl´ema Egy p´elda 5 3
10
4
7
2
8
1 9
9:30
6 10
10:30
11
11:30
12
12:30
13
13:30
9 14
14:30
15
15:30
16
16:30
16
16:30
Kevesebb el˝oad´o terem is el´eg lenne 3
5
8
2 1 9
9:30
7 6
4 10
10:30
Sergy´ an (OE NIK AII)
11
11:30
12
12:30
13
13:30
Programoz´ as I.
10 9 14
14:30
15
15:30
2014. december 1.
41 / 46
Esem´eny elk¨ul¨on´ıt´esi probl´ema Algoritmus Tegy¨ uk fel, hogy az esem´ enyek a kezd˝ o id˝ opontjaik szerint rendezettek, azaz s1 ≤ s2 ≤ . . . ≤ sn . Bemenet: s − id˝ o rendezett t¨ omb, f − id˝ o t¨ omb, n − eg´ esz (t¨ omb¨ ok m´ erete) Kimenet: A − eg´ esz t¨ omb ´ ¨ ¨ ´ ´ f¨ uggv´ eny EsemenyElkulonıtes(s, f , n) ´trehoz(eg´ A ← Le esz)[n] utols´ o←0 ciklus i ← 1-t˝ ol n-ig j ←1 ´nyEro ˝ forra ´ ssal(A, s, f , i, j) ciklus am´ıg (j ≤ utols´ o) ∧ ¬KompatiblisEseme j ←j +1 ciklus v´ ege ha j ≤ utols´ o akkor A[i] ← j k¨ ul¨ onben utols´ o ← utols´ o+1 A[i] ← utols´ o el´ agaz´ as v´ ege ciklus v´ ege vissza A f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
42 / 46
Tartalom 1
P´enzkifizet´es
2
0-1 h´atizs´ak probl´ema
3
Moh´o algoritmusok a dinamikus programoz´assal szemben
4
Moh´o strat´egia
5
¨ Utemez´ esi feladatok Esem´eny kiv´alaszt´asi probl´ema Esem´eny elk¨ ul¨ on´ıt´esi probl´ema ¨ Utemez´ es k´es´es minimaliz´al´assal
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
43 / 46
¨ Utemez´ es k´es´es minimaliz´al´assal Feladat Adottak egyetlen er˝ oforr´ast ig´enyl˝ o feladatok Ismerj¨ uk az i-edik feladat elv´egz´es´ehez sz¨ uks´eges ti id˝ot, illetve a feladat di hat´aridej´et Az i-edik feladat k´es´ese: li = max{0, fi − di } C´el: minimaliz´alni a k´es´esek maximum´at, azaz minimaliz´alni a max{li }i=1,...,n kifejez´est
P´elda ti di
1 3 6
2 2 8
3 1 9
4 4 9
5 3 14
6 2 15 k´ es´ es = 2
d3 = 9 0
d2 = 8 1
2
d6 = 15 3
Sergy´ an (OE NIK AII)
4
d1 = 6 5
6
k´ es´ es = 0
max k´ es´ es = 6
d5 = 14 7
8
Programoz´ as I.
9
10
d4 = 9 11
12
13
14
2014. december 1.
15
44 / 46
¨ Utemez´ es k´es´es minimaliz´al´assal Algoritmus Tegy¨ uk fel, hogy az esem´ enyek a hat´ aridej¨ uk szerint rendezettek, azaz d1 ≤ d2 ≤ . . . ≤ dn Bemenet: d − id˝ o rendezett t¨ omb, t − id˝ o t¨ omb, n − eg´ esz (t¨ omb¨ ok m´ erete) Kimenet: s − id˝ o t¨ omb, f − id˝ o t¨ omb ´se ´sMinimaliza ´ la ´ s(d, t, n) f¨ uggv´ eny Ke ´trehoz(id˝ s ← Le o)[n] ´trehoz(id˝ f ← Le o)[n] utols´ o←0 ciklus i ← 1-t˝ ol n-ig s[i] ← utols´ o f [i] ← s[i] + t[i] utols´ o ← f [i] ciklus v´ ege vissza (s, f ) f¨ uggv´ eny v´ ege
Megold´as max k´ es´ es = 1 d1 = 9 0
1
d2 = 8 2
3
Sergy´ an (OE NIK AII)
4
d3 = 9 5
d4 = 9 6
7
8
Programoz´ as I.
d5 = 14 9
10
11
12
d6 = 15 13
14
2014. december 1.
15
45 / 46
Felhaszn´alt irodalom T.H. Cormen, C.E. Leiserson, R.L. Rivest: Algoritmusok. M˝ uszaki K¨ onyvkiad´ o, 1999 ´ Tardos: Algorithm Design. (El˝ J. Kleinberg, E. oad´as prezent´aci´ok)
Sergy´ an (OE NIK AII)
Programoz´ as I.
2014. december 1.
46 / 46
