Consistência local

Na satisfação de restrições , as condições de consistência local são propriedades de problemas de satisfação de restrições relacionadas à consistência de subconjuntos de variáveis ​​ou restrições. Eles podem ser usados ​​para reduzir o espaço de busca e facilitar a solução do problema. Vários tipos de condições de consistência local são aproveitados, incluindo consistência de nó , consistência de arco e consistência de caminho .

Cada condição de consistência local pode ser imposta por uma transformação que altera o problema sem alterar as suas soluções; tal transformação é chamada de propagação de restrição . A propagação de restrições funciona reduzindo domínios de variáveis, fortalecendo restrições ou criando novas restrições. Isso leva a uma redução do espaço de busca, tornando o problema mais fácil de ser resolvido por alguns algoritmos. A propagação de restrições também pode ser usada como um verificador de insatisfatibilidade, incompleto em geral, mas completo em alguns casos particulares.

As condições de consistência local podem ser agrupadas em várias classes. As condições originais de consistência local exigem que toda atribuição parcial consistente (de um tipo particular) possa ser estendida consistentemente para outra variável. A consistência direcional só exige que esta condição seja satisfeita quando a outra variável for maior que as da atribuição, de acordo com uma determinada ordem. A consistência relacional inclui extensões para mais de uma variável, mas esta extensão só é necessária para satisfazer uma determinada restrição ou conjunto de restrições.

Premissas

Neste artigo, um problema de satisfação de restrições é definido 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 que a variável pode assumir. Uma restrição é composta por uma sequência de variáveis, chamada de escopo, e um conjunto de suas avaliações, que são as avaliações que satisfazem a restrição.

Os problemas de satisfação de restrições referidos neste artigo são assumidos como tendo uma forma especial. Um problema está na forma normalizada , respectivamente na forma regular , se cada sequência de variáveis ​​​​é o escopo de no máximo uma restrição ou exatamente uma restrição. A suposição de regularidade feita apenas para restrições binárias leva à forma padronizada . Essas condições sempre podem ser aplicadas combinando todas as restrições de uma sequência de variáveis ​​em uma única e/ou adicionando uma restrição que seja satisfeita 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 ​​indica que não existe nenhuma restrição ou existe uma restrição satisfeita por todos os valores entre estas duas variáveis. [ esclarecimento necessário ]

Consistência local

Todas as condições de consistência local "padrão" exigem que todas as avaliações parciais consistentes possam ser estendidas para outra variável de tal forma que a atribuição resultante seja consistente. Uma avaliação parcial é consistente se satisfaz todas as restrições cujo escopo é um subconjunto das variáveis ​​atribuídas. [ esclarecimento necessário ]

Consistência de nós

A consistência dos nós requer que cada restrição unária em uma variável seja satisfeita por todos os valores no domínio da variável e vice-versa. Esta condição pode ser aplicada trivialmente reduzindo o domínio de cada variável aos valores que satisfaçam todas as restrições unárias dessa variável. Como resultado, as restrições unárias podem ser negligenciadas e consideradas incorporadas aos domínios.

Por exemplo, dada uma variável com um domínio e uma restrição , a consistência do nó restringiria o domínio a e a restrição poderia então ser descartada. Esta etapa de pré-processamento simplifica etapas posteriores.

Consistência do arco

é consistente com, mas não com , pois o valor não é compatível com nenhum valor para .

Uma variável de um problema de satisfação de restrições é consistente com outra se cada um dos seus valores admissíveis for consistente com algum valor admissível da segunda variável. Formalmente, uma variável é consistente com outra variável se, para cada valor no domínio de existe um valor no domínio de tal que satisfaça a restrição binária entre e . Um problema é consistente em arco se cada variável for consistente em arco com todas as outras.

Por exemplo, considere a restrição em que as variáveis ​​variam no domínio de 1 a 3. Como nunca pode ser 3, não há arco de 3 para um valor, portanto é seguro removê-lo. Da mesma forma, nunca pode ser 1, portanto não há arco, portanto pode ser removido.

