Algoritmo greddy

Algoritmos Voraces (Greedy)

Algoritmos greedy
• Se aplican a problemas de optimización. • Un algoritmo greedy toma las decisiones en  función de la información que está  disponible en cada momento.  • Una vez tomada la decisión no vuelve a  replantearse en el futuro. • Suelen ser rápidos y fáciles de  implementar. • No garantizan alcanzar la solución óptima. 

Elementos de la técnica• Conjunto de candidatos a seleccionar. • Conjunto de candidatos seleccionados • Función Solución: determina si los candidatos  seleccionados han alcanzado una solución. • Función de Factibilidad: determina si es posible  completar el conjunto de candidatos seleccionas  para alcanzar una solución al problema. • Función Selección: determina el mejor candidatos  del conjunto a seleccionar. •Función Objetivo: da el valor de la solución  alcanzada.

Esquema Voraz.
Funcion voraz(set C) { // Inicialmente, C contiene todos los candidatos   set S;                // Solución inic. Vacía   while (!C.empty() && !solucion(S)) {      x = seleccionar(C);      C.erase(x);   if (factible(S,x)) S.insert(x);   }    if solucion(S) return S    else return “No_hay_solucion”; }Problema Selección de Actividades
• Tenemos la entrada de una Exposición que  organiza un conjunto de actividades 
– Para cada actividad conocemos su horario de  comienzo y fin.  – Con la entrada podemos asistir a todas las  actividades.  – Hay actividades que se solapan en el tiempo. 

• Objetivo: Asistir al mayor número de  actividades => Problema de selección de  actividades. 
–Otra alternativa: Minimizar el tiempo que estamos ociosos.

Selección de Actividades
• Dado un conjunto S de n actividades si = tiempo de comienzo de la actividad i fi = tiempo de finalización de la actividad i • Encontrar el subconjunto de actividades compatibles  A de tamaño  máximo 

3 4 2 1 5 6

Fijemos los elementos de la técnica
• • • • Candidatos a seleccionar.: Conj. Actividades, SCandidatos seleccionados: Conjunto A, inic. A={Ø } Función Solución: S={Ø }. Función Selección: determina el mejor candidato, x – Mayor, menor duración. – Menor solapamiento. – Termina antes.◀ • Función de Factibilidad: x es factible si es compatible  con las actividades en A. • Función Objetivo: Tamaño de A.

Algoritmo Greedy
• SelecciónActividades(Activ S,A)
– Ordenar S en orden creciente de tiempo de finalización – Seleccionar la primera actividad. – Repetir • Seleccionar la siguiente actividad en el orden  que comience despues de que la actividad  previa termine. – Hasta que S este vacio.;                 
•

SelecciónActividadesGreedy(S, A){      qsort(S,n); // según tiempo de finalización      A[0]= S[0] //Seleccionar primera actividad       i=1; prev = 0;     while (!S.empty())  {  // es solucion(S)           x = S[i]                                      // seleccionar;          if (x.inicio > A[prev].fin)             //factible  x     A[prev++] = x;                    // insertamos en solucion         else i++;                                   // rechazamos      } } Eficiencia ??

Demostración técnica greedy alcanza el  óptimo:   
Tenemos que demostrar que    Optimo Local  Solución global optimal • Paso 1. Demostrar que la primera decisión es correcta. • Paso 2. Demostrar que existen subestructuras  optimales. – Es decir, cuando la se ha tomado la decisión  #1, el  problema se reduce a encontrar una solución optimal  para el sub­problema de selección de actividades   que tiene como candidatos aquellas actividades en   S compatibles con #1

Demostración:
•1.) Primera decisión es correcta Teorema: 
   Si S es un problema de selección de actividades  ordenado en orden creciento de tiempo de  finalización, entonces  existe una solución  optimal A  S tal que  {1}  A
• Idea de la demostración: Si una solución optimal B  que no contiene  {1}, siempre podremos reemplazar la  primera actividad en B por {1} (??). Obteniendo el ...