U ovom vodiču naučit ćete što je pohlepni algoritam. Također ćete pronaći primjer pohlepnog pristupa.
Pohlepni algoritam pristup je rješavanju problema odabirom najbolje opcije dostupne u ovom trenutku, bez brige o budućem rezultatu koji bi to donijelo. Drugim riječima, lokalni odabir ima za cilj postizanje najboljih globalnih rezultata.
Ovaj algoritam možda nije najbolja opcija za sve probleme. U nekim slučajevima može donijeti pogrešne rezultate.
Ovaj se algoritam nikad ne vraća unatrag na donošenje odluke. Ovaj algoritam djeluje u pristupu od vrha prema dolje.
Glavna prednost ovog algoritma je:
- Algoritam je lakše opisati .
- Ovaj algoritam može raditi bolje od ostalih algoritama (ali ne u svim slučajevima).
Izvodljivo rješenje
Izvedivo rješenje je ono koje pruža optimalno rješenje problema.
Pohlepni algoritam
- Za početak je skup rješenja (koji sadrži odgovore) prazan.
- U svakom se koraku stavka dodaje u skup rješenja.
- Ako je skup rješenja izvediv, zadržava se trenutna stavka.
- Inače, stavka se odbija i nikad više ne razmatra.
Primjer - Pohlepni pristup
Problem: Morate izvršiti promjenu iznosa koristeći najmanji mogući broj kovanica. Iznos: 28 USD Dostupni kovanice: Kovanica od 5 dolara Kovanica od 2 dolara Novčić od 1 dolara
Riješenje:
- Stvorite prazno rješenje-set = ().
- kovanice = (5, 2, 1)
- zbroj = 0
- Dok je zbroj ≠ 28, učinite sljedeće.
- Odaberite novčić C od kovanica tako da je zbroj + C <28.
- Ako je C + zbroj> 28, nema rješenja.
- Inače, zbroj = zbroj + C.
- Dodaj C u skup rješenja.
Do prvih 5 ponavljanja, set rješenja sadrži 5 kovanica od 5 dolara. Nakon toga dobivamo kovanicu od 1 dolara i konačno 1 novčić od 1 dolara.
Primjene pohlepnog algoritma
- Sortiranje odabira
- Ruksak problem
- Minimalno rastezno drvo
- Problem najkraćeg puta s jednim izvorom
- Problem raspoređivanja poslova
- Primov algoritam minimalnog raspona stabla
- Kruskalov algoritam minimalnog raspona stabala
- Dijkstrin algoritam minimalnog raspona stabala
- Huffmanovo kodiranje
- Ford-Fulkersonov algoritam
