stringtranslate.com

Retrocediendo

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 método de 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 método de 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 en lugar 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.

Descripción del método

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.

Pseudocódigo

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:

  1. raíz ( P ): devuelve el candidato parcial en la raíz del árbol de búsqueda.
  2. rechazar ( P , c ): devuelve verdadero solo si el candidato parcial c no vale la pena completar.
  3. aceptar ( P , c ): devuelve verdadero si c es una solución de P , y falso en caso contrario.
  4. primero ( P , c ): genera la primera extensión del candidato c .
  5. siguiente ( 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 sea apropiado para la aplicación.

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)

Consideraciones de uso

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 .

Variantes de parada temprana

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 .

Ejemplos

Un sudoku resuelto retrocediendo

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 :

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 nk 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 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 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.

Véase también

Notas

Referencias

  1. ^ Gurari, Eitan (1999). "CIS 680: ESTRUCTURAS DE DATOS: Capítulo 19: Algoritmos de retroceso". Archivado desde el original el 17 de marzo de 2007.
  2. ^ Biere, A.; Heule, M.; van Maaren, H. (29 de enero de 2009). Manual de satisfacibilidad. Prensa IOS. ISBN 978-1-60750-376-7.
  3. ^ Watson, Des (22 de marzo de 2017). Un enfoque práctico para la construcción de compiladores. Springer. ISBN 978-3-319-52789-5.
  4. ^ Rossi, Francesca; van Beek, Peter; Walsh, Toby (agosto de 2006). "Satisfacción de restricciones: un paradigma emergente". Manual de programación con restricciones. Ámsterdam : Elsevier . pág. 14. ISBN. 978-0-444-52726-4. Recuperado el 30 de diciembre de 2008 .

Lectura adicional

Enlaces externos