A consistência do arco também pode ser definida em relação a uma restrição binária específica: uma restrição binária é consistente com o arco se cada valor de uma variável tiver um valor da segunda variável de modo que satisfaça a restrição. Esta definição de consistência de arco é semelhante à anterior, mas é específica para uma restrição. Esta diferença é especialmente relevante para problemas não normalizados, onde a definição acima consideraria todas as restrições entre duas variáveis ​​enquanto esta considera apenas uma específica.

Consistência do arco imposta pela remoção de 1 como valor para x2. Como resultado, x3 não é mais consistente com x2 porque x3=2 não corresponde a um valor para x2.

Se uma variável não for consistente com outra, isso pode ser feito removendo alguns valores de seu domínio. Esta é a forma de propagação de restrições que impõe consistência ao arco: remove, do domínio da variável, todo valor que não corresponde a um valor da outra variável. Essa transformação mantém as soluções do problema, já que os valores removidos não têm solução de qualquer maneira.

A propagação de restrições pode tornar todo o problema consistente, repetindo essa 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. Na verdade, remover valores do domínio de uma variável pode fazer com que outras variáveis ​​deixem de ser consistentes com ela. Por exemplo, se o arco for consistente com mas o algoritmo reduzir o domínio de , a consistência do arco com não será mais válida e deverá ser aplicada novamente.

Um algoritmo simplista percorreria os pares de variáveis, reforçando a consistência do arco, repetindo o ciclo até que nenhum domínio mudasse durante todo o ciclo. O algoritmo AC-3 melhora este algoritmo ao ignorar restrições que não foram modificadas desde a última análise. Em particular, funciona num conjunto de restrições que inicialmente contém todas as restrições; a cada passo, ele impõe uma restrição e reforça a consistência do arco; se esta operação tiver produzido uma violação da consistência do arco sobre outra restrição, ela coloca essa restrição de volta no conjunto de restrições a serem analisadas. Desta forma, uma vez imposta a consistência do arco a uma restrição, esta restrição não é considerada novamente a menos que o domínio de uma de suas variáveis ​​seja alterado.

Consistência do caminho (consistência k)

x1 e x2 não são consistentes com x3. Eles podem se tornar consistentes com o caminho removendo os valores azuis de R12.

A consistência de caminho é uma propriedade semelhante à consistência de arco, mas considera pares de variáveis ​​em vez de apenas uma. Um par de variáveis ​​é consistente com uma terceira variável se cada avaliação consistente do par puder ser estendida para a outra variável de tal forma que todas as restrições binárias sejam satisfeitas. Formalmente, e são caminhos consistentes com se, para cada par de valores que satisfaz a restrição binária entre e , existe um valor no domínio de tal que e satisfaz a restrição entre e e entre e , respectivamente.

A forma de propagação de restrições que impõe consistência de caminho funciona removendo alguma atribuição satisfatória de uma restrição. Na verdade, a consistência do caminho pode ser reforçada removendo de uma restrição binária todas as avaliações que não podem ser estendidas a outra variável. Quanto à consistência do arco, esta remoção pode ter que considerar uma restrição binária mais de uma vez. Quanto à consistência do arco, o problema resultante possui as mesmas soluções do original, pois os valores removidos não têm solução.

Duas variáveis ​​que não estão em uma restrição podem ser consideradas relacionadas por uma restrição virtual permitindo qualquer par possível de valores, representado pelas bordas azuis nesta figura.
Aplicar a consistência do caminho de x1 e x2 com x3 remove a borda no topo. 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 consistência de caminho pode introduzir novas restrições. Quando duas variáveis ​​não estão relacionadas por uma restrição binária, elas estão virtualmente relacionadas pela restrição que permite qualquer par de valores. No entanto, algum par de valores pode ser removido pela propagação de restrições. A restrição resultante não é mais satisfeita por todos os pares de valores. Portanto, não é mais uma restrição virtual e trivial.

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

Generalizações

A consistência de arco e caminho pode ser generalizada para restrições não binárias usando tuplas de variáveis ​​em vez de uma única ou um par. Uma tupla de variáveis ​​é consistente com outra variável se cada avaliação consistente das variáveis ​​puder ser estendida com um valor da outra variável, preservando a consistência. Esta definição se estende a problemas inteiros de maneira óbvia. Consistência forte é consistência para todos .

