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?
Un greedy siempre debe seguir ciertos lineamientos para poder ser aplicado. A veces estos son muy difíciles de ver o demostrar pero, si cumplimos la mayoría de los lineamientos, muy probablemente estaremos ante un reto que puede ser resuelto usando esta técnica. Algo muy interesante es que muchas personas han utilizado esta técnica sin siquiera saberlo, ya que es de cierta manera muy intuitiva. Podemos utilizar algoritmos greedy si:
- 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?
Usualmente debemos realizar alguna operación de ordenamiento o colocar condiciones que nos permitan calcular el máximo o mínimo requerido por el problema. Vamos a utilizar un ejemplo concreto para poder mostrar cómo es y cómo se soluciona un problema usando el algoritmo greedy: clic aquí.
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
Un ejemplo un poco más de la vida real podría ser el de organizar tareas en rangos de tiempo: imaginemos que tenemos muchísimas cosas que hacer en nuestro día a día, pero queremos maximizar la cantidad de tareas que realizamos diariamente. Nosotros no podemos dividir nuestra atención en dos tareas a la vez, así que una acción lógica es organizarnos de manera que ejecutemos las tareas más pequeñas primero y, luego, las que nos consuman más tiempo.
Algo interesante es que podemos incluso añadir importancia en forma de “peso”, es decir, quizás una tarea muy larga vale más que todas las pequeñas juntas. Esto también puede ser solucionado agregando un par de condiciones al ordenamiento, haciendo una especie de proporción o “ratio” entre el tiempo que toma realizar una tarea y la importancia que tiene en escala numérica.
Algoritmos greedy famosos
Hay algoritmos greedy muy famosos y utilizados ampliamente, de los cuales me gustaría hablar más en profundidad cuando ya estemos entrando en un área más avanzada de la programación. Pero podemos mencionarlos: el algoritmo de Kruskal, el algoritmo de Prim y el algoritmo de Dijkstra.
Conclusión
Los algoritmos greedy son una parte muy importante de la programación y organización de datos. Muchas aplicaciones usan algoritmos de este estilo para organizar nuestras agendas o cosas similares, haciéndolo en el menor tiempo posible, dando como resultado una resolución más eficiente y precisa. Así abrimos el espacio para hablar sobre algoritmos un poco más complejos que se basan en los mismos principios. Aún hay muchos algoritmos voraces más complejos de los cuales hablar, pero eso quedará para un próximo artículo, el cual planeo que sea acerca de algoritmos sobre grafos, donde incluiré los algoritmos greedy famosos, que mencioné más arriba.
Por Rodolfo Miquilarena, senior developer.
