Algoritme voraç

Un algoritme voraç determina el mínim número de monedes que deu tornar-se en el canvi. En la figura es mostren els passos que un ser humà deuria seguir per a emular a un algoritme voraç per a acumular 36 cèntims usant solament monedes de valors nominals d'1, 5, 10 i 20. La moneda del major valor menor que el restant degut és l'òptim local en cada pas. Note's que en general el problema de devolució del canvi requerix programació dinàmica o programació llineal per a trobar una solució òptima. No obstant, molts sistemes monetaris, incloent l'euro i el dólar nortamericà, són casos especials a on l'estratègia de l'algoritme voraç dona en la solució òptima.

En ciències de la computació, un algoritme voraç (també conegut com codicioso, goloso, ávido, devorador o greedy) és una estratègia de busca per la qual se seguix una heurística consistent en elegir l'opció òptima en cada pas local en l'esperança d'aplegar a una solució general òptima. Este esquema algorítmic és el que menys dificultats planteja a l'hora de dissenyar i comprovar el seu funcionament. Normalment s'aplica als problemes d'optimisació.

Esquema

Donat un conjunt finito d'entrades $C$, un algoritme voraç torna un conjunt $S$ (seleccionats) tal que $S\subseteq C$ i que ademés complix en les restriccions del problema inicial. A cada conjunt $S$ que satisfaça les restriccions se li sol denominar prometedor, i si este ademés conseguix que la funció objectiu es minimise o maximizar (segons corresponga) direm que $S$ és una solució òptima.

Característiques

S'utilisen generalment per a resoldre problemes d'optimisació (obtindre el màxim o el mínim). Prenen decisions en funció de l'informació que està disponible en cada moment. Una volta presa la decisió, esta no torna a replantejar-se en el futur. Solen ser ràpits i fàcils d'implementar. No sempre garantisen alcançar la solució òptima.

L'enfocament “greedy” no nos garantisa obtindre solucions òptimes. Per lo tant, sempre caldrà estudiar la correcció de l'algoritme per a demostrar si les solucions obtingudes són òptimes o no.

Elements dels que consta la tècnica

El conjunt $C$ de candidats, entrades del problema. Funció solució. Comprova, en cada pas, si el subconjunt actual de candidats elegits forma una solució (no importa si és òptima o no ho és). Funció de selecció. Informa quin és l'element més prometedor per a completar la solució. Este no pot haver segut triat en anterioritat. Cada element és considerat una sola volta. Després, pot ser rebujat o acceptat i pertanydrà a $C\setminus S$. Funció de factibilidad. Informa si a partir d'un conjunt es pot aplegar a una solució. Ho aplicarem al conjunt de seleccionats unit en l'element més prometedor. Funció objectiu. És aquella que volem maximizar o minimisar, el núcleu del problema.

Funcionament

L'algoritme tria en cada pas al millor element $x\in C$ possible, conegut com el element més prometedor. S'elimina eixe element del conjunt de candidats ($C\leftarrow C\setminus \{x\}$) i, acte seguit, comprova si l'inclusió d'este element en el conjunt d'elements seleccionats ($S\cup \{x\}$) produïx una solució factible.

En cas que aixina siga, s'inclou eixe element en $S$. Si l'inclusió no fora factible, es descarta l'element. Iteramos el bucle, comprovant si el conjunt de seleccionats és una solució i, si no és aixina, passant al següent element del conjunt de candidats.

Referències

Departament de ciències de la computació Universitat de Granada. (s. f.). Algoritmes Greedy. Abad Soriano, M. T. (2007–2008). Algoritmes voraços.

• Fillottrani, P. R. (2017). Algoritmes i complexitat.