Retroceso - Backtracking

El retroceso es un algoritmo general para encontrar soluciones a algunos problemas computacionales , en particular los problemas de satisfacción de restricciones , que construye gradualmente candidatos a las soluciones y abandona a un candidato ("retrocesos") tan pronto como determina que el candidato no se puede completar a un valor válido. solución.

El ejemplo clásico de libro de texto del uso del retroceso es el rompecabezas de las ocho reinas , que pide todos los arreglos de ocho reinas de ajedrez en un tablero de ajedrez estándar para que ninguna reina ataque a otra. En el enfoque de retroceso común, los candidatos parciales son arreglos 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 atacan 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 para obtener una solución válida. Es inútil, por ejemplo, para ubicar 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 , como crucigramas , aritmética verbal , sudoku y muchos otros acertijos. A menudo es la técnica más conveniente para analizar , para el problema de la mochila y otros problemas de optimización combinatoria . También es la base de los denominados lenguajes de programación lógica como Icon , Planner y Prolog .

El retroceso depende de los " procedimientos de caja negra " proporcionados por el usuario que definen el problema a resolver, la naturaleza de los candidatos parciales y cómo se amplían a candidatos completos. Por lo tanto, es un algoritmo metaheurístico más que específico, aunque, a diferencia de muchas otras metaheurísticas, está garantizado que encontrará todas las soluciones a un problema finito en un período de tiempo limitado.

El término "retroceso" fue acuñado por el matemático estadounidense DH Lehmer en la década de 1950. El lenguaje pionero de procesamiento de cadenas SNOBOL (1962) puede haber sido el primero en proporcionar una función de retroceso general incorporada.

Descripción del método

El algoritmo de retroceso enumera un conjunto de candidatos parciales que, en principio, podrían completarse de diversas formas para dar todas las posibles soluciones al problema dado. La finalización se realiza de forma incremental, mediante una secuencia de pasos de extensión 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 se diferencian de él en un solo 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 comprueba si c se puede completar con una solución válida. Si no puede, se salta (se poda ) todo el subárbol enraizado en c . De lo contrario, el algoritmo (1) comprueba si c en sí mismo 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 proporcionados por el usuario.

Por lo tanto, el árbol de búsqueda real que atraviesa 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.

Pseudocódigo

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:

  1. root ( P ): devuelve el candidato parcial en la raíz del árbol de búsqueda.
  2. rechazar ( P , c ): devuelve verdadero solo si no vale la pena completar el candidato parcial c .
  3. aceptar ( P , c ): devuelve verdadero si c es una solución de P , y falso en caso contrario.
  4. first ( P , c ): genera la primera extensión del candidato c .
  5. next ( P , s ): genera la siguiente extensión alternativa de un candidato, después de la extensión s .
  6. salida ( P , c ): utilice la solución c de P , según corresponda a la aplicación.

El algoritmo de retroceso reduce el problema al retroceso de la llamada ( raíz ( P )), donde retroceso es el siguiente procedimiento recursivo:

procedure backtrack(c) is
    if reject(P, c) then return
    if accept(P, c) then output(P, c)
    s ← first(P, c)
    while s ≠ NULL do
        backtrack(s)
        s ← next(P, s)

Consideraciones de uso

El rechazar procedimiento debe ser una función booleana de valor que los retornos cierto sólo si bien es cierto que no es posible la extensión 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 bt pierda algunas soluciones válidas. El procedimiento puede asumir que el rechazo ( P , t ) devolvió falso para cada antepasado t de c en el árbol de búsqueda.

Por otro lado, la eficiencia del algoritmo de retroceso depende de que el rechazo devuelva verdadero para los candidatos que están lo más cerca posible de la raíz. Si el rechazo siempre devuelve falso , el algoritmo seguirá encontrando 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 cy todos sus antepasados ​​en el árbol han pasado la prueba de rechazo .

El pseudocódigo general anterior no asume que las soluciones válidas son 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 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 primero ( P , c ) debería producir el primer hijo de c , en algún orden; y la llamada siguiente ( P , s ) debería 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 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, deben admitir un predicado de rechazo eficiente y eficaz .

Variantes de parada anticipada

El pseudocódigo anterior llamará a la salida de todos los candidatos que sean una solución para la instancia P dada . 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 cantidad determinada de tiempo de CPU .

Ejemplos de

Un Sudoku resuelto retrocediendo.

Los ejemplos en los que se puede usar 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 :

Satisfacción de restricciones

El problema general de satisfacción de restricciones consiste en encontrar una lista de 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, el de datos de instancia P sería los números enteros m y n , y el predicado F . En una solución típica de retroceso a 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 deben asignarse 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

function first(P, c) is
    k ← length(c)
    if k = n then
        return NULL
    else
        return (c[1], c[2], …, c[k], 1)
function next(P, s) is
    k ← length(s)
    if s[k] = m then
        return NULL
    else
        return (s[1], s[2], …, s[k − 1], 1 + s[k])

Aquí la longitud ( c ) es el número de elementos en la lista c .

El rechazo de llamada ( 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 forma 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 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 el rechazo se implementa como arriba, entonces accept ( P , c ) solo necesita verificar si c está completo, es decir, si tiene n elementos.

En general, 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 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 ya asignadas por ella. Pueden obtenerse mejoras adicionales mediante la técnica de propagación de restricciones .

Además de retener los valores mínimos de recuperación utilizados en la copia de seguridad, las implementaciones de retroceso suelen mantener un rastro variable para registrar el historial de cambios de valor. Una implementación eficiente evitará la creación de una entrada de ruta 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 a la ruta 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.

Ver también

Notas

Referencias

Otras lecturas

enlaces externos