En retrodetección algoritmos , backjumping es una técnica que reduce el espacio de búsqueda , por lo tanto, el aumento de la eficiencia. Si bien el retroceso siempre sube un nivel en el árbol de búsqueda cuando se han probado todos los valores de una variable, el retroceso puede subir más niveles. En este artículo, un orden fijo de evaluación de variables se utiliza, pero las mismas consideraciones se aplican a un orden dinámico de evaluación.
Un árbol de búsqueda visitado por retroceso regular
Un backjump: no se visita el nodo gris
Definición
Siempre que el retroceso ha probado todos los valores de una variable sin encontrar ninguna solución, reconsidera la última de las variables asignadas previamente, cambiando su valor o retrocediendo más si no se van a probar otros valores. Si es la asignación parcial actual y todos los valores para se han intentado sin encontrar una solución, el retroceso concluye que ninguna solución se extiende existe. El algoritmo luego "sube" a, cambiando si es posible, retrocediendo de otra manera.
La cesión parcial no siempre es necesaria en su totalidad para demostrar que ningún valor de conducir a una solución. En particular, un prefijo de la asignación parcial puede tener la misma propiedad, es decir, existe un índice tal que no puede extenderse para formar una solución con cualquier valor para . Si el algoritmo puede probar este hecho, puede considerar directamente un valor diferente para en lugar de reconsiderar como lo haría normalmente.
Un ejemplo en el que la asignación actual a ha sido probado sin éxito con todos los valores posibles de . Retroceder se remonta a, intentando asignarle un nuevo valor. | En lugar de dar marcha atrás, el algoritmo realiza una elaboración adicional, lo que demuestra que las evaluaciones , , y no forman parte de ninguna solución. | Como resultado, la evaluación actual de no es parte de ninguna solución, y el algoritmo puede retroceder directamente a , probando un nuevo valor. |
La eficiencia de un algoritmo de backjumping depende de qué tan alto sea capaz de retroceder. Idealmente, el algoritmo podría saltar de a cualquier variable es tal que la asignación actual a no puede extenderse para formar una solución con cualquier valor de . Si este es el caso,se llama salto seguro .
Establecer si un salto es seguro no siempre es factible, ya que los saltos seguros se definen en términos del conjunto de soluciones, que es lo que el algoritmo está tratando de encontrar. En la práctica, los algoritmos de backjumping utilizan el índice más bajo que pueden demostrar de manera eficiente como un salto seguro. Diferentes algoritmos utilizan diferentes métodos para determinar si un salto es seguro. Estos métodos tienen un costo diferente, pero un costo más alto de encontrar un salto seguro más alto puede compensarse con una cantidad reducida de búsqueda debido a saltarse partes del árbol de búsqueda.
Backjumping en los nodos de las hojas
La condición más simple en la que es posible el retroceso es cuando todos los valores de una variable han demostrado ser inconsistentes sin más ramificaciones. En la satisfacción de restricciones , una evaluación parcial es consistente si y solo si satisface todas las restricciones que involucran las variables asignadas, e inconsistente en caso contrario. Podría darse el caso de que una solución parcial consistente no se pueda extender a una solución completa consistente porque algunas de las variables no asignadas pueden no asignarse sin violar otras restricciones.
La condición en la que todos los valores de una variable dada son inconsistentes con la solución parcial actual se llama un callejón sin salida de la hoja . Esto sucede exactamente cuando la variable es una hoja del árbol de búsqueda (que corresponde a nodos que solo tienen hojas como hijos en las figuras de este artículo).
El algoritmo de backjumping de Gaschnig hace un backjump solo en callejones sin salida de hojas. En otras palabras, funciona de manera diferente al retroceso solo cuando todos los valores posibles de ha sido probado y resultó inconsistente sin la necesidad de ramificar otra variable.
Se puede encontrar un salto seguro simplemente evaluando, para cada valor , el prefijo más corto de inconsistente con . En otras palabras, si es un valor posible para , el algoritmo comprueba la coherencia de las siguientes evaluaciones:
... | ||||
... | ||||
... | ||||
El índice más pequeño (el más bajo de la lista) para el cual las evaluaciones son inconsistentes sería un salto seguro si fueron el único valor posible para . Dado que cada variable generalmente puede tomar más de un valor, el índice máximo que surge de la verificación para cada valor es un salto seguro, y es el punto donde salta el algoritmo de Gaschnig.
En la práctica, el algoritmo puede verificar las evaluaciones anteriores al mismo tiempo que verifica la consistencia de .
Backjumping en los nodos internos
El algoritmo anterior solo retrocede cuando los valores de una variable pueden mostrarse inconsistentes con la solución parcial actual sin más ramificaciones. En otras palabras, permite un retroceso solo en los nodos hoja del árbol de búsqueda.
Un nodo interno del árbol de búsqueda representa una asignación de una variable consistente con las anteriores. Si ninguna solución extiende esta asignación, el algoritmo anterior siempre retrocede: en este caso, no se realiza ningún retroceso.
El backjumping en los nodos internos no se puede realizar como en los nodos hoja. De hecho, si algunas evaluaciones debifurcación requerida, es porque son consistentes con la asignación actual. Como resultado, la búsqueda de un prefijo que no sea coherente con estos valores de la última variable no se realiza correctamente.
En tales casos, lo que resultó ser una evaluación no ser parte de una solución con la evaluación parcial actual es la búsqueda recursiva . En particular, el algoritmo "sabe" que no existe una solución a partir de este punto porque vuelve a este nodo en lugar de detenerse después de haber encontrado una solución.
Este retorno se debe a una serie de callejones sin salida , puntos en los que el algoritmo ha demostrado ser una solución parcial inconsistente. Para dar más backjump, el algoritmo debe tener en cuenta que la imposibilidad de encontrar soluciones se debe a estos callejones sin salida. En particular, los saltos seguros son índices de prefijos que aún hacen que estos callejones sin salida sean soluciones parciales inconsistentes.
En este ejemplo, el algoritmo vuelve a , después de probar todos sus valores posibles, debido a los tres puntos de inconsistencia cruzados. | El segundo punto sigue siendo inconsistente incluso si los valores de y se eliminan de su evaluación parcial (tenga en cuenta que los valores de una variable están en sus hijos) | Las otras evaluaciones inconsistentes siguen siendo así incluso sin , , y | El algoritmo puede retroceder a ya que esta es la variable más baja que mantiene todas las inconsistencias. Un nuevo valor para será probado. |
En otras palabras, cuando todos los valores de se ha probado, el algoritmo puede retroceder a una variable anterior siempre que la evaluación actual de la verdad de es inconsistente con todas las evaluaciones de verdad de en los nodos hoja que son descendientes del nodo .
Simplificaciones
Debido al número potencialmente alto de nodos que se encuentran en el subárbol de , la información necesaria para retroceder de forma segura desde se recoge durante la visita de su subárbol. Encontrar un salto seguro se puede simplificar mediante dos consideraciones. La primera es que el algoritmo necesita un salto seguro, pero aún funciona con un salto que no es el salto seguro más alto posible.
La segunda simplificación es que los nodos en el subárbol de que han sido saltados por un backjump se pueden ignorar mientras se busca un backjump para . Más precisamente, todos los nodos saltados por un salto hacia atrás desde el nodo hasta el nodo son irrelevantes para el subárbol enraizado en , y también son irrelevantes sus otros subárboles.
De hecho, si un algoritmo bajara del nodo para a través de un camino pero retrocede en su camino de regreso, entonces podría haber ido directamente desde para en lugar de. De hecho, el backjump indica que los nodos entre y son irrelevantes para el subárbol enraizado en . En otras palabras, un backjump indica que la visita a una región del árbol de búsqueda ha sido un error. Por lo tanto, esta parte del árbol de búsqueda se puede ignorar al considerar un posible retroceso de o de uno de sus antepasados.
Este hecho puede explotarse recolectando, en cada nodo, un conjunto de variables previamente asignadas cuya evaluación sea suficiente para demostrar que no existe solución en el subárbol enraizado en el nodo. Este conjunto se construye durante la ejecución del algoritmo. Al retirarse de un nodo, a este conjunto se le quita la variable del nodo y se recoge en el conjunto del destino de retroceso o retroceso. Dado que los nodos que se saltan del backjumping nunca se retiran, sus conjuntos se ignoran automáticamente.
Backjumping basado en gráficos
El fundamento del backjumping basado en gráficos es que se puede encontrar un salto seguro al verificar cuál de las variables están en una restricción con las variables que se instancian en los nodos hoja. Para cada nodo hoja y cada variable de índice que se instancia allí, los índices menores o iguales a cuya variable está en una restricción con se puede utilizar para encontrar saltos seguros. En particular, cuando todos los valores de se han probado, este conjunto contiene los índices de las variables cuyas evaluaciones permiten demostrar que no se puede encontrar una solución visitando el subárbol enraizado en . Como resultado, el algoritmo puede retroceder al índice más alto de este conjunto.
El hecho de que los nodos saltados por backjumping se puede ignorar cuando se considera un backjump adicional puede ser aprovechado por el siguiente algoritmo. Cuando se retrae de un nodo hoja, el conjunto de variables que están en restricción con él se crea y se "envía de vuelta" a su padre, o antepasado en caso de retroceso. En cada nodo interno, se mantiene un conjunto de variables. Cada vez que se recibe un conjunto de variables de uno de sus hijos o descendientes, sus variables se agregan al conjunto mantenido. Al retroceder más o retroceder desde el nodo, la variable del nodo se elimina de este conjunto y el conjunto se envía al nodo que es el destino del retroceso o retroceso. Este algoritmo funciona porque el conjunto mantenido en un nodo recoge todas las variables que son relevantes para probar la insatisfacción en las hojas que son descendientes de este nodo. Dado que los conjuntos de variables solo se envían al retroceder desde los nodos, los conjuntos recopilados en los nodos omitidos por el backjumping se ignoran automáticamente.
Backjumping basado en conflictos (también conocido como backjumping dirigido por conflictos (cbj))
Un algoritmo de backjumping aún más refinado, a veces capaz de lograr backjumps más grandes, se basa en verificar no solo la presencia común de dos variables en la misma restricción, sino también en si la restricción realmente causó inconsistencia. En particular, este algoritmo recopila una de las restricciones violadas en cada hoja. En cada nodo, el índice más alto de una variable que se encuentra en una de las restricciones recopiladas en las hojas es un salto seguro.
Si bien la restricción violada elegida en cada hoja no afecta la seguridad del salto resultante, la elección de restricciones de los índices más altos posibles aumenta la altura del salto. Por esta razón, las restricciones de órdenes de retroceso basadas en conflictos de tal manera que las restricciones sobre las variables de índices más bajos se prefieren sobre las restricciones sobre las variables de índices más altos.
Formalmente, una restricción se prefiere sobre otro si el índice más alto de una variable en pero no en es menor que el índice más alto de una variable en pero no en . En otras palabras, excluyendo las variables comunes, se prefiere la restricción que tiene todos los índices más bajos.
En un nodo hoja, el algoritmo elige el índice más bajo tal que es inconsistente con la última variable evaluada en la hoja. Entre las restricciones que se violan en esta evaluación, elige la más preferida y recopila todos sus índices menos de. De esta forma, cuando el algoritmo vuelve a la variable, el índice recopilado más bajo identifica un salto seguro.
En la práctica, este algoritmo se simplifica al recopilar todos los índices en un solo conjunto, en lugar de crear un conjunto para cada valor de . En particular, el algoritmo recopila, en cada nodo, todos los conjuntos provenientes de sus descendientes que no se han saltado por backjumping. Al retirarse de este nodo, este conjunto se quita la variable del nodo y se recoge en el destino de retroceso o retroceso.
Se propuso backjumping conflicto dirigida por Restricción Problemas de satisfacción por Patrick Prosser en su seminal artículo de 1993.
Ver también
Referencias
- Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann. ISBN 1-55860-890-7.
- Prosser, Patrick (1993). "Algoritmos híbridos para el problema de satisfacción de restricciones" (PDF) . Inteligencia Computacional 9 (3). Cite journal requiere
|journal=
( ayuda )