Algoritmos

Este material es proporcionado al estudiante con fines educativos, para la crítica y la investigación respetando la reglamentación en materia de derechos de autor.
Este documento no tiene costo alguno. El uso indebido de este documento es responsabilidad del estudiante.

Técnicas de diseño
de algoritmos

A través de los años, los científicos de la computación han identificado diversas téc-nicas generales que a menudo producen algoritmos eficientes para la resolución de
muchas clases de problemas. Este capitulo presenta algunas de las técnicas más importantes como dividir para vencer, programación dinámica, técnicas ávidas, el método de retroceso y búsqueda local. En el intento de diseñar un algoritmo para resolver un problema dado, a menudo es útil plantear cuestiones como %quéclase de
solución se puede obtener de la programación dinámica, del enfoque ávido, de la técnica dividir para vencer o de otra técnica estándar?».
Sin embargo, debe subrayarse que hay algunos problemas, como los NP completos, para los cuales ni éstas ni otras técnicas conocidas producirán soluciones eficientes. Cuando se encuentra algún problema de este tipo, suele ser útil determinar
si lasentradas al problema tienen características especiales que se puedan explotar
en la búsqueda de una solución, o si puede usarse alguna solución aproximada sencilla, en vez de la solución exacta, dificil de calcular.

10.1

Algoritmos dividlr para vencer

Tal vez la t h i c a más importante y aplicada para el diseño de algoritmos eficientes
sea la estrategia llamada dividir para vencer, queconsiste en la descomposición de
un problema de tamaño n en problemas más pequeños, de modo que a partir de la
solución de dichos problemas sea posible construir con facilidad una solución al problema completo. Ya se han visto varias aplicaciones de esta técnica, como la clasificación por intercalación o los árboles binarios de búsqueda.
Para ilustrar el método, considerese el conocido acertijode las «torres d e Han oh. Consta de tres postes A , B y C. Inicialmente, el poste A tiene cierta cantidad
de discos de distintos tamaños, con el más grande en la parte inferiof y otros suresivamente mas pequeños encima, como se muestra en la figura 10.1. El objeto del
acertijo es pasar un disco a la vez de un poste a otro, sin colocar nunca un disco grande sobre otro más pequeño, hasta quetodos los discos estén en el poste B.
Pronto se descubre que el acertijo puede resolverse con el sencillo algoritmo siguiente. Se imaginan los postes dispuestos en un triángulo. Con u n número de movimientos impar, se mueve el disco más pequeño hacia un poste en el sentido de las
manecillas del reloj. Con un número de movimientos pares, se hace el único movimiento válido que no implique al discomás pequeño.

Aho, Alfred V., John E. Hopcroft y Ullman. (1998). Técnicas de diseño de algoritmos.
En Estructuras de datos y algoritmos (pp. 307-347). México: Adisson Wesley Longman de México.

Este material es proporcionado al estudiante con fines educativos, para la crítica y la investigación respetando la reglamentación en materia de derechos de autor.
Este documento no tiene costo alguno.El uso indebido de este documento es responsabilidad del estudiante.

Fig. 10.1. Posición inicial

en el acertijo de las torres de Hanoi.

El algoritmo anterior es conciso y correcto, pero es difícil entender por qu6 funciona y de descubrir intuitivamente. En cambio, considérese el siguiente enfoque de
dividir para vencer. El problema de pasar los n discos más pequeños de A a B puedeconsiderarse compuesto de dos problemas de tamaño n - 1. Primero se mueven los
n - I discos más pequeños del poste A al C.dejando el n-ésimo disco más pequeño
en el poste A. Se mueve ese disco de A a B. Después se pasan los n - 1 discos más
pequeños de C a B. El movimiento de los n - 1 discos más pequeños se efectuará
por medio de la aplicación recursiva del método. Como los n discos implicados...