Hladové algoritmy
Platba mincemi
Mějme n druhů mincí hodnot v±t V2, ..., vn a částku C. Chceme zaplatit částku C co nejmenším počtem mincí. Předpokládáme, že mincí každého druhu máme neomezený počet.
► Uvažujme hladový přístup: „Vždy vezmeme největší minci, jejíž hodnota < aktuální částka." Dokažte, že tento přístup funguje pro sadu 1, 5, 10, 25.
► K procvičení: Pro jaké jiné sady funguje tento hladový přístup? Vymyslete formální důkaz.
Hladové algoritmy
Batoh s libovolným dělením
Mějme n předmětů s hodnotami h; a vahou vn dále maximální nosnost batohu V. Oproti klasickému problému batohu ale předpokládejme, že se předměty dají libovolně dělit a jsou homogenní (tzn. třetina předmětu má třetinu jeho hodnoty i váhy). Chceme nasbírat předměty (resp. jejich části) s co největší cenou tak, abychom nepřekročili nosnost batohu.
► Jaký hladový přístup bychom mohli zvolit v tomto případě?
► Dokažte, že je váš hladový přístup korektní.
Hladové algoritmy
Vrcholové pokrytí
Mějme neorientovaný graf. Vrcholovým pokrytím grafu je množina vybraných vrcholů taková, že se každá hrana grafu dotýká alespoň jednoho vybraného vrcholu. Chceme vrcholové pokrytí s minimálním počtem vybraných vrcholů.
► Jak řešit problém vrcholového pokrytí na obecném grafu?
Hladové algoritmy
Vrcholové pokrytí
Mějme neorientovaný graf. Vrcholovým pokrytím grafu je množina vybraných vrcholů taková, že se každá hrana grafu dotýká alespoň jednoho vybraného vrcholu. Chceme vrcholové pokrytí s minimálním počtem vybraných vrcholů.
► Jak řešit problém vrcholového pokrytí na obecném grafu?
► Jak řešit problém vrcholového pokrytí na stromě? Dokážeme použít hladový přístup?
► Pokud navrhnete hladový přístup, dokažte, že je korektní.
Hladové algoritmy
Nezávislá množina
Mějme neorientovaný graf. Nezávislou množinou grafu je množina vybraných vrcholů taková, že žádné dva vybrané vrcholy nejsou spojeny hranou. Chceme najít maximální nezávislou množinu.
► Jak řešit problém nezávislé množiny na obecném grafu?
Hladové algoritmy
Nezávislá množina
Mějme neorientovaný graf. Nezávislou množinou grafu je množina vybraných vrcholů taková, že žádné dva vybrané vrcholy nejsou spojeny hranou. Chceme najít maximální nezávislou množinu.
► Jak řešit problém nezávislé množiny na obecném grafu?
► Jak řešit problém nezávislé množiny na stromě? Dokážeme použít hladový přístup?
► Pokud navrhnete hladový přístup, dokažte, že je korektní.
Hladové algoritmy
Čerpací stanice
Chceme jet autem po dlouhé rovné dálnici mezi dvěma městy. Předpokládejme, že spotřeba auta po cestě je konstantní. Známe pozici všech čerpacích stanic na dálnici, víme, jaká je kapacita nádrže, a na počátku cesty máme nádrž plnou. Chceme naplánovat cestu tak, abychom co nejméně zastavovali na čerpacích stanicích.
► Jaké hladové kriterium bychom mohli zvolit v tomto případě?
► Dokažte, že je váš hladový algoritmus korektní.
Hladové algoritmy
Čerpací stanice
Chceme jet autem po dlouhé rovné dálnici mezi dvěma městy. Předpokládejme, že spotřeba auta po cestě je konstantní. Známe pozici všech čerpacích stanic na dálnici, víme, jaká je kapacita nádrže, a na počátku cesty máme nádrž plnou. Chceme naplánovat cestu tak, abychom co nejméně zastavovali na čerpacích stanicích.
► Jaké hladové kriterium bychom mohli zvolit v tomto případě?
► Dokažte, že je váš hladový algoritmus korektní.
► Varianta: Známe cenu pohonných hmot na každé čerpací stanici a chceme, aby byla cesta co nejlevnější. Jak budeme řešit problém teď?