Programación en algoritmos codiciosos

En este artículo, discutiremos varios algoritmos de programación para algoritmos codiciosos . Muchos problemas de programación se pueden resolver utilizando algoritmos codiciosos.

Planteamiento del problema: dados N eventos con sus horas de inicio y finalización, encuentre un cronograma que incluya tantos eventos como sea posible. No es posible seleccionar un evento parcialmente. Considere los siguientes eventos:

• En este caso, el número máximo de eventos es dos. Como eventos seleccionados B y D son los siguientes:

• Es posible inventar varios algoritmos codiciosos para el problema.

Algoritmos que funcionan con todos los casos:

Algoritmo 1 : 

• La primera idea es seleccionar eventos tan cortos como sea posible. En el ejemplo, este algoritmo selecciona los siguientes eventos:

• Sin embargo, seleccionar eventos cortos no siempre es una estrategia correcta. Por ejemplo, el algoritmo falla en el siguiente caso:

• Si se selecciona un evento corto, solo puede seleccionar un evento. Sin embargo, sería posible seleccionar ambos eventos largos.

Algoritmo 2 :

• Otra idea es seleccionar siempre el próximo evento posible que comience lo antes posible. Este algoritmo selecciona los siguientes eventos:

• Sin embargo, dado un contraejemplo para este algoritmo. En este caso, el algoritmo solo selecciona un evento:

• Si se selecciona el primer evento, no es posible seleccionar ningún otro evento. Sin embargo, sería posible seleccionar los otros dos eventos.

Algoritmo 3 :

• La tercera idea es seleccionar siempre el próximo evento posible que finalice lo antes posible. Este algoritmo selecciona los siguientes eventos:

• Resulta que este algoritmo siempre produce una solución óptima.
• La razón de esto es que siempre es una opción óptima seleccionar primero un evento que termine lo antes posible.
• Después de esto, es una opción óptima seleccionar el próximo evento usando la misma estrategia, etc., hasta que no se pueda seleccionar ningún otro evento.
• Una forma en que funciona el algoritmo es considerar lo que sucede si primero se selecciona un evento que finaliza más tarde que el evento que finaliza lo antes posible.
• Ahora, teniendo como máximo el mismo número de opciones, cómo se puede seleccionar el próximo evento.
• Por lo tanto, seleccionar un evento que finaliza más tarde nunca puede generar una mejor solución, y el algoritmo voraz es correcto.