Explicación De Backtracking

Video explicativo de backtracking (Problema de las N Reinas):

Características de un problema resoluble con backtracking

La  solución puede expresarse como una n-tupla,

 (x1,x2,x3,…,xn) 

donde cada xi es seleccionado  de  un  conjunto finito Si.

El  problema se  puede formular como la  búsqueda de  aquella tupla que optimiza (maximiza o  minimiza) un  determinado criterio P(x1, ...,xn).

Algoritmo Genérico de Backtracking:

Bt(A, k)

1          if Solucion?(A, k)

2          then procesarSolucion(A, k)

3          else for each c ∈ Sucesores(A, k)

4          do A[k] = c

5          Bt(A, k + 1)

6          if terminar?

7          then return

Donde:

• Solucion?(·) es una función que retorna verdadero si su argumento es una solución.

• procesarSolucion(·), depende del problema y que maneja una solución.

• Sucesores(·) es una función que dado un candidato, genera todos los candidatos que son extensiones de éste.

• terminar? es una variable global booleana inicialmente es falsa, pero que puede ser hecha verdadera por procesarSolucion, en caso que sólo interesa encontrar una solución.

Aspectos Relevantes de Backtracking

Definición de backtracking (Por Antonio Canela):

     El backtracking es una estrategia o una técnica usada en los algoritmo para buscar o llegar a una solución tras el método de prueba y error que quiere decir esto quiere decir que él va probando con cada opción posible hasta e ir avanzando hasta llegar a la solución si la opción tomada no llegar a una solución el computador vuelve hacia atrás hasta donde se tomó la decisión de ir por esa opción y toma otra y así sucesivamente, se puede usar este método como se dijo anteriormente para buscar una solución o buscar la solución más óptima.

Ventajas:

• Si existe una solución, la calcula.

• Es un esquema sencillo de implementar.

 • Adaptable a las características específicas de cada problema.

Desventajas:

• Si el Espacio de Búsqueda es infinito, la solución, aunque exista, no se encontrará nunca.

 • Por término medio consume mucha memoria al tener que almacenar las llamadas recursivas.

Aplicaciones del algoritmo

Este se emplea en el cálculo de expresiones regulares o para tareas de reconocimiento de texto y de sintaxis de lenguajes regulares, para la implementación de algunos lenguajes de programación, tales como Planner o Prolog, para dar soporte a muchos algoritmos en inteligencia artificial, ya que este método se puede implementar en la creación de árboles de búsqueda.

Entre ejemplos de implementación del método backtracking tenemos: el problema de salto al caballo o caballo de Atila, el problema de los cuadrados mágicos, el problema del laberinto, las ocho reinas u N reinas, por mencionar algunos.

Ejemplos gráficos de lo anteriormente mencionado:

Problema de salto al caballo o Caballo de Atila:

Problema de los cuadrados mágicos:

Problema del laberinto:

Problemas de la N Reinas:

Método Backtracking u Algoritmo “Vuelta Atrás”

Opinión personal (Bianca González):

El back tracking o algoritmo vuelta atrás, para mi es una forma de resolución de problemas, donde se evalúan las diferentes soluciones o solución (si es que hay una), dependiendo de cómo sea el caso. Con este se busca la forma más sencilla de resolver un enigma dentro de un espacio limitado, considerando que al momento de programar se debe es de hacer una búsqueda sistemática.

Con lo que quiero explicarme, si hay un enigma o problema el programador como tal deberá de desarrollar la respuesta u solución del mismo, como dije anteriormente si es que posee una, para luego llevarlo a un sentido programático (por medio de algoritmos), es decir, construyendo las posibilidades, para luego invocar al algoritmo todas ellas.

Su principal virtud es que en la mayoría de las implementaciones se puede evitar combinaciones, estableciendo funciones de acotación (o poda) reduciendo el tiempo de ejecución. Por tanto en ocasiones se aplica esta técnica para buscar la solución más corta o más sencilla, con el fin de aprovechar tiempo y ahorrar dinero.

Hay un documento en pdf que adjuntare a continuación (enlace) donde se indica que  el backtracking está muy relacionado con la búsqueda combinatoria. Este explica que este método funciona para dos tipos diferentes de problemas:

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.

También indica que este método es sistemático y organizado, por el cual se quiere llegar a la solución de un problema de manera que al concebir varias combinaciones este llegue hasta la correcta.

El documento relata lo siguiente:

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

Algunos ejemplos gráficos son los siguientes:

Ejemplo Nº1:

Ejemplo Nº2:

     Un ejemplo comúnmente utilizado para explicar el backtracking es el juego sudoku. Si nunca lo ha jugado, explico su dinámica: consiste en rellenar un cubo de 9 x 9 celdas dispuestas en 9 subgrupos de 3 x 3 celdas, con números del 1 al 9, atendiendo a la restricción de que no se debe repetir el mismo número en la misma fila, columna o subgrupo de 9.

     Un Sudoku dispone de varias celdas con un valor inicial, de modo que debemos empezar a resolver el problema a partir de esta solución parcial sin modificar ninguna de las celdas iniciales.

     Como se ve en el siguiente ejemplo los números que se encuentran con mayor tamaño son fijos (solo un número por casilla), mientras que los número que se encuentran de menor tamaño y hay varios dentro de una única casilla es debido a que estos son las posibles combinaciones para lograr el resultado o solución al juego. 

     Es bastante entretenido y eh de decir que me volví adicta al mismo cuando estaba en el colegio.