6 - Greedy algoritmy

Připomenutí teorie

Letos je téma ještě bez přednášky.

Greedy přístup patří mezi základní algoritmické postupy. Využívá se v optimalizačních úlohách, tedy v úlohách, v nichž máme účelovou funkci a chceme dosáhnout nejlepší hodnoty této funkce. Greedy přístup je charakterizován svou krátkozrakostí a tvrdohlavostí. Řešení úlohy sestavujeme krok po kroku a v každém kroku volíme lokálně nejlepší rozhodnutí. Zároveň se nikdy nemůžeme v řešení vrátit, jakmile jsme jednou učinili rozhodnutí, tak toto rozhodnutí je trvalé.

Mezi greedy algoritmy patří například Primův algoritmus pro nalezení minimální kostry v grafu. Pro připomenutí, Primův algoritmus sestavuje minimální kostru tak, že začne od libovolného vrcholu, položí jej jako základ stromu (budoucí kostry) a v každém kroku připojí nejlevnější hranu, jež vede ze stromu ven (tedy propojuje jeden z vrcholů stromu s vrcholem mimo strom).

Aby bylo možné sestavit greedy algoritmus, který problém vyřeší optimálně, tak problém musí splňovat následující 2 vlastnosti:

Optimální řešení celého problému lze sestavit z optimálních řešení podproblémů (optimal substructure).
Optimální řešení celého problému lze sestavit pomocí sekvence lokálně optimálních (greedy) rozhodnutí (Greedy choice property).

Zasazení do kontextu

Greedy algoritmy jsou jedním ze tří významných algoritmických postupů využívající vlastnosti optimálních podproblémů (optimal substructure). Tento princip je základem také dynamického programování a přístupu "rozděl a panuj" (divide and conquer).

Zásadní rozdíl mezi greedy přístupem a dynamickým programováním spočívá v tom, že greedy algoritmy nejdříve učiní rozhodnutí a poté řeší podproblém, který zůstal z celého problému po tomto rozhodnutí. Oproti tomu dynamické programování nejdříve řeší podproblémy a až na základě znalosti jejich výsledků činí rozhodnutí.

Řešené úlohy

Interval Scheduling / Activity Selection Problem

Řešená úloha 1: Máme na výběr \(n\) aktivit, každá z nich někdy začíná a trvá určitou dobu. Chceme naplánovat náš denní rozvrh, abychom stihli co nejvíce aktivit.

Formálně máme množinu aktivit \(A = \{a_i \, | \, 1 \leq i \leq n \}\). Každá aktivita \(a_i\) má čas začátku \(s(a_i)\) a čas konce \(f(a_i)\). Chceme vybrat, co největší podmnožinu množiny \(A\) tak, aby se vybrané aktivity nepřekrývaly.

Jaký greedy postup by mohl vést k optimálnímu řešení?

Řešení

Earliest start time first

Toto pravidlo v některých případech nenajde optimální řešení, například:

Shortest duration first

Toto pravidlo v některých případech nenajde optimální řešení, například:

Fewest conflicts first

Toto pravidlo v některých případech nenajde optimální řešení, například:

Earliest deadline first

Ano, volit nejdříve končící aktivitu je skutečně správný postup.

Pseudokód takového postupu by mohl vypadat například takto:

Let A be a list of all activities
Let B be an empty list
Sort the activities in a non-decreasing order by f[i]

Add the first activity to B
For i = 2, ..., n:
  If s[i] >= f[B[-1]]:
    Add i to B
End for

Return the list of planned activities B

Nyní ještě musíme dokázat, že tento postup skutečně vede k optimálnímu řešení.

Nápověda

Seřaďme aktivity od nejdříve končící a zkusme použít indukci.

Důkaz

Pro dokazování optimality greedy algoritmů se používají dva dominantní přístupy. Prvním z nich je "greedy stays ahead" přístup a my si jej ukážeme na tomto příkladu. "Greedy stays ahead" přístup využívá indukci, aby dokázal, že částečná řešení (řešení podproblémů) nalezená navrženým postupem jsou alespoň stejně tak dobrá jako odpovídající část optimálního řešení.

Nechť \(B \subseteq A\) je řešení nalezené naším postupem a nechť \(O \subseteq A\) je optimální řešení. Aby naše řešení \(B\) bylo také optimální, tak musí platit, že \(|B| = |O|\). Tento důkaz povedeme ve dvou krocích, nejdříve pomocí indukce ukážeme, že když seřadíme aktivity od nejdřívější po nejpozdější, tak prvních \(l\) aktivit našeho řešení \(B\) končí nejpozději ve stejnou chvíli jako prvních \(l\) aktivit optimálního řešení \(O\). Následně sporem ukážeme, že tím pádem musí být naše řešení \(B\) stejně dlouhé jako optimální řešení \(O\).