O caso particular de consistência 2 coincide com consistência de arco (todos os problemas são assumidos como consistentes com nós neste artigo). Por outro lado, a consistência 3 coincide com a consistência do caminho apenas se todas as restrições forem binárias, porque a consistência do caminho não envolve restrições ternárias, ao contrário da consistência 3.

Outra forma de generalizar a consistência do arco é a consistência do hiperarco ou consistência generalizada do arco , que requer extensibilidade de uma única variável para satisfazer uma restrição. Ou seja, uma variável é hiperarco consistente com uma restrição se cada valor da variável puder ser estendido para as outras variáveis ​​da restrição de tal forma que a restrição seja satisfeita.

Consistência e satisfatibilidade

Esta instância é consistente em arco e não contém domínio vazio, mas não tem solução. As linhas azuis indicam atribuições forçadas pela escolha x1=1.

A propagação de restrições (impondo uma forma de consistência local) pode produzir um domínio vazio ou uma restrição insatisfatória . Neste caso, o problema não tem solução. O inverso não é verdadeiro em geral: uma instância inconsistente pode ser consistente em arco ou consistente em caminho sem ter domínio vazio ou restrição insatisfatória.

Na verdade, a consistência local é apenas relativa à consistência de grupos de variáveis. Por exemplo, a consistência do arco garante que toda avaliação consistente de uma variável possa ser estendida de forma consistente para outra variável. Entretanto, quando um único valor de uma variável é estendido a duas outras variáveis, não há garantia de que esses dois valores sejam consistentes entre si. Por exemplo, pode ser consistente com e com , mas estas duas avaliações podem não ser consistentes entre si.

No entanto, a propagação de restrições pode ser usada para provar a satisfatibilidade em alguns casos. Um conjunto de restrições binárias que é consistente em arco e não possui domínio vazio pode ser inconsistente apenas se a rede de restrições contiver ciclos. Na verdade, se as restrições são binárias e formam um gráfico acíclico, os valores podem sempre ser propagados através das restrições: para cada valor de uma variável, todas as variáveis ​​numa restrição com ela têm um valor que satisfaz essa restrição. Como resultado, uma solução pode ser encontrada escolhendo iterativamente uma variável não atribuída e propagando recursivamente através das restrições. Este algoritmo nunca tenta atribuir um valor a uma variável que já esteja atribuída, pois isso implicaria a existência de ciclos na rede de restrições.

Uma condição semelhante vale para a consistência do caminho. Os casos especiais em que a satisfatibilidade pode ser estabelecida através da aplicação da consistência do arco e da consistência do caminho são os seguintes.

  1. impor a consistência do arco estabelece a satisfatibilidade de problemas feitos de restrições binárias sem ciclos (uma árvore de restrições binárias);
  2. impor a consistência do caminho estabelece a satisfatibilidade para restrições binárias (possivelmente com ciclos) com domínios binários;
  3. impor uma consistência forte estabelece a satisfatibilidade de problemas contendo variáveis.

Casos especiais

Algumas definições ou resultados sobre consistência relativa são válidos apenas em casos especiais.

Quando os domínios são compostos por números inteiros , a consistência ligada pode ser definida. Esta forma de consistência baseia-se na consistência dos valores extremos dos domínios, ou seja, os valores mínimo e máximo que uma variável pode assumir.

Quando as restrições são algébricas ou booleanas , a consistência do arco é equivalente a adicionar uma nova restrição ou modificar sintaticamente uma antiga, e isso pode ser feito compondo restrições adequadamente.

Restrições especializadas

Alguns tipos de restrições são comumente usados. Por exemplo, a restrição de que algumas variáveis ​​são todas diferentes é frequentemente usada. Existem algoritmos especializados eficientes para impor a consistência do arco em tais restrições.

A restrição que obriga uma série de variáveis ​​a serem diferentes é geralmente escrita ou . Esta restrição equivale à não igualdade de todos os pares de variáveis ​​diferentes, ou seja, para cada . Quando o domínio de uma variável é reduzido a um único valor, este valor pode ser removido de todos os outros domínios pela propagação de restrições ao impor a consistência do arco. O uso da restrição especializada permite explorar propriedades que não são válidas para desigualdades binárias individuais . alldifferent([X1,...,Xn])

