Las cosas

3.2 Técnicas de diseño de algoritmos

Algoritmos Voraces
Los algoritmos voraces típicamente se utilizan en la solución de problemas de
optimización y se caracterizan por ser:
Sencillos de diseñar y codificar.
Miopes: toman decisiones con la información que tienen disponible de forma
inmediata, sin tener en cuenta sus efectos futuros.
Eficientes: dan una solución rápida al problema (aunqueésta no sea siempre la
mejor).
Los algoritmos voraces se caracterizan por las propiedades siguientes:
Tratan de resolver problemas de forma óptima.
Disponen de un conjunto (o lista) de candidatos.
A medida que avanza el algoritmo vamos acumulando dos conjuntos:
 candidatos considerados y seleccionados.
 candidatos considerados y rechazados.
Existe una función que comprueba si un ciertoconjunto de candidatos constituye
una solución de nuestro problema, ignorando si es óptima o no por el momento.
Existe una función que comprueba si un cierto conjunto de candidatos es factible,
esto es, si es posible o no completar el conjunto añadiendo otros candidatos para
obtener al menos una solución al problema. Una vez más, no nos importa si la
solución es óptima o no. Normalmente seespera que al menos se pueda obtener
una solución a partir de los candidatos disponibles inicialmente.
Existe una función de selección que indica cuál es el más prometedor de los
candidatos restantes no considerados aún.
Implícitamente está presente una función objetivo que da el valor a la solución que
hemos hallado (valor que estamos tratando de optimizar).
Los algoritmos voraces suelen serbastante simples. Se emplean sobre todo para
resolver problemas de optimización, como por ejemplo, encontrar la secuencia
óptima para procesar un conjunto de tareas por una computadora, hallar el camino
mínimo de un grafo, etc. Habitualmente, los elementos que intervienen son:
 un conjunto o lista de candidatos (tareas a procesar, vértices del grafo,
etc.);
 un conjunto de decisiones yatomadas (candidatos ya escogidos);
 una función que determina si un conjunto de 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 es posible alcanzar una
solución al problema, suponiendo que esta exista;
 una función de selección que escoge elcandidato aún no seleccionado que
es más prometedor;
 una función objetivo que da el valor/costo de una solución (tiempo total del
proceso, la longitud del camino, etc.) y que es la que se pretende maximizar
o minimizar.
Divide y Vencerás
Otra técnica común usada en el diseño de algoritmos es el de “divide y vencerás”
y que consta de dos partes:
Dividir: los problemas más pequeños seresuelven recursivamente (excepto, por
supuesto, los casos base).
Vencer: la solución del problema original se forma entonces a partir de las
soluciones de los subproblemas.
Las rutinas en las cuales el texto contiene al menos dos llamadas recursivas se
denominan algoritmos de divide y vencerás, no así las rutinas cuyo texto sólo
contiene una llamada recursiva.
La idea de la técnica divide yvencerás es dividir un problema en subproblemas del
mismo tipo y aproximadamente todos ellos del mismo tamaño, resolver los
subproblemas recursivamente y, finalmente, combinar la solución de los
subproblemas para dar una solución al problema original. La recursión finaliza
cuando el problema es pequeño y la solución es fácil de construir directamente.
Programación Dinámica
La programación dinámicaes un método para reducir el tiempo de ejecución de un
algoritmo mediante la utilización de subproblemas superpuestos y subestructuras
óptimas. El matemático Richard Bellman inventó la programación dinámica en
1953.
Una subestructura óptima significa que soluciones óptimas de subproblemas
pueden ser usadas para encontrar las soluciones óptimas del problema en su
conjunto. En general, se...