Satisfação de problemas restritos

(CSP)Inteligência Artificial

Prof. Esp. Cristiano José Cecanho

Conteúdo

• Exemplos CSP.• Busca geral aplicada a CSP.• Backtracking.• Checagem do próximo.• Heurística para CSP.

CSP

• Problema de busca padrão:– Estado é uma “caixa-preta” – qualquer estrutura de dados antiga que

suporta teste de objetivo, avaliação e sucessor.

• CSP: – Estado é definido por variáveis Vi com valores para domínios Di.

– O teste de objetivo é configurado pela especificação da restrições avaliáveis por valores semi-configurados por variáveis.

• Um simples exemplo de uma representação de forma normal.• Permite que algoritmos de uso geral com mais poder do que

os algoritmos de busca padrão.

Exemplo: jogo com 4 rainhas

• Assuma uma rainha por coluna. Qual linha será alocada para cada uma?– Variáveis: Q1, Q2, Q3, Q4.

– Domínio: Di = {1, 2, 3, 4}.

– Restrições: • Qi ≠ Qj (não pode ser a mesma linha).

• |Qi – Qj| ≠ |i – j| (ou diagonal igual).

– Transpor cada restrição em um conjunto de valores permitidos para suas variáveis.

– Valores para (Q1, Q2) são (1, 3) (1, 4) (2, 4) (3, 1) (4, 1) (4, 2)

Grafo de restrições

• CSP binário: cada restrição relata mais de duas variáveis.

• Grafo de restrições: nós são variáveis, os arcos mostram restrições.

Retome o problema com 8 rainhas

Variáveis: ??Domínio: ??Restrições: ??

Um exemplo de cripto aritmética

• Variáveis:– DEMNORSY

• Domíno:– {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

• Restrições:– M ≠ 0, S ≠ 0 (restrições unárias).– Y = D + E ou Y = D + E – 10, etc.– D ≠ E, D ≠ M, D ≠ N, etc.

Exemplo: Colorir mapa

• Colorir um mapa para que nenhum país adjacente tenha a mesma cor.

• Variáveis: – Países Ci

• Domínio:– {Vermelho, Azul, Verde}

• Restrições:– C1 ≠ C2, C1 ≠ C5, etc.

• Grafo de restrições:

Mundo real com CSP

• Problemas atribuídos:– Quem ensina que classe.

• Problemas com calendários:– Qual classe é oferecida, quando e onde?

• Configuração de hardware.• Planilhas.• Programação de transporte.• Programação de fábrica.• Planta baixa.• Obs: observar que muitos problemas do mundo real envolvem variáveis

de valor real.

Aplicando a busca padrão

• Vamos começar com a abordagem direta, muda, de forma a corrigi-lo.

• Estados são definidos pelos valores atribuídos até agora.

• Estado inicial: todas as variáveis não são atribuídas.• Operadores: atribuir um valor a uma variável não

atribuída.• Teste objetivo: todas as variáveis atribuídas, sem

restrições violadas.• Note que isto é similar a todos CSP!

Implementação

• O CSP estado mantém o controle de quais variáveis têm valores até o momento, cada variável tem um domínio e um valor atual.

• Restrições podem ser representadas:– Explicitamente: como valores permitidos, ou– Implicitamente: por uma função que testa para satisfação da

restrição.

Busca padrão aplicada a colorização de mapas

Exercício• A figura abaixo mostra um retângulo formado por 40 ladrilhos

retangulares iguais de três tipos: ladrilhos brancos, ladrilhos cinza e ladrilhos metade branco e metade cinza. Com esses ladrilhos foi formada a letra M.

• A porcentagem da superfície do retângulo que é branca é igual a:a) 40%b) 50%c) 60%d) 63,33%e) 53,33%

Complexidade de aproximação muda

• Máximo de profundidade do espaço m = ??• Profundidade do estado solução d = ??• Algoritmo de busca para uso ??• Fator de ramificação b = ??

• Este pode ser realmente melhorado, notando o seguinte:1. Ordem de atribuição é irrelevante, portanto, muitos

caminhos são equivalentes.2. As missões adicionadas não podem corrigir uma restrição

violada.

Complexidade de aproximação muda

• Máximo de profundidade do espaço m = ?? n (número de variáveis).

• Profundidade do estado solução d = ?? n (todas as variáveis são atribuídas).

• Algoritmo de busca para uso ?? Busca em profundidade.• Fator de ramificação b = ??

• Este pode ser realmente melhorado, notando o seguinte:1. Ordem de atribuição é irrelevante, portanto, muitos caminhos são

