Problema de satisfação de restrição

Problemas de satisfação de restrições ( CSPs ) são questões matemáticas definidas como um conjunto de objetos cujo estado deve satisfazer uma série de restrições ou limitações . Os CSPs representam as entidades em um problema como uma coleção homogênea de restrições finitas sobre variáveis , que é resolvida por métodos de satisfação de restrições . Os CSPs são objeto de pesquisa tanto em inteligência artificial quanto em pesquisa operacional , uma vez que a regularidade em sua formulação fornece uma base comum para analisar e resolver problemas de muitas famílias aparentemente não relacionadas. Os CSPs geralmente apresentam alta complexidade , exigindo uma combinação de métodos heurísticos e de busca combinatória para serem resolvidos em um tempo razoável. A programação com restrições (CP) é o campo de pesquisa que se concentra especificamente em lidar com esses tipos de problemas. [1] [2] Além disso, o problema de satisfatibilidade booleana (SAT), as teorias do módulo de satisfatibilidade (SMT), a programação inteira mista (MIP) e a programação do conjunto de respostas (ASP) são todos campos de pesquisa com foco na resolução de formas particulares do problema de satisfação de restrições.

Exemplos de problemas que podem ser modelados como um problema de satisfação de restrições incluem:

Freqüentemente, são fornecidos tutoriais de solucionadores CP , ASP, Boolean SAT e SMT. No caso geral, os problemas de restrições podem ser muito mais difíceis e podem não ser exprimíveis em alguns destes sistemas mais simples. Exemplos da "vida real" incluem planejamento automatizado , [6] [7] desambiguação lexical , [8] [9] musicologia , [10] configuração de produto [11] e alocação de recursos . [12]

A existência de uma solução para um CSP pode ser vista como um problema de decisão . Isso pode ser decidido encontrando uma solução ou não conseguindo encontrar uma solução após uma pesquisa exaustiva ( algoritmos estocásticos normalmente nunca chegam a uma conclusão exaustiva, enquanto as pesquisas direcionadas geralmente o fazem, em problemas suficientemente pequenos). Em alguns casos, o CSP pode ser conhecido por ter soluções de antemão, através de algum outro processo de inferência matemática.

Definição formal

Formalmente, um problema de satisfação de restrições é definido como um triplo , onde [13]

  • é um conjunto de variáveis,
  • é um conjunto de seus respectivos domínios de valores, e
  • é um conjunto de restrições.

Cada variável pode assumir os valores do domínio não vazio . Cada restrição é, por sua vez, um par , onde é um subconjunto de variáveis ​​e é uma relação -ária no subconjunto de domínios correspondente . Uma avaliação das variáveis ​​é uma função de um subconjunto de variáveis ​​para um conjunto particular de valores no subconjunto de domínios correspondente. Uma avaliação satisfaz uma restrição se os valores atribuídos às variáveis ​​satisfazem a relação .

Uma avaliação é consistente se não viola nenhuma das restrições. Uma avaliação está completa se incluir todas as variáveis. Uma avaliação é uma solução se for consistente e completa; diz-se que tal avaliação resolve o problema de satisfação de restrições.

Solução

Problemas de satisfação de restrições em domínios finitos são normalmente resolvidos usando uma forma de pesquisa . As técnicas mais utilizadas são variantes de retrocesso , propagação de restrições e busca local . Estas técnicas também são frequentemente combinadas, como no método VLNS , e a pesquisa atual envolve outras tecnologias, como a programação linear . [14]

Backtracking é um algoritmo recursivo. Mantém uma atribuição parcial das variáveis. Inicialmente, todas as variáveis ​​não estão atribuídas. Em cada etapa, uma variável é escolhida e todos os valores possíveis são atribuídos a ela. Para cada valor é verificada a consistência da atribuição parcial com as restrições; em caso de consistência, é realizada uma chamada recursiva . Quando todos os valores foram testados, o algoritmo retrocede. Neste algoritmo básico de retrocesso, consistência é definida como a satisfação de todas as restrições cujas variáveis ​​são todas atribuídas. Existem diversas variantes de retrocesso. Backmarking melhora a eficiência da verificação de consistência. Backjumping permite salvar parte da pesquisa retrocedendo "mais de uma variável" em alguns casos. A aprendizagem por restrições infere e salva novas restrições que podem ser usadas posteriormente para evitar parte da pesquisa. A antecipação também é frequentemente usada em retrocesso para tentar prever os efeitos da escolha de uma variável ou valor, determinando às vezes antecipadamente quando um subproblema é satisfatório ou insatisfatório.

