V tej vadnici boste izvedeli, kaj je pohlepni algoritem. Prav tako boste našli primer pohlepnega pristopa.
Pohlepni algoritem je pristop k reševanju problema z izbiro najboljše trenutno razpoložljive možnosti, ne da bi se skrbeli za prihodnji rezultat, ki bi ga prinesel. Z drugimi besedami, lokalne najboljše odločitve so usmerjene v doseganje najboljših svetovnih rezultatov.
Ta algoritem morda ni najboljša možnost za vse težave. V nekaterih primerih lahko povzroči napačne rezultate.
Ta algoritem se nikoli ne vrne, da bi spremenil sprejeto odločitev. Ta algoritem deluje v pristopu od zgoraj navzdol.
Glavna prednost tega algoritma je:
- Algoritem je lažje opisljiv .
- Ta algoritem lahko deluje bolje kot drugi algoritmi (vendar ne v vseh primerih).
Izvedljiva rešitev
Izvedljiva rešitev je tista, ki nudi optimalno rešitev problema.
Pohlepni algoritem
- Za začetek je nabor rešitev (ki vsebuje odgovore) prazen.
- Na vsakem koraku se element doda v nabor rešitev.
- Če je nabor rešitev izvedljiv, se trenutni element ohrani.
- V nasprotnem primeru je postavka zavrnjena in nikoli več obravnavana.
Primer - Pohlepni pristop
Težava: Znesek morate spremeniti z najmanjšim možnim številom kovancev. Znesek: 28 USD Na voljo kovanci: 5 USD kovanec 2 USD kovanec 1 USD kovanec
Rešitev:
- Ustvarite prazen nabor rešitev = ().
- kovanci = (5, 2, 1)
- vsota = 0
- Medtem ko je vsota ≠ 28, naredite naslednje.
- Med kovanci izberite kovanec C, tako da je vsota + C <28.
- Če je C + vsota> 28, ne vrnite nobene rešitve.
- V nasprotnem primeru je vsota = vsota + C.
- V nabor rešitev dodajte C.
Do prvih 5 ponovitev vsebuje nabor rešitev 5 kovancev za 5 dolarjev. Po tem dobimo kovanec za 1 $ in nazadnje še 1 $ 1 kovanec.
Pohlepni algoritmi
- Razvrsti razvrstitev
- Nahrbtnik problem
- Najmanjše drevo
- Problem najkrajše poti z enim virom
- Problem razporejanja delovnih mest
- Primov algoritem minimalnega raztezajočega se drevesa
- Kruskalov algoritem minimalnega raztezajočega se drevesa
- Dijkstrin algoritem minimalnega raztezajočega se drevesa
- Huffmanovo kodiranje
- Ford-Fulkersonov algoritem
