Consistencia local

En satisfacción de restricciones , las condiciones de consistencia local son propiedades de los problemas de satisfacción de restricciones relacionados con la consistencia de subconjuntos de variables o restricciones. Se pueden utilizar para reducir el espacio de búsqueda y facilitar la resolución del problema. Se aprovechan varios tipos de condiciones de coherencia local, incluida la coherencia de nodos , la coherencia de arco y la coherencia de ruta .

Cada condición de coherencia local puede imponerse mediante una transformación que cambie el problema sin cambiar sus soluciones; Tal transformación se llama propagación de restricciones . La propagación de restricciones funciona reduciendo dominios de variables, fortaleciendo restricciones o creando nuevas restricciones. Esto conduce a una reducción del espacio de búsqueda, lo que hace que el problema sea más fácil de resolver mediante algunos algoritmos. La propagación de restricciones también se puede utilizar como un verificador de insatisfacibilidad, incompleta en general pero completa en algunos casos particulares.

Las condiciones de consistencia local se pueden agrupar en varias clases. Las condiciones de consistencia local originales requieren que cada asignación parcial consistente (de un tipo particular) pueda extenderse consistentemente a otra variable. La consistencia direccional sólo requiere que se cumpla esta condición cuando la otra variable es mayor que las de la asignación, según un orden determinado. La coherencia relacional incluye extensiones a más de una variable, pero esta extensión sólo es necesaria para satisfacer una restricción o un conjunto de restricciones determinado.

Suposiciones

En este artículo, un problema de satisfacción de restricciones se define como un conjunto de variables, un conjunto de dominios y un conjunto de restricciones. Las variables y los dominios están asociados: el dominio de una variable contiene todos los valores que la variable puede tomar. Una restricción se compone de una secuencia de variables, llamada alcance, y un conjunto de sus evaluaciones, que son las evaluaciones que satisfacen la restricción.

Se supone que los problemas de satisfacción de restricciones a los que se hace referencia en este artículo tienen una forma especial. Un problema está en forma normalizada , respectivamente regular , si cada secuencia de variables es el alcance de como máximo una restricción o exactamente una restricción. El supuesto de regularidad realizado sólo para restricciones binarias conduce a la forma estandarizada . Estas condiciones siempre se pueden hacer cumplir combinando todas las restricciones de una secuencia de variables en una sola y/o agregando una restricción que sea satisfecha por todos los valores de una secuencia de variables.

En las figuras utilizadas en este artículo, la falta de vínculos entre dos variables indica que no existe ninguna restricción o existe una restricción satisfecha por todos los valores entre estas dos variables. ^{[ se necesita aclaración ]}

Consistencia local

Todas las condiciones de consistencia local "estándar" requieren que todas las evaluaciones parciales consistentes puedan extenderse a otra variable de tal manera que la asignación resultante sea consistente. Una evaluación parcial es consistente si satisface todas las restricciones cuyo alcance es un subconjunto de las variables asignadas. ^{[ se necesita aclaración ]}

Consistencia de nodos

La coherencia de los nodos requiere que cada restricción unaria de una variable sea satisfecha por todos los valores en el dominio de la variable, y viceversa. Esta condición puede imponerse trivialmente reduciendo el dominio de cada variable a los valores que satisfagan todas las restricciones unarias de esa variable. Como resultado, las restricciones unarias pueden despreciarse y asumirse incorporadas a los dominios.

Por ejemplo, dada una variable con un dominio de y una restricción , la coherencia del nodo restringiría el dominio a y la restricción podría descartarse. Este paso de preprocesamiento simplifica las etapas posteriores. ${\displaystyle V}$ ${\displaystyle \left\{1,2,3,4\right\}}$ ${\displaystyle V\leq 3}$ ${\displaystyle \left\{1,2,3\right\}}$

Consistencia del arco

${\displaystyle x_{2}}$es consistente con pero no con , ya que el valor no es compatible con ningún valor para . ${\displaystyle x_{3}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}=1}$ ${\displaystyle x_{1}}$

Una variable de un problema de satisfacción de restricciones es consistente con otra si cada uno de sus valores admisibles es consistente con algún valor admisible de la segunda variable. Formalmente, una variable es consistente con otra variable si, para cada valor en el dominio de existe un valor en el dominio de tal que satisface la restricción binaria entre y . Un problema es consistente en arco si cada variable es consistente en arco con todas las demás. ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle a}$ ${\displaystyle x_{i}}$ ${\displaystyle b}$ ${\displaystyle x_{j}}$ ${\displaystyle (a,b)}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$

