¿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?

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 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í.

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.

Turning good ideas into outstanding software.

Turning good ideas into outstanding software.