Analsis y diseño de algoritmos

Estrategias para el diseño de Algoritmos


Las estrategias más comunes para el diseño de algoritmos son: voraz, divide y vencerás, programación dinámica y backtracking.

1

Algoritmo voraz



También conocido como ávido, devorador o goloso. Los algoritmos voraces suelen ser bastante simples. Se emplean sobre todo para resolver problemas de optimización, como por ejemplo, encontrarla secuencia óptima para procesar un conjunto de tareas por un computador, hallar el camino mínimo de un grafo, etc.
2

Algoritmo voraz

 







Habitualmente, los elementos queintervienen son: un conjunto o lista de candidatos (tareas a procesar, vértices del grafo, etc); un conjunto de decisiones ya tomadas (candidatos ya escogidos); una función que detemina si un conjuntode candidatos es una solución al problema (aunque no tiene por qué ser la óptima); una función que determina si un conjunto es completable, es decir, si añadiendo a este conjunto nuevos candidatos esposible alcanzar una solución al problema, suponiendo que esta exista; una función de selección que escoge el candidato aún no seleccionado que es más prometedor; una función objetivo que da elvalor/costo de una solución (tiempo total del proceso, la longitud del camino, etc) y que es la que se pretende maximizar o minimizar;
3

Algoritmo voraz


Para resolver el problema de optimizaciónhay que encontrar un conjunto de candidatos que optimiza la función objetivo. Los algoritmos voraces proceden por pasos. Inicialmente el conjunto de candidatos es vacío. A continuación, en cada paso,se intenta añadir al conjunto el mejor candidato de los aún no escogidos, utilizando la función de selección. Si el conjunto resultante no es completable, se rechaza el candidato y no se le vuelve aconsiderar en el futuro. En caso contrario, se incorpora al conjunto de candidatos escogidos y permanece siempre en él. Tras cada incorporación se comprueba si el conjunto resultante es una...