Uma primeira propriedade é que o número total de elementos nos domínios de todas as variáveis ​​deve ser pelo menos o número de variáveis. Mais precisamente, após a consistência do arco ser aplicada, o número de variáveis ​​não atribuídas não deve exceder o número de valores na união dos seus domínios. Caso contrário, a restrição não pode ser satisfeita. Esta condição pode ser facilmente verificada em uma restrição na alldifferentforma, mas não corresponde à consistência do arco da rede de desigualdades. Uma segunda propriedade da alldifferentrestrição única é que a consistência do hiperarco pode ser verificada de forma eficiente usando um algoritmo de correspondência bipartido . Em particular, um gráfico é construído com variáveis ​​e valores como os dois conjuntos de nós, e um algoritmo especializado de correspondência de grafos bipartidos é executado nele para verificar a existência de tal correspondência. [1]

Um tipo diferente de restrição comumente usado é cumulativeaquele. Foi introduzido por problemas de agendamento e colocação. Como exemplo, cumulative([S1,...,Sm], [D1,...,Dm], [R1,...,Rm], L)pode ser utilizado para formalizar a condição em que existem matividades, cada uma com horário de início si, duração die utilização de uma quantidade ride recurso. A restrição afirma que a quantidade total de recursos disponíveis é L. Existem técnicas especializadas de propagação de restrições para restrições cumulativas; diferentes técnicas são utilizadas dependendo de quais domínios variáveis ​​já estão reduzidos a um único valor.

Uma terceira restrição especializada usada na programação de lógica de restrição é elementaquela. Na programação de lógica de restrição, listas são permitidas como valores de variáveis. Uma restrição element(I, L, X)é satisfeita se Lfor uma lista e Xfor o I-ésimo elemento desta lista. Existem regras especializadas de propagação de restrições para essas restrições. Por exemplo, se Le Iforem reduzidos a um domínio de valor único, um valor único para Xpode ser determinado. De forma mais geral, valores impossíveis de Xpodem ser inferidos do domínio de e vice-versa.

Consistência direcional

Consistência direcional é a variante de arco, caminho e consistência adaptada para ser usada por um algoritmo que atribui valores a variáveis ​​seguindo uma determinada ordem de variáveis. Eles são semelhantes às suas contrapartes não direcionais, mas exigem apenas que uma atribuição consistente a algumas variáveis ​​possa ser estendida consistentemente a outra variável que seja maior que elas de acordo com a ordem.

Arco direcional e consistência de caminho

Uma instância que é direcionalmente consistente em arco de acordo com a ordem x1 x2 x3, mas não consistente em arco (nenhuma restrição está presente entre x1 e x3; arestas correspondentes omitidas). Cada valor de uma variável de índice inferior corresponde a valores de variáveis ​​de índice superior. Os pontos de interrogação indicam pontos onde o inverso não é válido.

Se um algoritmo avalia variáveis ​​na ordem , a consistência só é útil quando garante que os valores das variáveis ​​de índice mais baixo são todos consistentes com os valores das variáveis ​​de índice mais alto.

Ao escolher um valor para uma variável, os valores que são inconsistentes com todos os valores de uma variável não atribuída podem ser negligenciados. Na verdade, mesmo que estes valores sejam todos consistentes com a avaliação parcial actual, o algoritmo mais tarde não conseguirá encontrar um valor consistente para a variável não atribuída. Por outro lado, não é necessário impor consistência com variáveis ​​que já foram avaliadas: se o algoritmo escolher um valor que seja inconsistente com a avaliação parcial atual, a inconsistência será detectada de qualquer maneira.

Supondo que a ordem de avaliação das variáveis ​​seja , um problema de satisfação de restrições é direcionalmente consistente se cada variável for consistente com qualquer outra variável tal que . A consistência do caminho direcional é semelhante, mas duas variáveis ​​​​precisam ter consistência de caminho apenas com if . Forte consistência de caminho direcional significa consistência de caminho direcional e consistência de arco direcional. Definições semelhantes podem ser dadas para outras formas de consistência.

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

A propagação de restrições que impõe a consistência do arco direcional itera sobre as variáveis ​​da última para a primeira, reforçando a cada passo a consistência do arco de cada variável de índice inferior com ela. Se a ordem das variáveis ​​for , esse algoritmo itera sobre as variáveis ​​de até ; para variável , ele impõe consistência de arco de cada variável de índice menor que com .

