Chamtivé algoritmy jsou třídou algoritmů, které vytvářejí lokálně optimální možnosti na každém kroku s nadějí na nalezení a globální optimum řešení. V těchto algoritmech jsou rozhodnutí přijímána na základě informací dostupných v aktuálním okamžiku, aniž by se zvažovaly důsledky těchto rozhodnutí v budoucnu. Klíčovou myšlenkou je vybrat v každém kroku nejlepší možnou volbu, která vede k řešení, které nemusí být vždy nejoptimálnější, ale často je dost dobré pro mnoho problémů.

V tomto článku pochopíme chamtivé algoritmy na příkladech. Podíváme se také na problémy a jejich řešení pomocí zištného přístupu.

Chamtivé algoritmy

Obsah

• Co je to Greedy Algorithm?
• Kroky pro vytvoření chamtivého algoritmu
• Příklady chamtivých algoritmů
• Aplikace Greedy Algorithm
• Nevýhody/omezení používání nenasytného algoritmu
• Základy Greedy Algorithmu
• Standardní Greedy Algorithms
• Chamtivé problémy na poli
• Chamtivé problémy operačního systému
• Greedy problémy na grafu
• Přibližný algoritmus Greedy pro NP dokončen
• Chamtivý pro zvláštní případy DP
• Snadné problémy na Greedy Algorithm
• Střední problémy s chamtivým algoritmem
• Těžké problémy na Greedy Algorithm

Co je to Greedy Algorithm?

A chamtivý algoritmus je typ optimalizačního algoritmu, který v každém kroku provádí lokálně optimální volby za účelem nalezení globálně optimálního řešení. Funguje na principu výběru nejlepší možnosti hned, aniž by se zvažovaly dlouhodobé důsledky.

Chcete-li se dozvědět, co je to chamtivá metoda a jak používat chamtivý přístup, přečtěte si daný návod na Greedy Algorithm:

Kroky pro vytvoření chamtivého algoritmu

Kroky k definování chamtivého algoritmu jsou:

1. Definujte problém: Jasně uveďte problém, který je třeba vyřešit, a cíl, který má být optimalizován.
2. Identifikujte chamtivou volbu: Určete lokálně optimální volbu v každém kroku na základě aktuálního stavu.
3. Udělejte zištnou volbu: Vyberte chamtivý výběr a aktualizujte aktuální stav.
4. Opakovat: Pokračujte v chamtivých volbách, dokud nedosáhnete řešení.

Po daných krocích se lze naučit, jak používat chamtivé algoritmy k nalezení optimálních řešení.

Příklady chamtivých algoritmů

Příklady chamtivých algoritmů jsou nejlepším způsobem, jak algoritmu porozumět. Některé příklady chamtivých algoritmů ze skutečného života jsou:

• Frakční batoh : Optimalizuje hodnotu položek, které mohou být částečně zahrnuty do batohu s omezenou kapacitou.
• Dijkstrův algoritmus : Najde nejkratší cestu ze zdrojového vrcholu ke všem ostatním vrcholům ve váženém grafu.
• Kruskalův algoritmus : Najde minimální kostru váženého grafu.
• Huffmanovo kódování : Komprimuje data přiřazením kratších kódů častějším symbolům.

Aplikace Greedy Algorithm

Je jich mnoho aplikace chamtivé metody v DAA . Některé důležité aplikace chamtivých algoritmů jsou:

• Přiřazování úkolů ke zdrojům pro minimalizaci čekací doby nebo maximalizaci efektivity.
• Výběr nejcennějších předmětů, které se vejdou do batohu s omezenou kapacitou.
• Rozdělení obrazu do oblastí s podobnými vlastnostmi.
• Snížení velikosti dat odstraněním nadbytečných informací.

Nevýhody/omezení používání nenasytného algoritmu

Níže jsou uvedeny některé nevýhody Greedy Algorithm:

• Chamtivé algoritmy nemusí vždy najít nejlepší možné řešení.
• Pořadí, ve kterém jsou prvky zvažovány, může významně ovlivnit výsledek.
• Chamtivé algoritmy se zaměřují na místní optimalizace a mohou postrádat lepší řešení, která vyžadují zvážení širšího kontextu.
• Chamtivé algoritmy nejsou použitelné na problémy, kde chamtivá volba nevede k optimálnímu řešení.

Základy Greedy Algorithm:

• Greedy Algorithms (obecná struktura a aplikace)
• Rozdíl mezi algoritmem Greedy a algoritmem rozděl a panuj
• Chamtivý přístup vs dynamické programování
• Srovnání mezi Greedy, Divide and Conquer a algoritmem dynamického programování

Standardní chamtivé algoritmy:

• Problém s výběrem aktivity
• Problém řazení úloh
• Huffmanovo kódování
• Huffmanovo dekódování
• Problém s připojením vody
• Minimální swapy pro vyvažování držáků
• Egyptský zlomek
• Policisté chytají zloděje
• Problém s montáží polic
• Přiřaďte myši k dírám

Chamtivé problémy na poli:

• Minimální podmnožina produktů pole
• Maximalizujte součet pole po K negacích pomocí řazení
• Minimální součet součinu dvou polí
• Minimální součet absolutního rozdílu párů dvou polí
• Minimální přírůstek/snížení, aby se pole nezvyšovalo
• Třídicí pole s reverzem kolem středu
• Součet možných oblastí obdélníků pro pole
• Největší lexikografické pole s nejvýše K po sobě jdoucími swapy
• Rozdělení na dvě podpole o délkách k a (N – k) tak, aby rozdíl součtů byl maximální

Chamtivé problémy v operačním systému:

• Algoritmus First Fit ve správě paměti
• Algoritmus Best Fit ve správě paměti
• Algoritmus nejhoršího přizpůsobení ve správě paměti
• Nejkratší plánování práce jako první
• Plánování úloh se dvěma povolenými úlohami současně
• Program pro optimální algoritmus nahrazení stránky

Chamtivé problémy na grafu:

• Kruskalův minimální kostra
• Primův minimální kostra
• Borůvkův minimální kostra
• Dijkastrův algoritmus nejkratší cesty
• Algoritmus Dial
• Minimální náklady na připojení všech měst
• Úvod do problému maximálního průtoku
• Počet složek jednoho cyklu v neorientovaném grafu

Přibližný algoritmus Greedy pro NP dokončen:

• Problém s nastavením krytu
• Problém s balením do koše
• Barvení grafu
• Problém s K-centry
• Problém s nejkratší superstrunou
• Přibližné řešení problému Traveling Salesman pomocí MST

Chamtivý pro zvláštní případy DP:

• Problém frakčního batohu
• Minimální požadovaný počet mincí

Snadné problémy na Greedy Algoritmus :

• Rozdělte n na maximální složená čísla
• Nakupte maximální zásoby, pokud lze akcie i koupit i-tý den
• Najděte minimální a maximální částku pro nákup všech N bonbónů
• Maximální možný součet se rovná součtu tří hromádek
• Kvádr rozdělte na krychle tak, aby součet objemů byl maximální
• Maximální počet zákazníků, kteří mohou být spokojeni s daným množstvím
• Minimální otáčky pro odemknutí kruhového zámku
• Minimální místnosti pro m událostí n dávek s daným harmonogramem
• Minimální náklady na vytvoření pole velikosti 1 odstraněním většího z párů
• Minimální náklady na získání všech mincí s k mincí navíc povolenými ke každé minci
• Minimální přírůstek o k operací, aby byly všechny prvky stejné
• Najděte minimální počet bankovek a hodnot, které odpovídají dané částce
• Nejmenší podmnožina se součtem větším než všechny ostatní prvky

Střední problémy na Greedy Algoritmus :

• Maximální počet vlaků, u kterých lze zajistit zastavení
• Minimální Fibonacciho členy se součtem rovným K
• Rozdělte 1 až n do dvou skupin s minimálním rozdílem součtů
• Papír nařezaný na minimální počet čtverců
• Minimální rozdíl mezi skupinami velikosti dvě
• Spojte n lan s minimálními náklady
• Minimální počet nástupišť požadovaných pro železniční/autobusové nádraží
• Minimální počáteční vrcholy pro procházení celé matice s danými podmínkami
• Největší palindromické číslo pomocí permutovaných číslic
• Najděte nejmenší číslo s daným počtem číslic a součtem číslic
• Lexikograficky největší podsekvence taková, že každý znak se vyskytuje alespoň kkrát

Těžké problémy na Greedy Algoritmus :

• Maximální počet prvků, které lze vyrovnat k aktualizacím
• Minimalizujte peněžní tok mezi přáteli
• Minimální náklady na rozřezání desky na čtverce
• Minimální náklady na zpracování m úkolů, kde stojí přechod
• Minimální čas na dokončení všech úloh s danými omezeními
• Minimalizujte maximální rozdíl mezi výškami věží
• Minimální okraje pro obrácení, aby se vytvořila cesta od zdroje k cíli
• Najděte největší kostku vytvořenou odstraněním minimálního počtu číslic z čísla
• Uspořádejte znaky v řetězci tak, aby žádné dva sousední nebyly stejné
• Uspořádejte řetězec tak, aby byly všechny stejné znaky vzdáleny d

Rychlé odkazy:

• Naučte se datovou strukturu a algoritmy | Výukový program DSA
• 20 nejčastějších otázek k rozhovoru o chamtivých algoritmech
• „Procvičování problémů“ na chamtivých algoritmech
• „Kvíz“ o chamtivých algoritmech