consistência local - Local consistency

Na satisfação de restrições , de consistência locais condições são propriedades do problema da satisfação de restrições relacionadas com a consistência de subconjuntos de variáveis ou restrições. Eles podem ser usados para reduzir o espaço de busca e tornar o problema mais fácil de resolver. Vários tipos de condições de consistência locais são aproveitados, incluindo a consistência de nó , a consistência de arco , e consistência caminho .

Cada condição de consistência local pode ser aplicada por uma transformação que muda o problema sem alterar suas soluções. Essa transformação é chamado de propagação de restrições . Propagação de restrições funciona através da redução domínios das variáveis, fortalecendo as restrições, ou criar novos. Isto leva a uma redução do espaço de busca, tornando o problema mais fácil de resolver por alguns algoritmos. Propagação restrição também pode ser utilizado como um verificador unsatisfiability, incompleta, mas, em geral, completa, em alguns casos particulares.

Condições de consistência locais podem ser agrupados em diferentes classes. As condições de consistência locais originais exigem que cada atribuição consistente pode ser consistentemente estendida para outra variável. Consistência direccional requer apenas esta condição a ser satisfeito quando a outra variável é mais elevada do que os da atribuição, de acordo com uma determinada ordem. Consistência relacional inclui extensões para mais do que uma variável, mas esta extensão é necessária apenas para satisfazer uma determinada restrição ou conjunto de restrições.

Suposições

Neste artigo, um problema de satisfação de restrições é definida como um conjunto de variáveis, um conjunto de domínios, e um conjunto de restrições. Variáveis e domínios estão associados: o domínio de uma variável contém todos os valores da variável pode tomar. Uma restrição é composta de uma sequência de variáveis, chamado o seu âmbito, e um conjunto de suas avaliações, que são as avaliações que satisfazem a restrição.

Os problemas de satisfação restrição referidos neste artigo estão a ser assumida de uma forma especial. Um problema está na forma normalizada , respectivamente ordem regular , se cada sequência de variáveis é o escopo no máximo uma restrição ou exatamente uma restrição. A suposição de regularidade feito apenas por restrições binárias leva à forma padronizada . Estas condições podem sempre ser executada através da combinação de todas as restrições de mais de uma sequência de variáveis em uma única e / ou adição de um constrangimento que é satisfeito por todos os valores de uma sequência de variáveis.

Nas figuras utilizadas neste artigo, a falta de ligações entre duas variáveis ​​indicam que quer sem restrição ou uma restrição satisfeito por todos os valores existe entre as duas variáveis.

consistência local

O "padrão" condições de consistência locais todos requerem que todas as avaliações parciais consistentes pode ser estendido para uma outra variável de tal maneira a atribuição resultante é consistente. Uma avaliação parcial é consistente desde que preencha todos os constrangimentos cujo âmbito é um subconjunto de variáveis ​​atribuídos.

consistência nó

consistência exige que cada nó restrição unária em uma variável é satisfeito por todos os valores no domínio da variável, e vice-versa. Esta condição pode ser trivialmente executadas reduzindo o domínio de cada variável para os valores que satisfazem todas as restrições no que unárias variável. Como resultado, as restrições unárias pode ser desprezada e assumiu incorporados nos domínios.

Por exemplo, dada uma variável com um domínio de e uma restrição , a consistência do nó iria restringir o domínio para o e a restrição pode então ser descartado. Este passo de pré-processamento simplifica fases posteriores.

consistência Arc

x2 é arco-consistente com x3 mas não com x1, como o valor x2 = 1 não corresponder a qualquer valor de x1.

Uma variável de um problema de satisfação de restrições é arco-consistente com outro, se cada um de seus valores admissíveis são consistentes com algum valor admissível da segunda variável. Formalmente, uma variável é de arco de acordo com uma outra variável se, para cada valor no domínio da existe um valor no domínio de tal modo que satisfaz a restrição entre binário e . Um problema é arco consistente se cada variável é arco consistente com todos os outros um.

Por exemplo, considere a restrição de onde as variáveis variam sobre o domínio 1 a 3. Porque nunca pode ser 3, não há arco de 3 a um valor em portanto é seguro para remover. Do mesmo modo, não pode ser 1, então não há nenhum arco, por conseguinte, ele pode ser removido.

