14. óra
Mohó algoritmusok
Optimalizálás mohó stratégiával
Optimalizálási feladatok megoldása mohó stratégiával a következőt jelenti: az optimumot lépésenként állítjuk elő, a döntési helyzetekben mindig az aktuálisan legjobbnak látszó lehetőséget választjuk. Az már feladatfüggő, hogy mit értünk legjobb választás alatt.
A mohó algoritmusokat általában könnyű programozni, de
- nem mindig adnak tényleg optimális megoldást,
- és ha igen, azt általában nem triviális bizonyítani.
Intervallumok
Jól tanulmányozható a mohó algoritmusok témaköre az úgynevezett intervallum feladatokon. Ezek olyan problémák, ahol véges számú "munkát" kell elvégezni, (vagy közülük a lehető legtöbbet), feltéve, hogy mindegyiknek ismert az $s_i$ kezdési időpontja és $f_i$ befejeződési időpontja. (Tehát csak ekkor szabad elvégezni a munkát.)
Ütemezés 1. - Maximális számú feladat végrehajtása egy "processzoron"
Legyenek a munkák előadások, amelyek közül a lehető legtöbbet szeretnénk megtartani, de csak egy előadótermünk van, így csak olyan előadások engedhetők meg, amelyek időintervallumai nem metszők. (Az is tisztázandó, hogy a korábbi előadás vége egybeeshet-e a későbbi előadás kezdetével.)
Rendezzük a feladatokat (előadásokat) valahogyan, és válasszuk mindig a következő olyat, ami nem ütközik az eddigiekkel.
Lehetséges mohó választási stratégiák és rendezések:
Lehetséges mohó választási stratégiák és rendezések:
- Legkorábbi kezdet szerint választunk, a rendezés $s_i$ szerint növekvő;
- Legkorábbi befejeződés szerint választunk, a rendezés $f_i$ szerint növekvő;
- Legrövidebb feladatot választjuk, a rendezés $f_i-s_i$ szerint növekvő;
- Legkevesebb ütközés szerint választunk, a rendezés a feladatok ütközési száma szerint növekvő, ahol egy feladat ütközési száma azt jelöli, hogy hány másik feladattal ütközik.
A felsoroltak közül három (1., 3. 4,) rossz!
Bizonyítható viszont, hogy a legkorábbi befejeződés szerinti ütemezés optimális megoldást ad. Az indirekt bizonyítás vázlata:
- Legyen $r$ a legnagyobb szám, amire a mohó algoritmus által adott megoldás első $r$ feladata egyezik az (egyik) optimális megoldás első $r$ feladatával
- A mohó algoritmus által kiválasztott feladatok legyenek $i_1, i_2, \ldots, i_k$
- Az (egyik) optimális megoldásban kiválasztott feladatok legyenek $j_1, j_2,\ldots, j_m, (k < m)$
- Megmutatható, hogy van olyan optimális megoldás is, ahol az első $r+1$ feladat is egyezik, ellentmondás, bizonyítás vége.
Ütemezés 2. - Az összes feladat megoldás minimális számú "processzoron"
Most a legkorábbi kezdet szerinti mohó választás adja az optimumot.
