Korlátozás és szétválasztás elve ADAGOLO adattípus Értékhalmaz: E Adagolo : A ⊆ E M˝uveletek: A : Adagolo, x : E / • {Igaz} Letesit(A) {A = 0} • {A = A} Megszuntet(A) {Igaz} / • {A = A} Uresit(A) {A = 0} • {A = A} Betesz(A,x) {A = Pre(A) ∪ {x}} / Kivesz(A,x) {x ∈ Pre(A) ∧ Pre(A) = A ∪ {x}} • {A 6= 0} • {A = A} Elemszam(A) {Elemszam = |A|} Közös általánosítása a sornak, veremnek és prioritási sornak. Tesz˝oleges kivételi szabállyal lehet egy speciális adattípust kapni bel˝ole. Korlátozó függvény Egy általános algoritmust adunk meg, ami egy minimalizálási problémán m˝uködik, ahol z a célfüggvény. Az algoritmus használ egy AK korlátozó függvényt, amelyre a következ˝o tulajdonság teljesül. Minden X pontjára a megoldástért leíró fának fennáll, hogy AK(X) ≤ z(Y ) az összes Y megoldásra, amely leszármazottja X-nek a fában. Az AK függvény azért hasznos, mert amennyiben már van egy megoldásunk, aminek a célfüggvényértéke OPTERT, akkor azokat a részfákat,a melyek X gyökerére AK(X) ≥ OPT ERT nem kell bejárnunk, mert biztosan nem tartalmaznak jobb megoldást. KorlatValaszt(F) OPT:=Nil OPTERT:=Inf Letesit(A:Adagolo) If F=Nil Then return //Üres fa If Megoldas(F) Then If z(F)
1
A feladatspecifikus algoritmushoz a következ˝o részletek megadása szükséges • megoldástér és az azt leíró fa • korlátozó függvény (hatékonyan számítható, de elég éles) • az adagoló kivételi szabályának megadása Az algoritmus gyorsítása A korlátozó függvény hatékonysága attól is függ mennyire jó az aktuálisan ismert legjobb megoldásunk az OPT változóban. Így az algoritmus gyorsítása érdekében szokás az egész eljárást egy heurisztikus algoritmussal kezdeni, és az általa kapott lehetséges megoldást elhelyezni az OPT változóban. Bizonyos alkalmazásokban el˝ofordulhat, hogy az alsó korlát számítása során egyéb (a vizsgált ponttól különböz˝o) lehetséges megoldást is meghatározunk. Ilyenkor szokás, ezeket a megoldásokat is felhasználni az aktuálisan ismert legjobb megoldás javítására. Szétválasztási függvény A korlátozás és szétválasztás módszerét gyakran egy korlátozó függvény és egy szétválasztó függvény által definiálják. A szétválasztó függvény a megoldástér részhalmazain definiált. Minden részhalmazhoz az adott halmaz egy partícióját rendeli hozzá. A szétválasztási függvény a megoldástér fa reprezentációjának felel meg. A szétválasztási függvényb˝ol a következ˝oképpen kapjuk meg a megoldástért leíró fát. A részhalmazok a fa részfáinak felelnek meg, egy adott részhalmaz felbontása a neki megfelel˝o részfa további részfákra bontását jelenti. Optimális pénzváltás Az optimális 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 minimális elemszámú S halmazát, amelyre teljesül, hogy ∑i∈S pi = E. 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, Megoldás és AK 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
k
n
∑ pi j ≤ E ∧ ∑ pi j + ∑
j=1
p j ≥ E.
j=ik +1
j=1
Továbbá Megoldas(i1 , . . . , ik ) = True akkor és csak akkor, ha ∑kj=1 pi j = E Az AK függvény meghatározásához feltesszük, hogy a pénzérmék érték szerint nemnövekv˝o sorrendbe vannnak rendezve. Ekkor 2
k
AK(i1 , . . . , ik ) = k + d(S − ∑ pi j )/pik +1 e. j=1
Példa A váltópénzek 5, 4, 4, 2, 1 a felváltandó összeg 8. Az ADAGOLO egy fels˝o korlát szerinti minimumos prioritási sor. A két db 4 forintost megkülönböztetjük, az egyiket, amelyiket a sorban el˝ore vesszünk 40 jelöli. • Az ADAGOLO-ba az (5), (4’) megoldáskezdemények kerülnek be. Ekkor OPT ERT (legjobb ismert megoldás) értéke végtelen. Az ADAGOLO-ban a függvényértékek AK((5)) = 1 + d(8 − 5)/4e = 2, FK((5)) = 1 + d(8 − 5)/1e = 4 AK((40 )) = 1 + d(8 − 4)/4e = 2, FK((40 )) = 1 + d(8 − 4)/1e = 5. • Az FK szerinti minimumos sor az (5) kezdeményt adja ki. • Az ADAGOLO-ba az (5, 2) megoldáskezdemény kerül be. Erre AK((5, 2)) = 2+d(8−7)/1e = 3, FK((5, 2)) = 1 + d(8 − 7)/1e = 3. • Az FK szerinti minimumos sor az (5, 2) kezdeményt adja ki. • Az ADAGOLO-ba egyetlen megoldáskezdemény kerül be az (5, 2, 1), erre AK(5, 2, 1) = FK(5, 2, 1) = 3, és találtunk egy megoldást. Az aktuális optimális megoldás (5, 2, 1) a hozzá tartozó GFK érték 3. • Az FK szerinti minimumos sor az (5, 2, 1) kezdeményt adja ki, nem kerül új elem az ADAGOLO-ba. • Az FK szerinti minimumos sor a (40 ) kezdeményt adja ki. • Az ADAGOLO-ba egyetlen megoldáskezdemény kerül be (40 4), találunk egy megoldást a (40 , 4) megoldást. Ezt megjegyezzük, és GFK = 2. • Az FK szerinti minimumos sor az (40 , 4) kezdeményt adja ki, nem kerül új elem az ADAGOLO-ba. • Az ADAGOLO üres, az eljárás véget ér. Maximum feladatok Ha maximum feladatunk van, akkor lehet a célfüggvény -1-szeresét vizsgálni, de megadható az algoritmus maximum feladatra is. A különbség, hogy egy FK fels˝o korlátot kell számolni a pontokra, és azok az ágak zárhatóak le, ahol a fels˝o korlát kisebb, mint OPTERT. KorlatValaszt(F) OPT:=Nil OPTERT:=-Inf Letesit(A:Adagolo) If F=Nil Then return //Üres fa If Megoldas(F) Then If z(F)>OPTERT Then OPTERT:=z(F), OPT:=F Betesz(A,F) While(Elemszam(A)!=0) Kivesz(A,F) p:=F.Elsofiu 3
While (p!=Nil) // a gyerekeken sorbamenve If Megoldas(p) Then If z(p)>OPTERT //ha jobbat talál Then OPTERT:=z(p), OPT:=p If (LehetMego(p) and FK(p)>OPTERT) Then Betesz(A,p) //ha nem zár ki p:=p.Testver Return(OPT) Profit maximalizáló ütemezés A feladatban munkákat kell ütemezni, minden munkának van egy határideje, egy végrehajtási ideje és egy profitja. A cél a lehet˝o legtöbb összprofitot elér˝o munkát elvégezni a határid˝ok betartásával. Lemma: Ha egy munkahalmaznak van határid˝ot tartó ütemezése, akkor az az ütemezés is tartja a határid˝ot, amely a munkákat növekv˝o határid˝o szerint hajtja végre. Bizonyítás Vegyük a halmaznak azt a határid˝o tartó megoldást, amelynek a leghosszabb kezd˝oszelete határid˝o szerint növekv˝o. Ha nem a teljes halmaz határid˝o szerinti, akkor az els˝o eltérésnél hozzuk el˝ore azt a j munkát, amelynek a legkorábbi a határideje. Az így kapott sorrend is határid˝ot tartó, mivel a hátrább kerül˝o munkák legkés˝obb j eredeti befejezési idejében fejez˝odnek be, ami kisebb, mint j határideje, így kisebb az adott munka határidejénél is. Következésképpen feltehetjük, hogy a kiválasztott munkahalmazt mindig növekv˝o határid˝o szerint ütemezzük, és feltesszük azt is, hogy eleve ilyen sorrendben lettek megadva. Ekkor a megoldástérben csak a munkák részhalmazait kell vizsgálni. Így a megoldástér pontjait a munkák indexeinek olyan S ⊆ {1, . . . , n} halmazának X = (i1 , . . . , ik ) növekv˝o felsorolásáként reprezentáljuk. 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 függvény megadja, hogy az eddig kiválasztott munkák határid˝o szerinti sorrendben tartják- e a j határid˝oket. Azaz LehetMego(i1 , . . . , ik ) akkor és csak akkor igaz, ha ∀ j = 1, . . . , k esetén ∑r=1 ir .vegreha jtido ≤ i j .hatarido. Az FK korlátozó függvényhez feltesszük, hogy minden még nem eldöntött munkát ütemezünk, így FK(i1 , . . . , ik ) = (∑kr=1 ir .pro f it + ∑nr=ik +1 ir .pro f it).
Hátizsák feladat
Egy adott hátizsákba tárgyakat akarunk pakolni. Adott n tárgy minden tárgynak van egy fontossági értéke ( f [i]), és egy súlya (s[i]), a hátizsákba maximum összesen S súlyt pakolhatunk. Szeretnénk úgy választani tárgyakat, hogy az összfontosság maximális legyen. Tehát feladatunk, hogy kiválasszuk a tárgyaknak olyan halmazai közül, amelyekre az összsúly nem haladja meg S-t azt, amelyre maximális az összfontosság. A megoldás itt is az elemek egy részhalmaza, így a megoldástér pontjait (a tárgyak részhalmazát) a tárgyak indexeinek az S ⊆ {1, . . . , n} halmazának X = (i1 , . . . , ik ) növekv˝o felsorolásáként reprezentálhatjuk. 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. 4
Apa(i1 , . . . , ik−1 , ik ) = (i1 , . . . , ik−1 ), ha k ≥ 1 és Nil egyébként. Korlátozó függvény A megoldástér egy adott X = (i1 , . . . , ik ) pontjában az adott részfában az 1, . . . , ik tárgyakra már meghoztuk a döntést. Az eddig elért haszon ∑kj=1 fi j a felhasznált súly a kapacitásból ∑kj=1 si j , így a hátralev˝o (ik + 1, . . . , n) tárgyakhoz S − ∑kj=1 si j kapacitás marad. Következésképpen ahhoz, hogy a részfában az optimális megoldást megtaláljuk meg kell oldanunk egy kisebb hátizsák feladatot. A hátizsák feladat megoldása helyett egy relaxált változatot oldunk meg a töredékes hátizsák feladatot, amelyben a tárgyaknak részeit is be lehet rakni a hátizsákba, ez nyilvánvalóan fels˝o korlátot ad az eredeti feladat optimális célfüggvényértékére. Másrészt ez a korlátozó függvény hatékonyan számítható, mivel a mohó algoritmus (ami haszon/súly érték alapján veszi be a tárgyakat) optimális megoldást ad rá. Érdemes megjegyezni, hogy ez a függvény speciális esete annak a gyakran használt módszernek, ahol egy egészérték˝u programozási feladat helyett, azt a lineáris programozási feladatot használjuk korlátnak, ahol nem kötjük ki, hogy a változók egészek. Példa Vegyük a hátizsák problémát, ahol tárgyak (súly, fontosság) párokban A = (4, 6) B = (3, 5) C = (2, 3) D = (2, 3) a hátizsák kapacitása 8. Adagolóként fels˝o korlát szerinti maximum prioritási sort használunk. • Az ADAGOLO-ba az (A), (B) megoldáskezdemények, akik egyben megoldások kerülnek be. Ekkor a OPT ERT (legjobb ismert megoldás) 6. Amikor a (C) és (D) megoldáskezdeményeket vizsgáltuk OPT ERT ≥ FK(C) és OPT ERT ≥ FK(D) állt fenn, így nem kerültek be. Az ADAGOLO-ban a korlátozó függvények FK((A)) = 6 + 5 + 3/2 = 25/2, FK((B)) = 5 + 3 + 3 = 11. • Az FK szerinti maximumos sor az (A) kezdeményt adja ki. • Az (A, B) megoldás, így OPT ERT = 6 + 5 = 11. Az aktuális optimális megoldást felülírjuk. Bekerül az ADAGOLO-ba. A korlát FK((A, B)) = 6 + 5 + 3/2 = 25/2. • Az (A,C) megoldás, és FK(A,C) = 6+3+3 ≥ OPT ERT , így bekerül az ADAGOLO-ba. A korlátok FK((A,C)) = 12. • Az FK szerinti maximumos sor az (A, B) kezdeményt adja ki. • A fiúkra (A, B,C) és (A, B, D) nem LEHETMEGO, így nem kerülnek be az ADAGOLO-ba. • Az FK szerinti maximumos sor az (A,C) kezdeményt adja ki. • A fia (A,C, D) megoldás, így OPT ERT = 6+3+3 = 12. Az aktuális optimális megoldást felülírjuk, a megoldás bekerül az ADAGOLO-ba. • Az FK szerinti maximumos sor az (A,C, D) majd a (B) kezdeményeket adja ki, mindkett˝ore az FK érték nem nagyobb, mint OPT ERT . • Az ADAGOLO üres, az eljárás véget ér.
5
