¿Qué es un algoritmo voraz o greedy?

Un algoritmo greedy es aquel que tomando exclusivamente la solución óptima local puede generar una solución óptima global. Usualmente este algoritmo se utiliza en problemas donde se busca encontrar el mínimo o el máximo de algo… no siempre es la estrategia correcta para resolver estos problemas, pero en muchos casos se puede utilizar directamente o ver el reto de alguna manera que nos permita aplicar la técnica. Pasemos ahora a hablar un poco de cómo podemos identificar un greedy.

¿Cómo identificar un greedy?

  • El tamaño de los datos es demasiado grande como para utilizar algoritmos O(n²) o superior, es decir, estamos ante cientos de miles de entradas de datos a ser procesados.
  • El problema puede traducirse en una optimización de mínimo o máximo. Por ejemplo, la máxima suma posible en un arreglo dado que tenemos un límite de elementos “K” que podemos tomar.
  • Los datos se pueden manipular para seguir un orden o de plano siguen un orden estricto.

¿Cómo aplicar un greedy?

El problema anteriormente nombrado nos dice cuántas estampillas necesita Lucy para vencer a Raymond y cuántos amigos pueden prestarle cartas. Además de saber cuántas estampillas tiene cada amigo, el objetivo es saber cuál es la menor cantidad de amigos que ella necesita fastidiar para pedirles estampillas, de manera que consiga tener más que Raymond. Antes de leer el siguiente párrafo te invito a pensar un poco la solución…

Con todos estos datos ya debes haber supuesto que la mejor estrategia es ordenar de mayor a menor las estampillas ofrecidas por los amigos de Lucy y luego simplemente ir sumándolas hasta que el valor de cartas acumuladas sea mayor o igual al número de cartas de Raymond. Una vez que eso ocurra deberíamos saber el mínimo número de amigos que Lucy necesita fastidiar para humillar a su pobre rival. A su vez, si no podemos superar o igualar el número de cartas de Raymond, debemos imprimir “impossible”, es decir, que no encontramos una solución para este caso de prueba en particular. Esta solución es O (N*Log2(N)).

Como pueden ver, la solución es muy intuitiva, aunque hay otros algoritmos y problemas mucho más difíciles que caen en esta categoría, todos siguen los lineamientos anteriormente nombrados.

Otro ejemplo de greedy

Algoritmos greedy famosos

Conclusión

Por Rodolfo Miquilarena, senior developer.

Turning good ideas into outstanding software.

Turning good ideas into outstanding software.