PDF de programación - EL ESQUEMA ALGORÍTMICO DEL BACKTRACKING

L Ó G I C A Y C O M P U T A B I L I D A D

EL ESQUEMA

ALGORÍTMICO DEL

BACKTRACKING

INTRODUCCIÓN A ESTE MÉTODO DE

RESOLUCIÓN DE PROBLEMAS, ESTUDIO
DE VARIANTES POSIBLES Y EJEMPLOS DE

IMPLEMENTACIÓN

C A R L O S V E C I N O D E C A S A S

M I G U E L Á N G E L M E L Ó N P É R E Z
J O S É L U I S R E D O N D O G A R C Í A



C O N T E N I D O

1

2

3

4

5

6

7

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

5.1.1

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

5.1.2

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

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

Árboles de bú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

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ón de 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ón del 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

Problema del laberinto ................................................................................................ 13

9

10





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 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 Standards and Technology) lo define en su Diccionario de Algoritmos y Estructuras
de Datos [1] de la siguiente manera:


Find a solution by trying one of several choices. If the choice proves incorrect,
computation backtracks or restarts at the point of choice and tries another choice.
Traducción:
Encontrar una solución intentándolo con una de varias opciones. Si la elección
es incorrecta, el cómputo retrocede o vuelve a comenzar desde el punto de decisión
anterior y lo intenta con otra opción.
Definición 1. Backtracking


Este esquema algorítmico es utilizado para resolver problemas en los que la solución consta de una serie de
decisiones adecuadas hacia nuestro objetivo. El backtracking está muy relacionado con la búsqueda combinatoria. De
manera más exacta podemos indicar que los problemas a considerar son lo siguientes:

1. Problemas de Decisión: Búsqueda de las soluciones que satisfacen ciertas restricciones.
2. Problemas de Optimización: Búsqueda de la mejor solución en base a una función objetivo.

De forma general, el método del backtracking, concebido como tal, genera todas las secuencias de forma
sistemática y organizada, de manera que prueba todas las posibles combinaciones de un problema hasta que encuentra
la correcta. En general, la forma de actuar consiste en elegir una alternativa del conjunto de opciones en cada etapa
del proceso de resolución, y si esta elección no funciona (no nos lleva a ninguna solución), la búsqueda vuelve al
punto donde se realizó esa elección, e intenta con otro valor. Cuando se han agotado todos los posibles valores en ese
punto, la búsqueda vuelve a la anterior fase en la que se hizo otra elección entre valores. Si no hay más puntos de
elección, la búsqueda finaliza.

Para implementar algoritmos con Backtracking, se usan llamadas a funciones recursivas, en la que en cada
llamada la función asigna valores a un determinado punto de la posible solución, probando con todos los valores
posibles, y manteniendo aquella que ha tenido éxito en las posteriores llamadas recursivas a las siguientes partes de la
solución.


2 Aplicaciones del Método Algorítmico.
La técnica de Backtracking es usada en muchos ámbitos de la programación, por ejemplo, para el cálculo de
expresiones regulares o para tareas de reconocimiento de texto y de sintaxis de lenguajes regulares. También es usado
incluso en la implementación de algunos lenguajes de programación, tales como Planner o Prolog y da soporte a
muchos algoritmos en inteligencia artificial.


3 Esquema general.
A continuación vamos a mostrar un esquema general para este tipo de algoritmos, comentando posteriormente cada
una de sus partes y funciones a las que llama. Como ya hemos adelantado con anterioridad, se trata de una función
recursiva, que por lo general tiene una forma como la que sigue. Además hemos de señalar que este esquema sirve
para resolver aquellos problemas en los que estamos buscando una solución, es decir, cuando encontremos la primera
que cumpla todas las restricciones, finalizaremos, sin importarnos si en realidad existen algunas más o si se trata de la
mejor de las posibles. Estos otros casos son muy similares y se derivan de este esquema sin ninguna complicación. El
ejemplo de los cuadrados mágicos listado posteriormente usa la técnica de búsqueda de todas las soluciones.


Funcion Backtracking (Etapai) devuelve: boolean
Inicio










Éxito = falso;
IniciarOpciones(i, GrupoOpciones o);
Repetir







SeleccionarnuevaOpcion(o, Opcion n);
Si (Aceptable(n)) entonces

AnotarOpcion(i, n);
SiSolucionCompleta(i) entonces



Sino


Éxito = verdadero;



3

Cuando queremos encontrar la mejor solución,
eliminaremos esta instrucción. Y en su lugar
compararemos la solución obtenida con una de
referencia, para ver si tenemos que actualizar la
mejor solución obtenida hasta el momento.

cancelamosAnotacion(i, n);





Finsi;






Finsi;

Éxito = Backtracking(i+1);
Si Éxito = false entonces

finsi;







Hasta (éxito = verdadero) o (NoQuedanOpciones(o));
Retorna Éxito;









Fin;


Seguidamente, explicaremos brevemente cada una de las funciones que intervienen en el cuerpo del algoritmo

Si queremos todas las soluciones la instrucción
cambiaria por NoQuedanOpciones(o) para
conseguir así
las soluciones posibles.
También habría que hacer esto para la mejor
solución.

todas



principal y que vienen resaltadas en verde:



IniciarOpciones(Etapa i, GrupoOpciones o);

1.
En base a las alternativas elegidas en la solución parcial i que nos llega como parámetro, introducimos en “O” el
grupo de opciones posibles que podemos probar en la etapa actual. Si ninguno de estos valores condujese a una
solución válida, la llamada a la función finalizaría y volveríamos a una etapa posterior.

2. SeleccionarNuevaOpcion(GrupoOpciones o, Opcion n);
De entre todas las alternativas posibles que tenemos en O, elegimos una. Aquí podemos realizar funciones de
Poda, que pueden se r muy beneficiosas en ciertos algoritmos, proporcionando opciones que tienen una alta
probabilidad de convertirse en solución y evitando muchas pruebas innecesarias con valores que según nuestra
estimación no nos conducirán al éxito. Hay que señalar que, de alguna forma esta opción elegida tiene que ser
desechada o marcada como usada en el grupo de opciones O, para que no volvamos a probar con el mismo valor
repetidas veces, es decir, el conjunto vaya reduciéndose hasta que no queden mas alternativas por probar.

3. Aceptable(Opción n);
Los problemas que resuelve este tipo de esquemas algorítmicos tienen como cara