Por ejemplo, considere la restricción donde las variables varían en el dominio de 1 a 3. Como nunca puede ser 3, no hay ningún arco de 3 a un valor en, por lo que es seguro eliminarlo. Asimismo, nunca puede ser 1, por lo que no hay arco y, por lo tanto, se puede eliminar. ${\displaystyle x<y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$

La consistencia del arco también se puede definir en relación con una restricción binaria específica: una restricción binaria es consistente con el arco si cada valor de una variable tiene un valor de la segunda variable tal que satisfaga la restricción. Esta definición de consistencia de arco es similar a la anterior, pero se proporciona específicamente para una restricción. Esta diferencia es especialmente relevante para problemas no normalizados, donde la definición anterior consideraría todas las restricciones entre dos variables mientras que ésta considera solo una específica.

La coherencia del arco se aplica eliminando 1 como valor para x2. Como resultado, x3 ya no es consistente con x2 porque x3=2 no corresponde a un valor para x2.

Si una variable no es consistente con otra, se puede lograr eliminando algunos valores de su dominio. Esta es la forma de propagación de restricciones que impone la coherencia del arco: elimina, del dominio de la variable, todo valor que no corresponde a un valor de la otra variable. Esta transformación mantiene las soluciones del problema, ya que los valores eliminados no tienen solución de todos modos.

La propagación de restricciones puede hacer que todo el problema sea consistente repitiendo esta eliminación para todos los pares de variables. Es posible que este proceso deba considerar un par determinado de variables más de una vez. De hecho, eliminar valores del dominio de una variable puede hacer que otras variables dejen de ser consistentes con ella. Por ejemplo, si el arco es consistente con pero el algoritmo reduce el dominio de , la consistencia del arco con con ya no se mantiene y debe aplicarse nuevamente. ${\displaystyle x_{3}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{3}}$ ${\displaystyle x_{2}}$

Un algoritmo simplista recorrería los pares de variables, imponiendo la coherencia del arco, repitiendo el ciclo hasta que ningún dominio cambie durante un ciclo completo. El algoritmo AC-3 mejora este algoritmo al ignorar las restricciones que no se han modificado desde la última vez que se analizaron. En particular, funciona con un conjunto de restricciones que inicialmente contiene todas las restricciones; en cada paso, se requiere una restricción y se impone la coherencia del arco; Si esta operación puede haber producido una violación de la coherencia del arco sobre otra restricción, vuelve a colocar esa restricción en el conjunto de restricciones a analizar. De esta manera, una vez que se aplica la coherencia del arco a una restricción, esta restricción no se vuelve a considerar a menos que se cambie el dominio de una de sus variables.

Coherencia de ruta (k-consistencia)

x1 y x2 no son consistentes con la ruta de x3. Se puede hacer que la ruta sea consistente eliminando los valores azules de R12.

La consistencia de la ruta es una propiedad similar a la consistencia del arco, pero considera pares de variables en lugar de solo una. Un par de variables es consistente con una tercera variable si cada evaluación consistente del par puede extenderse a la otra variable de tal manera que se satisfagan todas las restricciones binarias . Formalmente, y son consistentes con si, para cada par de valores que satisface la restricción binaria entre y , existe un valor en el dominio de tal que y satisface la restricción entre y y entre y , respectivamente. ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{k}}$ ${\displaystyle (a,b)}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle c}$ ${\displaystyle x_{k}}$ ${\displaystyle (a,c)}$ ${\displaystyle (b,c)}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{k}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{k}}$

La forma de propagación de restricciones que impone la coherencia de la ruta funciona eliminando alguna asignación satisfactoria de una restricción. De hecho, la coherencia de la ruta se puede imponer eliminando de una restricción binaria todas las evaluaciones que no se pueden extender a otra variable. En cuanto a la coherencia del arco, es posible que esta eliminación deba considerar una restricción binaria más de una vez. En cuanto a la consistencia del arco, el problema resultante tiene las mismas soluciones que el original, ya que los valores eliminados no tienen solución.

Dos variables que no están en una restricción se pueden considerar relacionadas mediante una restricción virtual que permite cualquier par posible de valores, representado por los bordes azules en esta figura.

Al hacer cumplir la coherencia de la ruta de x1 y x2 con x3 se elimina el borde en la parte superior. Los valores de x1 y x2 ya no son libres, sino que están relacionados por una nueva restricción real.

La forma de propagación de restricciones que impone la coherencia de la ruta podría introducir nuevas restricciones. Cuando dos variables no están relacionadas por una restricción binaria, están virtualmente relacionadas por la restricción que permite cualquier par de valores. Sin embargo, es posible que algunos pares de valores se eliminen mediante la propagación de restricciones. La restricción resultante ya no se satisface con todos los pares de valores. Por lo tanto, ya no es una restricción virtual y trivial.

El nombre "consistencia de ruta" deriva de la definición original, que involucraba un par de variables y una ruta entre ellas, en lugar de un par y una sola variable. Si bien las dos definiciones son diferentes para un solo par de variables, son equivalentes cuando se refieren al problema completo.

Generalizaciones

