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 exibem alta complexidade, exigindo uma combinação de heurísticas e métodos de busca combinatória para serem resolvidos em um tempo razoável. A programação restrita (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 de módulo de satisfatibilidade (SMT), a programação inteira mista (MIP) e a programação de 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ção incluem:

Eles geralmente são fornecidos com tutoriais de solucionadores CP , ASP, Boolean SAT e SMT. No caso geral, os problemas de restrição podem ser muito mais difíceis e podem não ser expressos em alguns desses sistemas mais simples. Exemplos da "vida real" incluem planejamento automatizado , [6] [7] desambiguação lexical , [8] [9] musicologia , [10] configuração do 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 falhando em encontrar uma solução após uma pesquisa exaustiva (os 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, por meio de algum outro processo de inferência matemática.

Definição formal

Formalmente, um problema de satisfação de restrição é 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 no 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 determinado conjunto 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 é 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 tipicamente resolvidos usando uma forma de busca . As técnicas mais utilizadas são variantes de retrocesso , propagação de restrições e busca local . Essas 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 são atribuídas. A cada passo, 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, uma chamada recursiva é realizada. Quando todos os valores forem testados, o algoritmo retrocederá. Neste algoritmo básico de retrocesso, a consistência é definida como a satisfação de todas as restrições cujas variáveis ​​são todas atribuídas. Existem várias variantes de retrocesso. Backmarking melhora a eficiência da verificação de consistência. salto de costaspermite salvar parte da pesquisa retrocedendo "mais de uma variável" em alguns casos. O aprendizado de restrições infere e salva novas restrições que podem ser usadas posteriormente para evitar parte da pesquisa. Look-ahead também é freqüentemente usado em backtracking para tentar prever os efeitos da escolha de uma variável ou um valor, portanto, às vezes determinando com antecedência quando um subproblema é satisfatível ou insatisfatório.

As 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 outro equivalente, mas geralmente mais simples de resolver. Em segundo lugar, pode provar a satisfação ou insatisfabilidade dos problemas. Não é garantido que isso aconteça em geral; entretanto, sempre acontece para algumas formas de propagação de restrições e/ou para certos tipos de problemas. As formas mais conhecidas e usadas de consistência local são consistência de arco , consistência de hiper-arco e consistência de caminho. O método de propagação de restrição 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 uma solução para um problema, mas podem falhar mesmo que o problema seja satisfatível. Eles trabalham melhorando iterativamente uma atribuição completa sobre as variáveis. A cada passo, um pequeno número de variáveis ​​é alterado em valor, 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. Uma integração de busca com busca local foi desenvolvida, levando a algoritmos híbridos .

Aspectos teóricos

Problemas de decisão

Os CSPs também são estudados na teoria da complexidade computacional e na teoria dos modelos finitos . Uma questão importante é se, para cada conjunto de relações, o conjunto de todos os CSPs que podem ser representados usando apenas as relações escolhidas desse conjunto está em P ou NP-completo . Se tal teorema de dicotomia for verdadeiro, então CSPs fornecem 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 lida com o caso quando todas as relações disponíveis sãoOperadores booleanos , ou seja, para tamanho de domínio 2. O teorema da dicotomia de Schaefer foi recentemente generalizado para uma classe maior de relações. [15]

A maioria das classes de CSPs conhecidas por serem tratáveis ​​são aquelas em que 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 em que as restrições têm forma arbitrária, mas existem essencialmente polimorfismos não unários [ esclarecimento necessário ] do conjunto de relações de restrição.

Cada CSP também pode ser considerado como um problema de contenção de consulta conjuntiva . [16]

problemas de função

Uma 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. 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 generalizado ainda mais 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 está em FP ou #P-difícil. [17]

variantes

O modelo clássico de Problema de Satisfação de Restrições define um modelo de restrições estáticas e inflexíveis. Esse modelo rígido é uma deficiência que dificulta a representação fácil de problemas. [18] 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 [19] ( 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 devido ao ambiente. [20] 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 usadas 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 usadas como heurísticas para guiar 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 estágio da busca para representar o aprendizado de um grupo inconsistente 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 rígidas, significando que são imperativas (cada solução deve satisfazer todas elas) e inflexíveis (no sentido de que devem ser completamente satisfeitas ou então serão completamente violadas). CSPs flexíveis relaxam essas suposições, relaxando parcialmente as restrições e permitindo que a solução não cumpra todas elas. Isso é semelhante às preferências no planejamento baseado em preferências . Alguns tipos de CSPs flexíveis incluem:

  • MAX-CSP, onde um número de restrições pode ser violado, e a qualidade de uma solução é medida pelo número de restrições satisfeitas.
  • Weighted CSP , 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 do modelo Fuzzy CSP como relações fuzzy em que 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 [21], cada variável de restrição é considerada como tendo uma localização geográfica separada. Fortes restrições são colocadas na 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 – incl. opção de publicar acesso aberto". springer. com . Recuperado 2019-10-03 .
  3. ^ Chandra, Satish, e outros. "Inferência de tipo para compilação estática de JavaScript." ACM SIGPLAN Avisos 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 através 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. pp. 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 2009-02-06 no Wayback Machine Ian Miguel – slides.
  8. ^ Demetriou, George C. "Desambiguação lexical usando manipulação de restrição 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. "Contas de satisfação de restrição de compreensão lexical e de sentença." 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." Jornal de Tecnologia da Informação Teórica e Aplicada 86 (2). 2016. 327–331.
  11. ^ Aplicando abordagem de satisfação de restrição 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 de satisfação de restrição distribuída dinâmica 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 Russell; Peter Norvig (2010). Inteligência Artificial: Uma Abordagem Moderna . Prentice Hall. pág. Capítulo 6. ISBN 9780136042594.
  14. ^ Otimização híbrida: os dez anos do CPAIOR . Milano, Michela., Van Hentenryck, Pascal., Conferência Internacional sobre Integração de Técnicas AI e OR em Programação Restritiva para Problemas de Otimização Combinatória. Nova York: Springer. 2011. ISBN 9781441916440. OCLC  695387020.{{cite book}}: Manutenção CS1: outros ( link )
  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 para Máquinas de Computação . pp. 655–664. arXiv : 1011.2894 . Código Bib : 2010arXiv1011.2894B. doi : 10.1145/1993636.1993724. ISBN 978-1-4503-0691-1. S2CID  47097319.
  16. ^ Kolaitis, Phokion G.; Vardi, Moshe Y. (2000). "Contenção de consulta conjuntiva e satisfação de restrição". Journal of Computer and System Sciences . 61 (2): 302–332. doi : 10.1006/jcss.2000.1713 .
  17. ^ Cai, Jin-Yi; Chen, Xi (2012). "Complexidade de contar CSP com pesos complexos". Anais do Quadragésimo Quarto Simpósio Anual da ACM sobre Teoria da Computação (STOC '12) . pp. 909–920. arXiv : 1111.2384 . doi : 10.1145/2213977.2214059. ISBN 978-1-4503-1245-5. S2CID  53245129.
  18. ^ Miguel, Ian (julho de 2001). Satisfação de restrições dinâmicas flexíveis 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. 
  19. ^ Dechter, R. e Dechter, A., Manutenção de crenças em redes dinâmicas de restrição arquivadas em 17/11/2012 no Wayback Machine In Proc. de AAAI-88, 37-42.
  20. ^ Reuso de solução em problemas de satisfação de restrição dinâmica, Thomas Schiex
  21. ^ Duffy, KR; Leith, DJ (agosto de 2013), "Satisfação de restrição descentralizada", IEEE/ACM Transactions on Networking, 21(4) , vol. 21, pp. 1298–1308, arXiv : 1103.3240 , doi : 10.1109/TNET.2012.2222923, S2CID  11504393

Leitura adicional

  • Uma rápida introdução à satisfação de restrições no YouTube
  • Steve Minton; Andy Philips; Mark D. Johnston; Philip Laird (1993). "Minimizando Conflitos: Um Método de Reparo Heurístico para Problemas de Satisfação de Restrições e 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. S2CID  14830518.
  • Tsang, Edward (1993). Fundamentos da Satisfação das Restrições. Imprensa Acadêmica. ISBN  0-12-701610-4
  • Chen, Hubie (dezembro de 2009). "Um encontro de lógica, complexidade e álgebra". ACM Computing Surveys . 42 (1): 1–32. arXiv : cs/0611018 . doi : 10.1145/1592451.1592453. S2CID  11975818.
  • Dechter, Rina (2003). Processamento de restrições. Morgan Kaufmann. ISBN  1-55860-890-7
  • Apt, Krzysztof (2003). Princípios de programação por restrições . Cambridge University Press. ISBN 9780521825832. ISBN  0-521-82583-0
  • Lecoutre, Christophe (2009). Redes de Restrições: Técnicas e Algoritmos. ISTE/Wiley. ISBN  978-1-84821-106-3
  • Tomás Feder, Satisfação de restrições: uma perspectiva pessoal, manuscrito.
  • Arquivo de restrições
  • Benchmarks CSP Satisfíveis Forçados do Modelo RB
  • 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 dando um bom levantamento da teoria e questões de implementação