El backtracking es una clase de algoritmos para encontrar soluciones a algunos problemas computacionales , en particular problemas de satisfacción de restricciones , que construye candidatos de forma incremental para las soluciones y abandona un candidato ("backtracking") tan pronto como determina que el candidato no puede completarse hasta una solución válida. [1]
El ejemplo clásico de libro de texto del uso del retroceso es el problema de las ocho reinas , que pide todas las disposiciones de ocho reinas de ajedrez en un tablero de ajedrez estándar de modo que ninguna reina ataque a ninguna otra. En el enfoque común de retroceso, los candidatos parciales son disposiciones de k reinas en las primeras k filas del tablero, todas en diferentes filas y columnas. Cualquier solución parcial que contenga dos reinas que se atacan mutuamente puede abandonarse.
El retroceso sólo se puede aplicar a problemas que admiten el concepto de una "solución candidata parcial" y una prueba relativamente rápida de si es posible completarla hasta obtener una solución válida. Es inútil, por ejemplo, para localizar un valor dado en una tabla desordenada. Sin embargo, cuando es aplicable, el retroceso suele ser mucho más rápido que la enumeración por fuerza bruta de todos los candidatos completos, ya que puede eliminar muchos candidatos con una sola prueba.
El retroceso es una herramienta importante para resolver problemas de satisfacción de restricciones , [2] como crucigramas , aritmética verbal , sudoku y muchos otros acertijos. A menudo es la técnica más conveniente para el análisis sintáctico , [3] para el problema de la mochila y otros problemas de optimización combinatoria . También es la estrategia de ejecución de programas utilizada en los lenguajes de programación Icon , Planner y Prolog .
El retroceso depende de " procedimientos de caja negra " proporcionados por el usuario que definen el problema que se debe resolver, la naturaleza de los candidatos parciales y cómo se extienden a los candidatos completos. Por lo tanto, se trata de una metaheurística más que de un algoritmo específico, aunque, a diferencia de muchas otras metaheurísticas, se garantiza que encontrará todas las soluciones a un problema finito en un tiempo limitado.
El término "backtrack" fue acuñado por el matemático estadounidense DH Lehmer en la década de 1950. [4] El lenguaje pionero de procesamiento de cadenas SNOBOL (1962) puede haber sido el primero en proporcionar una función de retroceso general incorporada.
El algoritmo de retroceso enumera un conjunto de candidatos parciales que, en principio, podrían completarse de diversas maneras para obtener todas las soluciones posibles al problema planteado. La finalización se realiza de forma incremental, mediante una secuencia de pasos de extensión de candidatos.
Conceptualmente, los candidatos parciales se representan como los nodos de una estructura de árbol , el árbol de búsqueda potencial. Cada candidato parcial es el padre de los candidatos que difieren de él en un solo paso de extensión; las hojas del árbol son los candidatos parciales que no se pueden extender más.
El algoritmo de retroceso recorre este árbol de búsqueda de forma recursiva , desde la raíz hacia abajo, en orden de profundidad . En cada nodo c , el algoritmo comprueba si c se puede completar hasta una solución válida. Si no se puede, se omite ( poda ) todo el subárbol con raíz en c . De lo contrario, el algoritmo (1) comprueba si c en sí es una solución válida y, en caso afirmativo, se lo informa al usuario; y (2) enumera de forma recursiva todos los subárboles de c . Las dos pruebas y los hijos de cada nodo se definen mediante procedimientos proporcionados por el usuario.
Por lo tanto, el árbol de búsqueda real que recorre el algoritmo es solo una parte del árbol potencial. El costo total del algoritmo es el número de nodos del árbol real multiplicado por el costo de obtener y procesar cada nodo. Este hecho debe tenerse en cuenta al elegir el árbol de búsqueda potencial e implementar la prueba de poda.
Para aplicar el método de retroceso a una clase específica de problemas, se deben proporcionar los datos P para la instancia particular del problema que se va a resolver y seis parámetros de procedimiento : root , reject , accept , first , next y output . Estos procedimientos deben tomar los datos de instancia P como parámetro y deben hacer lo siguiente:
El algoritmo de retroceso reduce el problema a la llamada backtrack ( P , root ( P )), donde backtrack es el siguiente procedimiento recursivo:
procedimiento backtrack(P, c) es si rechaza(P, c) entonces retorna si acepta(P, c) entonces emite(P, c) s ← primero(P, c) mientras s ≠ NULL hacer retroceder(P, s) s ← siguiente(P, s)
El procedimiento de rechazo debe ser una función con valor booleano que devuelva verdadero solo si está seguro de que ninguna extensión posible de c es una solución válida para P. Si el procedimiento no puede llegar a una conclusión definitiva, debe devolver falso . Un resultado verdadero incorrecto puede hacer que el procedimiento de retroceso pase por alto algunas soluciones válidas. El procedimiento puede suponer que reject ( P , t ) devolvió falso para cada antecesor t de c en el árbol de búsqueda.
Por otra parte, la eficiencia del algoritmo de retroceso depende de que reject devuelva true para los candidatos que estén lo más cerca posible de la raíz. Si reject siempre devuelve false , el algoritmo encontrará todas las soluciones, pero será equivalente a una búsqueda de fuerza bruta.
El procedimiento de aceptación debe devolver verdadero si c es una solución completa y válida para la instancia del problema P , y falso en caso contrario. Puede suponer que el candidato parcial c y todos sus antecesores en el árbol han pasado la prueba de rechazo .
El pseudocódigo general anterior no presupone que las soluciones válidas sean siempre hojas del árbol de búsqueda potencial. En otras palabras, admite la posibilidad de que una solución válida para P pueda extenderse aún más para obtener otras soluciones válidas.
El algoritmo de retroceso utiliza los procedimientos first y next para enumerar los hijos de un nodo c del árbol, es decir, los candidatos que difieren de c en un único paso de extensión. La llamada first ( P , c ) debe devolver el primer hijo de c , en algún orden; y la llamada next ( P , s ) debe devolver el siguiente hermano del nodo s , en ese orden. Ambas funciones deben devolver un candidato "NULL" distintivo, si el hijo solicitado no existe.
Juntas, las funciones raíz , primera y siguiente definen el conjunto de candidatos parciales y el árbol de búsqueda potencial. Deben elegirse de modo que cada solución de P aparezca en algún lugar del árbol y ningún candidato parcial aparezca más de una vez. Además, deben admitir un predicado de rechazo eficiente y efectivo .
El pseudocódigo anterior generará una salida para todos los candidatos que sean una solución para la instancia dada P. El algoritmo se puede modificar para que se detenga después de encontrar la primera solución o una cantidad específica de soluciones; o después de probar una cantidad específica de candidatos parciales, o después de gastar una cantidad determinada de tiempo de CPU .
Algunos ejemplos en los que se puede utilizar el retroceso para resolver acertijos o problemas incluyen:
El siguiente es un ejemplo en el que se utiliza el retroceso para el problema de satisfacción de restricciones :
El problema general de satisfacción de restricciones consiste en encontrar una lista de números enteros x = ( x [1], x [2], …, x [ n ]) , cada uno en algún rango {1, 2, …, m }, que satisfaga alguna restricción arbitraria (función booleana) F .
Para esta clase de problemas, los datos de instancia P serían los enteros m y n , y el predicado F . En una solución típica de retroceso para este problema, se podría definir un candidato parcial como una lista de enteros c = ( c [1], c [2], …, c [k]) , para cualquier k entre 0 y n , que se asignarán a las primeras k variables x [1], x [2], …, x [ k ] . El candidato raíz sería entonces la lista vacía (). El primer y el siguiente procedimiento serían entonces
La función primero(P, c) es k ← longitud(c) si k = n entonces devuelve NULL de lo contrario devuelve (c[1], c[2], ..., c[k], 1)
La función siguiente(P, s) es k ← longitud(es) si s[k] = m entonces devuelve NULL de lo contrario devuelve (s[1], s[2], ..., s[k − 1], 1 + s[k])
Aquí la longitud ( c ) es el número de elementos en la lista c .
La llamada reject ( P , c ) debe devolver verdadero si la restricción F no puede ser satisfecha por ninguna lista de n enteros que comience con los k elementos de c . Para que el retroceso sea efectivo, debe haber una manera de detectar esta situación, al menos para algunos candidatos c , sin enumerar todas esas m n − k n -tuplas.
Por ejemplo, si F es la conjunción de varios predicados booleanos, F = F [1] ∧ F [2] ∧ … ∧ F [ p ] , y cada F [ i ] depende solo de un pequeño subconjunto de las variables x [1], …, x [ n ] , entonces el procedimiento de rechazo podría simplemente verificar los términos F [ i ] que dependen solo de las variables x [1], …, x [ k ] , y devolver verdadero si alguno de esos términos devuelve falso . De hecho, el procedimiento de rechazo solo necesita verificar aquellos términos que dependen de x [ k ], ya que los términos que dependen solo de x [1], …, x [ k − 1] se habrán probado más arriba en el árbol de búsqueda.
Suponiendo que rechazar se implementa como se indicó anteriormente, entonces aceptar ( P , c ) solo necesita verificar si c está completo, es decir, si tiene n elementos.
Generalmente es mejor ordenar la lista de variables de modo que comience con las más críticas (es decir, las que tienen menos opciones de valor o que tienen un mayor impacto en las elecciones posteriores).
También se podría permitir que la siguiente función elija qué variable debe asignarse al extender un candidato parcial, en función de los valores de las variables que ya ha asignado. Se pueden obtener mejoras adicionales mediante la técnica de propagación de restricciones .
Además de conservar los valores de recuperación mínimos utilizados en la copia de seguridad, las implementaciones de retroceso suelen mantener un registro variable para registrar el historial de cambios de valores. Una implementación eficiente evitará la creación de una entrada de registro variable entre dos cambios sucesivos cuando no hay un punto de elección, ya que el retroceso borrará todos los cambios en una sola operación.
Una alternativa al rastro de la variable es mantener una marca de tiempo de cuándo se realizó el último cambio en la variable. La marca de tiempo se compara con la marca de tiempo de un punto de elección. Si el punto de elección tiene un tiempo asociado posterior al de la variable, no es necesario revertir la variable cuando se retrocede al punto de elección, ya que se modificó antes de que se produjera el punto de elección.