La coherencia del arco y la ruta se puede generalizar a restricciones no binarias utilizando tuplas de variables en lugar de una sola o un par. Una tupla de variables es coherente con otra variable si cada evaluación coherente de las variables puede ampliarse con un valor de la otra variable preservando al mismo tiempo la coherencia. Esta definición se extiende a problemas completos de manera obvia. Una coherencia fuerte es coherencia para todos . ${\displaystyle i-1}$ ${\displaystyle i}$ ${\displaystyle i-1}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle j\leq i}$

El caso particular de la consistencia 2 coincide con la consistencia del arco (en este artículo se supone que todos los problemas son consistentes con los nodos). Por otro lado, la consistencia 3 coincide con la consistencia de caminos sólo si todas las restricciones son binarias, porque la consistencia de caminos no implica restricciones ternarias, mientras que la consistencia 3 sí.

Otra forma de generalizar la consistencia del arco es la consistencia del hiperarco o la consistencia del arco generalizada , que requiere la extensibilidad de una sola variable para satisfacer una restricción. Es decir, una variable es hiperarco consistente con una restricción si cada valor de la variable se puede extender a las otras variables de la restricción de tal manera que se satisfaga la restricción.

Consistencia y satisfacibilidad

Esta instancia es consistente con el arco y no contiene ningún dominio vacío, pero no tiene solución. Las líneas azules indican asignaciones forzadas por la elección x1=1.

La propagación de restricciones (imponer una forma de coherencia local) podría producir un dominio vacío o una restricción insatisfactoria . En este caso el problema no tiene solución. Lo contrario no es cierto en general: una instancia inconsistente puede ser consistente con el arco o la ruta sin tener un dominio vacío o una restricción insatisfactoria.

De hecho, la consistencia local es sólo relativa a la consistencia de grupos de variables. Por ejemplo, la consistencia del arco garantiza que cada evaluación consistente de una variable pueda extenderse consistentemente a otra variable. Sin embargo, cuando un único valor de una variable se extiende a otras dos variables, no hay garantía de que estos dos valores sean consistentes entre sí. Por ejemplo, puede ser consistente con y con , pero estas dos evaluaciones pueden no ser consistentes entre sí. ${\displaystyle x_{1}=1}$ ${\displaystyle x_{2}=1}$ ${\displaystyle x_{3}=1}$

Sin embargo, la propagación de restricciones se puede utilizar para demostrar la satisfacibilidad en algunos casos. Un conjunto de restricciones binarias que es consistente con el arco y no tiene un dominio vacío puede ser inconsistente sólo si la red de restricciones contiene ciclos. De hecho, si las restricciones son binarias y forman un gráfico acíclico, los valores siempre se pueden propagar a través de restricciones: para cada valor de una variable, todas las variables en una restricción con ella tienen un valor que satisface esa restricción. Como resultado, se puede encontrar una solución eligiendo iterativamente una variable no asignada y propagándola recursivamente a través de restricciones. Este algoritmo nunca intenta asignar un valor a una variable que ya está asignada, ya que eso implicaría la existencia de ciclos en la red de restricciones.

Una condición similar se cumple para la coherencia de la ruta. Los casos especiales en los que se puede establecer la satisfacibilidad aplicando la consistencia del arco y la consistencia de la trayectoria son los siguientes.

1. hacer cumplir la coherencia del arco establece la satisfacibilidad de problemas formados por restricciones binarias sin ciclos (un árbol de restricciones binarias);
2. hacer cumplir la coherencia de la ruta establece la satisfacibilidad de las restricciones binarias (posiblemente con ciclos) con dominios binarios;
3. imponer una fuerte coherencia establece la satisfacibilidad de los problemas que contienen variables. ${\displaystyle n}$ ${\displaystyle n}$

Casos especiales

Algunas definiciones o resultados sobre la consistencia relativa sólo son válidos en casos especiales.

Cuando los dominios están compuestos de números enteros , se puede definir la coherencia ligada. Esta forma de consistencia se basa en la consistencia de los valores extremos de los dominios, es decir, los valores mínimo y máximo que puede tomar una variable.

Cuando las restricciones son algebraicas o booleanas , la coherencia del arco equivale a agregar una nueva restricción o modificar sintácticamente una antigua, y esto se puede hacer componiendo restricciones adecuadamente.

Restricciones especializadas

Se utilizan habitualmente algunos tipos de restricciones. Por ejemplo, a menudo se utiliza la restricción de que algunas variables son todas diferentes. Existen algoritmos especializados eficientes para imponer la coherencia del arco en tales restricciones.