Arco consistência também pode ser definida em relao a uma restrição binário específico: um constrangimento binário é consistente arco-se cada valor de uma variável tem um valor da segunda variável de tal modo que eles satisfazem a restrição. Esta definição de consistência de arco é semelhante ao anterior, mas é dado específico para uma restrição. Esta diferença é especialmente relevante para os problemas não normalizados, onde a definição acima consideraria todas as restrições entre duas variáveis ​​enquanto este considera apenas um específico.

consistência de arco executada por remoção de um como um valor de x2. Como resultado, já não é x3 arco-consistente com x2 x3 porque = 2 não corresponde a um valor de x2.

Se uma variável não é arco consistente com um outro, ele pode ser feito de modo removendo alguns valores de seu domínio. Esta é a forma de propagação restrição que impõe a consistência de arco: ele remove, do domínio da variável, cada valor que não corresponde a um valor da outra variável. Esta transformação mantém as soluções para os problemas, como os valores são removidos em qualquer solução de qualquer maneira.

Propagação de restrições pode fazer todo o problema arco consistente, repetindo esta remoção para todos os pares de variáveis. Este processo pode ter que considerar um determinado par de variáveis mais de uma vez. De fato, a remoção de valores a partir do domínio de uma variável pode causar outras variáveis para se tornar não arco coerente com ela. Por exemplo, se é consistente com arco , mas o algoritmo reduz o domínio , consistência arco de com não se sustenta por mais tempo, e tem que ser aplicada novamente.

Um algoritmo simplista seria ciclo longo dos pares de variáveis, impondo arco-consistência, repetindo o ciclo até que nenhum domínio mudar para um ciclo inteiro. O algoritmo AC-3 melhora ao longo deste algoritmo, ignorando restrições que não foram alteradas desde que foram última analisados. Em particular, ele funciona em um conjunto de restrições que inicialmente contém todas elas; em cada passo, leva-se um constrangimento e aplica-arco consistência; se esta operação pode ter produzido uma violação do arco-consistência ao longo do outro constrangimento, ele coloca-lo de volta no conjunto de restrições para analisar. Desta forma, uma vez arco-consistência é imposta em uma restrição, esta restrição não é considerada novamente a menos que o domínio de uma das suas variáveis é alterado.

consistência caminho

x1 e x2 não são caminho consistente com x3. Elas podem ser feitas caminho consistente, removendo os valores azuis do R12.

Consistência caminho é uma propriedade semelhante ao arco consistência, mas considera pares de variáveis em vez de apenas um. Um par de variáveis é caminho-de acordo com uma terceira variável, se cada uma avaliação consistente do par pode ser estendido para a outra variável, de tal maneira que todos os binários constrangimentos sejam satisfeitos. Formalmente, e são consistentes com o caminho se, para cada par de valores que satisfaça a restrição de binário entre e , existe um valor no domínio de tal modo que e satisfazer a restrição entre e e entre e , respectivamente.

A forma de propagação restrição que impõe a consistência caminho funciona através da remoção de algumas atribuição satisfatório a partir de um constrangimento. Na verdade, a consistência caminho pode ser executada através da remoção de uma restrição binário todas as avaliações que não podem ser estendidos a outra variável. Quanto à consistência de arco, esta remoção pode ter que considerar uma restrição binário mais de uma vez. Quanto à consistência de arco, o problema resultante tem as mesmas soluções do original, como os valores são removidos em qualquer solução.

Dois não variáveis ​​em uma restrição pode ser considerado relacionado por uma restrição virtuais, permitindo que qualquer par possível de valores, representado pelas arestas azuis nesta figura.
Impondo consistência caminho de x1 e x2 x3 com remove o bordo da parte superior. Os valores de X1 e X2 não são mais livres, mas relacionados por uma nova restrição real.

A forma de propagação de restrições que impõe a consistência caminho pode introduzir novas restrições. Quando duas variáveis ​​não estão relacionadas por uma restrição binário, eles são praticamente relacionados pela restrição permitindo que qualquer par de valores. No entanto, alguns par de valores pode ser removido por propagação de restrições. A restrição resultante não é satisfeita por todos os pares de valores. Portanto, ele não é mais um constrangimento virtual, trivial.

O nome "consistência caminho" deriva da definição original, que envolveu um par de variáveis ​​e um caminho entre eles, em vez de um par e uma única variável. Embora as duas definições são diferentes para um único par de variáveis, eles são equivalentes quando se refere a todo o problema.

generalizações

