Hispanopedia WikiEl retroceso es una clase de algoritmos para encontrar soluciones a algunos problemas computacionales , en particular problemas de satisfacción de restricciones o de enumeración, que construyen incrementalmente candidatos a las soluciones y abandonan un candidato ("retroceden") tan pronto como determinan que el candidato no puede completarse a una solución válida. [ 1 ]
El ejemplo clásico del uso del método de retroceso es el problema de las ocho reinas , que consiste en encontrar todas las disposiciones posibles de ocho reinas en un tablero estándar de ajedrez , de manera que ninguna reina ataque a otra. En el método de retroceso común, las soluciones parciales candidatas son disposiciones de k reinas en las primeras k filas del tablero, todas en filas y columnas diferentes. Cualquier solución parcial que contenga dos reinas que se ataquen mutuamente puede descartarse.
El retroceso solo se puede aplicar a problemas que admiten el concepto de "solución candidata parcial" y una prueba relativamente rápida para determinar 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 todas las soluciones candidatas completas, ya que puede eliminar muchas 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 rompecabezas. 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 " definidos por el usuario, que establecen el problema a resolver, la naturaleza de los candidatos parciales y cómo se extienden para formar candidatos completos. Por lo tanto, se trata de una metaheurística más que de un algoritmo específico ; si bien, a diferencia de muchas otras metaheurísticas, garantiza 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 dar todas las soluciones posibles al problema dado. La compleció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 recursivamente , desde la raíz hacia abajo, en orden de búsqueda en profundidad . En cada nodo c , el algoritmo comprueba si c puede completarse a una solución válida. Si no es posible, se omite ( poda ) todo el subárbol con raíz en c . En caso contrario, el algoritmo (1) comprueba si c es una solución válida y, de ser así, se lo comunica 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 recorre el algoritmo es solo una parte del árbol potencial. El costo total del algoritmo es igual al 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:
- raíz ( P ): devuelve el candidato parcial en la raíz del árbol de búsqueda.
- rechazar ( P , c ): devuelve verdadero solo si el candidato parcial c no merece la pena completarse.
- aceptar ( P , c ): devuelve verdadero si c es una solución de P , y falso en caso contrario.
- primero ( P , c ): genera la primera extensión del candidato c .
- next ( P , s ): genera la siguiente extensión alternativa de un candidato, después de la extensión s .
- salida ( P , c ): utilice la solución c de P , según corresponda a la aplicación.
El algoritmo de retroceso reduce el problema a la llamada backtrack ( P , root ( P )), donde backtrack es el siguiente procedimiento recursivo:
El procedimiento backtrack(P, c) es si reject(P, c) entonces return si accept(P, c) entonces output(P, c) s ← primero(P, c) mientras s ≠ NULL hacer Retroceso(P, s) s ← siguiente(P, s)
Consideraciones de uso
El procedimiento de rechazo debe ser una función booleana que devuelva verdadero solo si es seguro 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 provocar que el procedimiento de retroceso omita algunas soluciones válidas. El procedimiento puede asumir que reject ( 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 la función `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 seguirá encontrando todas las soluciones, pero será equivalente a una búsqueda por 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 asumir que el candidato parcial c y todos sus ancestros en el árbol han superado 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 generar otras soluciones válidas.
Los procedimientos `first` y `next` son utilizados por el algoritmo de retroceso 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 devolver 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.
En conjunto, 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 aparezca en algún punto 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 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 consumir una cantidad determinada de tiempo de CPU .
Ejemplos
Algunos ejemplos en los que se puede utilizar el retroceso para resolver acertijos o problemas son:
- Rompecabezas como el rompecabezas de las ocho reinas , crucigramas , aritmética verbal , Sudoku [ nb 1 ] y Peg Solitaire .
- Problemas de optimización combinatoria como el análisis sintáctico y el problema de la mochila .
- Lenguajes de programación orientados a objetivos, como Icon , Planner y Prolog , que utilizan el retroceso internamente para generar respuestas.
- El algoritmo DPLL para resolver el problema de satisfacibilidad booleana .
El siguiente es un ejemplo donde 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 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 (). Los procedimientos primero y siguiente serían entonces
La función first(P, c) es k ← longitud(c) Si k = n, entonces devuelve NULL; de lo contrario, devuelve (c[1], c[2], ..., c[k], 1).
función next(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í, length ( c ) es el número de elementos en la lista c .
La llamada reject ( 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 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 sí 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 se indicó anteriormente, entonces aceptar ( P , c ) solo necesita verificar si c está completo, es decir, si tiene n elementos.
Por lo general, es mejor ordenar la lista de variables de manera que comience con las más importantes (es decir, las que tienen menos opciones de valor o las que tienen un mayor impacto en las decisiones posteriores).
También se podría permitir que la siguiente función elija qué variable debe asignarse al extender un candidato parcial, basándose en 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 mínimos de recuperación utilizados en la copia de seguridad, las implementaciones de retroceso suelen mantener un registro de variables para documentar el historial de cambios de valor. Una implementación eficiente evitará crear una entrada en el registro de variables entre dos cambios sucesivos cuando no haya un punto de decisión, ya que el retroceso borrará todos los cambios en una sola operación.
Una alternativa al registro de la variable consiste en conservar una marca de tiempo que indique cuándo se realizó el último cambio en la variable. Esta marca de tiempo se compara con la de un punto de decisión. Si el punto de decisión tiene una fecha posterior a la de la variable, no es necesario revertir la variable al retroceder en el punto de decisión, ya que se modificó antes de que este ocurriera.
Véase también
- El hilo de Ariadna (lógica) – Método de resolución de problemas
- Retroceso : en los algoritmos de retroceso, técnica que reduce el espacio de búsqueda.
- Encadenamiento hacia atrás : método para realizar inferencias.
- Algoritmo de enumeración : algoritmo que genera todas las soluciones a un problema.
- Algoritmos para resolver Sudoku – Algoritmos para completar un Sudoku
Notas
Referencias
- ↑ Gurari, Eitan (1999). "CIS 680: ESTRUCTURAS DE DATOS: Capítulo 19: Algoritmos de retroceso" . Archivado del original el 17 de marzo de 2007.
- ^ Biere, A.; Heule, M.; van Maaren, H. (29 de enero de 2009). Manual de Satisfacibilidad . Prensa IOS. ISBN 978-1-60750-376-7.
- ↑ Watson, Des (22 de marzo de 2017). Un enfoque práctico para la construcción de compiladores . Springer. ISBN 978-3-319-52789-5.
- ↑ 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. Consultado el 30 de diciembre de 2008 .
Lecturas adicionales
- Gilles Brassard, Paul Bratley (1995). Fundamentos de algoritmia . Prentice-Hall. ISBN 9780133350685.
Enlaces externos
- HBmeyer.de , Animación interactiva de un algoritmo de retroceso
- Resolución de problemas combinatorios con STL y retroceso : artículo y código fuente en C++ para una implementación genérica de retroceso.
- Coincidencia de patrones
- Algoritmos de búsqueda