Nechť \(b_1, ..., b_l\) jsou aktivity našeho řešení \(B\) seřazené od nejdřívější po nejpozdější. Protože \(B\) je možné řešení daného problému (správně bychom měli i toto dokázat), tak se jeho aktivity nepřekrývají, platí tedy, že aktivita \(b_1\) končí před začátkem aktivity \(b_2\) a tak dále. Obdobně nechť je \(o_1, ..., o_l\) prvních (chronologicky) \(l\) aktivit optimálního řešení \(O\). Poté platí, že pro všechna \(1 \leq k \leq l\) je \(f(b_k) \leq f(o_k)\).

Pro \(k=1\) je toto zjevné, náš algoritmus z dostupných aktivit vybírá tu, která končí nejdříve. První zvolená aktivita tedy zajisté nemůže končit později než libovolná jiná aktivita.

Pro \(k > 1\) použijeme indukci s indukční hypotézou, že pro aktivitu \(k-1\) platí, že \(f(b_{k-1}) \leq f(o_{k-1})\). Víme, že \(f(o_{k-1}) \leq s(o_k)\), v kombinaci s indukční hypotézou tedy víme, že \(f(b_{k-1}) \leq s(o_k)\). Náš algoritmus tedy mohl zvolit aktivitu \(o_k\), protože není překryta dříve zvolenou aktivitou. Buď ji tedy zvolil, poté platí \(f(b_{k}) \leq f(o_{k})\), nebo zvolil jinou aktivitu, ale protože náš algoritmus volí nejdříve končící aktivitu, tak zvolená aktivita nebude končit později než aktivita \(o_k\). Platí tedy \(f(b_{k}) \leq f(o_{k})\).

Tímto jsme dokázali, že pro prvních (chronologicky) \(l = |B|\) prvků platí, že pro všechna \(1 \leq k \leq l\) je \(f(b_k) \leq f(o_k)\). Předpokládejme tedy, že \(|B| < |O|\), poté existuje aktivita \(o_{l+1}\) a platí, že \(f(o_l) \leq s(o_{l+1})\). Zároveň tedy platí, že \(f(b_l) \leq s(o_{l+1})\), tedy náš algoritmus mohl zvolit aktivitu \(o_{l+1}\). Náš algoritmus se zastaví jen pokud již nemůže zvolit další aktivitu, ale zjevně mohl zvolit další aktivitu. Což je spor. Musí tedy platit, že \(|B| \geq |O|\) a protože \(O\) je z předpokladu optimální, tak platí \(|B| = |O|\).

Scheduling to minimize lateness

Řešená úloha 2: Máme jediný stroj a musíme na něm naplánovat výrobu \(n\) rozdílných výrobků. O všech výrobcích víme na začátku plánovacího období. Pro každý výrobek víme, do kdy jej máme vyrobit a jak dlouho jeho výroba trvá. V jeden okamžik lze pracovat na výrobě pouze jednoho výrobku. Chceme naplánovat výrobu všech výrobků tak, abychom dosáhli co nejmenšího maximálního zpoždění.

Formálně máme množinu výrobků \(V = \{v_i \, | \, 1 \leq i \leq n \}\). Každý výrobek \(v_i\) má čas trvání výroby \(t(v_i)\) a čas do kdy má být vyroben \(d(v_i)\). O všech výrobcích víme od začátku plánovacího období a chceme naplánovat jejich výrobu tak, abychom minimalizovali maximální zpoždění (lateness). Zpoždění \(l(v_i)\) ve výrobě výrobku \(v_i\) definujeme jako \(l(v_i) := f(v_i) - d(v_i)\), kde \(f(v_i)\) je čas dokončení výrobku \(v_i\). Musíme rozhodnout čas začátku výroby \(s(v_i)\) pro všechny výrobky \(v_i \in V\), tak abychom minimalizovali \(max_{v_i \in V} \, l(v_i)\).

Jaký greedy postup by mohl vést k optimálnímu řešení?

Řešení

Optimální řešení lze nalézt strategií Earliest Deadline First. Tedy tak, že výrobky budeme vyrábět v pořadí dle jejich deadlinů.

Pseudokód takového postupu by mohl vypadat například takto:

Sort the products in a non-decreasing order by d[i]
Set s[1] := 0
Set f[1] := t[1]

For i = 2, ..., n:
  s[i] = f[i-1]
  f[i] = s[i] + t[i]
End for

