GeeksforGeeks

Requisitos previos :

• Recursión
• Análisis de complejidad

El Backtracking es una técnica algorítmica para resolver problemas recursivamente al tratar de construir una solución de forma incremental, una pieza a la vez, eliminando aquellas soluciones que no satisfacen las restricciones del problema en cualquier punto del tiempo (por tiempo, aquí, se refiere al tiempo transcurrido hasta alcanzar cualquier nivel del árbol de búsqueda).

Según la definición del wiki,

El backtracking se puede definir como una técnica algorítmica general que considera buscar todas las combinaciones posibles para resolver un problema computacional.

Hay tres tipos de problemas en el retroceso–

1. Problema de decisión: En esto, buscamos una solución viable.
2. Problema de optimización: En esto, buscamos la mejor solución.
3. Problema de enumeración: En esto, encontramos todas las soluciones factibles.

¿Cómo determinar si un problema se puede resolver utilizando Backtracking?

Generalmente, cada problema de satisfacción de restricciones que tenga restricciones claras y bien definidas en cualquier solución objetiva, que construya gradualmente candidato a la solución y abandone a un candidato («backtracks») tan pronto como determine que el candidato no puede completarse a una solución válida, se puede resolver retrocediendo. Sin embargo, la mayoría de los problemas que se discuten, se pueden resolver usando otros algoritmos conocidos como Programación Dinámica o Algoritmos Codiciosos en complejidad de tiempo logarítmica, lineal, lineal-logarítmica en orden de tamaño de entrada, y por lo tanto, eclipsan al algoritmo de retroceso en todos los aspectos (ya que los algoritmos de retroceso son generalmente exponenciales tanto en el tiempo como en el espacio). Sin embargo, todavía quedan algunos problemas, que solo tienen algoritmos de retroceso para resolverlos hasta ahora.

Considere una situación en la que tiene tres cajas frente a usted y solo una de ellas tiene una moneda de oro, pero no sabe cuál. Por lo tanto, para obtener la moneda, tendrá que abrir todas las cajas una por una. Primero marque la primera casilla, si no contiene la moneda, tendrá que cerrar y marque la segunda casilla y así sucesivamente hasta encontrar la moneda. Esto es lo que es retroceder, es decir, resolver todos los subproblemas uno por uno para alcanzar la mejor solución posible.

Considere el siguiente ejemplo para comprender el enfoque de retroceso de manera más formal,

Dada una instancia de cualquier problema computacional y datos correspondientes a la instancia, todas las restricciones que deben satisfacerse para resolver el problema están representadas por . Un algoritmo de retroceso funcionará de la siguiente manera:

El algoritmo comienza a construir una solución, comenzando con un conjunto de soluciones vacío . S = {}

1. Agregue a el primer movimiento que aún queda (Todos los movimientos posibles se agregan a uno por uno). Esto ahora crea un nuevo subárbol en el árbol de búsqueda del algoritmo.
2. Compruebe si satisface cada una de las restricciones en .
   • En caso afirmativo, el subárbol es » elegible «para agregar más»hijos».
   • De lo contrario, todo el subárbol es inútil, por lo que vuelve al paso 1 utilizando el argumento .
3. En caso de» elegibilidad » del subárbol recién formado , vuelve al paso 1, utilizando el argumento .
4. Si la comprobación de devuelve que es una solución para todos los datos . Salida y finalización del programa.
   Si no, devuelva que no es posible ninguna solución con la corriente y, por lo tanto, deséchela.

Diferencia entre Recursión y Retroceso:

En recursión, la función se llama a sí misma hasta que alcanza un caso base. En backtracking, utilizamos la recursividad para explorar todas las posibilidades hasta obtener el mejor resultado para el problema.

Pseudocódigo para Retrotraer :

1. Solución recursiva de retroceso.

void findSolutions(n, other params) : if (found a solution) : solutionsFound = solutionsFound + 1; displaySolution(); if (solutionsFound >= solutionTarget) : System.exit(0); return for (val = first to last) : if (isValid(val, n)) : applyValue(val, n); findSolutions(n+1, other params); removeValue(val, n);

2. Para encontrar si existe una solución o no

boolean findSolutions(n, other params) : if (found a solution) : displaySolution(); return true; for (val = first to last) : if (isValid(val, n)) : applyValue(val, n); if (findSolutions(n+1, other params)) return true; removeValue(val, n); return false;

Intentemos resolver un problema de retroceso estándar, el Problema de N-Queen.
La N Reina es el problema de colocar N reinas de ajedrez en un tablero de ajedrez N×N para que no haya dos reinas que se ataquen entre sí. Por ejemplo, la siguiente es una solución para el problema de 4 Queen.

La salida esperada es una matriz binaria que tiene 1s para los bloques donde se colocan las reinas. Por ejemplo, a continuación se muestra la matriz de salida para la solución de 4 reinas anterior.

{ 0, 1, 0, 0}{ 0, 0, 0, 1}{ 1, 0, 0, 0}{ 0, 0, 1, 0}

Algoritmo de retroceso: La idea es colocar reinas una por una en diferentes columnas, comenzando desde la columna más a la izquierda. Cuando colocamos una reina en una columna, comprobamos si hay enfrentamientos con reinas ya colocadas. En la columna actual, si encontramos una fila para la que no hay conflicto, marcamos esta fila y columna como parte de la solución. Si no encontramos tal fila debido a enfrentamientos, retrocedemos y regresamos en falso.

1) Start in the leftmost column2) If all queens are placed return true3) Try all rows in the current column. Do following for every tried row. a) If the queen can be placed safely in this row then mark this as part of the solution and recursively check if placing queen here leads to a solution. b) If placing the queen in leads to a solution then return true. c) If placing queen doesn't lead to a solution then unmark this (Backtrack) and go to step (a) to try other rows.3) If all rows have been tried and nothing worked, return false to trigger backtracking.

Puede consultar el artículo sobre Backtracking | Set 3 (Problema N Queen) para una implementación completa del enfoque anterior.
Más Problemas de Retroceso:

• Retroceso / Conjunto 1 (El problema del tour del Caballero)
• Retroceso / Conjunto 2 (Rata en un Laberinto)
• Retroceso | Conjunto 4 (Suma de Subconjuntos)
• Retroceso | Conjunto 5 (Problema de color m)
• –> Haga clic aquí para obtener más