Vés al contingut

Algorisme voraç

De la Viquipèdia, l'enciclopèdia lliure

En matemàtiques, un algorisme voraç és un algorisme que, per resoldre un problema d'optimització, fa una seqüència d'eleccions, prenent en cada pas un òptim local,[1] amb l'esperança (no sempre complerta)[2] d'arribar a un òptim global. L'algorisme voraç no torna mai enrere per reavaluar les eleccions ja preses.

Esquema

[modifica]

Tot algorisme voraç conté el següent:[3]

  • Un conjunt no infinit de candidats, de possibles solucions (parcials o totals) del problema,
  • Una funció de selecció, que ens permet seleccionar el millor dels candidats,
  • Una funció de factibilitat, que ens permet avaluar si el candidat ajuda a resoldre el problema,
  • Una funció solució, que avalua si el conjunt de candidats seleccionats soluciona el problema (totalment o parcialment).

Exemples

[modifica]
Un algorisme voraç determina el mínim nombre de monedes al tornar un canvi. Aquests són els pasos que qualsevol persona fa emulant un algorisme voraç per obtenir els 36 cèntims utilitzant monedes només de {1, 5, 10, 20} cèntims.

L'exemple més habitual és el de tornar un canvi amb el mínim de monedes de determinat valor. A la dreta es pot veure com s'escullen les monedes per tornar un canvi de 36 cèntims. El conjunt de candidats és {20, 10, 5, 1}, la funció de selecció és escollir sempre la de valor més alt, la funció de factibilitat és no superar mai els 36 cèntims amb els candidats escollits, la funció solució és aconseguir 36 cèntims.

Els algorismes voraços no garanteixen sempre una solució, ni que la solució obtinguda sigui l'òptima. En l'exemple anterior, si el conjunt de candidats hagués sigut {50, 20, 10, 5, 2}, l'algorisme no retornaria cap solució perquè en arribar a 35 cèntims {20+10+5} no tindria cap candidat que ajudés a resoldre el problema. En canvi, és obvi que existeix una solució amb {20+10+2+2+2}. En general, l'algorisme voraç produeix sempre una solució quan el conjunt de candidats té estructura de matroide.[4][5][6]

Altres exemples típics són el de minimitzar el recorregut que ha de fer un viatjant de comerç per a visitar una sèrie de clients distanciats entre ells (vegeu algorisme de Dijkstra)[7] o el d'empaquetar objectes de diferents volums en el mínim nombre de caixes idèntiques.[8]

Referències

[modifica]
  1. Curtis, pàgina 125.
  2. Franquesa Niubó, pàgina 199.
  3. Bofill i Arasa, pàgines 135-136.
  4. Cormen, pàgines 370 i 393 i ss.
  5. Curtis, pàgina 148.
  6. Franquesa Niubó, pàgina 200.
  7. Bofill i Arasa, pàgines 137 i següents.
  8. Serna Iglesias, pàgina 197.

Bibliografia

[modifica]

Vegeu també

[modifica]

Enllaços externs

[modifica]
  • Paul E., Black. «Greedy algorithm». Dictionary of Algorithms and Data Structures, 2005. [Consulta: 3 abril 2015].