Uma instância que não é consistente com arco direcional: não corresponde a nenhum valor de e não corresponde a nenhum valor de . Nenhuma restrição está presente entre e (as arestas correspondentes são omitidas). A aplicação da consistência do arco direcional começa com e torna o arco consistente com ele removendo o valor . A aplicação da consistência do arco direcional prossegue com . Como já foi removido, ambos e são removidos.

A consistência do caminho direcional e a forte consistência do caminho direcional podem ser reforçadas por algoritmos semelhantes àqueles para consistência de arco. Eles processam variáveis ​​de para ; para cada variável, duas variáveis ​​são consideradas e a consistência do caminho delas é aplicada. Nenhuma operação é necessária se o problema não contiver nenhuma restrição e ou nenhuma restrição entre e . No entanto, mesmo que não haja restrição entre e , uma restrição trivial é assumida. Se a propagação de restrições reduzir seu conjunto de atribuições satisfatórias, ela efetivamente criará uma nova restrição não trivial. A propagação de restrições que impõe forte consistência de caminho direcional é semelhante, mas também impõe consistência de arco.

Consistência direcional e satisfatibilidade

A consistência direcional garante que soluções parciais que satisfaçam uma restrição possam ser estendidas consistentemente para outra variável de índice mais alto. No entanto, não garante que as extensões para diferentes variáveis ​​sejam consistentes entre si. Por exemplo, uma solução parcial pode ser consistentemente estendida para variável ou para variável , mas ainda assim essas duas extensões não são consistentes uma com a outra.

Existem dois casos em que isso não acontece, e a consistência direcional garante a satisfatibilidade se nenhum domínio estiver vazio e nenhuma restrição for insatisfatível.

O primeiro caso é o de um problema de restrição binária com uma ordenação das variáveis ​​que faz com que o gráfico ordenado de restrição tenha largura 1. Tal ordenação existe se e somente se o gráfico de restrições for uma árvore. Se for esse o caso, a largura do gráfico limita o número máximo de nós inferiores (de acordo com a ordem) aos quais um nó está unido. A consistência do arco direcional garante que toda atribuição consistente a uma variável possa ser estendida para nós superiores, e a largura 1 garante que um nó não seja unido a mais de um nó inferior. Como resultado, uma vez atribuída a variável inferior, seu valor pode ser estendido de forma consistente a cada variável superior à qual está associada. Esta extensão não pode conduzir posteriormente a inconsistências. Na verdade, nenhuma outra variável inferior está associada a essa variável superior, pois o gráfico tem largura 1.

Como resultado, se um problema de restrição tem largura 1 em relação a uma ordenação de suas variáveis ​​(o que implica que seu gráfico correspondente é uma árvore) e o problema é direcionalmente consistente em relação à mesma ordenação, uma solução (se houver) pode ser encontrado atribuindo variáveis ​​iterativamente de acordo com a ordenação.

O segundo caso em que a consistência direcional garante a satisfatibilidade se nenhum domínio estiver vazio e nenhuma restrição for insatisfatível é o dos problemas de restrição binária cujo gráfico induziu largura 2, usando forte consistência de caminho direcional. Na verdade, esta forma de consistência garante que cada atribuição a uma variável ou a um par de variáveis ​​pode ser estendida a uma variável superior, e a largura 2 garante que esta variável não esteja unida a outro par de variáveis ​​inferiores.

A razão pela qual a largura induzida é considerada em vez da largura é que impor a consistência do caminho direcional pode adicionar restrições. Na verdade, se duas variáveis ​​não estão na mesma restrição, mas estão numa restrição com uma variável superior, alguns pares dos seus valores podem violar a consistência do caminho. A remoção de tais pares cria uma nova restrição. Como resultado, a propagação de restrições pode produzir um problema cujo gráfico possui mais arestas que o original. Porém, todas essas arestas estão necessariamente no grafo induzido, pois estão todas entre dois pais do mesmo nó. A largura 2 garante que toda avaliação parcial consistente possa ser estendida para uma solução, mas esta largura é relativa ao gráfico gerado. Como resultado, a largura induzida sendo 2 é necessária para uma forte consistência do caminho direcional para garantir a existência de soluções.

Consistência i direcional

