Marca de retroceso

En satisfacción de restricciones , el backmarking es una variante del algoritmo de backtracking .

Las marcas de retroceso funcionan como retroceder al evaluar variables de forma iterativa en un orden determinado, por ejemplo . Mejora el retroceso al mantener información sobre la última vez que se instancia una variable a un valor e información sobre lo que cambió desde entonces. En particular: ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle x_{i}}$

Un ejemplo en el que la búsqueda ha llegado por primera vez. ${\displaystyle x_{i}=d}$

1. para cada variable y valor , el algoritmo registra información sobre la última vez que se configuró ; en particular, almacena el índice mínimo tal que la asignación a era inconsistente ; ${\displaystyle x_{i}}$ ${\displaystyle a}$ ${\displaystyle x_{i}}$ ${\displaystyle a}$ ${\displaystyle j<i}$ ${\displaystyle x_{1},\ldots ,x_{j},x_{i}}$
2. para cada variable , el algoritmo almacena cierta información relativa a lo que cambió desde la última vez que se evaluó ; en particular, almacena el índice mínimo de una variable que ha cambiado desde entonces. ${\displaystyle x_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle k<i}$

La primera información se recopila y almacena cada vez que el algoritmo evalúa una variable y se realiza simplemente verificando la coherencia de las asignaciones actuales para , para , para , etc. ${\displaystyle x_{i}}$ ${\displaystyle a}$ ${\displaystyle x_{1},x_{i}}$ ${\displaystyle x_{1},x_{2},x_{i}}$ ${\displaystyle x_{1},x_{2},x_{3},x_{i}}$

Cuando la búsqueda llega por segunda vez, parte del camino es el mismo que la primera vez. ${\displaystyle x_{i}=d}$

La segunda información cambia cada vez que se evalúa otra variable. En particular, el índice de la "variable máxima sin cambios desde la última evaluación de " posiblemente cambie cada vez que otra variable cambia de valor. Cada vez que cambia una variable arbitraria, todas las variables se consideran por turno. Si era su índice asociado anterior, este valor se cambia a . ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{i}}$ ${\displaystyle i>j}$ ${\displaystyle k}$ ${\displaystyle min(k,j)}$

Los datos recopilados de esta manera se utilizan para evitar algunas comprobaciones de coherencia. En particular, siempre que se establezca el retroceso , el retroceso compara los dos índices en relación con y el par . Dos condiciones permiten determinar la consistencia o inconsistencia parcial sin verificar las restricciones. Si es el índice mínimo de una variable que cambió desde la última vez que se evaluó y es el índice mínimo tal que la evaluación fue consistente la última vez que se evaluó , entonces: ${\displaystyle x_{i}=a}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}=a}$ ${\displaystyle k}$ ${\displaystyle x_{i}}$ ${\displaystyle j}$ ${\displaystyle x_{1},\ldots ,x_{j},x_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle a}$

1. si , la evaluación de sigue siendo inconsistente como antes, ya que ninguna de estas variables cambió hasta el momento; como resultado, no es necesaria ninguna verificación adicional de coherencia; ${\displaystyle j<k}$ ${\displaystyle x_{1},\ldots ,x_{j},x_{i}}$
2. si , la evaluación sigue siendo consistente como antes; esto permite omitir algunas comprobaciones de coherencia, pero la asignación aún puede ser inconsistente. ${\displaystyle j\geq k}$ ${\displaystyle x_{1},\ldots ,x_{k},x_{i}}$ ${\displaystyle x_{1},\ldots ,x_{i}}$

A diferencia de otras variantes del retroceso, el retroceso no reduce el espacio de búsqueda, sino que sólo posiblemente reduce el número de restricciones que se satisfacen con una solución parcial.

Referencias

• Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufman. ISBN 1-55860-890-7.