o 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.