Estrategiaas de diseño de los algoritmos

1

Estrategias para el diseño de Algoritmos: Un Estudio Comparativo.
Ojeda R., Hermes, Estudiante de Ingeniería en Computación, Octavo Semestre, Grupo A, UTM
Abstract— De las estrategias para el diseño de algoritmos, cada una tiene una gran importancia, además de características propias. Este documento trata de dar un panorama general de algunas estrategias tales como: vueltra atrás,ramificación y poda, divide y vencerás, algoritmos ávidos y programación dinámica, así como una comparación de las mismas.

Dividir y conquistar, también conocido como “divide y vencerás” (divide and conquer), algoritmos ávidos (greedy algorithms), método de retroceso o vuelta atrás (backtracking), ramificación y poda (Branch and Bound) y programación dinámica (dinamic programming o simplemente DP) [1].II. DIVIDE Y VENCERÁS

E

I.INTRODUCCIÓN

l diseño de un algoritmo para solucionar algún problema muchas veces se realiza de una forma intuitiva, pero eso no asegura su eficiencia y una idea rebuscada puede hacer que su implementación sea muy complicada. La eficiencia y la facilidad para su implementación deben ser 2 cuestiones a tomar en cuenta al momento de diseñar un algoritmo, y cadauna de estas tendrá un peso mayor o menor, dependiendo de la situación. Por ejemplo: Si una compañía solicitará un algoritmo para el manejo cuestiones críticas de la empresa (como controlar un reactor nuclear, o dispositivos de seguridad), sería conveniente que este proporcionara una respuesta rápida y confiable (sin importar mucho, que su implementación sea complicada), otro ejemplo, seríadurante un concurso de programación algorítmica (tales como el ACM-ICPC, o TopCoder en los concursos de algoritmos), en este tipo de concursos es necesario tener en cuenta que el algoritmo diseñado sea eficiente pero además fácil de implementar, ya que un algoritmo demasiado eficiente para el cual se requieran 10 o 20 horas para implementarlo es inútil, así también lo es un algoritmo fácil deimplementar pero que no sea eficiente para solucionar el problema en cuestión. Tomando en cuenta, los aspectos de eficiencia y la facilidad de implementación, la teoría de algoritmos nos brinda algunas técnicas generales para el diseño de algoritmos, las cuales, al conocer sus características, ventajas y desventajas, son una herramienta importante para diseñar algoritmos que sean eficientes y muyprobablemente fácil de implementar. A lo largo de la historia del estudio de los algoritmos, se han podido encontrar diversas técnicas generales para producir algoritmos eficientes y lograr la resolución de una gran cantidad de problemas, algunas de la más importantes y que serán tratas en este documento son:

La técnica de divide y vencerás (divide and conquer) también conocida como dividir yconquistar, esta técnica, se basa en la idea “entre más simple, mejor”, dividiendo el problemas en problemas más pequeños que pueden ser resueltos más fácil que el problema principal, después al combinar la solución de esos subproblemas se obtiene la solución del problema principal [2]. En general, la técnica de divide y vencerás consta de 3 pasos, los cuales son los siguientes: – Dividir: Divide elproblema en problemas más pequeños (similares o iguales al problema original). – Conquistar: Resolver los subproblemas, usualmente de forma recursiva, hasta que los subproblemas sean tan pequeños como para poder resolverlos directamente. – Combinar: Unir las soluciones obtenidas en los subproblemas para obtener la solución del problema original. Esta técnica tiene muchas ventajas, la primera es quedespués de dividir el problema en subproblemas parecidos (que sería la parte complicada) su diseño e implementación son sencillas, otra ventaja es que provee una forma fácil y directa de solucionar problemas complejos, además de proporcionar una forma natural de adaptación a su ejecución en entornos multiprocesador [3]. Una de sus desventajas es el gasto producido por usar recursión, y por esa misma...