Problemas de satisfação de restrições

Satisfação de Restrições
Capítulo 5 http://aima.cs.berkeley.edu/newchap05.pdf Sumário




Problemas de Satisfação de Restrições (CSPs) Procura com Retrocesso para CSPs
 

Ordenação de variáveis e de valores Propagação de informação nas restrições

 

Procura Local para CSPs Estrutura dos CSPs

Problemas de Satisfação de Restrições


Problema de Procura Tradicional:




CSP:
 

estado é uma “caixa preta” – qualquer estrutura de dados que suporte função sucessores, função heurística, e teste objectivo estado é definido por variáveis Xi com valores do domínio Di Teste objectivo é um conjunto de restrições que especificam combinações possíveis de valores para subconjuntos de variáveis



Possível utilização de algoritmos genéricos mais poderosos do que os tradicionais algoritmos de procura

Exemplo: Coloração de Mapa

   

Variáveis WA, NT, Q, NSW, V, SA, T Domínios Di = {vermelho, verde, azul} Restrições: regiões adjacentes com cores diferentes e.g., WA ≠ NT, ou (WA,NT)  {(vermelho,verde), (vermelho,azul), (verde,vermelho), (verde,azul), (azul,vermelho), (azul,verde)}

Exemplo: Coloração de Mapa



Soluções são atribuições completas e consistentes, e.g., WA = vermelho, NT = verde, Q = vermelho, NSW = verde, V = vermelho, SA = azul, T = verde

Grafo de Restrições
 

CSP binário: cada restrição relaciona duas variáveis Grafo de restrições: nós são variáveis, arcos são restrições

Tipos de Variáveis em CSPs


Variáveis discretas


Domínios finitos (podem ser enumerados)
 

n variáveis, domínio dimensão d  O(dn) atribuições completas e.g., CSPs Booleanos, incluindo satisfação Booleana - SAT (NPcompleto) inteiros, strings, etc. e.g., escalonamento de tarefas, variáveis têm datas de início/fim para cada tarefa necessidade de uma linguagem de restrições




Domínios infinitos (não podem ser enumerados)
 





Variáveis contínuas


e.g., InícioTarefa1 + 5 ≤