La restricción que obliga a que varias variables sean diferentes generalmente se escribe o . Esta restricción equivale a la no igualdad de todos los pares de variables diferentes, es decir, para cada . Cuando el dominio de una variable se reduce a un único valor, este valor se puede eliminar de todos los demás dominios mediante la propagación de restricciones al imponer la coherencia del arco. El uso de la restricción especializada permite explotar propiedades que no se cumplen para desigualdades binarias individuales . ${\displaystyle \mathop {\rm {alldifferent}} (x_{1},\ldots ,x_{n})}$alldifferent([X1,...,Xn]) ${\displaystyle x_{i}\not =x_{j}}$ ${\displaystyle i\not =j}$

Una primera propiedad es que el número total de elementos en los dominios de todas las variables debe ser al menos el número de variables. Más precisamente, una vez que se aplica la coherencia del arco, el número de variables no asignadas no debe exceder el número de valores en la unión de sus dominios. De lo contrario, no se puede satisfacer la restricción. Esta condición se puede verificar fácilmente mediante una restricción en la alldifferentforma, pero no corresponde a la consistencia del arco de la red de desigualdades. Una segunda propiedad de la restricción única alldifferentes que la consistencia del hiperarco se puede verificar de manera eficiente utilizando un algoritmo de coincidencia bipartita . En particular, se construye un gráfico con variables y valores como dos conjuntos de nodos, y se ejecuta en él un algoritmo especializado de coincidencia de gráficos bipartitos para verificar la existencia de dicha coincidencia. ^[1]

Un tipo diferente de restricción que se usa comúnmente es el cumulativeuno. Se introdujo por problemas de programación y colocación. Como ejemplo, cumulative([S1,...,Sm], [D1,...,Dm], [R1,...,Rm], L)se puede utilizar para formalizar la condición en la que existen mactividades, cada una con hora de inicio si, duración diy utilización de una cantidad ride un recurso. La restricción establece que la cantidad total de recursos disponibles es L. Existen técnicas especializadas de propagación de restricciones para restricciones acumulativas; Se utilizan diferentes técnicas dependiendo de qué dominios variables ya estén reducidos a un solo valor.

Una tercera restricción especializada que se utiliza en la programación de lógica de restricciones es la elementuno. En la programación de lógica de restricciones, se permiten listas como valores de variables. Una restricción element(I, L, X)se cumple si Les una lista y Xes el I-ésimo elemento de esta lista. Existen reglas de propagación de restricciones especializadas para estas restricciones. Por ejemplo, si Ly Ise reducen a un dominio de valor único, Xse puede determinar un valor único para. De manera más general, Xse pueden inferir valores imposibles de del dominio de y viceversa. ${\displaystyle I}$

Consistencia direccional

La consistencia direccional es la variante de arco, ruta y consistencia diseñada para ser utilizada por un algoritmo que asigna valores a variables siguiendo un orden determinado de variables. Son similares a sus contrapartes no direccionales, pero solo requieren que una asignación consistente a algunas variables pueda extenderse consistentemente a otra variable que sea mayor que ellas según el orden. ${\displaystyle i}$

Consistencia de trayectoria y arco direccional

Una instancia que es direccionalmente consistente en arco según el orden x1 x2 x3 pero no consistente en arco (no hay ninguna restricción entre x1 y x3; se omiten los bordes correspondientes). Cada valor de una variable de índice más bajo corresponde a valores de variables de índice más alto. Los signos de interrogación indican puntos en los que lo contrario no se cumple.

Si un algoritmo evalúa las variables en el orden , la coherencia solo es útil cuando garantiza que los valores de las variables de índice más bajo sean todos consistentes con los valores de las de índice más alto. ${\displaystyle x_{1},\ldots ,x_{n}}$

Al elegir un valor para una variable, se pueden ignorar los valores que sean inconsistentes con todos los valores de una variable no asignada. De hecho, incluso si todos estos valores son consistentes con la evaluación parcial actual, el algoritmo luego no podrá encontrar un valor consistente para la variable no asignada. Por otro lado, no es necesario imponer coherencia con variables que ya están evaluadas: si el algoritmo elige un valor que es inconsistente con la evaluación parcial actual, la inconsistencia se detecta de todos modos.

Suponiendo que el orden de evaluación de las variables es , un problema de satisfacción de restricciones es direccionalmente consistente si cada variable es consistente con cualquier otra variable tal que . La consistencia de la ruta direccional es similar, pero dos variables deben ser consistentes con la ruta solo si . Una fuerte consistencia de trayectoria direccional significa tanto consistencia de trayectoria direccional como consistencia de arco direccional. Se pueden dar definiciones similares para las otras formas de coherencia. ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle i<j}$ ${\displaystyle x_{i},x_{j}}$ ${\displaystyle x_{z}}$ ${\displaystyle i,j<z}$

Propagación de restricciones para la coherencia del arco y la ruta.