Arco ea consistência caminho pode ser generalizado a limitações não-binários usando tuplos de variáveis, em vez de um único ou de um par. Uma tupla de variáveis é -consistent com outra variável se cada avaliação consistente das variáveis pode ser estendido com um valor da outra variável, preservando a consistência. Esta definição se estende a problemas inteiros na maneira óbvia. Strong -Coerência é -Coerência para todos .

O caso particular de 2-consistência coincide com consistência de arco (todos os problemas são assumidos nó-consistente neste artigo). Por outro lado, 3-consistência coincide com consistência caminho somente se todas as restrições são binários, porque a consistência caminho não envolve restrições ternários, enquanto 3-consistência faz.

Outra forma de generalizar consistência de arco é consistência hiper-arco ou consistência de arco generalizada , o que exige capacidade de extensão de uma única variável, a fim de satisfazer uma restrição. Ou seja, uma variável é hiper-arc consistente com uma restrição se cada valor da variável pode ser estendido para as outras variáveis da restrição de tal forma a restrição é satisfeita.

Consistência e satisfiability

Este exemplo é arco consistente e não contém qualquer domínio vazio, mas não tem uma solução. As linhas azuis indicam atribuições forçadas pela escolha x1 = 1.

Propagação de restrições (execução de uma forma de consistência local) pode produzir um domínio vazio ou uma restrição de insatisfatível. Neste caso, o problema não tem solução. O inverso não é verdadeiro, em geral: um exemplo pode ser inconsistente arco consistente ou caminho consistente, não tendo qualquer domínio vazio ou restrição insatisfatível.

Na verdade, a consistência local é apenas relativa à consistência dos grupos de variáveis. Por exemplo, a consistência de arco garante que cada avaliação consistente de uma variável pode ser consistentemente estendida para outra variável. No entanto, quando um único valor de uma variável é estendido para duas outras variáveis, não há nenhuma garantia de que esses dois valores são consistentes entre si. Por exemplo, pode ser consistente com e com , mas essas duas avaliações podem não ser consistentes entre si.

No entanto, a propagação de restrições pode ser usado para provar satisfiability em alguns casos. Um conjunto de restrições binárias que é arco consistente e não possui domínio vazio pode ser inconsistente apenas se a rede de restrições contém ciclos. Na verdade, se as restrições são binários e formam um grafo acíclico, valores sempre pode ser propagada através restrições: para cada valor de uma variável, todas as variáveis ​​em uma restrição com que ela tem um valor que satisfaz essa restrição. Como resultado, uma solução pode ser encontrado de forma iterativa escolher uma variável não atribuída e de forma recursiva propagação através restrições. Este algoritmo nunca tenta atribuir um valor a uma variável que já está atribuído, como que implicaria a existência de ciclos na rede de restrições.

Uma condição semelhante é válido para a consistência caminho. Os casos especiais em que satisfiability podem ser estabelecidos através da aplicação de arco consistência e caminho consistência são as seguintes.

  1. reforçando a consistência de arco estabelece satisfiability de problemas feitos de restrições binárias sem ciclos (uma árvore de restrições binárias);
  2. aplicar coerência caminho estabelece satisfazibilidade por restrições binárias (possivelmente com ciclos) com domínios binários;
  3. aplicar forte consistência estabelece satisfazibilidade de problemas contendo variáveis.

Casos especiais

Algumas definições ou resultados sobre a consistência relativa detêm apenas em casos especiais.

Quando os domínios são compostos de números inteiros , a consistência ligado pode ser definido. Esta forma de consistência baseia-se na consistência dos valores extremos dos domínios, isto é, os valores mínimo e máximo uma variável pode tomar.

Quando constrangimentos são algébrica ou booleana , consistência de arco é equivalente a adicionar um novo constrangimento ou sintacticamente modificando um antigo, e este pode ser feito por constrangimentos adequadamente compõem.

restrições especializados

Alguns tipos de restrições são comumente usados. Por exemplo, a restrição de que algumas variáveis ​​são todos diferentes são usadas frequentemente. algoritmos especializados eficientes para reforçar a consistência de arco em tais restrições existem.

A restrição de execução de uma série de variáveis para ser diferente é geralmente escrito ou . Essa restrição é equivalente ao não-igualdade de todos os pares de variáveis diferentes, isto é, para cada . Quando o domínio de uma variável é reduzida para um único valor, este valor pode ser removido de todos os outros domínios de propagação de restrições aquando da execução consistência de arco. O uso da restrição especializado permite a exploração de propriedades que não sejam titulares de disequalities binários individuais. alldifferent([X1,...,Xn])