Técnicas de propagação de restrições são métodos usados ​​para modificar um problema de satisfação de restrições. Mais precisamente, são métodos que impõem uma forma de consistência local , que são condições relacionadas à consistência de um grupo de variáveis ​​e/ou restrições. A propagação de restrições tem vários usos. Primeiro, transforma um problema em um problema equivalente, mas geralmente mais simples de resolver. Em segundo lugar, pode provar a satisfatibilidade ou insatisfatibilidade dos problemas. Não é garantido que isso aconteça em geral; no entanto, isso sempre acontece para algumas formas de propagação de restrições e/ou para certos tipos de problemas. As formas mais conhecidas e utilizadas de consistência local são consistência de arco , consistência de hiperarco e consistência de caminho . O método de propagação de restrições mais popular é o algoritmo AC-3 , que reforça a consistência do arco.

Os métodos de busca local são algoritmos de satisfatibilidade incompletos. Eles podem encontrar a solução para um problema, mas podem falhar mesmo que o problema seja satisfatório. Eles funcionam melhorando iterativamente uma atribuição completa sobre as variáveis. A cada passo, o valor de um pequeno número de variáveis ​​é alterado, com o objetivo geral de aumentar o número de restrições satisfeitas por esta atribuição. O algoritmo min-conflicts é um algoritmo de busca local específico para CSPs e é baseado nesse princípio. Na prática, a busca local parece funcionar bem quando essas mudanças também são afetadas por escolhas aleatórias. Foi desenvolvida uma integração da busca com a busca local, levando a algoritmos híbridos .

Aspectos teóricos

Problemas de decisão

CSPs também são estudados na teoria da complexidade computacional e na teoria dos modelos finitos . Um importante teorema de dicotomia afirma que para cada conjunto de relações, o conjunto de todos os CSPs que podem ser representados usando apenas relações escolhidas desse conjunto está em P ou NP-completo . Os CSPs fornecem, portanto, um dos maiores subconjuntos conhecidos de NP que evita problemas NP-intermediários , cuja existência foi demonstrada pelo teorema de Ladner sob a suposição de que P ≠ NP . O teorema da dicotomia de Schaefer trata do caso quando todas as relações disponíveis são operadores booleanos , ou seja, para tamanho de domínio 2. O teorema da dicotomia de Schaefer foi posteriormente generalizado para uma classe maior de relações, [15] e um teorema de dicotomia completo foi conjecturado pela primeira vez como Feder –Conjectura de Vardi [16] e finalmente provada de forma independente por Andrei Bulatov [17] e Dmitriy Zhuk. [18]

A maioria das classes de CSPs que são conhecidas por serem tratáveis ​​são aquelas onde o hipergrafo de restrições tem largura de árvore limitada (e não há restrições no conjunto de relações de restrição), ou onde as restrições têm forma arbitrária, mas existem polimorfismos essencialmente não unários [ esclarecimento necessário ] do conjunto de relações de restrição.

Todo CSP também pode ser considerado um problema de contenção de consulta conjuntiva . [19]

Problemas de função

Situação semelhante existe entre as classes funcionais FP e #P . Por uma generalização do teorema de Ladner , também não há problemas nem em FP nem em #P-completo desde que FP ≠ #P. Assim como no caso de decisão, um problema no #CSP é definido por um conjunto de relações. Cada problema recebe uma fórmula booleana como entrada e a tarefa é calcular o número de atribuições satisfatórias. Isso pode ser ainda mais generalizado usando tamanhos de domínio maiores e atribuindo um peso a cada atribuição satisfatória e calculando a soma desses pesos. Sabe-se que qualquer problema #CSP ponderado complexo é FP ou #P-difícil. [20]

Variantes

O modelo clássico do Problema de Satisfação de Restrições define um modelo de restrições estáticas e inflexíveis. Este modelo rígido é uma deficiência que torna difícil representar facilmente os problemas. [21] Várias modificações da definição básica de CSP foram propostas para adaptar o modelo a uma ampla variedade de problemas.

CSPs dinâmicos

CSPs dinâmicos [22] ( DCSP s) são úteis quando a formulação original de um problema é alterada de alguma forma, normalmente porque o conjunto de restrições a considerar evolui por causa do ambiente. [23] DCSPs são vistos como uma sequência de CSPs estáticos, cada um uma transformação do anterior em que variáveis ​​e restrições podem ser adicionadas (restrição) ou removidas (relaxamento). As informações encontradas nas formulações iniciais do problema podem ser utilizadas para refinar as próximas. O método de resolução pode ser classificado de acordo com a forma como a informação é transferida:

  • Oráculos : as soluções encontradas para os CSPs anteriores na sequência são utilizadas como heurísticas para orientar a resolução do CSP atual do zero.
  • Reparo local: cada CSP é calculado a partir da solução parcial do anterior e reparando as restrições inconsistentes com busca local .
  • Registro de restrições: novas restrições são definidas em cada etapa da busca para representar o aprendizado de grupos inconsistentes de decisões. Essas restrições são transportadas para os novos problemas de CSP.

