Backtraking

LÓGICA Y COMPUTABILIDAD

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...