Rendszeroptimalizálás, 19. tétel

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

<style> ol { margin-top: 0px; } td { padding: 0em 0.4em; text-align: center; } </style>

!! Graham közelítő algoritmusai a P|||C_max és a P||prec||C_max feladatokra (biz. nélkül). A P||prec, p_j=1||C_max feladat, Hu algoritmusa (biz. nélkül). A P₂||prec, p_j=1C_max feladat: Coffman és Graham algoritmusa (biz. nélkül).

P|C_max

Ez már volt a 18. tétel végén.

P|precC_max

• Tétel*: a listás ütemezés (ha van szabad gép, a sorban az első olyan jobot teszem fel rá, ami már elkezdhető) (2-1/m)-approximációs a P|precC_max feladatra is.

P|prec, p_j=1C_max

A feladatosztály bonyolultsága

• P|prec, p_j=1C_max NP-nehéz
• P_m|prec, p_j=1C_max bonyolultsága ismeretlen
• P|prec, p_j=1, in-treeC_max-re a Hu-algoritmus polinom időben optimális megoldást ad.

• Def.*: Az in-tree (be-fenyő) egy olyan irányított gyökeres fa, aminek az élei a gyökér felé vannak irányítva.
  
• Hu-algoritmus*:

1. A precedencia gráf minden csúcsához határozzuk meg a gyökérbe vezető út hosszát.
2. Alkalmazzuk a listás ütemezést úthossz szerint csökkenő sorrendben.

P₂|prec, p_j=1C_max

• Coffman-Graham algoritmus*:

1. Végezzünk a precedencia gráfok tranzitív redukciót: ha ∃a→b él és ettől különböző a→b út, töröljük az élt.
2. Minden csúcshoz hozzárendelünk egy sorszámot és egy listát.
3. A nyelők az 1,2,3,... sorszámokat kapják valamilyen sorrendben, és üres lista tartozik hozzájuk.
4. Amint egy csúcs összes kimenő szomszédjának van sorszáma, kitöltjük a hozzá tartozó listát a kimenő szomszédok sorszámával csökkenő sorrendben.
5. Ha nincs kitölthető lista, a lexikografikusan legkisebb listával rendelkező számozatlan csúcs kapja a következő sorszámot.
6. A csúcs sorszámok szerint csökkenő sorrendben kell listás ütemezést végrehajtani.

• Tétel*: a Coffman-Graham algoritmus optimális ütemezést ad az a P₂|prec, p_j=1C_max feladatra.

• Megj.*: a könyvben el van szúrva a példa, a 4.7a ábra helyesen

A	C	F	G	I
B	D	E	J	H

-- Peti - 2007.01.03.