Return the production intervals [s[i], f[i]] for i = 1, ..., n

Nyní ještě musíme dokázat, že tento postup skutečně produkuje optimální řešení.

Důkaz

V následujícím důkazu si ukážeme druhý dominantní postup používaný k dokazování optimality greedy algoritmů. Jedná se o postup založený na argumentu záměny (Exchange Argument). Postup spočívá v tom, že vezmeme optimální řešení a řešení nalezené naším algoritmem a postupně optimální řešení upravujeme, aniž bychom zhoršili jeho hodnotu. Tímto postupem z optimálního řešení bez zhoršení uděláme řešení stejně dobré jako naše řešení. Čímž dokážeme, že naše řešení je stejně dobré jako optimální a tedy také optimální.

První si musíme uvědomit, že existuje optimální řešení, které bude plánovat všechny výrobky těsně za sebou. Kdyby mezi po sobě jdoucími výrobky byla mezera, tak existuje rozvrh, který plánuje výrobky ve stejném pořadí, ale bez této mezery. Takový rozvrh nemůže být horší, protože uzavřením mezery zpoždění následujících úloh zlepšil a zpoždění předcházejících úloh nezměnil.

Dále si musíme uvědomit, že rozvrh nalezený naším postupem plánuje všechny výrobky těsně za sebou. Vskutku, náš algoritmus nastavuje počáteční čas výroby následujícího produktu vždy tak, aby byl totožný s koncovým časem výroby předchozího produktu.

Nyní víme, že oba rozvrhy jsou bez mezer. Čím se tedy může optimální rozvrh lišit od našeho? Buď optimální rozvrh také plánuje výrobu v neklesajícím pořadí deadline, poté se od našeho rozvrhu může lišit pouze pořadím výroby produktů se stejným deadlinem, nebo obsahuje alespoň dva výrobky takové, že dříve naplánovaný má pozdější deadline než později naplánovaný výrobek.

V obou případech platí, že pokud námi nalezený rozvrh \(R\) není totožný s optimálním rozvrhem \(O\), tak rozvrh \(O\) obsahuje výrobky \(a, b\), pro které platí \(s_O(a) < s_O(b)\) a které jsou naplánovány těsně po sobě, ale v rozvrhu \(R\) jsou naplánovány v opačném pořadí (ne nutně těsně po sobě). Této situaci budeme říkat, že rozvrh \(O\) obsahuje inverzi vůči rozvrhu \(R\).

Kvůli tomu, jak byl rozvrh \(R\) sestaven, tak musí platit \(d(b) \leq d(a)\). Prohozením pořadí výrobků \(a, b\) dostaneme rozvrh \(O'\), který obsahuje o jednu inverzi méně. Zároveň toto prohození nezhoršilo největší zpoždění celého rozvrhu. Protože jsme prohodili po sobě jdoucí výrobky, tak změna se týká jen jich a časy ostatních výrobků jsou beze změny. V případě výrobku \(b\) je zjevné, že nedošlo k zhoršení. Výrobek je nyní vyráběn dříve, nemůže být tedy více zpožděný. V případě výrobku \(a\) to tak jasné není. Musíme si uvědomit, že celkový výrobní čas výrobků je stejný nezávisle na pořadí. Druhý z obou výrobků tedy končí ve stejném čase v obou rozvrzích (\(O\) i \(O'\)). Platí tedy, že \(f'(a) = f(b)\), zpoždění výrobku \(a\) v rozvrhu \(O'\) je tedy \(l'(a) = f'(a) - d(a) = f(b) - d(a) \leq f(b) - d(b) = l(b)\) Zpoždění výrobku \(a\) v novém rozvrhu tedy není horší než bylo zpoždění výrobku \(b\) v původním rozvrhu, nemohlo tedy zhoršit nejhorší zpoždění celého rozvrhu.

Protože máme konečně mnoho výrobků, tak můžeme mít jen konečně mnoho inverzí, opakováním tohoto postupu tedy dokážeme optimální rozvrh proměnit na rozvrh nalezený naším postupem bez zhoršení jeho hodnoty. I námi nalezený rozvrh je tedy optimální.

Využití v heuristikách

Greedy algoritmy jsou často používány i na problémy, kde nejsou optimální. Díky jejich jednoduchosti a rychlosti se často používají jako heuristiky ve složitějších problémech.

Řešená úloha 3: Uvažujme jednoduché rozšíření úlohy 2. Mějme \(P\) totožných strojů a \(n\) úloh, které na nich musíme zpracovat. O všech úlohách víme na začátku plánovacího období. U každé úlohy víme, do kdy ji musíme splnit a jak dlouho její řešení trvá. V jeden okamžik lze na jednom stroji pracovat pouze na jedné úloze. Chceme naplánovat splnění všech úloh tak, abychom dosáhli co nejmenšího maximálního zpoždění.

