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
Algoritmo
Implementación
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
- La parte fundamental de un algoritmo voraz es su criterio de seleccion voraz:
- Seleccionar la actividad que comience mas temprano.
- Seleccionar la actividad de menos duracion.
- Seleccionar la actividad que termine m as pronto.
- Seleccionar la actividad que menos solapamientos tenga con el resto de actividades candidatas.
- 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
Publicar un comentario