NézetNyomtat

14. óra
Elmélet > Algoritmusok > Mohó
Címkék > Óra

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:
  • 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:
  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 $i_1, i_2, \ldots, i_k$
  3. Az (egyik) optimális megoldásban kiválasztott feladatok legyenek $j_1, j_2,\ldots, j_m, (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.

Ütemezés 3. - Késések és bírságok

Olvasnivaló

Feladatok