logo

TechCodeview

Chamtivé algoritmy

Chamtivé algoritmy sú triedou algoritmov, ktoré vytvárajú lokálne optimálne možnosti na každom kroku s nádejou nájsť a globálne optimum Riešenie. V týchto algoritmoch sa rozhodnutia robia na základe informácií dostupných v súčasnosti bez toho, aby sa zohľadnili dôsledky týchto rozhodnutí v budúcnosti. Kľúčovou myšlienkou je vybrať v každom kroku najlepšiu možnú voľbu, ktorá vedie k riešeniu, ktoré nemusí byť vždy najoptimálnejšie, ale často je dostatočne dobré pre mnohé problémy.

V tomto článku pochopíme chamtivé algoritmy s príkladmi. Pozrieme sa aj na problémy a ich riešenia pomocou zištného prístupu.

Chamtivé algoritmy



Obsah

Čo je to Greedy Algorithm?

A chamtivý algoritmus je typ optimalizačného algoritmu, ktorý v každom kroku robí lokálne optimálne voľby s cieľom nájsť globálne optimálne riešenie. Funguje na princípe výberu najlepšej možnosti hneď bez zváženia dlhodobých následkov.

Ak sa chcete dozvedieť, čo je to chamtivá metóda a ako používať chamtivý prístup, prečítajte si daný návod na Greedy Algorithm:

mapovanie v strojopise

Kroky na vytvorenie chamtivého algoritmu

Kroky na definovanie chamtivého algoritmu sú:

  1. Definujte problém: Jasne uveďte problém, ktorý sa má vyriešiť, a cieľ, ktorý sa má optimalizovať.
  2. Identifikujte chamtivú voľbu: V každom kroku určte miestne optimálnu voľbu na základe aktuálneho stavu.
  3. Urobte chamtivý výber: Vyberte chamtivý výber a aktualizujte aktuálny stav.
  4. Opakujte: Pokračujte v chamtivých rozhodnutiach, kým sa nedosiahne riešenie.

Po daných krokoch sa môžete naučiť, ako používať chamtivé algoritmy na nájdenie optimálnych riešení.

Príklady chamtivých algoritmov

Príklady chamtivých algoritmov sú najlepším spôsobom, ako pochopiť algoritmus. Niektoré príklady chamtivých algoritmov v reálnom živote sú:

  • Frakčný batoh : Optimalizuje hodnotu položiek, ktoré možno čiastočne zahrnúť do batohu s obmedzenou kapacitou.
  • Dijkstrov algoritmus : Nájde najkratšiu cestu zo zdrojového vrcholu do všetkých ostatných vrcholov vo váženom grafe.
  • Kruskalov algoritmus : Nájde minimálnu kostru váženého grafu.
  • Huffmanovo kódovanie : Komprimuje údaje priradením kratších kódov k častejším symbolom.

Aplikácie Greedy Algorithm

Je ich veľa aplikácie chamtivé metódy v DAA . Niektoré dôležité aplikácie chamtivých algoritmov sú:

  • Priraďovanie úloh k zdrojom s cieľom minimalizovať čakaciu dobu alebo maximalizovať efektivitu.
  • Výber najcennejších predmetov, ktoré sa zmestia do batohu s obmedzenou kapacitou.
  • Rozdelenie obrázka na oblasti s podobnými vlastnosťami.
  • Zníženie veľkosti údajov odstránením nadbytočných informácií.

Nevýhody/obmedzenia používania chamtivého algoritmu

Nižšie sú uvedené niektoré nevýhody Greedy Algorithm:

menu nastavení android
  • Chamtivé algoritmy nemusia vždy nájsť najlepšie možné riešenie.
  • Poradie, v ktorom sa prvky zvažujú, môže výrazne ovplyvniť výsledok.
  • Nenásytné algoritmy sa zameriavajú na lokálne optimalizácie a môžu im chýbať lepšie riešenia, ktoré si vyžadujú zváženie širšieho kontextu.
  • Chamtivé algoritmy nie sú použiteľné na problémy, kde chamtivá voľba nevedie k optimálnemu riešeniu.

Základy chamtivého algoritmu:

  • Greedy Algorithms (všeobecná štruktúra a aplikácie)
  • Rozdiel medzi algoritmom Greedy a algoritmom rozdeľovania a panovania
  • Chamtivý prístup verzus dynamické programovanie
  • Porovnanie medzi algoritmami Greedy, Divide and Conquer a Dynamic Programming

Štandardné chamtivé algoritmy:

  • Problém s výberom aktivity
  • Problém poradia úloh
  • Huffmanovo kódovanie
  • Huffmanovo dekódovanie
  • Problém s pripojením vody
  • Minimálne swapy pre vyvažovanie zátvoriek
  • Egyptský zlomok
  • Policajti chytajú zlodejov
  • Problém s montážou políc
  • Priraďte myši k otvorom