CSPs flexíveis

Os CSPs clássicos tratam as restrições como difíceis, o que significa que são imperativas (cada solução deve satisfazer todas elas) e inflexíveis (no sentido de que devem ser completamente satisfeitas ou serão completamente violadas). Os CSPs flexíveis relaxam essas suposições, relaxando parcialmente as restrições e permitindo que a solução não cumpra todas elas. Isto é semelhante às preferências no planejamento baseado em preferências . Alguns tipos de CSPs flexíveis incluem:

  • MAX-CSP, onde uma série de restrições podem ser violadas e a qualidade de uma solução é medida pelo número de restrições satisfeitas.
  • CSP ponderado , um MAX-CSP em que cada violação de uma restrição é ponderada de acordo com uma preferência predefinida. Assim, é preferível satisfazer a restrição com mais peso.
  • Restrições fuzzy do modelo CSP como relações fuzzy nas quais a satisfação de uma restrição é uma função contínua dos valores de suas variáveis, indo de totalmente satisfeita a totalmente violada.

CSPs descentralizados

Nos DCSPs [24], cada variável de restrição é considerada como tendo uma localização geográfica separada. Fortes restrições são impostas à troca de informações entre variáveis, exigindo o uso de algoritmos totalmente distribuídos para resolver o problema de satisfação de restrições.

Veja também

