Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2013-2014‎ > ‎

10. alkalom

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 si kezdési időpontja és fi befejeződési időpontja. (Tehát csak ekkor szabad elvégezni a munkát.)

Intervallum feladatok

Ü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:
  • Legkorábbi kezdet szerint választunk, a rendezés si szerint növekvő;
  • Legkorábbi befejeződés szerint választunk, a rendezés fi szerint növekvő;
  • Legrövidebb feladatot választjuk, a rendezés fi-si 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:
  1. 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
  2. A mohó algoritmus által kiválasztott feladatok legyenek i1, i2, …, ik
  3. Az (egyik) optimális megoldásban kiválasztott feladatok legyenek j1, j2, …, jm, ( k < m )
  4. 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.

Bizonyítás vázlat:
  1. Ha van olyan pillanat, amikor M feladat "él", akkor legalább M processzor kell. Legyen M* a maximális ilyen érték, tehát bármely pillanatban legfeljebb M* feladat van.
  2. M* processzor elég. Rendezzük a munkákat a kezdő időpont szerint, és használjunk M* processzort. Amikor az új munka kezdődik, biztosan lesz szabad processzor, különben nem lenne igaz, hogy egy időben legfeljebb M* munka "él".

További olvasnivaló

Richard Anderson: Greedy algorithms
Paul Beame: Greedy algorithms
T. M. Murali: Greedy algorithms

Feladatok