El retroceso es una clase de algoritmos para encontrar soluciones a algunos problemas computacionales , en particular problemas de satisfacción de restricciones , que construye incrementalmente candidatos para las soluciones y abandona un candidato ("retrocede") tan pronto como determina que el candidato no puede completarse hasta un solución válida. [1]
El ejemplo clásico de libro de texto sobre el uso del retroceso es el rompecabezas de las ocho reinas , que pide que se coloquen todas las ocho reinas en un tablero de ajedrez estándar para que ninguna reina ataque a 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. Se puede abandonar cualquier solución parcial que contenga dos reinas que se ataquen mutuamente.
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 llegar a una solución válida. Es inútil, por ejemplo, para localizar un valor determinado 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 analizar [ 3] 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 los " procedimientos de caja negra " dados por el usuario que definen el problema a resolver, la naturaleza de los candidatos parciales y cómo se extienden a candidatos completos. Por lo tanto, es una metaheurística más que 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 período de tiempo limitado.
El término "retroceder" 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 seguimiento general incorporada.
El algoritmo de retroceso enumera un conjunto de candidatos parciales que, en principio, podrían completarse de varias maneras para dar todas las soluciones posibles al problema dado. La finalización se realiza de forma incremental, mediante una secuencia de pasos de extensión candidata.
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 por un único paso de extensión; las hojas del árbol son las candidatas parciales que no pueden extenderse más.
El algoritmo de retroceso atraviesa este árbol de búsqueda de forma recursiva , desde la raíz hacia abajo, en orden de profundidad . En cada nodo c , el algoritmo verifica si c puede completarse hasta obtener una solución válida. Si no es posible, 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, de ser así, lo informa al usuario; y (2) enumera recursivamente todos los subárboles de c . Las dos pruebas y los hijos de cada nodo se definen mediante procedimientos dados por el usuario.
Por lo tanto, el árbol de búsqueda real que recorre el algoritmo es sólo 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 considerarse al elegir el árbol de búsqueda potencial y al implementar la prueba de poda.
Para aplicar el 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 , raíz , rechazar , aceptar , primero , siguiente y salida . Estos procedimientos deben tomar los datos de instancia P como parámetro y deben hacer lo siguiente:
El algoritmo de retroceso reduce el problema al retroceso de llamada ( P , raíz ( P )), donde el retroceso es el siguiente procedimiento recursivo:
El procedimiento de retroceso (P, c) es si se rechaza (P, c) y luego regresa si se acepta (P, c) y luego se genera (P, c) s ← primero(P, c) mientras que s ≠ NULL hazlo 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, debería devolver falso . Un resultado verdadero incorrecto puede hacer que el procedimiento de retroceso omita algunas soluciones válidas. El procedimiento puede suponer que rechazar ( P , t ) devolvió falso para cada ancestro t de c en el árbol de búsqueda.
Por otro lado, la eficiencia del algoritmo de retroceso depende de que el rechazo sea verdadero para los candidatos que están lo más cerca posible de la raíz. Si el rechazo siempre devuelve false , el algoritmo seguirá encontrando todas las soluciones, pero será equivalente a una búsqueda de fuerza bruta.
El procedimiento de aceptación debería devolver verdadero si c es una solución completa y válida para la instancia del problema P , y falso en caso contrario. Se puede suponer que el candidato parcial c y todos sus ancestros en el árbol han pasado la prueba de rechazo .
El pseudocódigo general anterior no supone 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 ampliarse aún más para producir otras soluciones válidas.
El algoritmo de retroceso utiliza los procedimientos primero y siguiente para enumerar los hijos de un nodo c del árbol, es decir, los candidatos que difieren de c en un solo paso de extensión. La llamada first ( P , c ) debería producir el primer hijo de c , en algún orden; y la llamada next ( P , s ) debería devolver el siguiente hermano del nodo s , en ese orden. Ambas funciones deberían 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 manera que cada solución de P ocurra en algún lugar del árbol y ningún candidato parcial ocurra más de una vez. Además, deberían admitir un predicado de rechazo eficiente y efectivo .
El pseudocódigo anterior llamará a la salida de 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 un número específico de soluciones; o después de probar un número específico de candidatos parciales, o después de gastar una determinada cantidad de tiempo de CPU .
Los 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 algunos restricción arbitraria (función booleana) F .
Para esta clase de problemas, los datos de instancia P serían los números 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 números 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 siguiente procedimiento serían entonces
la función primero (P, c) es k ← longitud(c) si k = n entonces devuelve NULL ; en caso 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 ; en caso 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 rechazar ( P , c ) debería 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, rechazar sólo necesita comprobar aquellos términos que sí dependen de x [ k ], ya que los términos que dependen sólo de x [1],…, x [ k − 1] se habrán probado más arriba en el árbol de búsqueda.
Suponiendo que el rechazo 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 para que comience con las más críticas (es decir, las que tienen menos opciones de valor o las que tienen un mayor impacto en las elecciones posteriores).
También se podría permitir que la siguiente función elija qué variable se debe asignar al extender un candidato parcial, en función de los valores de las variables ya asignadas por ella. 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 seguimiento suelen mantener un rastro variable para registrar el historial de cambios de valores. Una implementación eficiente evitará la creación de una entrada de seguimiento variable entre dos cambios sucesivos cuando no hay un punto de elección, ya que el retroceso borrará todos los cambios como una sola operación.
Una alternativa al seguimiento 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 el punto de elección, ya que se cambió antes de que ocurriera el punto de elección.