Úvod do chamtivého algoritmu
Stratégia použitá na riešenie problémov. Greedy Algorithm sa považuje za jeden z prístupov používaných na riešenie problémov. Tento heretik zameraný na riešenie problémov ide s výberom, ktorý sa v danom okamihu zdá byť najlepším. Tento prístup sa najlepšie používa na riešenie problémov s optimalizáciou. Problémy s optimalizáciou možno definovať ako problémy, ktoré si vyžadujú minimálne alebo maximálne výsledky. Algoritmus Greedy je najjednoduchší a najpriamejší prístup, ktorý možno použiť na dosiahnutie optimálneho riešenia.
Čo je Greedyov algoritmus?
Greedy Algorithm je algoritmická stratégia, ktorá sa používa na výber najlepšej voliteľnej voľby vo veľmi malom štádiu a nakoniec na výstup globálne optimálneho riešenia. Tento algoritmus vyberie najlepšie možné riešenie v danom okamihu bez ohľadu na akékoľvek dôsledky. Greedyova metóda hovorí, že problém by sa mal riešiť v etapách, v ktorých sa každý jeden vstup považuje za uskutočniteľný. Keďže sa tento prístup zameriava iba na okamžitý výsledok bez ohľadu na väčší obraz, považuje sa za chamtivý.
Definovanie základnej koncepcie
Doteraz vieme, čo je chamtivý algoritmus a prečo sa volá. Nižšie uvedené ukazovatele vám umožnia lepšie porozumieť chamtivému algoritmu. Už bolo jasné, že chamtivý algoritmus funguje iba v prípade problému; tento prístup sa však dá uplatniť iba vtedy, ak máme na tento problém stav alebo obmedzenie.
Typy problémov
- Problém s minimalizáciou: Riešenie problému je ľahké vzhľadom na splnenie všetkých podmienok. Ak však tento problém vyžaduje minimálny výsledok, nazýva sa to problém minimalizácie.
- Problém maximalizácie: Problém, ktorý vyžaduje maximálny výsledok, sa nazýva problém maximalizácie.
- Problém s optimalizáciou: Problém sa nazýva problém s optimalizáciou, ak vyžaduje minimálne alebo maximálne výsledky.
Druhy riešení
- Možné riešenie: Teraz, keď sa vyskytne problém, máme veľa možných riešení tohto problému. Napriek tomu, berúc do úvahy podmienku stanovenú pre tento problém, vyberáme riešenia, ktoré spĺňajú danú podmienku. Takéto riešenia, ktoré nám pomáhajú dosahovať výsledky spĺňajúce danú podmienku, sa nazývajú uskutočniteľné riešenie .
- Optimálne riešenie: Riešenie sa nazýva optimálne, ak je už uskutočniteľné a dosiahne cieľ problému; najlepší výsledok. Týmto cieľom by mohol byť minimálny alebo maximálny výsledok. Treba si všimnúť, že akýkoľvek problém bude mať iba jedno optimálne riešenie.
Nasledujúci príklad vám umožní ľahko pochopiť chamtivú metódu. Povedzme, že jeden chce kúpiť najlepšie auto dostupné na trhu. Jednou z metód na výber tohto automobilu je analýza všetkých automobilov na trhu. Teraz, pretože je to časovo náročné, aby sa uľahčilo vyberanie automobilu od tých konkrétnych značiek, do ktorých majú záujem investovať. Pri zatrieďovaní do tejto kategórie by si znova vybral požadované modely, pričom by preskúmal jeho vlastnosti. Prístup, ktorý sa tu používa, je preto chamtivý, pretože toto riešenie bolo pre vás optimálnym riešením, pričom všetky faktory boli pre vás priaznivé.
Základné komponenty chamtivého algoritmu
Teraz, keď lepšie porozumieme tomuto mechanizmu, preskúmajme základné komponenty chamtivého algoritmu, ktorý ho odlišuje od ostatných procesov:
- Kandidátska sada: Z tejto sady sa vytvorí odpoveď.
- Funkcia výberu: Vyberie najlepšieho kandidáta, ktorý bude zahrnutý do riešenia.
- Funkcia uskutočniteľnosti: V tejto časti sa počíta, či sa kandidát môže použiť na prispenie k riešeniu.
- Objektívna funkcia: Priradí hodnotu úplnému alebo čiastočnému riešeniu.
- Funkcia riešenia: Používa sa na označenie, či bolo splnené správne riešenie.
Kde funguje Greedyho algoritmus najlepšie?
Greedyov algoritmus je možné aplikovať na nižšie uvedené problémy.
- Greedyov prístup sa dá použiť na nájdenie minimálneho preklenovacieho stromového grafu pomocou Primovho alebo Kruskalovho algoritmu
- Nájdenie najkratšej cesty medzi dvoma vrcholmi je ďalším problémom, ktorý je možné vyriešiť pomocou chamtivého algoritmu. Aplikácia algoritmu Dijkstra spolu s chamtivým algoritmom vám poskytne optimálne riešenie.
- Huffmanovo kódovanie
výhody
Najväčšou výhodou algoritmu Greedy oproti ostatným je to, že sa dá ľahko implementovať a vo väčšine prípadov je veľmi efektívny.
nevýhody
Greedy Algorithm v podstate stavia časť riešenia po častiach a vyberá si ďalšiu časť tak, aby okamžite poskytol najlepšie riešenie súčasného problému. V dôsledku toho neexistujú žiadne obavy ani obavy z dôsledkov súčasného prijatého rozhodnutia. Greedy Algorithm nikdy neprehodnotí predtým prijaté rozhodnutia a nedokáže vytvoriť optimálne riešenie, aj keď poskytuje takmer optimálne riešenie . Problém s batohom a cestovný problém s obchodníkom sú príklady problémov, pri ktorých Greedy Algorithm nedokáže vytvoriť optimálne riešenie.
- Problém s batohom: Najbežnejšie známy problém s batohom na meno je každodenným problémom, ktorému čelí mnoho ľudí. Povedzme, že máme množinu položiek a každá z nich má inú váhu a hodnotu (zisk), ktorá sa má plniť do kontajnera, alebo by sa mala zhromažďovať takým spôsobom, aby celková hmotnosť bola menšia alebo rovná hmotnosti kontajnera, zatiaľ čo celkový zisk bude maximalizovaný,
záver
Greedy Algorithm je najlepšie aplikovateľný, keď človek potrebuje riešenie v reálnom čase a približné odpovede sú „dosť dobré“. Bezpochyby chamtivý algoritmus minimalizuje čas a zároveň zabezpečuje optimálne riešenie, takže je vhodnejšie ho použiť v situácii, keď je potrebný kratší čas. Po prečítaní tohto článku by niekto mohol mať férovú predstavu o chamtivých algoritmoch. Tento príspevok okrem toho vysvetľuje, prečo sa považuje za najlepší rámec, ktorý zodpovedá takmer všetkým výzvam v oblasti programovania, a zároveň vám pomáha pri rozhodovaní o najoptimálnejšom riešení v danom okamihu.
Z hrubého hľadiska je však pri uplatňovaní teórie chamtivého algoritmu potrebné usilovnejšie poznať správne problémy. Aj keď je to vedecký koncept, ktorý má logiku, má tiež podstatu tvorivosti.
Odporúčané články
Toto bol sprievodca „Čo je chamtivý algoritmus“. Tu sme diskutovali o základnej koncepcii, komponentoch, výhodách a nevýhodách chamtivého algoritmu. Viac informácií nájdete aj v ďalších navrhovaných článkoch -
- Algoritmus v programovaní
- Čo je Perl?
- Úvod do algoritmu
- Čo je Agile Sprint?