As linhas azuis indicam que não há restrição entre x3 e x4, de modo que todo 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.

A consistência direcional é a garantia de que toda atribuição consistente a variáveis ​​possa ser estendida consistentemente para outra variável que seja superior na ordem. A consistência direcional forte é definida de maneira semelhante, mas todos os grupos de no máximo variáveis ​​são considerados. Se um problema for fortemente consistente direcionalmente e tiver largura menor e não tiver domínio vazio ou restrição insatisfatória, ele terá soluções.

Todo problema pode ser tornado fortemente consistente direcionalmente, mas esta operação pode aumentar a largura de seus gráficos correspondentes. O procedimento de propagação de restrições que impõe consistência direcional é semelhante ao usado para consistência de arco direcional e consistência de caminho. As variáveis ​​são consideradas sucessivamente, da última para a primeira de acordo com a ordem. Para variável , o algoritmo considera todo grupo de variáveis ​​que possuem índice menor que e estão em restrição com . A consistência dessas variáveis ​​é verificada e possivelmente reforçada pela remoção de atribuições satisfatórias da restrição entre todas essas variáveis ​​(se houver, ou pela criação de uma nova, caso contrário).

Aplicar consistência em x5 remove a linha vermelha, criando assim uma nova restrição não trivial entre x3 e x4. Como resultado, x4 tem x3 como novo pai, além de x1 e x2. Essa alteração aumenta a largura para 3.

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

No entanto, a propagação de restrições apenas adiciona restrições a variáveis ​​que são inferiores àquela que está sendo considerada atualmente. Como resultado, nenhuma restrição sobre uma variável é modificada ou adicionada uma vez que o algoritmo tenha lidado com esta variável. Em vez de considerar um fixo , pode-se 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 inferior à variável e que estão em restrição com a variável). Isto corresponde a considerar todos os pais de uma determinada variável em cada etapa. Em outras palavras, para cada variável da última à primeira, todos os seus pais são incluídos em uma nova restrição que limita seus valores àqueles que são consistentes com . Como 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ó, ele é denominado consistência adaptativa .

Este algoritmo impõe consistência fortemente direcional igual à largura induzida do problema. A instância resultante é satisfatória se e somente se nenhum domínio ou restrição for vazio. Se for este o caso, uma solução pode ser facilmente encontrada definindo iterativamente uma variável não atribuída para um valor arbitrário e propagando esta avaliação parcial para outras variáveis. Este algoritmo nem sempre é de tempo polinomial, pois o número de restrições introduzidas pela aplicação de uma forte consistência direcional pode produzir um aumento exponencial de tamanho. O problema, entretanto, pode ser resolvido em tempo polinomial se a forte consistência direcional imposta não ampliar a instância superpolinomialmente . Como resultado, se uma instância tiver largura induzida limitada por uma constante, ela poderá ser resolvida em tempo polinomial.

Eliminação do balde

A eliminação do balde é um algoritmo de satisfatibilidade. Pode ser definida como uma reformulação da consistência adaptativa. Suas definições utilizam buckets, que são contêineres para restrição, cada variável possuindo um bucket associado. Uma restrição sempre pertence ao intervalo de sua variável mais alta.

O algoritmo de eliminação do intervalo procede da variável mais alta para a mais baixa, por sua vez. A cada passo são consideradas as restrições nos buckets desta variável . Por definição, essas restrições envolvem apenas variáveis ​​inferiores a . O algoritmo modifica a restrição entre essas variáveis ​​inferiores (se houver, caso contrário, cria uma nova). Em particular, ele impõe que seus valores sejam extensíveis de forma consistente com as restrições no intervalo de . Essa nova restrição, se houver, é então colocada no intervalo apropriado. Como essa restrição envolve apenas variáveis ​​inferiores a , ela é adicionada a um intervalo de uma variável inferior a .

Este algoritmo é equivalente a impor consistência adaptativa. Como ambos reforçam a consistência de uma variável com todos os seus pais, e como nenhuma nova restrição é adicionada depois que uma variável é considerada, o resultado é uma instância que pode ser resolvida sem retrocesso .

