En la 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 del nodo , la coherencia del arco y la coherencia de la ruta .
Cada condición de coherencia local se puede imponer mediante una transformación que cambie el problema sin cambiar sus soluciones. Esta transformación se denomina propagación de restricciones . La propagación de restricciones funciona reduciendo dominios de variables, fortaleciendo restricciones o creando nuevas. Esto conduce a una reducción del espacio de búsqueda, lo que facilita la resolución del problema mediante algunos algoritmos. La propagación de restricciones también se puede utilizar como un verificador de insatisfacción, incompleta en general pero completa en algunos casos particulares.
Las condiciones de coherencia local se pueden agrupar en varias clases. Las condiciones de coherencia local originales requieren que cada asignación coherente se pueda extender de forma coherente a otra variable. La consistencia direccional solo requiere que se cumpla esta condición cuando la otra variable es más alta que las de la asignación, según un orden determinado. La consistencia relacional incluye extensiones a más de una variable, pero esta extensión solo es necesaria para satisfacer una restricción determinada o un conjunto de restricciones.
Supuestos
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 su 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 en forma 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 solo para restricciones binarias conduce a la forma estandarizada . Estas condiciones siempre se pueden hacer cumplir combinando todas las restricciones sobre una secuencia de variables en una sola y / o agregando una restricción que se satisfaga con todos los valores de una secuencia de variables.
En las cifras utilizadas en este artículo, la falta de vínculos entre dos variables indica que entre estas dos variables no existe una restricción o una restricción satisfecha por todos los valores. [ aclaración necesaria ]
Consistencia local
Todas las condiciones de consistencia local "estándar" requieren que todas las evaluaciones parciales consistentes se puedan extender a otra variable de tal manera que la asignación resultante sea consistente. Una evaluación parcial es coherente si satisface todas las restricciones cuyo alcance es un subconjunto de las variables asignadas. [ aclaración necesaria ]
Consistencia de nodo
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 se puede hacer cumplir trivialmente reduciendo el dominio de cada variable a los valores que satisfacen todas las restricciones unarias sobre esa variable. Como resultado, las restricciones unarias pueden descuidarse y asumirse incorporadas en 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.
Consistencia del arco
Una variable de un problema de satisfacción de restricciones es coherente con otra si cada uno de sus valores admisibles es coherente con algún valor admisible de la segunda variable. Formalmente, una variable es coherente con otra variable si, por 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 coherente con el arco si todas las variables son coherentes con todas las demás.
Por ejemplo, considere la restricción donde las variables oscilan en el dominio de 1 a 3. Porque nunca puede ser 3, no hay arco de 3 a un valor en por lo que es seguro quitarlo. Igualmente, nunca puede ser 1, por lo que no hay arco, por lo tanto, se puede eliminar.
La consistencia del arco también se puede definir en relación con una restricción binaria específica: una restricción binaria es coherente con el arco si cada valor de una variable tiene un valor de la segunda variable de modo que satisfaga la restricción. Esta definición de consistencia de arco es similar a la anterior, pero se da específicamente a 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 esta considera solo una específica.
Si una variable no es coherente con otra, se puede hacer quitando algunos valores de su dominio. Esta es la forma de propagación de restricciones que refuerza la coherencia del arco: elimina, del dominio de la variable, todo valor que no corresponda 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. Este proceso puede tener que considerar un par de variables dado 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 es arco consistente con pero el algoritmo reduce el dominio de , consistencia de arco de con ya no se mantiene y debe hacerse cumplir nuevamente.
Un algoritmo simplista recorrería los pares de variables, imponiendo la coherencia del arco, repitiendo el ciclo hasta que ningún dominio cambie durante todo un ciclo. 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, trabaja sobre un conjunto de restricciones que inicialmente las contiene todas; en cada paso, toma una restricción y refuerza la coherencia del arco; si esta operación puede haber producido una violación de la coherencia del arco sobre otra restricción, la coloca nuevamente en el conjunto de restricciones para analizar. De esta manera, una vez que se aplica la coherencia del arco en una restricción, esta restricción no se vuelve a considerar a menos que se cambie el dominio de una de sus variables.
Consistencia de ruta
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 coherente con la ruta de una tercera variable si cada evaluación coherente del par puede extenderse a la otra variable de tal manera que se satisfagan todas las restricciones binarias . Formalmente, y son la ruta consistente con si, por cada par de valores que satisface la restricción binaria entre y , existe un valor en el dominio de tal que y satisfacer la restricción entre y y entre y , respectivamente.
La forma de propagación de restricciones que refuerza la coherencia de la ruta funciona eliminando algunas asignaciones satisfactorias de una restricción. De hecho, la consistencia de la ruta se puede hacer cumplir eliminando de una restricción binaria todas las evaluaciones que no se pueden extender a otra variable. En cuanto a la coherencia del arco, esta eliminación podría tener que 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.
La forma de propagación de restricciones que refuerza 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, algunos pares de valores pueden eliminarse 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 a todo el problema.
Generalizaciones
La consistencia 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 -consistente con otra variable si cada evaluación consistente de la las variables se pueden ampliar con un valor de la otra variable conservando la coherencia. Esta definición se extiende a problemas completos de forma obvia. Fuerte-la coherencia es -consistencia para todos .
El caso particular de coherencia 2 coincide con la coherencia del arco (en este artículo se asume que todos los problemas son coherentes con los nodos). Por otro lado, la consistencia 3 coincide con la consistencia de la ruta solo si todas las restricciones son binarias, porque la consistencia de la ruta no implica restricciones ternarias, mientras que la consistencia 3 sí.
Otra forma de generalizar la consistencia del arco es la consistencia del hiper-arco 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 puede extenderse a las otras variables de la restricción de tal manera que se satisfaga la restricción.
Consistencia y satisfacibilidad
La propagación de restricciones (imponer una forma de coherencia local) puede 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 coherente con el arco o coherente con la trayectoria 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 coherencia del arco garantiza que cada evaluación coherente de una variable se pueda extender de forma coherente a otra variable. Sin embargo, cuando un solo 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 coherentes entre sí.
Sin embargo, la propagación de restricciones se puede utilizar para demostrar la satisfacibilidad en algunos casos. Un conjunto de restricciones binarias que es coherente con el arco y no tiene un dominio vacío puede ser inconsistente solo 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 es válida para la coherencia de la ruta. Los casos especiales en los que se puede establecer la satisfacibilidad imponiendo la coherencia del arco y la coherencia de la ruta son los siguientes.
- hacer cumplir la coherencia del arco establece la capacidad de satisfacción de problemas hechos de restricciones binarias sin ciclos (un árbol de restricciones binarias);
- hacer cumplir la coherencia de la ruta establece la capacidad de satisfacer las restricciones binarias (posiblemente con ciclos) con dominios binarios;
- hacer cumplir fuerte La coherencia establece la satisfacibilidad de los problemas que contienen variables.
Casos especiales
Algunas definiciones o resultados sobre la coherencia relativa son válidos solo en casos especiales.
Cuando los dominios están compuestos por números enteros , se puede definir la consistencia ligada. Esta forma de consistencia se basa en la consistencia de los valores extremos de los dominios, es decir, los valores mínimos y máximos que puede tomar una variable.
Cuando las restricciones son algebraicas o booleanas , la coherencia del arco es equivalente a agregar una nueva restricción o modificar sintácticamente una anterior, y esto se puede hacer componiendo restricciones de manera adecuada.
Restricciones especializadas
Algunos tipos de restricciones se utilizan comúnmente. Por ejemplo, a menudo se utiliza la restricción de que algunas variables son todas diferentes. Existen algoritmos especializados eficientes para hacer cumplir la coherencia del arco en tales restricciones.
La restricción que obliga a un número de variables a ser diferentes generalmente se escribe o alldifferent([X1,...,Xn])
. Esta restricción es equivalente 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 solo valor, este valor puede eliminarse 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 son válidas para las desigualdades binarias individuales .
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, después de 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, la restricción no se puede satisfacer. Esta condición se puede verificar fácilmente en una restricción en el alldifferent
formulario, pero no corresponde a la coherencia del arco de la red de desigualdades. Una segunda propiedad de la alldifferent
restricción simple es que la consistencia del hiperarco se puede verificar de manera eficiente utilizando un algoritmo de coincidencia bipartito . En particular, se construye un gráfico con variables y valores como los dos conjuntos de nodos, y se ejecuta un algoritmo especializado de coincidencia de gráficos bipartitos para verificar la existencia de dicha coincidencia.
Un tipo diferente de restricción que se usa comúnmente es el cumulative
. Se introdujo por problemas de programación y ubicación. A modo de ejemplo, cumulative([S1,...,Sm], [D1,...,Dm], [R1,...,Rm], L)
se puede utilizar para formalizar la condición en la que se encuentran las m
actividades, cada una con hora de inicio si
, duración di
y uso de una cantidad ri
de un recurso. La restricción establece que la cantidad total disponible de recursos es L
. Existen técnicas especializadas de propagación de restricciones para restricciones acumulativas; Se utilizan diferentes técnicas dependiendo de qué dominios de variables ya estén reducidos a un solo valor.
Una tercera restricción especializada que se utiliza en la programación lógica de restricciones es la element
única. En la programación de lógica de restricción, se permiten listas como valores de variables. Una restricción element(I, L, X)
se satisface si L
es una lista y X
es el I
-ésimo elemento de esta lista. Existen reglas de propagación de restricciones especializadas para estas restricciones. Por ejemplo, si L
y I
se reducen a un dominio de valor único, X
se puede determinar un valor único para . De manera más general, los valores imposibles de X
pueden inferirse del dominio de y viceversa.
Consistencia direccional
La consistencia direccional es la variante de arco, trayectoria y -consistencia adaptada para ser utilizada por un algoritmo que asigna valores a las variables siguiendo un orden dado 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.
Consistencia de trayectoria y arco direccional
Si un algoritmo evalúa variables en el orden , la consistencia solo es útil cuando garantiza que los valores de las variables de índice más bajo sean consistentes con los valores de las de índice más alto.
Al elegir un valor para una variable, se pueden ignorar los valores que son inconsistentes con todos los valores de una variable no asignada. De hecho, incluso si estos valores son todos coherentes con la evaluación parcial actual, el algoritmo no podrá encontrar un valor coherente para la variable no asignada más adelante. Por otro lado, no es necesario hacer cumplir la coherencia con las 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 coherente si cada variable es arco consistente con cualquier otra variable tal que . La consistencia de la ruta direccional es similar, pero dos variables tiene que ser coherente con el camino sólo si . La fuerte consistencia de la ruta direccional significa tanto la consistencia de la ruta direccional como la consistencia del arco direccional. Se pueden dar definiciones similares para las otras formas de coherencia.
Propagación de restricciones para la coherencia del arco y la trayectoria
La propagación de restricciones que impone la consistencia del arco direccional itera sobre las variables desde la última hasta la primera, imponiendo en cada paso la consistencia del arco de cada variable de índice más bajo con ella. Si el orden de las variables es, este algoritmo itera sobre variables de a ; para variable, refuerza la coherencia del arco de cada variable de índice inferior a con .
Una instancia que no es coherente con el arco direccional: no corresponde a ningún valor de y no corresponde a ningún valor de . No hay ninguna restricción entre y (se omiten los bordes correspondientes). | La aplicación de la coherencia del arco direccional comienza con , y hace arco consistente con ella quitando el valor . | La aplicación de la coherencia del arco direccional procede con . Desde ya ha sido eliminado, ambos y son removidos. |
La coherencia de la trayectoria direccional y la coherencia de la trayectoria direccional fuerte se pueden aplicar mediante algoritmos similares al de la coherencia del arco. Procesan variables de a ; para cada variable dos variables con son considerados, y la consistencia de la ruta de ellos con se hace cumplir. No se requiere ninguna operación si el problema no contiene ninguna restricción en y o sin restricción entre y . Sin embargo, incluso si no hay ninguna restricción entre y , se asume una trivial. Si la propagación de restricciones reduce su conjunto de asignaciones satisfactorias, crea efectivamente una nueva restricción no trivial. La propagación de restricciones que impone una fuerte consistencia de la ruta direccional es similar, pero también refuerza la consistencia del arco.
Consistencia direccional y satisfacibilidad
La consistencia direccional garantiza que las soluciones parciales que satisfacen una restricción se puedan extender de manera consistente a otra variable de índice más alto. Sin embargo, no garantiza que las extensiones a diferentes variables sean coherentes entre sí. Por ejemplo, una solución parcial puede extenderse consistentemente a variables o a variable , pero sin embargo, estas dos extensiones no son coherentes entre sí.
Hay dos casos en los que esto no sucede, y la coherencia 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 restricción binaria con un orden de las variables que hace que el gráfico ordenado de restricción tenga ancho 1. Tal ordenación existe si y solo 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 coherencia del arco direccional garantiza que cada asignación coherente 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 que se asigna la variable más baja, su valor puede extenderse consistentemente a cada variable más alta con la que se une. Esta extensión no puede dar lugar posteriormente a una inconsistencia. De hecho, ninguna otra variable inferior se une a esa variable superior, ya que el gráfico tiene un ancho de 1.
Como resultado, si un problema de restricción tiene un ancho de 1 con respecto al orden de sus variables (lo que implica que su gráfico correspondiente es un árbol) y el problema es coherente con el arco direccional con respecto al mismo orden, una solución (si existe) 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 restricción binaria 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 unirá 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 consistencia 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 consistencia de la ruta. La eliminación de estos pares crea una nueva restricción. Como resultado, la propagación de restricciones puede producir un problema cuyo gráfico tenga más bordes 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. Ancho 2 garantiza que cada evaluación parcial consistente puede extenderse a una solución, pero este ancho es relativo al gráfico generado. Como resultado, se requiere que el ancho inducido sea 2 para una fuerte consistencia de la trayectoria direccional para garantizar la existencia de soluciones.
I-consistencia direccional
Direccional -La coherencia es la garantía de que toda asignación coherente a las variables pueden extenderse consistentemente a otra variable que sea más alta en el orden. Fuerte direccional-la consistencia se define de manera similar, pero todos los grupos de como máximo se consideran variables. Si un problema es fuertemente direccional-consistente y tiene un ancho menor que y no tiene un dominio vacío o una restricción insatisfactoria, tiene soluciones.
Cada problema se puede hacer fuertemente direccionalmente -consistente, 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 trayectoria. Las variables se consideran a su vez, de la última a la primera según el orden. Para variable, el algoritmo considera cada grupo de variables que tienen un índice menor que y están en una restricción con . La coherencia de estas variables con se comprueba y posiblemente se hace cumplir mediante la eliminación de asignaciones satisfactorias de la restricción entre todos estos variables (si las hay, o creando una nueva en caso contrario).
Este procedimiento genera un fuerte direccional -instancia consistente. 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, una fuerte consistencia direccional no implica satisfacibilidad incluso si ningún dominio está vacío y ninguna restricción es insatisfactoria.
Sin embargo, la propagación de restricciones solo agrega restricciones a las variables que son más bajas que la que está considerando actualmente. Como resultado, no se modifica ni se agrega ninguna restricción sobre una variable una vez que el algoritmo ha tratado 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 más bajas que la variable y que están en una restricción con la variable). Esto corresponde a considerar a todos los padres de una determinada variable en cada paso. En otras palabras, para cada variable desde el último al primero, 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 valorque se cambia al número de padres de cada nodo, se llama consistencia adaptativa .
Este algoritmo aplica fuertemente direccional -consistencia con igual al ancho inducido del problema. La instancia resultante es satisfactoria si y solo si no se deja vacío ningún dominio o restricción. Si este es el caso, se puede encontrar una solución fácilmente 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 polinomial si la fuerte consistencia direccional impuesta no agranda superpolinomialmente la instancia. Como resultado, si una instancia tiene un ancho inducido limitado por una constante, se puede resolver en tiempo polinomial.
Eliminación de cangilones
La eliminación de cubos es un algoritmo de satisfacción. Puede definirse como una reformulación de la coherencia adaptativa. Sus definiciones usan cubos, que son contenedores de restricción, cada variable tiene un cubo asociado. Una restricción siempre pertenece al grupo de su variable más alta.
El algoritmo de eliminación de cubos procede a su vez de la variable más alta a la más baja. En cada paso, las restricciones en los depósitos de esta variableson considerados. Por definición, estas restricciones solo involucran variables que son menores que. El algoritmo modifica la restricción entre estas variables inferiores (si las hay, de lo contrario crea una nueva). En particular, hace cumplir sus valores para que sean extensibles a consistentemente con las limitaciones en el cubo 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 menores que, se agrega a un depósito de una variable que es menor que .
Este algoritmo es equivalente a hacer cumplir la coherencia adaptativa. Dado que ambos imponen la coherencia de una variable con todos sus padres, y dado que no se agrega ninguna nueva restricción después de que se considera 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 subgráfico del gráfico inducido, si el ancho inducido está limitado por una constante, la instancia generada es de tamaño polinomial 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 un conjunto de restricciones únicamente. Más precisamente, la consistencia relacional implica que toda 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 en variables es arco relacional coherente con una de sus variables si cada asignación consistente a se puede extender a de tal manera Está satisfecho. La diferencia entre "regular" La consistencia y la consistencia del arco relacional es que la última solo requiere la asignación extendida para satisfacer una restricción dada, mientras que la primera requiere que satisfaga todas las restricciones relevantes.
Esta definición se puede extender a más de una restricción y más de una variable. En particular, la consistencia de la ruta relacional es similar a la consistencia 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, pero la considerada, puede extenderse de tal manera que se satisfagan las dos restricciones.
Para más de dos restricciones, relacional -Se define la coherencia. Relacional-la coherencia implica un conjunto de restricciones y una variable que está dentro del alcance de todas estas restricciones. En particular, estos las restricciones son relacionales -consistente con la variable si cada asignación consistente a todas las demás variables que están en sus alcances puede extenderse a la variable de tal manera que se satisfagan estas restricciones. Un problema es-relacional consistente si cada conjunto de las restricciones son relacionales -consistente con todas las variables que se encuentran en todos sus ámbitos. Fuerte relacional la consistencia se define como arriba: es la propiedad de ser relacional -consistente para cada .
La consistencia relacional también se puede definir para más variables, en lugar de una. Un conjunto de las restricciones son relacionales -consistente si cada asignación consistente a un subconjunto de de sus variables se puede extender a una evaluación a 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.
Si se da un orden de las variables, la consistencia relacional se puede restringir a los casos en los que la (s) variable (s) la evaluación debería ser ampliable 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, sin embargo, ser insatisfactorio. Sin embargo, hay algunos casos en los que esto no es posible.
El primer caso es el de las relaciones fuertemente relacionales. -Problema constante cuando los dominios contienen como máximo elementos. En este caso, una evaluación consistente delas variables siempre se pueden extender a una sola otra variable. Si es tal evaluación y es la variable, solo hay posibles valores que puede tomar la variable. Si todos esos valores son incompatibles con la evaluación, hayrestricciones (no necesariamente únicas) que son violadas por la evaluación y uno de sus posibles valores. Como resultado, la evaluación no se puede extender para satisfacer todas estas-o menos restricciones, violando la condición de fuerte relacional -consistencia.
El segundo caso está relacionado con una medida de las restricciones, más que con los dominios. Una restricción es-fuerte si cada evaluación a todas sus variables, pero una puede extenderse para satisfacer la restricción, ya sea por todos los valores posibles de la otra variable o por como máximo de sus valores. Problema de tener-Las restricciones estrictas son satisfactorias si y solo si están fuertemente relacionalmente -consistente.
El tercer caso es el de las restricciones binarias que se pueden representar mediante matrices convexas de fila. Una restricción binaria se puede representar mediante una matriz bidimensional, dónde es 0 o 1 dependiendo de si el -ésimo valor del dominio de y el -ésimo valor del dominio de satisfacer la restricción. Una fila de esta matriz es convexa si los 1 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.
La condición que hace que la consistencia de la trayectoria relacional fuerte 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 estén representadas por matrices convexas de filas. Este resultado se basa en el hecho de que un conjunto de filas convexas que tienen un elemento común por parejas también tienen un elemento común globalmente. Considerando una evaluación sobre variables, los valores permitidos para el -th uno se da seleccionando algunas filas de algunas restricciones. En particular, para cada variable entre los unos, la fila relativa a su valor en la matriz que representa la restricción que la relaciona con el uno representa los valores permitidos de este último. Dado que estas filas son convexas y tienen un elemento común por pares debido a la consistencia de la ruta, también tienen un elemento común compartido, que representa un valor de la última variable que es consistente con las otras.
Usos de la coherencia local
Todas las formas de coherencia local pueden imponerse mediante la propagación de restricciones, lo 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 insatisfactorio, el problema original es insatisfactorio. Por lo tanto, todas las formas de consistencia local pueden usarse como aproximaciones de satisfacibilidad. Más precisamente, se pueden usar como algoritmos de insatisfacción incompletos, ya que pueden probar que un problema es insatisfactorio, pero en general no pueden probar que un problema es satisfactorio. Tales algoritmos aproximados pueden ser utilizados por los algoritmos de búsqueda ( marcha atrás , backjumping , búsqueda local, etc.) como heurística para decir si una solución parcial se puede ampliar para satisfacer todas las restricciones sin más analizarla.
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 consistencia local demuestra la capacidad de satisfacción en algunos casos restringidos (consulte Complejidad de la satisfacción de restricciones # Restricciones ). Este es el caso de algunos tipos especiales de problemas y / o de algunos tipos de coherencia local. Por ejemplo, hacer cumplir la coherencia del arco en problemas acíclicos binarios permite saber si el problema es satisfactorio. Hacer cumplir fuerte direccional-La coherencia permite contar la satisfacibilidad de los problemas que han inducido el ancho. según el mismo orden. La coherencia direccional adaptativa permite determinar la satisfacibilidad de un problema arbitrario.
Ver también
enlaces externos
- Propagación de restricciones : disertación de Guido Tack que ofrece una buena revisión de la teoría y los problemas de implementación.
Referencias
- Lecoutre, Christophe (2009). Redes de restricción: técnicas y algoritmos . ISTE / Wiley.ISBN 978-1-84821-106-3
- Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann.ISBN 1-55860-890-7
- Apt, Krzysztof (2003). Principios de la 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