Chamtivé problémy na poli:

  • Minimálna podmnožina produktov poľa
  • Maximalizujte súčet poľa po K negáciách pomocou triedenia
  • Minimálny súčet súčinu dvoch polí
  • Minimálny súčet absolútneho rozdielu párov dvoch polí
  • Minimálny prírastok/zníženie, aby sa pole nezväčšovalo
  • Triediace pole so spätným chodom okolo stredu
  • Súčet oblastí obdĺžnikov možných pre pole
  • Najväčšie lexikografické pole s najviac K po sebe idúcimi zámenami
  • Rozdelenie na dve podpolia dĺžok k a (N – k) tak, aby rozdiel súčtov bol maximálny

Nenápadné problémy operačného systému:

  • Algoritmus First Fit v správe pamäte
  • Algoritmus Best Fit v správe pamäte
  • Algoritmus najhoršieho prispôsobenia v správe pamäte
  • Najkratšie plánovanie práce
  • Plánovanie úloh s dvomi povolenými úlohami súčasne
  • Program pre algoritmus optimálneho nahradenia strán

Chamtivé problémy na grafe:

  • Kruskalov minimálny kostrový strom
  • Primov minimálny kostrový strom
  • Minimálny strom Boruvka
  • Dijkastrov algoritmus najkratšej cesty
  • Algoritmus číselníka
  • Minimálne náklady na pripojenie všetkých miest
  • Úvod do problému maximálneho prietoku
  • Počet komponentov jedného cyklu v neorientovanom grafe

Približný chamtivý algoritmus pre NP dokončený:

  • Problém s nastavením krytu
  • Problém balenia koša
  • Farbenie grafu
  • Problém s K-centrami
  • Problém s najkratšou superstrunou
  • Približné riešenie problému Traveling Salesman pomocou MST

Chamtivý pre špeciálne prípady DP:

  • Problém zlomkového batohu
  • Vyžaduje sa minimálny počet mincí

Jednoduché problémy na Greedy Algoritmus :

  • Rozdeľte n na maximálne zložené čísla
  • Kúpte maximálne zásoby, ak je možné akcie kúpiť v i-tý deň
  • Nájdite minimálnu a maximálnu sumu na nákup všetkých N cukríkov
  • Maximálny možný súčet sa rovná súčtu troch hromádok
  • Rozdeľte kváder na kocky tak, aby súčet objemov bol maximálny
  • Maximálny počet zákazníkov, ktorí môžu byť spokojní s daným množstvom
  • Minimálne otáčky na odomknutie kruhového zámku
  • Minimálne miestnosti pre m udalostí z n dávok s daným harmonogramom
  • Minimálne náklady na vytvorenie poľa veľkosti 1 odstránením väčšieho z párov
  • Minimálne náklady na získanie všetkých mincí s k mincami navyše povolenými ku každej minci
  • Minimálny prírastok o k operácií, aby boli všetky prvky rovnaké
  • Nájdite minimálny počet bankoviek a hodnôt, ktoré zodpovedajú danej sume
  • Najmenšia podmnožina so súčtom väčším ako všetky ostatné prvky

Stredné problémy na Greedy Algoritmus :

  • Maximálny počet vlakov, pre ktoré možno poskytnúť zastávku
  • Minimálne Fibonacciho členy so súčtom rovným K
  • Rozdeľte 1 až n do dvoch skupín s minimálnym rozdielom súčtu
  • Papier narezaný na minimálny počet štvorcov
  • Minimálny rozdiel medzi skupinami veľkosti dva
  • Spojte n lán s minimálnymi nákladmi
  • Minimálny počet nástupíšť požadovaných pre železničnú/autobusovú stanicu
  • Minimálne počiatočné vrcholy na prejdenie celej matice s danými podmienkami
  • Najväčšie palindromické číslo podľa permutácie číslic
  • Nájdite najmenšie číslo s daným počtom číslic a súčtom číslic
  • Lexikograficky najväčšia podsekvencia taká, že každý znak sa vyskytuje aspoň k-krát

Ťažké problémy na Greedy Algoritmus :

  • Maximálny počet prvkov, ktoré možno vyrovnať s k aktualizáciami
  • Minimalizujte peňažný tok medzi priateľmi
  • Minimálne náklady na rozrezanie dosky na štvorce
  • Minimálne náklady na spracovanie m úloh, kde náklady na zmenu
  • Minimálny čas na dokončenie všetkých úloh s danými obmedzeniami
  • Minimalizujte maximálny rozdiel medzi výškami veží
  • Minimálne okraje na obrátenie, aby sa vytvorila cesta od zdroja k cieľu
  • Nájdite najväčšiu kocku vytvorenú odstránením minimálneho počtu číslic z čísla
  • Zmeňte usporiadanie znakov v reťazci tak, aby žiadne dva susediace neboli rovnaké
  • Usporiadajte reťazec tak, aby boli všetky rovnaké znaky vzdialené d
  • Naučte sa dátovú štruktúru a algoritmy | Príručka DSA
  • 20 najčastejších otázok na rozhovor o chamtivých algoritmoch
  • „Problémy s precvičovaním“ chamtivých algoritmov
  • „Kvíz“ o chamtivých algoritmoch