Aula Prática 3 – Problemas de satisfação de restrições

Matéria da aula T7 (problemas de satisfação de restrições). Os exercícios são para trabalho autónomo, individualmente ou em grupos de dois. Os exercícios que ficarem por resolver na aula devem ser resolvidos em casa — o 8 e, se faltar tempo, o 7 são os candidatos naturais. (As secções 5.3.3, 5.3.4 e 5.5.2 do livro — salto atrás, aprendizagem de restrições, decomposição em árvore — não fazem parte da matéria e não aparecem aqui; o caderno tem um bloco à parte para quem quiser ir além.)

Convenções

Toda a terminologia é a do AIMA, 4.ª edição (capítulo 5 da edição global, 6 da americana) e a dos slides T7.

• Na procura com retrocesso (fig. 5.5), salvo indicação em contrário: a variável é escolhida pelo MRV (menos valores restantes — a variável mais constrangida), com desempate pelo grau (a variável mais constrangedora) e, se o empate persistir, pela ordem alfabética; os valores tentam-se por ordem alfabética / crescente; e depois de cada atribuição corre-se o MAC (INFERENCE). Conta-se um retrocesso de cada vez que uma atribuição {X = x} é desfeita — porque a inferência esvaziou um domínio ou porque o ramo abaixo dela falhou.
• No min-conflitos, o valor escolhido para a variável é o que viola menos restrições com os valores actuais das outras variáveis; quando o enunciado pede uma iteração completa, a variável é a que participa em mais restrições violadas, com empates desfeitos pela ordem das variáveis, e empates entre valores pela ordem dos valores.

Exercício 1 – Modelar um problema como CSP

Cinco amigos — Ana (A), Bruno (B), Carla (C), Duarte (D) e Eva (E) — vão sentar-se à volta de uma mesa redonda com cinco lugares, numerados de 1 a 5 (o lugar 5 é vizinho do 4 e do 1). Há três exigências: a Eva fica no lugar 1, junto à porta; a Ana e o Bruno querem ficar lado a lado; a Carla e o Duarte não querem ficar lado a lado.

(a) Formule o problema como CSP: variáveis, domínios e restrições — escreva cada restrição como um par ⟨escopo, rel⟩ (a relação como fórmula e, para «lado a lado», por extenso). Classifique cada restrição como unária, binária ou global. Há outra formulação possível (com os lugares como variáveis)? Qual prefere, e porquê?

(b) Desenhe o grafo de restrições. Como representa a restrição global? Em quantas restrições binárias ≠ se desdobra e qual é o grafo resultante?

(c) Quantas atribuições completas há? Compare com o número de folhas da procura «ingénua» (que escolhe qualquer variável em cada nó) e explique a diferença — comutatividade.

(d) Imponha a restrição unária (consistência de nó) e, em seguida, aplique a verificação para a frente à atribuição E = 1. Que domínios ficam? E que domínios teria deixado o AC-3, a partir dos mesmos domínios? Porquê?

(e) Quantas soluções tem o problema? Encontre-as por raciocínio (sem procura) e diga que simetria as relaciona.

(f) Resolva com a procura com retrocesso das convenções a partir dos domínios obtidos após a imposição da restrição unária (consistência de nó). Quantos retrocessos e por que é que as primeiras tentativas falham?

Exercício 2 – Colorir um mapa

Figura 1 — Grafo de restrições de uma parte do mapa da Europa: Alemanha (DE), Áustria (AT), Suíça (CH), Itália (IT) e Eslovénia (SI). Países ligados por uma aresta são vizinhos.

Pretende-se colorir cada país com uma de três cores — (B)ege, (G)rená ou (R)osa — de modo a que países vizinhos tenham cores diferentes.

(a) Formule o problema como um CSP: variáveis, domínios e restrições. O que representam os nós e as arestas da figura? Indique o grau de cada variável. Quantas atribuições completas existem, e quantas delas são soluções?

(b) Suponha que a cor rosa já foi atribuída a IT. Aplique a verificação para a frente e indique as cores que ficam em cada domínio.

(c) Suponha agora que foram atribuídas CH = bege e DE = grená, sem qualquer propagação. Aplique o AC-3: indique os arcos que apagam valores, pela ordem em que são tratados, e os domínios finais. Compare com o que a verificação para a frente teria feito depois das mesmas duas atribuições.

(d) Considere os domínios abaixo, obtidos depois de escolher AT = grená e propagar. Que variáveis poderia a heurística MRV escolher a seguir? E a heurística do grau? Qual é escolhida de acordo com as convenções da aula?

(e) Considere a atribuição completa (e inconsistente) AT = grená, CH = bege, DE = bege, IT = bege, SI = grená. A variável CH acabou de ser escolhida pelo min-conflitos. Que cor lhe é atribuída? Apresente o número de conflitos de cada cor.

(f) Resolva o problema com a procura com retrocesso das convenções (MRV, grau, ordem alfabética; MAC depois de cada atribuição; cores por ordem alfabética). Indique, em cada passo, a variável escolhida e porquê, o valor atribuído e os domínios que o MAC deixa. Qual é a solução e quantos retrocessos houve?