A primeira propriedade é que o número total de elementos nos domínios de todas as variáveis devem ser pelo menos o número de variáveis. Mais precisamente, depois de consistência de arco é aplicada, o número de variáveis não atribuídas não deve exceder o número de valores na união de seus domínios. Caso contrário, a restrição não pode ser satisfeita. Esta condição pode ser verificado facilmente em uma restrição na alldifferentforma, mas não corresponde ao arco consistência da rede de disequalities. A segunda propriedade da única alldifferentrestrição é que a consistência hiper-arco pode ser eficientemente controlados usando uma correspondência bipartite algoritmo. Em particular, um gráfico é construído com variáveis e valores como os dois conjuntos de nós, e um algoritmo gráfico correspondente bipartite especializado é executado em-lo para verificar a existência de uma tal correspondência.

Um tipo diferente de restrição que é vulgarmente utilizado é o cumulativeum. Foi introduzido para problemas de agendamento e colocação. Como um exemplo, cumulative([S1,...,Sm], [D1,...,Dm], [R1,...,Rm], L)pode ser utilizado para formalizar a condição em que há mactividades, cada um com a hora de início si, duração die utilizando uma quantidade ride um recurso. A restrição afirma que o montante total disponível de recursos é L. Técnicas de propagação de restrição especializadas para constrangimentos cumulativos existe; são usadas técnicas diferentes dependendo de qual domínios variáveis já são reduzidos a um único valor.

A terceira restrição especializado que é usado em lógica de programação restrição é o elementum. Na lógica de programação de restrição, as listas são permitidas como valores das variáveis. Uma restrição element(I, L, X)é satisfeita se Lé uma lista e Xé o Ielemento -ésimo desta lista. Regras de propagação restrição especializados para essas restrições existem. Como um exemplo, se Le Isão reduzidos a um domínio de valor único, um valor único para Xpode ser determinada. Mais geralmente, valores de impossíveis Xpode ser inferida a partir do domínio de e vice-versa.

consistência direcional

Consistência direccional é a variante de arco, caminho, e -Coerência adaptada para ser utilizada por um algoritmo que atribui valores para as variáveis seguintes uma determinada ordem das variáveis. Eles são semelhantes aos seus homólogos não-direcionais, mas apenas exige que uma atribuição consistente para algumas variáveis podem ser consistentemente estendida para outra variável que é maior do que os de acordo com a ordem.

arco direcional e consistência caminho

Um exemplo que é direccionalmente consistentes arco de acordo com a x2 x3 ordem x1 mas não arco consistente (sem restrição está presente entre x1 e x3; bordas correspondente omitido). Cada valor de uma variável de menor índice corresponde a valores de variáveis ​​de índice mais elevados. pontos de interrogação indicam pontos onde o inverso não se sustenta.

Se um algoritmo de variáveis avalia no fim , a consistência é apenas útil quando se garante que os valores de variáveis de menor índice são todos consistentes com os valores de os de maior índice.

Ao escolher um valor para uma variável, valores que são inconsistentes com todos os valores de uma variável não atribuído pode ser negligenciada. Na verdade, mesmo se estes valores são consistentes com a avaliação parcial atual, o algoritmo irá depois não conseguem encontrar um valor consistente para a variável não atribuída. Por outro lado, reforçar a consistência com as variáveis ​​que já estão avaliadas não é necessária: se o algoritmo escolhe um valor que é inconsistente com a avaliação parcial atual, inconsistência detectada qualquer maneira.

Supondo-se que a ordem de avaliação das variáveis é , um problema de satisfação de restrições é direcionalmente arco consistente se cada variável é arco consistente com qualquer outra variável tal que . Consistência caminho direcional é semelhante, mas duas variáveis têm de ser caminho consistente com apenas se . Forte consistência caminho direccional significa tanto consistência caminho direccional e consistência de arco direccional. Definições semelhantes podem ser dadas para as outras formas de consistência.

Propagação de restrições para o arco e o caminho consistência

Propagação de restrições aplicação itera consistência arco direccionais mais variáveis a partir do último para o primeiro, aplicando em cada passo a consistência de arco de cada variável de menor índice de com ele. Se a ordem das variáveis é , este algoritmo itera sobre variáveis de a ; para variável , que impõe consistência de arco de todas as variáveis de índice mais baixo do que com .

