Backtraking
E L E S QU E MA A L G OR Í T MIC O D EL BACK TR ACK IN G
INTRODUCCIÓN A ESTE MÉTODO DE RESOLUCIÓN DE PROBLEMAS, ESTUDIO DE VARIANTES POSIBLES Y EJEMPLOS DE IMPLEMENTACIÓN
CARLOS VECINO DE CASAS MIGUEL ÁNGEL MELÓN PÉREZ JOSÉ LUIS REDONDO GARCÍA
CONTENIDO
1 2 3 4 5 Contenido.............................................................................................................................. 2 Introducción .......................................................................................................................... 3 Aplicaciones del Método Algorítmico. .................................................................................. 3 Esquema general................................................................................................................... 3 Variantes del esquema general ............................................................................................. 4 5.1 Una solución cualquiera ................................................................................................ 4 Todas las soluciones.............................................................................................. 5 La mejor de todas las soluciones........................................................................... 5
5.1.1 5.1.2 6 7
Eficiencia y costes.................................................................................................................. 6 Árboles debúsqueda............................................................................................................. 6 7.1 7.2 Ejemplo de espacio de búsqueda: las N- Reinas. .......................................................... 7 Ejemplo de espacio de búsqueda: el problema del laberinto ....................................... 8
8
Ejemplos de implementación. ............................................................................................... 9 8.1 Problema del “salto de caballo”.................................................................................... 9 Etapas de la resolución........................................................................................ 10 Estructuras de datos utilizadas para resolver el problema. ................................ 10 Función de Vuelta Atrás. ..................................................................................... 118.1.1 8.1.2 8.1.3 8.2
Problema de los Cuadrados Mágicos. ......................................................................... 12 ¿Qué es un cuadrado mágico? ............................................................................ 12 Breve esbozo del proceso de construcción del cuadrado mágico. ..................... 12 Aplicación del algoritmo general. Funciones claves implicadas......................... 13 Coste computacional y complejidad del problema. ............................................ 13
8.2.1 8.2.2 8.2.3 8.2.4 8.3
9 10
Problema del laberinto................................................................................................ 13
Conclusión........................................................................................................................... 14 Referencias ...................................................................................................................... 14
2
1 Introducción
El backtracking es una estrategia usada para encontrar soluciones a problemas que tienen una solución completa, en los que el orden de los elementos no importa, y en los que existen una serie de variables a cada unade las cuales debemos asignarle un valor teniendo en cuenta unas restricciones dadas. El término fue acuñado por el matemático D. H. Lehmer e la década de los cincuenta y formalizado por Walker, Golom y Baumert en el siguiente decenio. El NIST (U.S. National Institute of Standards and Technology) lo define en su Diccionario de Algoritmos y Estructuras de Datos [1] de la siguiente manera: Find a...
Regístrate para leer el documento completo.