Algoritmo Selección de Actividades en C++

Este fue el tema final para la exposición de mi proyecto en Técnicas de Construcción de Programas, recopile información de muchos sitios web para lograr entender y asi poder implementar. Espero que les guste este pequeño aporte.



Suponga que se cuenta con un conjunto S ={a1, . . . , an}, de actividades que necesitan usar un recurso que no puede ser usado sino por una actividad a la vez. Cada actividad ai tiene un tiempo inicial si y final fi asociados, tal que si≤ fi< ∞.

Las actividades ai y aj son compatibles si la intersección de los intervalos [si, fi) ∩[sj, fj) = φ.

El problema de selección de actividades:
Entrada: S = {a1, ..., an} si, fi1 ≤ i ≤ n
Salida: A ⊆ S: todas las actividades de A son mutuamente compatibles, y | A | es el máximo posible.


Las actividades representadas de forma grafica :


Los subconjuntos : {a3, a9, a11}, {a1, a4, a8, a11}, {a2, a4, a9, a11} estan compuestos de actividades mutuamente compatibles.

Criterio de selección voraz
  1. La parte fundamental de un algoritmo voraz es su criterio de seleccion voraz:
  2. Seleccionar la actividad que comience mas temprano.
  3. Seleccionar la actividad de menos duracion.
  4. Seleccionar la actividad que termine m as pronto.
  5. Seleccionar la actividad que menos solapamientos tenga con el resto de actividades candidatas.
  6. Para que puedan formar una solucion, debemos adjuntarles el criterio de completabilidad: que no se solape con las actividades ya seleccionadas.

Algoritmo


Implementación


Comentarios

Entradas populares de este blog

Obtener numeros aleatorios en C++ (rand, srand)

Árboles Binarios de Búsqueda en C++ | Recorrido por niveles (Amplitud)

Pilas en C++