Formálně máme množinu úloh \(J = \{j_i \, | \, 1 \leq i \leq n \}\). Každá úloha \(j_i\) má čas řešení \(t(j_i)\) a čas do kdy má být splněna \(d(j_i)\). O všech úlohách víme od začátku plánovacího období a chceme naplánovat jejich řešení tak, abychom minimalizovali maximální zpoždění (lateness). Zpoždění \(l(j_i)\) v řešení úlohy \(j_i\) definujeme jako \(l(j_i) := f(j_i) - d(j_i)\), kde \(f(j_i)\) je čas dokončení úlohy \(j_i\). Musíme rozhodnout čas začátku zpracování \(s(j_i)\) pro všechny úlohy \(j_i \in J\), tak abychom minimalizovali \(max_{j_i \in J} \, l(j_i)\).

Tato úloha již patří mezi NP-Complete úlohy (povíme si o nich na pozdějším cvičení). Prozatím nám postačí, že se jedná o těžkou úlohu, jejíž řešení je časově náročné. Greedy algoritmy na optimální řešení této úlohy nestačí. I tak se tento postup často používá jako heuristika, protože v krátkém čase nachází často dostatečně dobrá řešení.

Upravte Earliest Deadline First (někdy také Earliest Due Date first) postup známý z předchozích úloh tak, aby šel použít pro více strojů.

Řešení

Nejdříve seřadíme všechny úlohy vzestupně dle deadline. Následně jdeme úlohu po úloze a úlohu vždy přiřazujeme stroji, který je nejdříve volný.

Pseudokód takového postupu by mohl vypadat například takto:

Sort the products in a non-decreasing order by d[i]
Set p[i] := 0   for i = 1, ..., P
Set m[i] := 0   for i = 1, ..., n

For i = 1, ..., n:
  k = argmin(p[i] for i = 1, ..., P)
  m[i] = k
  s[i] = p[k]
  f[i] = s[i] + t[i]
  p[k] = f[i]
End for

Return the production intervals [s[i], f[i]] and assigned machines m[i] for i = 1, ..., n

Tomuto postupu se obecně říká List Scheduling, v našem případě řadíme úlohy dle Earliest Deadline First pravidla, jedná se tedy o EDF List Scheduling.

Ukažte, že tento postup není optimální.

Nápověda

Nalezněte příklad na kterém navržený postup nenajde optimální řešení.

Řešení

Uvažujme dva stroje a tři úlohy.

Úloha	Čas řešení (t)	Deadline (d)
🟦 1	2	2
🟧 2	2	4
🟩 3	10	10

Náš postup nalezne řešení:

Vidíme, že úloha 3 se na stroji 1 dokončí až v čase 12, tedy o 2 později, než je její deadline. Maximální zpoždění tohoto rozvrhu je tedy \(l(j_3) = 2\).

Ale optimální řešení je:

V tomto rozvrhu je splněn deadline všech úloh, maximální zpoždění je tedy \(0\).

Další úlohy

Interval Scheduling / Activity Selection Problem

Úloha 4: Představte si, že jste byli najati jako konzultanti přepravní společnosti. Potřebují vaši radu s nastavením pravidel pro nakládání kamionů. Přepravují zásilky, každá zásilka \(i\) má svou váhu \(w_i\). Zásilky jsou celkem malé, ale velmi těžké, limitem na přepravu je tedy maximální povolená váha kamionu \(C\), nikoliv rozměry zásilek. Požadavek vedení je, že zásilky musí být odbaveny v takovém pořadí v jakém přišly. Dříve tomu tak nebylo a vedlo to k stížnostem zákazníků. K nakládání kamionů používají tedy velmi jednoduchý postup, nakládají zásilky v pořadí v jakém přišly, jakmile by další zásilka v pořadí svou vahou způsobila přetížení kamionu, tak kamion odešlou a zásilka je první zásilkou dalšího kamionu.

Vedení si není jisté, jestli neexistuje efektivnější postup. Tedy jestli nelze využít méně kamionů. Dokažte, že pokud budete respektovat uvedený požadavek vedení, tak efektivnější postup neexistuje.

Nápověda

Zamyslete se nad možností uplatnění greedy stays ahead argumentu.

Interval Partitioning Problem

Úloha 5: Z první úlohy již známe Activity Selection Problem, v kterém musíme vybrat nepřekrývající se aktivity a chceme jich vykonat co nejvíce. Plánování více aktivit je omezeno tím, že všechny aktivity vyžadují stejný zdroj a my máme k dispozici jen jeden takový zdroj. Musíme tedy vybrat jen část aktivit, co můžeme vykonat.