(g) Repita sem inferência nenhuma e com a ordem estática AT, CH, DE, IT, SI: quantos valores são tentados e rejeitados por serem inconsistentes com a atribuição corrente? Quantos retrocessos?

Exercício 3 – Um horário

Uma escola tem que marcar cinco unidades curriculares, A, B, C, D e E, no mesmo dia. Há três horários — T1 de manhã, e T2 e T3 à tarde, seguidos, com a pausa de almoço entre T1 e T2 — e duas salas, R1 (o anfiteatro) e R2 (o laboratório). Cada sala só recebe uma aula por horário, e há mais requisitos:

• A e E precisam do anfiteatro; C precisa do laboratório.
• O docente de B tem que sair antes de T3; o de D só chega à tarde.
• O docente de C quer a sua sala livre nos horários imediatamente antes e depois da sua aula (a pausa do almoço conta como sala livre).
• Os alunos de E precisam da matéria de B: B tem que ocorrer antes de E.
• B e D usam material que fica montado numa sala: têm que ser na mesma sala.
• C e D têm o mesmo docente.

(a) Formule como CSP: variáveis, domínios (cada valor é um par horário/sala, escrito T1R1, T1R2, …) e restrições. Separe as restrições unárias das binárias. Quantas atribuições completas há?

(b) Imponha as restrições unárias (consistência de nó): para cada variável, indique os valores que saem do domínio.

(c) A partir dos domínios de (b), suponha que se atribui C = T2R2. Aplique a verificação para a frente e indique os valores removidos.

(d) Em vez da verificação para a frente, aplique o AC-3 depois de C = T2R2. O que acontece? Explique a diferença para (c).

(e) Suponha agora que se atribui C = T1R2 (a partir dos domínios de (b)) e se aplica o AC-3. Que valores são removidos? Que variável escolhe a seguir a heurística MRV?

(f) Considere a atribuição completa inconsistente A = T2R1, B = T2R2, C = T1R2, D = T3R1, E = T1R1. Que restrições viola? A variável D foi escolhida pelo min-conflitos: que valor lhe é atribuído?

(g) A partir dos domínios de (b), resolva o problema com a procura com retrocesso das convenções. Qual é a solução? Quantos retrocessos?

Exercício 4 – O AC-3 em pormenor, e os seus limites

Figura 2 — Três variáveis inteiras, X, Y e Z, com domínio {1, 2, 3, 4, 5}, e três restrições: X < Y, Y < Z e Z ≤ 2X.

(a) Quantos arcos tem a fila inicial do AC-3? Escreva-os pela ordem das variáveis — primeiro os arcos que saem de X, depois os de Y, depois os de Z.

(b) Execute o AC-3 passo a passo: para cada arco tirado da fila, diga o que REVISE apaga e que arcos voltam à fila (o arco é sempre tirado da frente da fila, e os que voltam vão para o fim). Quais são os domínios finais? Quantas vezes é que cada arco foi tratado?

(c) Quais são as soluções do problema? Todos os valores que sobraram em (b) aparecem em alguma solução?

(d) Considere agora X, Y ∈ {1, 2}, Z ∈ {1, 2, 3} e as restrições X ≠ Y, Y ≠ Z e X ≠ Z. Aplique o AC-3. O que conclui sobre os valores 1 e 2 de Z? Que ferramenta dos slides apanharia isto de imediato?

(e) Colorir WA, NT e SA (que se tocam duas a duas) só com duas cores: mostre que o problema é consistente de arco e não tem solução. Que nível de consistência o detecta?

(f) No pior caso, quantas vezes pode um mesmo arco (Xᵢ, Xⱼ) entrar na fila? Deduza daí a complexidade O(cd³) do AC-3.

Exercício 5 – A Austrália: verificação para a frente, MAC e as heurísticas

Figura 3 — O grafo de restrições da Austrália (fig. 5.1 dos slides); as cores são vermelho (r), verde (g) e azul (b), por esta ordem.

(a) Refaça a fig. 5.7 dos slides: aplique a verificação para a frente depois de cada uma das atribuições WA = vermelho, Q = verde e V = azul, indicando os sete domínios em cada linha. Onde é que a procura se apercebe de que este ramo falhou?

(b) Repita com o MAC: depois de WA = vermelho e, sobretudo, depois de Q = verde, mostre a fila de arcos do AC-3 e o momento em que a inconsistência é detectada. Porque é que o MAC é «estritamente mais poderoso» do que a verificação para a frente?

(c) Resolva o problema com verificação para a frente + MRV (desempate pelo grau e pela ordem WA, NT, SA, Q, NSW, V, T) a partir do zero. Que variável é escolhida primeiro, e porquê? Há necessidade de usar a procura com retrocesso?

(d) Depois de WA = vermelho e NT = verde, a próxima variável é Q. Que cor prefere a heurística do valor menos restritivo? Justifique contando o que cada cor apaga aos vizinhos.