Direcional de arco-2.svg Direcional de arco-3.svg Direcional de arco-4.svg
Uma instância que não é direcional arco consistente: não corresponde a nenhum valor e não corresponde a nenhum valor . Sem restrição está presente entre e (bordas correspondentes são omitidos). Reforçando a consistência de arco direcional começa com , e faz arco consistente com isso, removendo o valor . Impondo consistência de arco direccional prossegue com . Desde já foi removido, tanto e são removidos.

Consistência caminho direcional e forte consistência caminho direcional pode ser executada por meio de algoritmos semelhantes ao de consistência de arco. Eles processam variáveis a partir de ; para cada variável duas variáveis com são considerados e consistência caminho deles com é aplicada. Nenhuma operação é necessária se o problema não contém nenhuma restrição sobre e ou nenhuma restrição entre e . No entanto, mesmo se não houver nenhuma restrição entre e , trivial é assumido. Se a propagação de restrições reduz o seu conjunto de atribuições satisfatórias, ele efetivamente criar uma nova restrição não-trivial. Propagação de restrições aplicação forte consistência caminho direccional é semelhante, mas também reforça a consistência de arco.

consistência direccional e satisfazibilidade

Consistência direccional garante que as soluções parciais que satisfazem uma restrição pode ser estendida de forma consistente a uma outra variável de maior índice. No entanto, ele não garante que as extensões para diferentes variáveis são consistentes entre si. Por exemplo, uma solução parcial pode ser consistentemente estendida a variável ou variável , mas contudo estas duas extensões não são compatíveis uns com os outros.

Há dois casos em que isso não acontece, e consistência direcional garante satisfiability se nenhum domínio está vazio e nenhuma restrição é insatisfatível.

O primeiro caso é o de um problema restrição binário com uma ordenação das variáveis que torna o gráfico ordenado de constrangimento de ter largura existe 1. Tal ordenamento se e somente se o grafo de restrições é uma árvore. Se este for o caso, a largura do gráfico limita o número máximo de inferior (de acordo com o ordenamento) nodos um nó está associado a. Consistência de arco direccional garante que cada atribuição consistente para uma variável pode ser estendido para os nódulos mais elevados e a largura 1 garante que um nó não está associado a mais do que um nó inferior. Como resultado, uma vez que a variável mais baixo é atribuído, o seu valor pode ser consistentemente estendida a todas as variáveis maior ele se junta com. Esta extensão não pode mais tarde levar a inconsistência. De facto, nenhum outro variável inferior é unida a essa variável mais elevado, como o gráfico que tem um largura.

Como resultado, se um problema de restrição tem largura 1 com respeito a uma ordenação das suas variáveis ​​(o que implica que o seu gráfico correspondente é uma árvore) e o problema é direccionalmente arco consistente no que diz respeito à mesma ordem, uma solução (se houver) pode ser encontrado variáveis ​​iteratively atribuição de acordo com a ordenação.

No segundo caso, em que a consistência direccional garante satisfazibilidade se nenhum domínio está vazia e sem restrição é insatisfatível é que os problemas de restrição binários cujo gráfico foi induzida largura 2, usando forte consistência caminho direccional. Com efeito, esta forma de consistência garante que todas as designações de uma variável ou um par de variáveis pode ser estendida a um maior variáveis, e largura de 2 garante que esta variável não está unido ao outro par de variáveis inferiores.

A razão pela qual a largura induzida é considerada em vez da largura é que a aplicação consistência caminho direccional pode adicionar restrições. De fato, se duas variáveis ​​não estão na mesma restrição, mas estão em uma restrição com uma variável superior, alguns pares de seus valores podem violar consistência caminho. Remoção de tais pares cria uma nova restrição. Como resultado, a propagação de restrição pode produzir um problema cujo gráfico tem bordas mais do que a original. No entanto, todas estas bordas são necessariamente no gráfico induzida, uma vez que são todos entre dois pais do mesmo nó. Largura 2 garante que todas as avaliações parcial consistente pode ser estendido para uma solução, mas esta largura é relativo ao gráfico gerado. Como um resultado, a largura induzida sendo 2 é necessário para a consistência forte caminho direccional para garantir a existência de soluções.

I-direccional consistência

As linhas azuis indicam que não há nenhuma restrição entre x3 e x4, de modo que cada par de valores é permitido. Nestas imagens, a falta de arestas entre duas variáveis ​​indica implicitamente a falta de uma restrição. Este problema tem largura 2.

