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:
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:
![]() Ü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. ![]() ![]()
További olvasnivaló
|