TÉCNICAS PARA DISEÑO DE ALGORITMOS

ALGORITMOS VORACES

- Descripción:

Los algoritmos voraces, sirven para resolver problema de optimización. Trata de tomar el mejor elemento sin pensar a donde exactamente va a llevarle, si no funciona elimina esa opción y sigue con la anterior y prueba con los elementos que faltan hasta llegar a la solución deseada.

Para poder explicar mejor como funcionan yo diría que es como tener un árbol y un insecto subiendo por el, trata de llegar a una fruta en una rama, lo que el insecto hace es escoger la rama que parece mejor opción entre las que tiene, y sube por ella, si esta rama tiene mas divisiones sigue tomando decisiones de cual elegir según le parezca, si al llegar a la última rama del camino que eligió no le funciona deja regresa hasta el tramo donde escogió ese camino, y toma el que le parece mejor segunda opción, Así sucesivamente, hasta encontrar la fruta que esta buscando.

- Problema que ayuda a resolver:
Regularmente un algoritmo voraz es utilizado para resolver problemas de optimización, en otras palabras este tipo de algoritmo es mucho más agradable para poder ayudar a solucionar situaciones que consisten en elegir el mejor elemento tomado desde un conjunto de datos disponibles, esto para obtener la solución más adecuada en base a un criterio definido.


- ¿Cuando conviene usarlo?:

• Primero tienes que encontrar si hay un conjunto de candidatos que optimice la solución que quieres.
• Verificar que el conjunto de candidatos es vacío.
• Después escoge el candidato que sea más prometedor.
• Si en un caso el conjunto no es compatible se rechaza el candidato y ya no se considera en el futuro.
• En caso contrario se incorpora al conjunto de candidatos escogidos y permanece siempre en el.
• UN ALGORITMO VORAZ ES CORRECTO SI LA SOLUCIÓN ENCONTRADA ES SIEMPRE OPTIMA.

- ¿Cuando no conviene usarla (o no aplica):

Los algoritmos voraces suelen ser muy eficientes y pueden implementarse de forma sencilla. Sin embargo, la mayoría de los intentos de crear un algoritmo voraz correcto fallan a menos que exista previamente una prueba precisa que demuestre la certeza del algoritmo.

Cuando una estrategia voraz falla al producir resultados óptimos en las entradas, en lugar de algoritmo suele denominarse heurística.

Las heurísticas resultan útiles cuando la velocidad es más importante que los resultados exactos (por ejemplo, cuando resultados "bastante buenos" son suficientes).

- Ejemplo de instancia que resuelve un algoritmo ligado a la técnica:

Es común que las conferencias científicas estén divididas en varias secciones simultáneas.
Se necesita realizar el trabajo de varias secciones de forma simultánea para reducir el tiempo de la conferencia y tener suficiente tiempo para las comidas, tomar café, y las discusiones informales. Sin embargo, es posible que se estén dando ponencias interesantes de forma simultánea en distintas secciones.
Un participante ha escrito una tabla con los horarios de todas las ponencias que le interesan. Te ha pedido que encuentres la cantidad máxima de ponencias a los que puede asistir.La primera línea contiene el número 1 ≤ n ≤ 100000, que es la cantidad de ponencias interesantes. Cada una de las siguientes n líneas contiene a dos enteros ts y te separados por un espacio (1 ≤ ts < te ≤ 30000). Estos números corresponden al horario en que las ponencias empiezan y terminan. Los horarios están dados en minutos a partir del inicio del evento.
Escribir la cantidad máxima de ponencias a las que el participante puede asistir. El participante no puede estar en dos ponencias al mismo tiempo, y a las ponencias a las que asista tienen que estar separadas por un minuto por lo menos. Por ejemplo, si una ponencia termina en el minuto 15, la siguiente ponencia a la que puede asistir debe empezar al minuto 16 o después.

#include<stdio.h>
long i, N, Start, Endg;
long aiSegments[300001];

long max_segments(long aiArray[])
{
     long i, End, Total;
     for(i=1,End=0,Total=0;i<=30000;i++)
     if(aiArray[i]>iEnd)
     {
          End=i;
          Total++;
     }
     return(Total);
}

int main(void)
{
    scanf("%ld",%N);
    for(i=0;i<iN;i++)
    {
        scanf("%ld %ld",&Start, %End);
        if(iStart>aiSegments[iEnd])
             aiSegments[End]=Start;
    }
    printf("%ld",mx_segments(aiSegments));
}