Direcional -Coerência é a garantia de que cada atribuição consistente para variáveis podem ser consistentemente estendida para outra variável que é maior em ordem. Direcional forte -Coerência é definido de forma semelhante, mas todos os grupos de no máximo variáveis são consideradas. Se um problema é fortemente direcional -consistent e tem largura inferior e não tem domínio vazio ou restrição insatisfatível, tem soluções.

Todo problema pode ser feita fortemente direcional -consistent, mas esta operação pode aumentar a largura de seus gráficos correspondentes. O procedimento de propagação de restrições que impõe a consistência direccional é semelhante ao utilizado para a consistência de arco direccional e consistência caminho. As variáveis são consideradas, por sua vez, a partir do último para o primeiro acordo com a ordem. Para variável , o algoritmo considera cada grupo de variáveis que têm índice inferior e estão em uma restrição com . Consistência destas variáveis com é verificada e possivelmente executada removendo atribuições satisfatórios da restrição entre todas estas variáveis (se houver, ou criar um novo caso contrário).

Impondo consistência em x5 remove a linha vermelha, criando assim uma nova restrição não trivial entre X3 e X4. Como resultado, tem x4 x3 como uma nova matriz, em adição à x1 e x2. Esta alteração aumenta a largura de três.

Este procedimento gera uma fortemente direccional exemplo -consistent. No entanto, também pode adicionar novas restrições à instância. Como resultado, mesmo que a largura do problema original é , a largura do exemplo resultante pode ser maior. Se este for o caso, a consistência forte direcional não implica satisfiability mesmo se nenhum domínio está vazio e nenhuma restrição é insatisfatível.

No entanto, a propagação de restrições só acrescenta restrições para variáveis que são mais baixos do que a que está actualmente a considerar. Como resultado, nenhuma restrição sobre uma variável é modificado ou adicionado uma vez que o algoritmo tem lidado com esta variável. Em vez de considerar um fixo , pode modificá-lo para o número de pais de cada variável considerada (os pais de uma variável são as variáveis de índice mais baixo do que a variável e que estão em uma restrição com a variável). Isto corresponde a considerar todos os pais de uma dada variáveis em cada etapa. Em outras palavras, para cada variável do último para o primeiro, todos os seus pais estão incluídas em uma nova restrição que limita os valores para os que são consistentes com . Uma vez que este algoritmo pode ser visto como uma modificação do anterior, com um valor que é alterado para o número de pais de cada nó, é chamado de consistência adaptativa .

Este algoritmo reforça fortemente direcional -Coerência com igual à largura induzida do problema. O exemplo resultante pode ser satisfeita se e apenas se nenhum domínio ou restrição é feito vazio. Se este for o caso, uma solução pode ser facilmente encontrado, definindo iterativamente uma variável não atribuído a um valor arbitrário, e propagando desta avaliação parcial para outras variáveis. Este algoritmo nem sempre é polinomial em tempo, como o número de restrições introduzidas através da aplicação de forte consistência direccional pode produzir um aumento exponencial do tamanho. O problema é no entanto resolvidas em tempo polinomial se a reforçar a consistência forte direcional não superpolynomially ampliar a instância. Como um resultado, se uma instância induziu largura delimitada por uma constante, que pode ser resolvido em tempo polinomial.

eliminação Bucket

eliminação balde é um algoritmo de satisfatibilidade. Pode ser definida como uma reformulação de consistência adaptativo. As suas definições utiliza baldes, os quais são recipientes para restrição, cada variável que tem um balde associado. Uma restrição pertence sempre ao balde da sua mais elevada variável.

O algoritmo procede de eliminação do balde da maior para a menor variável, por sua vez. Em cada passo, os constrangimentos nos baldes de esta variável são considerados. Por definição, essas restrições envolvem apenas as variáveis que são inferiores . O algoritmo modifica a restrição entre essas variáveis mais baixos (se houver, caso contrário, ele cria um novo). Em particular, ele aplica seus valores para ser extensível para consistentemente com os constrangimentos no balde de . Esta nova restrição, se for o caso, é então colocado no recipiente apropriado. Desde essa restrição envolve apenas as variáveis que são mais baixos do que , ele é adicionado a um balde de uma variável que é inferior .

