Algoritm lacom

În acest tutorial, veți afla ce este un algoritm Greedy. De asemenea, veți găsi un exemplu de abordare lacomă.

Un algoritm lacom este o abordare pentru rezolvarea unei probleme prin selectarea celei mai bune opțiuni disponibile în acest moment, fără a vă face griji cu privire la rezultatul viitor pe care l-ar aduce. Cu alte cuvinte, cele mai bune alegeri locale vizează producerea celor mai bune rezultate la nivel global.

Este posibil ca acest algoritm să nu fie cea mai bună opțiune pentru toate problemele. Poate produce rezultate greșite în unele cazuri.

Acest algoritm nu se întoarce niciodată pentru a inversa decizia luată. Acest algoritm funcționează într-o abordare de sus în jos.

Principalul avantaj al acestui algoritm este:

  1. Algoritmul este mai ușor de descris .
  2. Acest algoritm poate funcționa mai bine decât alți algoritmi (dar, nu în toate cazurile).

Soluție fezabilă

O soluție fezabilă este cea care oferă soluția optimă la problemă.

Algoritm lacom

  1. Pentru început, setul de soluții (care conține răspunsuri) este gol.
  2. La fiecare pas, un element este adăugat în setul de soluții.
  3. Dacă setul de soluții este fezabil, elementul curent este păstrat.
  4. Altfel, articolul este respins și nu mai este luat în considerare.

Exemplu - Abordarea lacomă

 Problemă: Trebuie să faceți o modificare a unei sume folosind cel mai mic număr posibil de monede. Suma: 28 $ Monede disponibile: Monedă de 5 $ Monedă de 2 $ Monedă de 1 $

Soluţie:

  1. Creați un set de soluții gol = ().
  2. monede = (5, 2, 1)
  3. sumă = 0
  4. În timp ce suma ≠ 28, faceți următoarele.
  5. Selectați o monedă C din monede astfel încât suma + C <28.
  6. Dacă suma C +> 28, nu returnați nicio soluție.
  7. Altfel, suma = suma + C.
  8. Adăugați C la setul de soluții.

Până la primele 5 iterații, setul de soluții conține 5 monede de 5 USD. După aceea, primim 1 monedă de 2 $ și, în cele din urmă, 1 monedă de 1 $.

Aplicații pentru algoritmul lacom

  • Selecție Sortare
  • Problema rucsacului
  • Arborele minim care se întinde
  • Cea mai scurtă problemă a căii cu o singură sursă
  • Problemă de programare a locurilor de muncă
  • Algoritmul copacului minim al lui Prim
  • Algoritmul arborelui minim al lui Kruskal
  • Algoritmul arborelui minim al Dijkstra
  • Codificare Huffman
  • Algoritmul Ford-Fulkerson

Articole interesante...