Efektívne algoritmy a zložitosť - 03 - Greedy algoritmy

Zhrnutie prednášky

Prednáška rozoberá greedy algoritmy na probléme výberu aktivít, kde treba vybrať najväčší počet navzájom sa neprekrývajúcich aktivít. Najprv sa ukáže, že stratégia výberu aktivity s najmenším počtom konfliktov nie je správna, lebo na protipríklade dá 3 aktivity namiesto optimálnych 4. Potom sa predstaví stratégia výberu aktivity, ktorá končí najskôr, s časovou zložitosťou Θ(n log n) dominovanou triedením podľa koncového času. Správnosť algoritmu sa dokazuje matematickou indukciou: pre každé L existuje optimálne riešenie, ktorého prvých L aktivít sa zhoduje s greedy riešením. V indukčnom kroku sa aktivita optimálneho riešenia nahradí greedy aktivitou, ktorá končí skôr, čím vznikne rovnako veľké optimálne riešenie.

• - Problém výberu aktivít: maximalizovať počet navzájom sa neprekrývajúcich aktivít.
• - Heuristika najmenšieho počtu konfliktov je nesprávna, protipríklad dáva 3 namiesto 4 aktivít.
• - Správna greedy stratégia: vždy vybrať aktivitu, ktorá končí najskôr, a zahodiť prekrývajúce sa.
• - Časová zložitosť je Θ(n log n), dominuje triedenie podľa koncového času.
• - Dôkaz správnosti indukciou: existuje optimálne riešenie zhodné s greedy v prvých L výberoch.
• - Indukčný krok: aktivitu O_{L+1} možno nahradiť G_{L+1}, ktorá končí skôr a nevytvára konflikt.
• - Pre L = K greedy riešenie nemožno rozšíriť, a teda je optimálne.

Zhrnutie pripravené s pomocou AI z prepisu videa.