Referências

  1. ^ Lecoutre, Christophe (2013). Redes de restrições: técnicas e algoritmos . Wiley. pág. 26.ISBN 978-1-118-61791-5.
  2. ^ "Restrições - incluindo opção de publicação em acesso aberto" . springer.com . Recuperado em 03/10/2019 .
  3. ^ Chandra, Satish, e outros. "Inferência de tipo para compilação estática de JavaScript." Avisos ACM SIGPLAN 51.10 (2016): 410-429.
  4. ^ Jim, Trevor e Jens Palsberg. "Inferência de tipos em sistemas de tipos recursivos com subtipagem." Disponível na página dos autores (1999).
  5. ^ Farhi, Edward e Harrow, Aram. "Supremacia Quântica por meio do Algoritmo de Otimização Aproximada Quântica." arXiv:1602.07674
  6. ^ Malik Ghallab; Dana Nau; Paolo Traverso (21 de maio de 2004). Planejamento Automatizado: Teoria e Prática. Elsevier. pág. 1–. ISBN 978-0-08-049051-9.
  7. ^ Satisfação de restrição flexível dinâmica e sua aplicação ao planejamento de IA, arquivado em 06/02/2009 na Wayback Machine Ian Miguel - slides.
  8. ^ Demetriou, George C. "Desambiguação lexical usando tratamento de restrições em Prolog (CHIP)." Anais da sexta conferência sobre o capítulo europeu da Association for Computational Linguistics. Associação de Lingüística Computacional, 1993.
  9. ^ MacDonald, Maryellen C. e Mark S. Seidenberg. "Relatos de satisfação de restrições de compreensão lexical e de frases." Manual de Psicolinguística (segunda edição). 2006. 581–611.
  10. ^ Mauricio Toro, Carlos Agon, Camilo Rueda, Gerard Assayag. "GELISP: UM QUADRO PARA REPRESENTAR PROBLEMAS DE SATISFAÇÃO DE RESTRIÇÕES MUSICAIS E ESTRATÉGIAS DE PESQUISA." Revista de Tecnologia da Informação Teórica e Aplicada 86 (2). 2016. 327–331.
  11. ^ Aplicando abordagem de satisfação de restrições para resolver problemas de configuração de produto com regras de configuração baseadas em cardinalidade , Dong Yang & Ming Dong, Journal of Intelligent Manufacturing volume 24, páginas 99–111 (2013)
  12. ^ Modi, Pragnesh Jay, e outros. "Uma abordagem dinâmica de satisfação de restrições distribuídas para alocação de recursos." Conferência Internacional sobre Princípios e Práticas de Programação com Restrições. Springer, Berlim, Heidelberg, 2001.
  13. ^ Stuart Jonathan Russel; Pedro Norvig (2010). Inteligência Artificial: Uma Abordagem Moderna . Salão Prentice. pág. Capítulo 6. ISBN 9780136042594.
  14. ^ Milão, Michela ; Van Hentenryck, Pascal, eds. (2011). Otimização híbrida: os dez anos do CPAIOR . Conferência Internacional sobre Integração de Técnicas de IA e OR em Programação de Restrições para Problemas de Otimização Combinatória. Nova York: Springer. ISBN 9781441916440. OCLC695387020  .
  15. ^ Bodirsky, Manuel; Pinsker, Michael (2011). "Teorema de Schaefer para gráficos". Anais do 43º Simpósio Anual de Teoria da Computação (STOC '11) . Associação de Máquinas de Computação . pp. 655–664. arXiv : 1011.2894 . Bibcode :2010arXiv1011.2894B. doi :10.1145/1993636.1993724. ISBN 978-1-4503-0691-1. S2CID47097319  .
  16. ^ Feder, Tomás; Vardi, Moshe Y. (1998). "A estrutura computacional do SNP monádico monótono e da satisfação das restrições: um estudo por meio do registro de dados e da teoria de grupos". Jornal SIAM de Computação . 28 (1): 57–104. doi :10.1137/S0097539794266766. ISSN0097-5397  .
  17. ^ Bulatov, Andrei (2017). "Um Teorema de Dicotomia para CSPs Não Uniformes". Anais do 58º Simpósio Anual IEEE sobre Fundamentos da Ciência da Computação, FOCS 2017 . Sociedade de Computação IEEE. páginas 319–330. doi :10.1109/FOCS.2017.37.
  18. ^ Zhuk, Dmitry (2020). "Uma prova da conjectura da dicotomia CSP". Jornal da ACM . 67 (5): 1–78. arXiv : 1704.01914 . doi :10.1145/3402029.
  19. ^ Kolaitis, Phokion G.; Vardi, Moshe Y. (2000). "Contenção de consulta conjuntiva e satisfação de restrições". Jornal de Ciências da Computação e Sistemas . 61 (2): 302–332. doi : 10.1006/jcss.2000.1713 .
  20. ^ Cai, Jin-Yi; Chen, Xi (2012). “Complexidade de contagem de CSP com pesos complexos”. Anais do Quadragésimo Quarto Simpósio Anual ACM sobre Teoria da Computação (STOC '12) . páginas 909–920. arXiv : 1111.2384 . doi :10.1145/2213977.2214059. ISBN 978-1-4503-1245-5. S2CID53245129  .
  21. ^ Miguel, Ian (julho de 2001). Satisfação de restrições flexíveis dinâmicas e sua aplicação ao planejamento de IA (tese de doutorado). Escola de Informática da Universidade de Edimburgo . CiteSeerX 10.1.1.9.6733 . hdl :1842/326. 
  22. ^ Dechter, R. e Dechter, A., Manutenção de crenças em redes de restrições dinâmicas arquivadas em 17/11/2012 na máquina Wayback In Proc. da AAAI-88, 37–42.
  23. ^ Reutilização de soluções em problemas de satisfação de restrições dinâmicas, Thomas Schiex
  24. ^ Duffy, KR; Leith, DJ (agosto de 2013), "Decentralized Constraint Satisfaction", IEEE/ACM Transactions on Networking, 21(4) , vol. 21 , pp . ​

Leitura adicional

  • Uma rápida introdução à satisfação com restrições no YouTube
  • Steven Minton; Andy Phillips; Mark D. Johnston; Philip Laird (1993). "Minimizando conflitos: um método de reparo heurístico para satisfação de restrições e problemas de agendamento". Jornal de Pesquisa em Inteligência Artificial . 58 (1–3): 161–205. CiteSeerX  10.1.1.308.6637 . doi :10.1016/0004-3702(92)90007-k. S2CID14830518  .
  • Tsang, Edward (1993). Fundamentos da satisfação das restrições. Imprensa Acadêmica. ISBN0-12-701610-4 
  • Chen, Hubie (dezembro de 2009). "Um encontro de lógica, complexidade e álgebra". Pesquisas de computação ACM . 42 (1): 1–32. arXiv : cs/0611018 . doi :10.1145/1592451.1592453. S2CID11975818  .
  • 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. ISBN 9780521825832. ISBN0-521-82583-0 
  • Lecoutre, Christophe (2009). Redes de restrições: técnicas e algoritmos. IST/Wiley. ISBN  978-1-84821-106-3
  • Tomás Feder, Satisfação com restrições: uma perspectiva pessoal, manuscrito.
  • Arquivo de restrições
  • Benchmarks CSP satisfatórios forçados do modelo RB arquivados em 25/01/2021 na Wayback Machine
  • Benchmarks – representação XML de instâncias CSP
  • XCSP3 – Um formato baseado em XML projetado para representar instâncias CSP
  • Propagação de Restrições – Dissertação de Guido Tack apresentando um bom levantamento da teoria e questões de implementação
Obtido em "https://en.wikipedia.org/w/index.php?title=Constraint_satisfaction_problem&oldid=1215758412"