Algorisme voraç

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, amb l'esperança (no sempre complerta) d'arribar a un òptim global. L'algorisme voraç no torna mai enrere per reavaluar les eleccions ja preses.

Esquema

Tot algorisme voraç conté el següent:

• 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

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.

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) o el d'empaquetar objectes de diferents volums en el mínim nombre de caixes idèntiques.

Bibliografia

• Bofill i Arasa, Miquel. Teoria d'autòmats i llenguatges formals II. Barcelona: Edicions de la UOC, 2000. ISBN 84-8429-098-0. 
• Cormen, Thomas H; Leiserson, Charles E; Rivest, Ronald L; Stein, Clifford. Introduction To Algorithms. Boston: MIT Press, 2003. ISBN 0-262-03293-7. 
• Curtis, S.A. «The classification of greedy algorithms». Science of Computer Programming, Vol. 49, 2003, pàg. 125-157. DOI: 10.1016/j.scico.2003.09.001. ISSN: 0167-6423.
• DeVore, R.A; Temlyakov, V.N. «Some remarks on greedy algorithms». Advances in Computational Mathematics, Vol. 5, 1996, pàg. 173-187. DOI: 10.1007/BF02124742. ISSN: 1019-7168.
• Franquesa i Niubò, Carles. Algorísmia comentada. Barcelona: Publicacions i Edicions de la Universitat de Barcelona, 2004. ISBN 978-84-475-3715-0. 
• Serna Iglesias, Ma José. Els Límits de la computació: indecidibilitat i NP-completesa. Barcelona: Edicions UPC, 2001. ISBN 84-8301-513-7. 

Vegeu també

• Algorisme de Huffman
• Algorisme de Dijkstra
• Algorisme heurístic

Enllaços externs

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