La propagación de restricciones que impone la coherencia del arco direccional itera sobre las variables desde la última a la primera, imponiendo en cada paso la coherencia del arco de cada variable de índice más bajo. Si el orden de las variables es , este algoritmo itera sobre las variables desde hasta ; para la variable , impone la coherencia del arco de cada variable de índice inferior al de . ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle x_{n}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{j}}$ ${\displaystyle j}$ ${\displaystyle x_{j}}$

La coherencia de la ruta direccional y una fuerte coherencia de la ruta direccional se pueden imponer mediante algoritmos similares al de la coherencia del arco. Procesan variables desde hasta ; para cada variable se consideran dos variables y se aplica la coherencia de la ruta de ellas . No se requiere ninguna operación si el problema no contiene ninguna restricción sobre o entre y . Sin embargo, incluso si no hay ninguna restricción entre y , se supone que es trivial. Si la propagación de restricciones reduce su conjunto de asignaciones satisfactorias, efectivamente crea una nueva restricción no trivial. La propagación de restricciones que impone una fuerte coherencia de ruta direccional es similar, pero también exige coherencia de arco. ${\displaystyle x_{n}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{z}}$ ${\displaystyle x_{i},x_{j}}$ ${\displaystyle i,j<z}$ ${\displaystyle x_{z}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{z}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{z}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$

Consistencia direccional y satisfacibilidad.

La consistencia direccional garantiza que las soluciones parciales que satisfacen una restricción puedan extenderse consistentemente a otra variable de índice más alto. Sin embargo, no garantiza que las extensiones a diferentes variables sean consistentes entre sí. Por ejemplo, una solución parcial puede extenderse consistentemente a variable o a variable , pero aún así estas dos extensiones no son consistentes entre sí. ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$

Hay dos casos en los que esto no sucede, y la consistencia direccional garantiza la satisfacibilidad si ningún dominio está vacío y ninguna restricción es insatisfactoria.

El primer caso es el de un problema de restricciones binarias con un orden de las variables que hace que el gráfico ordenado de la restricción tenga un ancho de 1. Tal ordenamiento existe si y sólo si el gráfico de restricciones es un árbol. Si este es el caso, el ancho del gráfico limita el número máximo de nodos inferiores (según el orden) a los que se une un nodo. La consistencia del arco direccional garantiza que cada asignación consistente a una variable se pueda extender a nodos superiores, y el ancho 1 garantiza que un nodo no esté unido a más de un nodo inferior. Como resultado, una vez asignada la variable inferior, su valor se puede extender consistentemente a cada variable superior a la que se una. Esta ampliación no puede dar lugar posteriormente a incoherencias. De hecho, ninguna otra variable inferior está unida a esa variable superior, ya que el gráfico tiene ancho 1.

Como resultado, si un problema de restricciones tiene ancho 1 con respecto al orden de sus variables (lo que implica que su gráfico correspondiente es un árbol) y el problema es direccionalmente consistente con respecto al mismo orden, una solución (si la hay) se puede encontrar asignando variables iterativamente según el orden.

El segundo caso en el que la consistencia direccional garantiza la satisfacibilidad si ningún dominio está vacío y ninguna restricción es insatisfactoria es el de los problemas de restricciones binarias cuyo gráfico ha inducido un ancho 2, utilizando una fuerte consistencia de ruta direccional. De hecho, esta forma de coherencia garantiza que cada asignación a una variable o un par de variables se pueda extender a una variable superior, y el ancho 2 garantiza que esta variable no se una a otro par de variables inferiores.

La razón por la que se considera el ancho inducido en lugar del ancho es que hacer cumplir la coherencia de la ruta direccional puede agregar restricciones. De hecho, si dos variables no están en la misma restricción pero sí en una restricción con una variable más alta, algunos pares de sus valores pueden violar la coherencia de trayectoria. Eliminar esos pares crea una nueva restricción. Como resultado, la propagación de restricciones puede producir un problema cuyo gráfico tenga más aristas que el original. Sin embargo, todos estos bordes están necesariamente en el gráfico inducido, ya que todos están entre dos padres del mismo nodo. El ancho 2 garantiza que cada evaluación parcial consistente se pueda extender a una solución, pero este ancho es relativo al gráfico generado. Como resultado, se requiere un ancho inducido de 2 para una fuerte consistencia de la ruta direccional para garantizar la existencia de soluciones.

I-consistencia direccional

Las líneas azules indican que no hay restricción entre x3 y x4, por lo que se permiten todos los pares de valores. En estas imágenes, la falta de aristas entre dos variables indica implícitamente la falta de una restricción. Este problema tiene ancho 2.

La consistencia direccional es la garantía de que cada asignación consistente a variables se pueda extender consistentemente a otra variable que esté más arriba en el orden. La consistencia direccional fuerte se define de manera similar, pero se consideran todos los grupos de como máximo variables. Si un problema es fuertemente consistente direccionalmente y tiene un ancho menor y no tiene dominio vacío o restricción insatisfactoria, tiene soluciones. ${\displaystyle i}$ ${\displaystyle i-1}$ ${\displaystyle i}$ ${\displaystyle i-1}$ ${\displaystyle i}$ ${\displaystyle i}$

Cada problema puede hacerse fuertemente consistente direccionalmente, pero esta operación puede aumentar el ancho de sus gráficos correspondientes. El procedimiento de propagación de restricciones que impone la coherencia direccional es similar al utilizado para la coherencia del arco direccional y la coherencia de la ruta. Las variables se consideran por turno, de la última a la primera según el orden. Para la variable , el algoritmo considera cada grupo de variables que tienen un índice inferior y están en una restricción con . La coherencia de estas variables se verifica y posiblemente se aplica eliminando asignaciones satisfactorias de la restricción entre todas estas variables (si las hay, o creando una nueva en caso contrario). ${\displaystyle i}$ ${\displaystyle x_{k}}$ ${\displaystyle i-1}$ ${\displaystyle k}$ ${\displaystyle x_{k}}$ ${\displaystyle x_{k}}$ ${\displaystyle i}$

Hacer cumplir la coherencia en x5 elimina la línea roja, creando así una nueva restricción no trivial entre x3 y x4. Como resultado, x4 tiene a x3 como nuevo padre, además de x1 y x2. Este cambio aumenta el ancho a 3.

Este procedimiento genera una instancia fuertemente coherente con la dirección. Sin embargo, también puede agregar nuevas restricciones a la instancia. Como resultado, incluso si el ancho del problema original es , el ancho de la instancia resultante puede ser mayor. Si este es el caso, la consistencia fuerte direccional no implica satisfacibilidad incluso si ningún dominio está vacío y ninguna restricción es insatisfacible. ${\displaystyle i}$ ${\displaystyle i}$

Sin embargo, la propagación de restricciones solo agrega restricciones a variables que son más bajas que la que se está considerando actualmente. Como resultado, no se modifica ni agrega ninguna restricción sobre una variable una vez que el algoritmo ha tratado con esta variable. En lugar de considerar un fijo , se puede modificar al número de padres de cada variable considerada (los padres de una variable son las variables de índice menor que la variable y que están en restricción con la variable). Esto corresponde a considerar todos los padres de una determinada variable en cada paso. En otras palabras, para cada variable desde la última hasta la primera, todos sus padres están incluidos en una nueva restricción que limita sus valores a los que son consistentes con . Dado que este algoritmo puede verse como una modificación del anterior con un valor que se cambia al número de padres de cada nodo, se le llama consistencia adaptativa . ${\displaystyle i}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle i}$

