Problema da satisfação de restrições

O problema da satisfação de restrições do inglês constraint satisfaction problems (CSPs) são problemas matemáticos definidos como um conjunto de objetos cujo estado dos mesmos deve satisfazer uma série de restrições. CSPs representam as entidades de um problema como um conjunto homogêneo de restrições finitas sobre as variável do problema, tal problema é resolvido por métodos de satisfação de restrições. Temos que CSPs são alvos de pesquisa tanto em Inteligência Artificial quanto em Pesquisa Operacional , uma vez a regularidade presente em sua formulação proporciona uma base comum para analise e resolução de problemas de famílias não relacionadas. CSPs geralmente apresentam alta complexidade e são custosos exigindo que sejam usadas métodos heurísticos e de busca combinatória para que se possa resolver tais problemas em tempo aceitável. O problema da satisfabilidade booleana (SAT), o Problema da Satisfabilidade de Módulos Teóricos (SMT) e a programação de conjunto de respostas (ASP) pode ser aproximado pensando-se em certas formas do problema da satisfação de restrições.

Como exemplo de problemas simples que podem ser modelados como um problema de satisfação de restrições temos:

• O problema das oito rainhas
• Coloração de grafos
• Sudoku, Futoshiki, Kakuro (Somas cruzadas), Numbrix, Hidato e muitos outros puzzles lógicos

Estes exemplos acima geralmente são usados para demonstrar a teoria em tutoriais de ASP, SAT e solucionados SMT. No caso geral tais problemas de restrição podem ser muito mais complicados de serem resolvidos, ou tais sistemas simples não são capazes de expressar tais problemas.

Como exemplos mais próximos da vida real temos os problemas de alocação de recursos e alocação de horários.

Definição Formal

Formalmente, um problema de satisfação de restrições e definido com uma tripla $\langle X,D,C\rangle$. onde $X$ é um conjunto de variáveis, $D$ é o domínio dos valores e $C$ é um conjunto de restrições. Assim toda restrição $c\in C$ é um par $\langle t,R\rangle$(normalmente representado como uma matriz), onde $t$ é um $n$-tupla de variáveis e $R$ é uma relação matemática $n$-aria em $D$. Uma avaliação das variáveis é uma função de variáveis para o domínio de valores $v:X\rightarrow D$. Uma avaliação $v$ satisfaz as restrições $\langle (x_{1},\ldots ,x_{n}),R\rangle$ se $(v(x_{1}),\ldots ,v(x_{n}))\in R$. Uma solução é uma avaliação que satisfaz todas as restrições.

Resolução de CSPs

O problema da satisfação de restrições sobre domínios finitos é tipicamente resolvido usado uma forma de algoritmo de busca. Dentre as técnicas mais usadas estão variantes dos algoritmos de backtracking, propagação de restrições e busca local.

Backtracking é um algoritmo recursivo muito conhecido para resolução de alguns problemas difíceis que não possuem uma solução bem definida. Ele mantem uma atribuição parcial das variáveis de um conjunto a medida que é executado. Inicialmente, todas as variáveis não possuem nenhum valor atribuído. A cada passo tomado, uma variável é escolhida, e todos os possíveis valores para a mesma são testados. Para cada valor, e checada a consistência parcial do conjunto e caso esteja consistente uma chamada recursiva é realizada. Quando todos os valores tiverem sido avaliados, o algoritmo realiza o processo de avaliar a consistência o algoritmo realiza uma verificação e caso este conjunto não seja satisfeito tem-se o início do processo de retornar ao passo anterior e tentar uma nova configuração. No algoritmo de backtracking normal a consistência é definida como a satisfação de todas as restrições com o conjunto de valores que foi atribuído as variáveis. Existem muitas variantes do algoritmo de backtracking. Como exemplo temos:

• Backmarking que melhora a eficiência do processo de checagem de consistência.
• Backjumping que permite salvar parte da busca realizada de modo a permitir retornar mais de um passo por vez.
• Aprendizagem de restrições que permite inferir e salvar novas restrições que podem ser usadas em passos futuros para evitar que seja realizada muitas buscas.
• Look-ahead também é muito usado no processo de voltar atrás para tentar prever o efeito da escolha de uma variável ou valor e muitas vezes é capaz de dizer se um subproblema e satisfazível ou não.

Técnicas de propagação de restrições são métodos usados para modificar o problema da satisfação de restrições. Mais precisamente, tais métodos impõem uma forma de consistência local, cujas condições estão relacionadas com a consistência de um grupo de variáveis e/ou restrições. Temos que a propagação de restrições possui diversos usos. O primeiro deles é verificar se um problema é equivalente a outro, mas tal tarefa e normalmente simples de resolver. Em segundo temos que ele pode verificar a satisfabilidade ou insatisfabilidade de problema. Consequentemente é perceptível que isso nem sempre ocorre, principalmente em alguns problemas de propagação de restrições. A forma mais conhecida é usado sob a forma de consistência local, sendo estes o arco de consistência, hiper-arco de consistência e o caminho consistente. O método mais usado para resolver problemas de propagação de restrições é uma instância do algoritmo AC-3, que força um arco de consistência.

Os algoritmos de busca local são exemplos de algoritmos voltados para insatisfabilidade que são incompletos. Eles pode encontrar uma solução para o problema, mas os mesmo podem falhar em alguns casos mesmo que o problema seja satisfatível. Tais algoritmos trabalham com a melhoria interativa sobre as atribuições realizadas sobre o conjunto de valores. A cada passo, um pequeno número de variáveis são alteradas, com o objetivo de alimentar o número global de restrições satisfeitas. O algoritmo de conflito mínimo e um exemplo de algoritmo de busca local que faz uso desse princípio. Na prática, os algoritmos de busca local parecem trabalhar bem quando as alterações são realizadas sob escolhas randômicas. A integração de busca com busca local tem sido desenvolvidas ao longo dos anos, levando a criação de algoritmos híbridos.

Aspectos Teóricos de CSPs

Problemas de decisão

CSPs também são estudados em teoria da complexidade computacional e teoria de modelos finitos. Uma questão importante é saber se, para cada conjunto de relações, o conjunto de todos os CSPs que podem ser representados usando apenas as relações escolhidas a partir desse conjunto está em P ou NP-completo. Se o Teorema da dicotomia de Schaefer é verdadeiro, então CSPs são capazes de prover o maior subconjunto de NP que não contem problemas NP-intermediário, tal existência foi demonstrada pelo teorema de Ladner que assume que P ≠ NP. O Teorema da dicotomia de Schaefer lida com o caso em que todas as relações disponíveis são operadores booleanos cujo domínio tem tamanho 2. Recentemente o teorema da dicotomia de Schaefer foi generalizado para uma classe maior de relações.

Muitas classes de CSPs são conhecidas por serem tratáveis são aquelas onde o hipergrafo de restrições e uma arvore espalhada ligada (e não há restrições para o conjunto de relações), ou quando as restrições possuem uma forma arbitrária mas essencialmente não existe um polimorfismo unário para o conjunto de restrições.

Cada CSP pode ser considerado como um conjunto de busca contendo um problema.

Problemas de Funções

Uma situação similar existe entre as classes de funções FP e #P. Por uma generalização do Teorema de Ladner, existem problemas que nem estão na classe FP nem na #P enquanto FP ≠ #P. Tal como no caso de problemas de decisão, um problema em um #CSP é definido com um conjunto de relações. Cada problema tem como entrada uma fórmula booleana cuja tarefa é calcular o número de atribuições satisfeitas. Pode-se ainda generalizar ainda mais usando tamanho maiores de domínios e atribuir um peso para cada tarefa e então calcular a soma desses pesos. Sabe-se que apenas problemas #CSP ponderados ou são FP ou #P-difícil.

Variantes de CSPs