Como o gráfico da instância que eles produzem é um subgrafo do gráfico induzido, se a largura induzida for limitada por uma constante, a instância gerada terá tamanho polinomial no tamanho da instância original. Como resultado, se a largura induzida de uma instância for limitada por uma constante, a solução pode ser feita em tempo polinomial pelos dois algoritmos.

Consistência relacional

Embora as definições anteriores de consistência sejam todas sobre consistência de atribuições, a consistência relacional envolve apenas a satisfação de uma determinada restrição ou conjunto de restrições. Mais precisamente, a consistência relacional implica que cada atribuição parcial consistente pode ser estendida de tal forma que uma determinada restrição ou conjunto de restrições seja satisfeito. Formalmente, uma restrição sobre variáveis ​​é um arco relacional consistente com uma de suas variáveis ​​se toda atribuição consistente que puder ser estendida de tal forma for satisfeita. A diferença entre consistência "regular" e consistência de arco relacional é que a última requer apenas a atribuição estendida para satisfazer uma determinada restrição, enquanto a primeira exige que ela satisfaça todas as restrições relevantes.

i-consistência (regular): se uma avaliação for consistente, ela pode ser estendida a outra variável de forma que todas as restrições relevantes sejam satisfeitas.
Consistência do arco relacional: se uma avaliação sobre as variáveis ​​de uma restrição for consistente, ela sempre poderá ser estendida a essa variável de forma que a restrição seja satisfeita. As arestas 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 do caminho relacional é semelhante à consistência do arco relacional, mas duas restrições são usadas no lugar de uma. Duas restrições são caminhos relacionais consistentes com uma variável se toda atribuição consistente a todas as suas variáveis, exceto a considerada, pode ser estendida de tal forma que as duas restrições sejam satisfeitas.

Para mais de duas restrições, a consistência relacional é definida. A consistência relacional 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 consistentes com a variável se cada atribuição consistente a todas as outras variáveis ​​que estão nos seus âmbitos puder ser estendida à variável de tal forma que estas restrições sejam satisfeitas. Um problema é relacional consistente se todo conjunto de restrições for relacional consistente com todas as variáveis ​​que estão em todos os seus escopos. A consistência relacional forte é definida como acima: é a propriedade de ser consistente em relação a todos .

A consistência relacional também pode ser definida para mais variáveis, em vez de uma. Um conjunto de restrições é relacional -consistente se cada atribuição consistente a um subconjunto de suas variáveis ​​puder ser estendida a uma avaliação de todas as variáveis ​​que satisfaça todas as restrições. Esta definição não estende exatamente a anterior porque as variáveis ​​às quais as avaliações deveriam ser extensíveis não estão necessariamente em todos os âmbitos das restrições envolvidas.

Se for dada uma ordem das variáveis, a consistência relacional pode ser restrita aos casos em que a(s) variável(is) a avaliação deve(m) ser extensível(s) para seguir as outras variáveis ​​na ordem. Esta condição modificada é chamada de consistência relacional direcional.

Consistência relacional e satisfatibilidade

Um problema de satisfação de restrições pode ser relacionalmente consistente, não ter domínio vazio ou restrição insatisfatória e, ainda assim, ser insatisfatório. No entanto, existem alguns casos em que isso não é possível.

O primeiro caso é o de problema fortemente relacional-consistente quando os domínios contêm no máximo elementos. Neste caso, uma avaliação consistente das variáveis ​​pode sempre ser estendida a uma única outra variável. Se for essa avaliação e for a variável, só existem valores possíveis que a variável pode assumir. Se todos esses valores forem inconsistentes com a avaliação, existem restrições (não necessariamente únicas) que são violadas pela avaliação e por um dos seus valores possíveis. Como resultado, a avaliação não pode ser estendida para satisfazer todas essas restrições -ou-menos, violando a condição de forte consistência relacional.

O segundo caso está relacionado a uma medida das restrições, e não aos domínios. Uma restrição é rígida se cada avaliação para todas as suas variáveis, exceto uma, pode ser estendida para satisfazer a restrição por todos os valores possíveis da outra variável ou pelo máximo de seus valores. Problemas com restrições rígidas são satisfatórios se, e somente se, forem fortemente consistentes em termos relacionais.

Uma matriz convexa de linha: os 1 em cada linha são contíguos (sem 0 entre eles).