Este algoritmo impone una fuerte coherencia direccional igual a la amplitud inducida del problema. La instancia resultante es satisfactoria si y sólo si ningún dominio o restricción queda vacío. Si este es el caso, se puede encontrar fácilmente una solución estableciendo iterativamente una variable no asignada en un valor arbitrario y propagando esta evaluación parcial a otras variables. Este algoritmo no siempre es de tiempo polinómico, ya que el número de restricciones introducidas al imponer una fuerte coherencia direccional puede producir un aumento exponencial de tamaño. Sin embargo, el problema se puede resolver en tiempo polinómico si la fuerte coherencia direccional que se aplica no amplía superpolinomialmente la instancia. Como resultado, si una instancia tiene un ancho inducido limitado por una constante, se puede resolver en tiempo polinomial. ${\displaystyle i}$ ${\displaystyle i}$

Eliminación de cubos

La eliminación del depósito es un algoritmo de satisfacibilidad. Puede definirse como una reformulación de la consistencia adaptativa. Sus definiciones utilizan depósitos, que son contenedores de restricciones y cada variable tiene un depósito asociado. Una restricción siempre pertenece al segmento de su variable más alta.

El algoritmo de eliminación de cubos procede sucesivamente de la variable más alta a la más baja. En cada paso, se consideran las restricciones en los depósitos de esta variable . Por definición, estas restricciones solo involucran variables inferiores a . El algoritmo modifica la restricción entre estas variables inferiores (si las hay; de lo contrario, crea una nueva). En particular, exige que sus valores sean extensibles de manera consistente con las restricciones en el grupo de . Esta nueva restricción, si la hay, se coloca en el depósito correspondiente. Dado que esta restricción solo involucra variables que son inferiores a , se agrega a un grupo de una variable que es inferior a . ${\displaystyle x_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}}$

Este algoritmo equivale a imponer coherencia adaptativa. Dado que ambos imponen la coherencia de una variable con todos sus padres, y dado que no se agrega ninguna restricción nueva después de considerar una variable, el resultado es una instancia que se puede resolver sin retroceder .

Dado que el gráfico de la instancia que producen es un subgrafo del gráfico inducido, si el ancho inducido está limitado por una constante, la instancia generada es de tamaño polinómico en el tamaño de la instancia original. Como resultado, si el ancho inducido de una instancia está limitado por una constante, los dos algoritmos pueden resolverlo en tiempo polinómico.