O modelo clássico do Problema da Satisfação de restrições define um modelo de restrições estáticas e inflexíveis. Este modelo rígido é um problema que torna difícil representar problemas de forma fácil. Muitas modificações da definição básica de CSPs foram propostos e adaptados para modelar uma grande variedade de problemas.

CSPs Dinâmicos

CSPs Dinâmicos (DCSPs) são usados quando a formulação original de um problema e alterado de alguma forma, tipicamente porque o conjunto de restrições considerado envolve o ambiente. DCSPs são vistos com uma sequência de CSPs estáticos, cada um é uma transformação do anterior onde as variáveis e restrições podem ser adicionados(restrição) ou removidas(relaxamento). Assim as informações encontradas no início da formulação do problema pode ser usado para refinar as próximas. Os métodos de solução pode ser classificados de acordo com a maneira na qual a informação é transferida.

• Oráculos: usam a solução da sequência de CSPs anteriores e usam heurísticas para guiar a resolução do CSP atual.
• Reparação Local: cada CSP e calculado inicialmente como uma solução parcial dos anteriores e então reparando as inconsistências nas restrições usando busca local.
• Restrições de gravação: novas restrições são definidas em cada estágio de busca para representar o conhecimento do grupo de decisões incompatíveis. Essas restrições são transferidas sobre novos problemas CSP.

CSPs Flexíveis

O tratamento de restrições por CSPs clássicos é tido como difícil, o que significa que eles são imperativos (cada solução deve satisfazer a todos eles) e inflexíveis (no sentido de que eles devem ser completamente satisfeitos, ou então eles estão completamente errados). CSPs Flexíveis relaxam essas presunções, relaxando parcialmente e permitindo a soluções que não cumprem todas elas. Isto é semelhante ao planejamento baseado em preferências. Dentre alguns tipos de CSPs flexíveis temos:

• MAX-CSP, onde um certo número de restrições podem ser violadas, e a qualidade de uma solução é medida pelo número de restrições satisfeitas.
• CSP ponderada, a MAX-CSP, em que cada violação de uma restrição é ponderado de acordo com a preferência predefinida. Assim restrições satisfatórias com mais peso são preferidas.
• CSPs de restrições Fuzzy é um modelo de relações em que a satisfação de uma restrição é uma função contínua de valores de suas variáveis, passando de totalmente satisfeito totalmente violada.

Ver também

• Satisfação de restrições
• Programação declarativa

Leituras Futuras

• Steven Minton, Andy Philips, Mark D. Johnston, Philip Laird (1993). «Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems» (PDF). Journal of Artificial Intelligence Research. 58: 161–205  !CS1 manut: Nomes múltiplos: lista de autores (link)^{[ligação inativa]}

Ligações externas

• CSP Tutorial
• Tsang, Edward (1993). Foundations of Constraint Satisfaction. [S.l.]: Academic Press  ISBN 0-12-701610-4
• Chen, Hubie (dezembro de 2009). «A Rendezvous of Logic, Complexity, and Algebra». ACM. ACM Computing Surveys. 42 (1): 1–32. doi:10.1145/1592451.1592453 
• Dechter, Rina (2003). Constraint processing. [S.l.]: Morgan Kaufmann  ISBN 1-55860-890-7
• Apt, Krzysztof (2003). Principles of constraint programming. [S.l.]: Cambridge University Press  ISBN 0-521-82583-0
• Lecoutre, Christophe (2009). Constraint Networks: Techniques and Algorithms. [S.l.]: ISTE/Wiley  ISBN 978-1-84821-106-3
• Tomás Feder, Constraint satisfaction: a personal perspective, manuscript.
• Constraints archive
• Forced Satisfiable CSP Benchmarks of Model RB
• Benchmarks -- XML representation of CSP instances
• Dynamic Flexible Constraint Satisfaction and Its Application to AI Planning, Ian Miguel - slides.
• Constraint Propagation - Dissertation by Guido Tack giving a good survey of theory and implementation issues