O terceiro caso é o das restrições binárias que podem ser representadas por matrizes linha-convexas. Uma restrição binária pode ser representada por uma matriz bidimensional , onde é 0 ou 1 dependendo se o -ésimo valor do domínio de e o -ésimo valor do domínio de satisfazem a restrição. Uma linha desta matriz é convexa se os 1 que ela contém forem consecutivos (formalmente, se dois elementos são 1, todos os elementos intermediários também são 1). Uma matriz é convexa por linha se todas as suas linhas forem convexas.

Cada matriz representa a restrição entre x i e x k +1 . Se a 1 ... a k são valores para x 1 ... x k , as linhas de a 1 ... a k em cada matriz indicam os valores permitidos para x k +1 . A convexidade da linha e a forte consistência do caminho relacional implicam a existência de um valor consistente a k +1 para x k +1 .

A condição que torna a consistência do caminho relacional forte equivalente à satisfatibilidade é a dos problemas de satisfação de restrições para os quais existe uma ordem das variáveis ​​que faz com que todas as restrições sejam representadas por matrizes convexas em linha. Este resultado é baseado no fato de que um conjunto de linhas convexas tendo um elemento comum aos pares também possui um elemento globalmente comum. Considerando uma avaliação sobre variáveis, os valores permitidos para a -ésima são dados selecionando algumas linhas de algumas restrições. Em particular, para cada variável entre aquelas, a linha relativa ao seu valor na matriz que representa a restrição que a relaciona com aquela representa os valores permitidos desta última. Como essas linhas são convexas e possuem um elemento comum aos pares devido à consistência do caminho, elas também possuem um elemento comum compartilhado, que representa um valor da última variável que é consistente com as demais.

Usos de consistência local

Todas as formas de consistência local podem ser impostas pela 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 insatisfatória, o problema original é insatisfatório. Portanto, todas as formas de consistência local podem ser usadas como aproximações de satisfatibilidade. Mais precisamente, podem ser usados ​​como algoritmos de insatisfatibilidade incompleta, pois podem provar que um problema é insatisfatório, mas em geral são incapazes de provar que um problema é satisfatível. Tais algoritmos aproximados podem ser usados ​​por algoritmos de busca ( backtracking , backjumping , busca local , etc.) como heurísticas para dizer se uma solução parcial pode ser estendida para satisfazer todas as restrições sem analisá-la mais detalhadamente.

Mesmo que a propagação de restrições não produza um domínio vazio ou uma restrição insatisfatória, ela pode, no entanto, reduzir os domínios ou fortalecer as restrições. Se for esse o caso, o espaço de busca do problema é reduzido, reduzindo assim a quantidade de busca necessária para resolver o problema.

A consistência local prova a satisfatibilidade em alguns casos restritos (veja Complexidade da satisfação de restrições#Restrições ). Este é o caso de alguns tipos especiais de problemas e/ou de alguns tipos de consistência local. Por exemplo, impor a consistência do arco em problemas binários acíclicos permite dizer se o problema é satisfatório. Aplicar uma forte consistência direcional permite informar a satisfatibilidade de problemas que induziram largura de acordo com a mesma ordem. A consistência direcional adaptativa permite informar a satisfatibilidade de um problema arbitrário.

Veja também

links externos

  • Propagação de Restrições - Dissertação de Guido Tack apresentando um bom levantamento da teoria e questões de implementação

Referências

  1. ^ Régin, Jean-Charles (julho de 1994). "Um algoritmo de filtragem para restrições de diferença em CSPs" (PDF) . Anais da Conferência AAAI . Recuperado em 16 de dezembro de 2022 .
  • Lecoutre, Christophe (2009). Redes de restrições: técnicas e algoritmos. IST/Wiley. ISBN  978-1-84821-106-3
  • Dechter, Rina (2003). Processamento de restrições. Morgan Kaufmann. ISBN  1-55860-890-7
  • Apto, Krzysztof (2003). Princípios de programação com restrições . Cambridge University Press. ISBN0-521-82583-0 
  • Marriott, Kim; Peter J. Stuckey (1998). Programação com restrições: uma introdução . Imprensa do MIT. ISBN  0-262-13341-5
Retrieved from "https://en.wikipedia.org/w/index.php?title=Local_consistency&oldid=1179702336#Bucket_elimination"