Consistencia relacional

Si bien las definiciones anteriores de coherencia tienen que ver con la coherencia de las asignaciones, la coherencia relacional implica la satisfacción de una restricción determinada o de un conjunto de restricciones únicamente. Más precisamente, la consistencia relacional implica que cada asignación parcial consistente puede extenderse de tal manera que se satisfaga una restricción o un conjunto de restricciones dado. Formalmente, una restricción sobre variables es consistente con una de sus variables si se satisface toda asignación consistente a que pueda extenderse de tal manera . La diferencia entre la consistencia "regular" y la consistencia del arco relacional es que esta última sólo requiere que la asignación extendida satisfaga una restricción determinada, mientras que la primera requiere que satisfaga todas las restricciones relevantes. ${\displaystyle C}$ ${\displaystyle X}$ ${\displaystyle x}$ ${\displaystyle X\backslash \{x\}}$ ${\displaystyle x}$ ${\displaystyle C}$ ${\displaystyle i}$

I-consistencia (regular): si una evaluación es consistente, se puede extender a otra variable de tal manera que se cumplan todas las restricciones relevantes.

Consistencia del arco relacional: si una evaluación de las variables de una restricción es consistente, siempre se puede extender a esa variable de tal manera que se cumpla la restricción . Los bordes cian representan restricciones que la extensión no debe satisfacer.

Esta definición se puede extender a más de una restricción y más de una variable. En particular, la coherencia de la ruta relacional es similar a la coherencia del arco relacional, pero se utilizan dos restricciones en lugar de una. Dos restricciones son una ruta relacional consistente con una variable si cada asignación consistente a todas sus variables, excepto la considerada, puede extenderse de tal manera que se satisfagan las dos restricciones.

Para más de dos restricciones, se define la coherencia relacional. La coherencia relacional implica un conjunto de restricciones y una variable que está dentro del alcance de todas estas restricciones. En particular, estas restricciones son relacionales: consistentes con la variable si cada asignación consistente a todas las demás variables que están en su alcance se puede extender a la variable de tal manera que se satisfagan estas restricciones. Un problema es relacionalmente consistente si cada conjunto de restricciones es relacionalmente consistente con cada variable que se encuentra en todos sus alcances. La consistencia relacional fuerte se define como anteriormente: es la propiedad de ser consistente relacional para todos . ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle k<m}$

La coherencia relacional también se puede definir para más variables, en lugar de una. Un conjunto de restricciones es relacional consistente si cada asignación consistente a un subconjunto de sus variables se puede extender a una evaluación de todas las variables que satisfaga todas las restricciones. Esta definición no extiende exactamente lo anterior porque las variables a las que se supone que las evaluaciones son extensibles no están necesariamente en todos los ámbitos de las restricciones involucradas. ${\displaystyle m}$ ${\displaystyle (i,m)}$ ${\displaystyle i}$

Si se da un orden de las variables, la coherencia relacional puede restringirse a los casos en los que la(s) variable(s) de la evaluación deben ser extensibles para seguir a las otras variables en el orden. Esta condición modificada se llama consistencia relacional direccional.

Consistencia relacional y satisfacibilidad

Un problema de satisfacción de restricciones puede ser relacionalmente consistente, no tener un dominio vacío o una restricción insatisfactoria y, aun así, ser insatisfactorio. Sin embargo, hay algunos casos en los que esto no es posible.

El primer caso es el de un problema fuertemente relacional y consistente cuando los dominios contienen como máximo elementos. En este caso, una evaluación consistente de variables siempre se puede extender a una sola variable más. Si existe tal evaluación y es la variable, solo hay valores posibles que la variable puede tomar. Si todos esos valores son inconsistentes con la evaluación, existen restricciones (no necesariamente únicas) que son violadas por la evaluación y uno de sus posibles valores. Como resultado, la evaluación no puede extenderse para satisfacer todas estas restricciones -o menos-, violando la condición de fuerte consistencia relacional. ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$ ${\displaystyle x_{k+1}}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$

El segundo caso está relacionado con una medida de las restricciones, más que con los dominios. Una restricción es estricta si cada evaluación de todas sus variables excepto una puede extenderse para satisfacer la restricción ya sea con todos los valores posibles de la otra variable o con la mayoría de sus valores. Los problemas que tienen restricciones estrictas son satisfacibles si y sólo si son fuertemente consistentes relacionalmente. ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m+1}$

Una matriz convexa de filas: los 1 en cada fila son contiguos (no hay 0 entre ellos).