Interval partitioning problém otáčí toto omezení. Musíme vykonat všechny aktivity a zajímá nás, jaký je nejmenší počet zdrojů, jenž potřebujeme. Zdrojem může být místnost nebo stroj. Mohli bychom třeba plánovat přednášky s daným začátkem a koncem a zajímalo by nás, kolik potřebujeme přednáškových místností.

Formálně máme množinu aktivit \(A = \{a_i \, | \, 1 \leq i \leq n \}\). Každá aktivita \(a_i\) má čas začátku \(s(a_i)\) a čas konce \(f(a_i)\). Každá aktivita vyžaduje jeden zdroj typu \(R\). Zajímá nás, kolik zdrojů typu \(R\) potřebujeme, abychom mohli vykonat všechny aktivity.

Navrhněte greedy algoritmus, který tuto úlohu optimálně vyřeší.

Ostatní

Úloha 6: Chceme rozmístit vysílací věže pro mobilní signál v poněkud zvláštním městě (The Line). Toto zvláštní město má podobu jedné dlouhé ulice táhnoucí se desítky kilometrů s domy volně rozesetými po obou stranách silnice. Každý dům je obklopen rozdílně velkou zahradou. Domy mezi sebou mají tedy nepravidelně velké mezery. Naším cílem je navrhnout rozmístění vysílacích stanic podél této cesty tak, aby všechny domy byly pokryty mobilním signálem a zároveň, abychom použili nejmenší možné množství vysílacích stanic.

Navrhněte postup, který nalezne toto rozmístění a dokažte jeho optimalitu.

Úloha 7: Malá firma nabízí zákazníkům tisk na 3D tiskárně, protože se jedná o malou firmu, tak mají zatím pouze jednu tiskárnu. Majitel firmy chce, aby jeho podnik prosperoval a tedy chce, aby jeho zákazníci byli co nejspokojenější. Zákazníci přes internet zadávají výrobky, které by chtěli vytisknout. Každý zákazník \(i\) má dobu trvání tisku jeho výrobků \(t_i\). V jednu chvíli lze tisknout jen výrobky jednoho zákazníka. Spokojenost zákazníka je úměrná času dokončení jeho tisku, čas dokončení tisku výrobků zákazníka \(i\) je \(C_i\). Někteří zákazníci jsou pro firmu důležitější než jiní, zákazník \(i\) má váhu \(w_i\). Spokojenost důležitých zákazníků je cennější než spokojenost méně důležitých zákazníků. Všechny výrobky, které je potřeba vyrobit, jsou známy na začátku plánovacího období (například ve 3 ráno daného dne). Firma chce optimalizovat váženou spokojenost svých zákazníků, chceme tedy najít pořadí tisku výrobků jednotlivých zákazníků takové, abychom minimalizovali \(\sum_i w_i C_i\).

Navrhněte postup řešení a odůvodněte jeho optimalitu.

Úloha 8: Firma z úlohy 7 koupila druhou 3D tiskárnu, jak se změní postup nalezení optimálního řešení? Lze úlohu stále řešit optimálně greedy postupem?

Úloha 9: S přáteli připravujete sportovní utkání pro děti na škole v přírodě. Každý soutěžící uplave 20 bazénů, poté ujede 10 kilometrů na kole a následně uběhne 3 km. Protože soutěžící známe z hodin tělocviku, tak máme pro každého odhad, jak dlouho bude plavat, jak dlouho pojede na kole a jak dlouho poběží. K dispozici máme jen menší bazén v kterém může v jednu chvíli plavat jen jeden soutěžící. Cesty jsou naštěstí dost velké, takže najednou může jet na kole libovolný počet soutěžících. Chceme, aby sportovní utkání zabralo co nejméně času, naším úkolem tedy je naplánovat pořadí soutěžících tak, aby soutěž skončila v nejkratším čase. Soutěž skončí jakmile doběhne poslední soutěžící.

Navrhněte efektivní postup, který dosáhne tohoto cíle.

Zdroje

Obsah dnešního cvičení je kompilací a adaptací 4. kapitoly knihy Algorithm Design (2006) od autorů: Jon Kleinberg a Éva Tardos, 16. kapitoly knihy Introduction to Algorithms, 3. edice (2009) od autorů: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest a Clifford Stein, a 5. kapitoly knihy Algorithms (2006) od autorů: Sanjoy Dasgupta, Christos H. Papadimitriou a Umesh V. Vazirani.