(e) Suponha WA = vermelho e NSW = vermelho, e aplique o AC-3. Que domínios ficam? A atribuição é consistente? O que é que o AC-3 «não vê», e que restrição global o veria?

(f) Com a ordem estática WA, NT, Q, NSW, V, SA, T da fig. 5.6 e sem inferência, quantos valores inconsistentes são tentados até à solução? E com verificação para a frente?

Exercício 6 – Min-conflitos

Figura 4 — Quatro rainhas, uma por coluna: o estado {Q1 = 1, Q2 = 3, Q3 = 1, Q4 = 2} (a linha 1 é a de baixo).

(a) Formule as 4 rainhas como CSP com variáveis Q1–Q4 (a linha de cada coluna). Quantas restrições binárias há?

(b) No estado da figura, escreva em cada casa o número de rainhas que a atacariam (o número de conflitos de cada valor), como na fig. 5.8 dos slides. Que variáveis estão em conflito?

(c) Execute o min-conflitos a partir desse estado com as convenções (variável com mais conflitos, desempate pela ordem; valor com menos conflitos, desempate pelo menor). Quantos passos até à solução?

(d) Aplique o min-conflitos ao problema de (e) do exercício 4 — WA, NT e SA com duas cores — a partir de WA = vermelho, NT = vermelho, SA = azul. O que acontece? Que propriedade do algoritmo é esta?

(e) Volte ao mapa do exercício 2 e à atribuição de (e) — AT = grená, CH = bege, DE = bege, IT = bege, SI = grená. Todas as restrições têm peso 1. Faça um passo de ponderação de restrições: qual é o par variável/valor que minimiza o peso total das restrições violadas (desempate pela ordem das variáveis e das cores)? Que pesos são incrementados a seguir, e para que serve isso?

(f) Porque é que o min-conflitos resolve um milhão de rainhas em cerca de 50 passos? Que característica do problema é responsável?

Exercício 7 – A estrutura do problema

Figura 5 — Oito tarefas, A a H, a escalonar em quatro períodos, {1, 2, 3, 4}; cada aresta tem a restrição que liga as duas tarefas.

(a) O grafo tem duas componentes ligadas. O que é que isso permite? Se cada componente tiver c variáveis, num total de n, qual é o trabalho total, e como se compara com dⁿ?

(b) Aplique o AC-3 aos domínios iniciais (basta indicar os domínios finais e as remoções mais importantes).

(c) A componente A–F não é uma árvore. Indique todos os conjuntos de corte de tamanho 1. Use S = {C}: para cada valor de C que sobrou em (b), pela ordem crescente, apague dos vizinhos os valores incompatíveis e aplique o TREE-CSP-SOLVER ao resto (raiz A, ordenação topológica por pesquisa em largura a partir de A, com os vizinhos por ordem alfabética), mostrando as chamadas MAKE-ARC-CONSISTENT. Qual é a solução?

(d) Compare o custo do condicionamento por conjunto de corte, O(dᶜ (n − c) d²), com o do retrocesso puro, O(dⁿ), para a componente A–F.

(e) Num CSP geral com n variáveis e d valores, qual é o número máximo de retrocessos da procura com retrocesso: (i) sem heurísticas; (ii) com MRV, grau e AC-3; (iii) num CSP em árvore com AC-3 e uma ordenação de variáveis óptima?

Exercício 8 – Verdadeiro ou falso

Para cada afirmação, diga se é verdadeira ou falsa e justifique numa frase.

(a) Um CSP com restrições apenas unárias e binárias pode sempre representar-se por um grafo de restrições, e qualquer CSP de domínio finito pode reduzir-se a um CSP binário.

(b) Se o AC-3 deixar algum domínio vazio, o CSP não tem solução.

(c) Se o AC-3 não deixar nenhum domínio vazio, o CSP tem solução.

(d) Depois de impor consistência de arco como pré-processamento, a verificação para a frente durante a procura mantém a consistência de arco de todas as variáveis.

(e) A heurística MRV escolhe a variável com mais valores legais, para maximizar as hipóteses de sucesso.

(f) Se se quiser encontrar todas as soluções, a ordem dos valores é irrelevante.

(g) A procura com retrocesso escolhe uma variável por nó porque os CSPs são comutativos; sem isso a árvore teria n! · dⁿ folhas.

(h) O MAC chama o AC-3 com a fila inicial reduzida aos arcos (Xⱼ, X) para a variável X acabada de atribuir, e propaga a partir daí.

(i) Um CSP com estrutura de árvore resolve-se em tempo linear no número de variáveis.

(j) Com um conjunto de corte de tamanho c, o condicionamento por conjunto de corte custa O(dᶜ · (n − c) · d²) e corre em memória linear.

(k) A consistência de caminho pode detectar inconsistências que a consistência de arco não detecta, e um CSP fortemente n-consistente resolve-se sem retrocesso — mas impor a forte n-consistência custa tempo exponencial em n.

(l) O min-conflitos é completo: se um CSP tem solução, encontra-a.