El tercer caso es el de las restricciones binarias que pueden representarse mediante matrices convexas por filas. Una restricción binaria se puede representar mediante una matriz bidimensional , donde es 0 o 1 dependiendo de si el -ésimo valor del dominio de y el -ésimo valor del dominio de satisfacen la restricción. Una fila de esta matriz es convexa si los unos que contiene son consecutivos (formalmente, si dos elementos son 1, todos los elementos intermedios también son 1). Una matriz es convexa por filas si todas sus filas son convexas. ${\displaystyle M}$ ${\displaystyle M_{ij}}$ ${\displaystyle i}$ ${\displaystyle x_{i}}$ ${\displaystyle j}$ ${\displaystyle x_{j}}$

Cada matriz representa la restricción entre x _i y x _{k +1} . Si a ₁ ... a _k son valores para x ₁ ... x _k , las filas de a ₁ ... a _k en cada matriz indican los valores permitidos para x _{k +1} . La convexidad de las filas y la fuerte coherencia de la ruta relacional implican la existencia de un valor consistente a _{k +1} para x _{k +1} .

La condición que hace que una fuerte consistencia de caminos relacionales sea equivalente a la satisfacibilidad es la de los problemas de satisfacción de restricciones para los cuales existe un orden de las variables que hace que todas las restricciones se representen mediante matrices convexas por filas. Este resultado se basa en el hecho de que un conjunto de filas convexas que tienen un elemento común por pares también tienen un elemento globalmente común. Considerando una evaluación sobre variables, los valores permitidos para la -ésima se dan seleccionando algunas filas de algunas restricciones. En particular, para cada variable entre unas, la fila relativa a su valor en la matriz que representa la restricción que la relaciona con una representa los valores permitidos de esta última. Dado que estas filas son convexas y tienen un elemento común por pares debido a la coherencia de la ruta, también tienen un elemento común compartido, que representa un valor de la última variable que es consistente con las demás. ${\displaystyle k}$ ${\displaystyle k+1}$ ${\displaystyle k}$ ${\displaystyle k+1}$

Usos de la consistencia local

Todas las formas de coherencia local pueden imponerse mediante la propagación de restricciones, que puede reducir los dominios de las variables y los conjuntos de asignaciones que satisfacen una restricción y puede introducir nuevas restricciones. Siempre que la propagación de restricciones produce un dominio vacío o una restricción insatisfactoria, el problema original es insatisfactorio. Por lo tanto, todas las formas de consistencia local pueden usarse como aproximaciones de satisfacibilidad. Más precisamente, pueden usarse como algoritmos de insatisfacibilidad incompletos, ya que pueden probar que un problema es insatisfactorio, pero en general no pueden probar que un problema es satisfacible. Estos algoritmos aproximados pueden ser utilizados por algoritmos de búsqueda ( retroceso , salto hacia atrás , búsqueda local , etc.) como heurística para determinar si una solución parcial se puede extender para satisfacer todas las restricciones sin analizarla más.

Incluso si la propagación de restricciones no produce un dominio vacío o una restricción insatisfactoria, puede reducir los dominios o fortalecer las restricciones. Si este es el caso, el espacio de búsqueda del problema se reduce, reduciendo así la cantidad de búsqueda necesaria para resolver el problema.

La coherencia local demuestra la satisfacibilidad en algunos casos restringidos (consulte Complejidad de la satisfacción de restricciones#Restricciones ). Éste es el caso de algún tipo especial de problemas y/o de algunos tipos de coherencia local. Por ejemplo, hacer cumplir la coherencia del arco en problemas binarios acíclicos permite saber si el problema es satisfactoria. Hacer cumplir una fuerte consistencia direccional permite determinar la satisfacibilidad de problemas que han inducido ancho de acuerdo con el mismo orden. La consistencia direccional adaptativa permite determinar la satisfacibilidad de un problema arbitrario. ${\displaystyle i}$ ${\displaystyle i-1}$

Ver también

• Propagación unitaria
• Programación de restricciones
• Programación lógica de restricciones
• Mirar hacia adelante (retroceder)

enlaces externos

• Propagación de restricciones: disertación de Guido Tack que ofrece un buen estudio de la teoría y las cuestiones de implementación.

Referencias

1. Régin, Jean-Charles (julio de 1994). "Un algoritmo de filtrado para restricciones de diferencia en CSP" (PDF) . Actas de la Conferencia AAAI . Consultado el 16 de diciembre de 2022 .

• Lecoutre, Christophe (2009). Redes de restricciones: técnicas y algoritmos. ISTE/Wiley. ISBN  978-1-84821-106-3
• Dechter, Rina (2003). Procesamiento de restricciones. Morgan Kaufman. ISBN  1-55860-890-7
• Apto, Krzysztof (2003). Principios de programación de restricciones . Prensa de la Universidad de Cambridge. ISBN  0-521-82583-0
• Marriott, Kim; Peter J. Stuckey (1998). Programación con restricciones: una introducción . Prensa del MIT. ISBN  0-262-13341-5