Investigacion y desarrollo sobre backtracking

Ingeniería de SistemasAlgoritmos y Complejidad |
Proyecto de investigación y desarrollo (I+D): “Backtracking” |
Presentado a:Ing. José Capacho Portilla |
|
Presentado por:Andrés Núñez Visbal (200023166)Brayan García Sales (200023161)Fernando Núñez Estrada (200023940)David Mogollón Fernández (200023913)Jossie Parada Guarguati (200019323) |
Mayo 03 del 2010Barranquilla/Colombia |Investigación y desarrollo del tema de “Backtracking”. Análisis de sus beneficios y desventajas en la solución de problemas. Diferentes clases de ejemplos y comparaciones con otro tipo de métodos.
TABLA DE CONTENIDO
1. Resumen………………………………………………………………………………....3
2. Introducción…………………………………………………………………………….4
3. Justificación……………………………………………………………………………..4
4. Objetivosgenerales……………………………………………………………………..5
5. Objetivos específicos……………………………………………………………………5
6. Planteamiento del problema……………………………………………………………5
7. Marco teórico:
7.1 Definición general de Backtracking………………………………………….6
7.2 Formulación general de Backtracking…………………………………….…6
7.3 Ejemplos de algoritmos Backtracking………………………………………..7
i) Definición general del algoritmo.
ii) Solución del algoritmo.
iii) Complejidad del algoritmo.
8.Resultados………………………………………………………………………………15
9. Conclusiones……………………………………………………………………………17
10. Glosario………………………………………………………………………………..17
11. Bibliografía……………………………………………………………………………18

Información del documento de investigación y desarrollo (I+D):
“Backtracking”

1. Resumen.
En este documento se realizará una investigación detallada de los algoritmos que emplean el método de Backtracking. Definiremos para que se utiliza este método, la forma deutilizarlo y las consecuencias de que trae solucionar diferentes clases de problemas con este método. Para todo lo anterior es necesario tener claro unos conceptos básicos y unos nuevos tales como “métodos de podado” y “árbol de retroceso” que serán explicados en el documento con el fin del buen entendimiento de este. Además, citaremos algunos ejemplos, analizándolos y elaborando una breve conclusióndel uso del método de Backtracking en esos ejemplos. Al finalizar haremos una comparación de otros tipos de métodos de resoluciones de problemas vs. Backtracking.
Palabras claves: Backtracking, métodos de podado, árbol de retroceso.

Abstract.
This paper will conduct a detailed investigation of algorithms that employ the method of backtracking. We are going to define why to use this method, howto use it and the consequences that it brings to solve different kinds of problems with this method. For all the above is necessary to be clear about basic concepts and new ones such as "pruning methods" and "backtrack tree" that will be explained in the document to the proper understanding of it .In addition, we will cite some examples, analyzing and preparing a brief conclusion of using themethod of backtracking in these examples. Finally we make a comparison of alternative methods of solving problems vs. Backtracking.
Key Words: Backtracking, pruning methods, backtrack tree.

2. Introducción.
Hoy en día la gama de problemas a la cual nos enfrentamos es demasiado extensa. Por lo tanto deben existir diversas formas de enfrentarnos a esos problemas Ya sea por lógica voraz, paralela,probabilística, dinámica o en el caso que estaremos investigando en este documento: lógica de retroceso (Backtracking). Esto nos conlleva a que al resolver el problema por cualquier método nos podemos presentar con dos casos: “Primero, es posible que haya un conjunto de algoritmos que solucionen el problema en mención. La elección del “mejor algoritmo” del conjunto es un proceso que conlleva alanálisis de variables del algoritmo tales como: menor tiempo de ejecución, mínimo espacio para su operación y fácil de programar; por lo tanto, el proceso puede ser complicado y algunas veces conlleva un análisis matemático sofisticado. Segundo, si el algoritmo adecuado para la solución del problema no existe, hay...