Este algoritmo é equivalente à aplicação de consistência adaptativo. Uma vez que ambos reforçar a consistência de uma variável com todos os seus pais, e uma vez que nenhuma nova restrição é adicionado depois de uma variável é considerada, o que resulta é uma instância que pode ser resolvido sem retrocesso .

Como o gráfico da instância eles produzem é um subgráfico do gráfico induzida, se a largura induzida é limitada por uma constante o exemplo gerado é de tamanho polinomial no tamanho da ocorrência original. Como resultado, se a largura induzida de uma instância é delimitada por uma constante, resolvendo-o pode ser feito em tempo polinomial pelos dois algoritmos.

consistência relacional

Embora as definições anteriores de consistência são todos sobre a consistência das atribuições, consistência relacional envolve a satisfação de uma determinada restrição ou conjunto de restrições somente. Mais precisamente, a consistência relacional implica que cada cessão parcial consistente pode ser estendido de tal forma que uma restrição dada ou conjunto de restrições é satisfeito. Formalmente, uma restrição sobre as variáveis é arco-consistente relacional com uma de suas variáveis se cada atribuição consistente para pode ser estendido para de tal maneira está satisfeito. A diferença entre "regular" a coerência ea consistência de arco relacional é que este último requer apenas a atribuição estendida para satisfazer uma determinada restrição, enquanto o primeiro requer que para satisfazer todas as restrições relevantes.

(Regular) i-consistência: se uma avaliação é consistente, ele pode ser estendido para uma outra variável de tal maneira todas as restrições relevantes forem satisfeitos.
Consistência de arco relacional: se uma avaliação sobre as variáveis de uma restrição, mas um só é consistente, ele sempre pode ser estendido para essa variável, de tal forma a restrição é satisfeita. As bordas ciano representam restrições que não precisam ser satisfeitas pela extensão.

Esta definição pode ser estendida a mais de uma restrição e mais de uma variável. Em particular, a consistência caminho relacional é semelhante ao relacional arco-consistência, mas duas restrições são usados ​​em lugar de um. Duas restrições são caminho relacional consistente com uma variável se cada atribuição consistente para todas as suas variáveis, mas a considerada pode ser estendido de tal forma as duas restrições estão satisfeitos.

Por mais de duas restrições, relacional -Coerência está definida. Relacional -Coerência envolve um conjunto de restrições e uma variável que está no escopo de todas essas restrições. Em particular, estas restrições são relacionais -consistent com a variável se cada atribuição consistente para todas as outras variáveis que estão em seus escopos pode ser estendido para a variável de tal maneira essas restrições são satisfeitas. Um problema é -relational consistente se cada conjunto de restrições é relacional -consistent com cada variável que está em todos os seus âmbitos. Relacional forte consistência é definido como acima: que é a propriedade de ser relacional -consistent para cada .

Consistência relacional também pode ser definida para mais variáveis, em vez de um. Um conjunto de restrições é relacional -consistent se cada atribuição consistente para um subconjunto de suas variáveis pode ser estendido para uma avaliação de todas as variáveis que satisfaz todas as restrições. Esta definição não é exatamente estende o acima porque as variáveis a que as avaliações deveriam ser extensível não estão necessariamente em todos os âmbitos das restrições envolvidas.

Se uma ordem das variáveis ​​é dada, consistência relacional pode ser restrita aos casos em que as variáveis ​​(s) a avaliação deve ser extensível a seguir as outras variáveis ​​no fim. Esta condição modificado é chamado consistência relacional direccional.

consistência relacional e satisfazibilidade

Um problema de satisfação de restrições pode ser relacionalmente consistente, não têm domínio vazio ou restrição insatisfatível, e ainda ser insatisfatível. No entanto, existem alguns casos em que tal não é possível.

O primeiro caso é o de fortemente relacional problema -consistent quando os domínios conter no máximo elementos. Neste caso, uma avaliação consistente das variáveis podem ser sempre estendida a uma única outra variável. Se é essa avaliação e é a variável, existem apenas valores possíveis a variável pode tomar. Se todos esses valores são inconsistentes com a avaliação, há (não necessariamente único) restrições que são violados pela avaliação e um dos seus possíveis valores. Como resultado, a avaliação não pode ser estendido para satisfazer todos estes constrangimentos -ou menos, violando a condição de forte relacional -Coerência.

O segundo caso está relacionado com uma medida das restrições, em vez dos domínios. Uma restrição é -tight se cada avaliação para todas as suas variáveis, mas um pode ser estendido para satisfazer a restrição quer por todos os valores possíveis da outra variável ou por, no máximo, dos seus valores. Problema com restrições -tight são satisfiable se e somente se eles são fortemente relacionalmente -consistent.