equivalentes.2. As missões adicionadas não podem corrigir uma restrição violada.

Busca por backtracking

• Usa busca em profundidade, mas:1. Fixar a ordem de atribuição.

(pode ser feito em função SUCCESSORS).

2. Verificar se há violações de restrição.

• A violação de restrição de verificação pode ser implementada de duas maneiras:1. Modificar SUCCESSORS para permitir valores únicos que são

permitidos, dado os valores já atribuídos, ou.2. Conferir restrições que são satisfeitas antes de expandir um estado.

• Busca Backtracking é o algoritmo básico para um CSP desinformado.

• Pode resolver n-rainhas para n = 15.

Verificação para frente

• Ideia: acompanhar os valores restante legais para as variáveis não atribuídas, Terminar a pesquisa quando qualquer variável não tem valores legais:

• Coloração de mapa simplificado:

• Pode resolver n-rainhas até n = 30.

Heurísticas para CSP• Mai decisões inteligentes em:

– Qual o valor a ser escolhido para cada variável.– Qual variável para atribuir ao próximo.

• Dado C1 = Vermelho, C2 = Verde, escolher C3 = ??

• Dado C1 = Vermelho, C2 = Verde, qual o próximo ??

• Pode resolver n-rainhas para n = 100.

Heurísticas para CSP• Mai decisões inteligentes em:

– Qual o valor a ser escolhido para cada variável.– Qual variável para atribuir ao próximo.

• Dado C1 = Vermelho, C2 = Verde, escolher C3 = ??– C3 = Verde: menor restrição de valor.

• Dado C1 = Vermelho, C2 = Verde, qual o próximo ??– C5 : maior restrição de calor.

• Pode resolver n-rainhas para n = 1000.

Algoritmos iterativos para CSP

• Hill-climbing, simula reaver, tipicamente trabalha com estados completos, todas as variáveis são permitidas.

• Para aplicar CSP:– Todos os estados com restrições insatisfeitas;– operadores realocam os valores das variáveis.

• Seleção de variáveis: randomicamente seleciona qualquer variável em conflito.

• Heurísticas de min-conflicts:– Escolhe o valor que viola a restrição menor.– Hill-climbing com h(n) = número total de restrições violadas.

Exemplo: 4 - rainhas

• Estado: 4 rainhas em 4 colunas (44 = 256 estados).

• Operadores: mover a rainha para uma coluna.• Objetivo teste: não pode atacar.• Avaliação: h(n) = número de ataques.

Exercício

• A tabela mostra o número de funcionários de uma empresa presentes ao trabalho durante os cinco dias de uma semana.

• Na quinta-feira não houve faltas. A média diária de faltas de funcionários, nessa semana, foi aproximadamente:

a) 18b) 12c) 26d) 30e) 20

Dias da semana Funcionários presentes

2ª 216

3ª 204

4ª 228

5ª 240

6ª 180

Performance de min-conflicts

• Dado um estado inicial aleatório, pode resolver n-rainhas em tempo quase constante para n arbitrário com alta probabilidade (n = 10.000.00).

• O mesmo parece ser verdadeiro para qualquer CSP gerado aleatoriamente, exceto num intervalo estreito da relação.

Estrutura de árvore com CSP

• Teorema: se o gráfico não tem restrição de loops, o CSP pode ser resolvido em O (n | D | 2) tempo.

• Comparado com o CSP geral, o tempo de pior caso é O (| D | n).

• Esta propriedade também se aplica ao raciocínio lógico e probabilístico: como exemplo importante da relação entre restrições sintáticas e complexidade de raciocínio.

Algoritmo com estrutura de árvore CSP

• Passo básico chamado de filtragem:

• FILTER(Vi, Vj)

– Remove valores de Vi que são inconsistentes com todos os valores de Vj.

• Exemplo de filtragem:

Algoritmo

1. Ordena os nós em largura iniciando por qualquer nó.

2. Para j = n até 1, aplicar FILTER(Vi, Vj) quando Vi é parente de Vj.

3. Para j = 1 até n, escolher um valor válido para Vj dado o calor do parente.

Exercícios• Observe que cada um dos dois primeiros pares de palavras abaixo, a palavra

da direita foi formada a partir da palavra da esquerda, utilizando-se um mesmo critério.

• DIANA –ANDA• CRATERA – ARCA• BROCHES – ?

• Com base nesse critério, a palavra que substitui corretamente o ponto de interrogação é:

a) RECO.b) ROBE.c) SECO.d) SEBO.e) SOBE.