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

Contenido.............................................................................................................................. 2

2

Introducción .......................................................................................................................... 3

3

Aplicaciones del Método Algorítmico. .................................................................................. 3

4

Esquema general................................................................................................................... 3

5

Variantes del esquema general ............................................................................................. 4
5.1

Una solución cualquiera ................................................................................................ 4

5.1.1

Todas las soluciones.............................................................................................. 5

5.1.2

La mejor de todas las soluciones........................................................................... 5

6

Eficiencia y costes.................................................................................................................. 6

7

Árboles debúsqueda............................................................................................................. 6
7.1

Ejemplo de espacio de búsqueda: las N- Reinas. .......................................................... 7

7.2

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

8.1.1

Etapas de la resolución........................................................................................ 10

8.1.2

Estructuras de datos utilizadas para resolver el problema. ................................ 10

8.1.3

Funciónde Vuelta Atrás. ..................................................................................... 11

8.2

Problema de los Cuadrados Mágicos. ......................................................................... 12

8.2.1

¿Qué es un cuadrado mágico? ............................................................................ 12

8.2.2

Breve esbozo del proceso de construccióndel cuadrado mágico. ..................... 12

8.2.3

Aplicación del algoritmo general. Funciones claves implicadas. ........................ 13

8.2.4

Coste computacional y complejidad del problema. ............................................ 13

8.3
9
10

Problema del laberinto................................................................................................ 13Conclusión ........................................................................................................................... 14
Referencias ...................................................................................................................... 14

2

1 Introducción
El backtracking es una estrategia usada para encontrar soluciones a problemas que tienen una solucióncompleta, en
los que el orden de los elementos no importa, y en los que existen una serie de variables a cada una de 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...