Uma fileira de matriz convexa: o 1s em cada fila são contíguas (sem 0 em entre eles).

O terceiro caso é o de restrições binárias que podem ser representados por matrizes de linha-convexo. Uma restrição de binário pode ser representado por uma matriz bidimensional , onde é 0 ou 1, dependendo se o valor -ésimo do domínio de e o valor -ésimo do domínio de satisfazer a restrição. Uma fileira de esta matriz é convexa se os de 1 que ele contém sejam consecutivos (formalmente, se dois elementos são 1, todos os elementos são entre 1 e). A matriz é linha convexa se todas as suas linhas são convexas.

Cada matriz representa a restrição entre x i e x k 1 . Se a 1 ... um k são valores para x 1 ... x k , as fileiras de um 1 ... um k em cada matriz contar os valores permitidos para x k +1 . Fila-convexo-dade e forte consistência caminho relacional implica a existência de um valor consistente um k 1 para x k 1 .

A condição que faz com que a consistência forte caminho relacional equivalente a satisfazibilidade é que de problemas de satisfação restrição para os quais existe uma ordem das variáveis que faz com que todas as restrições de ser representado por fileira matrizes convexas. Este resultado é baseado no fato de que um conjunto de linhas convexas que tenham um elemento pares comum também têm um elemento globalmente comum. Considerando-se uma avaliação sobre variáveis, os valores permitidos para a uma -ésimo são dadas por seleccionar algumas linhas de algumas limitações. Em particular, para cada variável entre os ones, a linha em relação ao seu valor na matriz representando a restrição relacionando-a com o um representa os valores permitidos de este último. Uma vez que estas linhas são convexas, e eles têm um elemento em pares comum por causa da consistência caminho, eles também têm um elemento comum compartilhada, o que representa um valor da última variável que é consistente com os outros.

Usos de consistência local,

Todas as formas de consistência local pode ser aplicada por propagação de restrições, o que pode reduzir os domínios de variáveis e os conjuntos de atribuições que satisfazem uma restrição e pode introduzir novas restrições. Sempre que a propagação de restrições produz um domínio vazio ou uma restrição de insatisfatível, o problema original é insatisfatível. Portanto, todas as formas de consistência local pode ser utilizado como aproximações de satisfazibilidade. Mais precisamente, eles podem ser usados como algoritmos unsatisfiability incompletos, como eles podem provar que um problema é insatisfatível, mas são em geral incapazes de provar que um problema pode ser satisfeita. Tais algoritmos podem ser aproximadas usadas por algoritmos de busca ( retrocesso , backjumping , busca local , etc.) como heurística para dizer se uma solução parcial pode ser estendido para satisfazer todas as restrições, sem analisar-lo ainda mais.

Mesmo se a propagação de restrição não produz um domínio vazio ou uma restrição de insatisfatível, ele pode, no entanto, reduzir os domínios ou reforçar as restrições. Se este for o caso, o espaço de busca do problema é reduzida, reduzindo assim a quantidade de pesquisa necessária para resolver o problema.

Consistência local comprova satisfiability em alguns casos restritos (veja Complexidade de Restrições de restrição satisfação # ). Este é o caso de algum tipo especial de problemas e / ou para alguns tipos de consistência local. Por exemplo, reforçando a consistência de arco sobre problemas acíclicos binários permite dizer se o problema é satisfeita. Impondo forte direccional -Coerência permite contar o satisfazibilidade de problemas que têm largura induzidas de acordo com o mesmo fim. Adaptive consistência direcional permite dizer a satisfiability de um problema arbitrário.

Veja também

links externos

  • Restrição Propagação - Dissertação de Guido Tack dando um bom levantamento de questões teóricas e implementação

Referências

  • Lecoutre, Christophe (2009). Redes de restrição: técnicas e algoritmos . ISTE / Wiley. ISBN  978-1-84821-106-3
  • Dechter, Rina (2003). Processamento de restrição . Morgan Kaufmann.ISBN  1-55860-890-7
  • Apt, Krzysztof (2003). Princípios de programação por restrições . Cambridge University Press.ISBN  0-521-82583-0
  • Marriott, Kim; Peter J. Stuckey (1998). Programação com restrições: Uma introdução . MIT Press.ISBN  0-262-13341-5