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.