Chamtivý algoritmus

V tomto tutoriáli sa dozviete, čo je to chamtivý algoritmus. Nájdete tiež príklad chamtivého prístupu.

Chamtivý algoritmus je prístup k riešeniu problému výberom najlepšej možnosti, ktorá je momentálne k dispozícii, bez obáv z budúceho výsledku, ktorý prinesie. Inými slovami, lokálne najlepšie možnosti sú zamerané na dosiahnutie globálne najlepších výsledkov.

Tento algoritmus nemusí byť najlepšou voľbou pre všetky problémy. V niektorých prípadoch môže spôsobiť nesprávne výsledky.

Tento algoritmus sa nikdy nevráti späť, aby zmenil prijaté rozhodnutie. Tento algoritmus funguje zhora nadol.

Hlavnou výhodou tohto algoritmu je:

  1. Algoritmus je ľahšie opísať .
  2. Tento algoritmus môže fungovať lepšie ako iné algoritmy (ale nie vo všetkých prípadoch).

Realizovateľné riešenie

Realizovateľné riešenie je riešenie, ktoré poskytuje optimálne riešenie problému.

Chamtivý algoritmus

  1. Na začiatok je sada riešení (obsahujúca odpovede) prázdna.
  2. V každom kroku sa do súpravy roztoku pridá položka.
  3. Ak je sada riešení možná, aktuálna položka sa uchová.
  4. V opačnom prípade je položka odmietnutá a už nikdy sa nezvažuje.

Príklad - chamtivý prístup

 Problém: Musíte zmeniť sumu s použitím najmenšieho možného počtu mincí. Suma: 28 dolárov Dostupné mince: mince 5 dolárov, mince 2 doláre, mince 1 dolár

Riešenie:

  1. Vytvorte prázdnu množinu riešení = ().
  2. coiny = (5, 2, 1)
  3. súčet = 0
  4. Zatiaľ čo súčet ≠ 28, postupujte takto.
  5. Vyberte mincu C z mincí, ktorých súčet je + C <28.
  6. Ak C + súčet> 28, nevráti žiadne riešenie.
  7. Inak, súčet = súčet + C.
  8. Pridajte C do sady riešení.

Až do prvých 5 iterácií obsahuje sada riešení 5 coinov v hodnote 5 dolárov. Potom dostaneme 1 mincu 2 doláre a nakoniec 1 mincu 1 dolár.

Chamtivé algoritmické aplikácie

  • Výber Zoradiť
  • Problém s batohom
  • Minimálny rozpätie stromu
  • Problém s najkratšou cestou jedného zdroja
  • Problém s plánovaním práce
  • Algoritmus minimálneho rozpätia stromu Prim
  • Kruskalov algoritmus minimálneho rozpätia stromov
  • Dijkstraov algoritmus minimálneho rozpätia stromov
  • Huffmanovo kódovanie
  • Ford-Fulkersonov algoritmus

Zaujímavé články...