Satisfcao de restricao

Constraint Satisfaction Problem
(Problemas de Satisfação de Restrições) Membros: Cleber T. Kawamorita Gabriel S. Sorrentino Willian F. Mendes Prof.: Cesar Marcondes

Constraint Satisfaction Problem
● ● ● ● ● ● Constraint Satisfaction Problem Representação Brute-Force Search Intelligent Backtracking Constraint Recording Heuristic Repair

Constraint Satisfaction Problem
● Solução é estado que: ○ satisfaz a restrição dada ○ atribui valor para todas as variáveis ○ descrição do estado final é dada pelas características. ● Foco não é no custo dos caminhos como no single-agent path-finding ou two-player games.

Benefícios do CSP
● Utiliza-se a mesma estrutura representacional para ● ● modelar-se problemas diferentes. Validação de objetivo pode ser definido da mesma forma para todos os CSP que forem igualmente representados. Heurísticas efetivas e genéricas podem ser desenvolvidas sem nenhum conhecimento sobre o domínio dos problemas.

Representação
● Conjunto de variáveis ○ Domíno de valores ● Restrição ○ unária binária ○ ternária ● Cada represenação possui o seu dual ○ Inversão de restrição e variável ● Escolher representação mais fácil de resolver

Representação
X: { a, b }

X
(X,Y): { (b, c), (b, d) } (X,Z): { (b, e), (a, f) }

Y
Y: { c, d }

(Y,Z): { (c, e), (d, f) }

Z
Z: { e, f }

Exemplo
● Nenhuma região vizinha deve ter a mesma cor ● Queremos colorir cada região do mapa abaixo com as cores vermelho, verde e azul

Exemplo
● 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)} ● 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

Exemplo
WA, NT, Q, NSW, V, SA, T: { Vermelho, Verde, Azul }

Restrição: {