Problemas de satisfação de restrições

Um problema de satisfação de restrições, ou CSP, descreve um conjunto de escolhas e as regras que as conectam. Seu estado é uma representação fatorada: você pode examinar variáveis individuais e seus valores e depois reutilizar métodos gerais de redução de domínios e busca.

Variáveis, domínios e restrições

Uma variável nomeia algo a ser escolhido. Seu domínio lista seus valores permitidos. Uma restrição especifica quais combinações podem ocorrer juntas. Para as oficinas A e B, seja cada valor um horário de $\{1,2,3\}$. A regra “A ocorre antes de B” tem escopo $\{A,B\}$ e relação $\{(1,2),(1,3),(2,3)\}$. Escrever $A<B$ expressa a mesma relação de forma compacta.

O escopo nomeia as variáveis envolvidas; a relação fornece as tuplas de valores permitidas. Confundi-los leva a um modelo em que “vermelho” se torna uma variável. Na coloração de mapas, as regiões são variáveis e as cores são valores.

O que constitui uma solução?

Uma atribuição dá valores a variáveis. Três verificações descrevem sua situação:

• Ela é parcial se algumas variáveis não têm valor.
• Ela é completa se toda variável tem um valor.
• Ela é consistente se não viola nenhuma restrição entre as variáveis atribuídas.

Uma solução deve ser completa e consistente. Apenas com $A=2$, a atribuição é consistente, mas parcial. Estendê-la com $B=1$ torna-a completa e inconsistente. Escolher $B=3$ produz uma solução para este exemplo de duas variáveis. Uma atribuição parcial consistente ainda pode não ter nenhuma complementação possível: variáveis sem valor podem ficar sem escolhas compatíveis.

Interprete um grafo de restrições

Para um CSP binário, desenhe um nó por variável e uma aresta para cada par sujeito a uma restrição. Em um mapa simplificado da Austrália, as variáveis são WA, NT, SA, Q, NSW, V e T, cada uma com domínio {vermelho, verde, azul}. Os pares vizinhos são WA–NT, WA–SA, NT–SA, NT–Q, SA–Q, SA–NSW, SA–V, Q–NSW e NSW–V. Cada aresta exige cores diferentes.

Uma solução é WA vermelho, NT verde, SA azul, Q vermelho, NSW verde, V vermelho e T vermelho. Verifique cada aresta, incluindo SA–V. T não tem arestas, então sua cor é independente da parte continental. Há 6 colorações da parte continental e 3 escolhas para T, produzindo 18 soluções. Uma restrição que envolve várias variáveis precisa de uma representação em hipergrafo; um nó adicional de restrição pode se conectar a cada variável em seu escopo.

Domínios e tamanho da busca

Um domínio discreto finito é uma lista fixa, como três cores. Um domínio discreto infinito pode conter todos os horários de início inteiros não negativos. Um domínio contínuo pode conter horários com valores reais. Os dois últimos precisam de representações e métodos adequados a esses domínios; a programação linear trata restrições lineares contínuas.

Para $n$ variáveis com $d$ valores cada, há $d^n$ atribuições completas. O mapa tem $3^7=2187$ candidatas antes que as restrições eliminem alguma. CSPs finitos incluem problemas NP-completos, então não se conhece um método geral de resolução em tempo polinomial. Sua estrutura interna ainda permite reduzir domínios: o resolvedor pode descartar uma escolha sem listar todas as atribuições completas que a contêm. Apenas os valores finais determinam se a resposta é válida; o caminho usado para encontrá-los é irrelevante.

As restrições diferem no número de variáveis que conectam e em se estabelecem exigências ou preferências. Reconhecer essa estrutura ajuda você a escrever um modelo fiel e escolher métodos úteis de propagação.

Classifique o escopo

Uma restrição unária restringe uma variável. Se a oficina E não puder usar o horário 1, aplique $E\mathrm{\ne }1$ reduzindo seu domínio de $\{1,2,3\}$ para $\{2,3\}$ antes da busca. Uma restrição binária relaciona duas variáveis, como $A<B$ ou $A\mathrm{\ne }D$. Um CSP binário contém apenas restrições unárias e binárias.

Uma restrição de ordem superior envolve pelo menos três variáveis. Se as durações das tarefas X, Y e Z devem preencher 10 horas, escreva $X+Y+Z=10$. Com cada duração em $\{1,2,3,4,5\}$, a tupla $(2,3,4)$ falha, enquanto $(2,3,5)$ funciona. Verificar uma regra de ordem superior exige que os valores funcionem em conjunto.

Mantenha restrições globais úteis

Uma restrição global fornece uma regra nomeada sobre um grupo de tamanho variável. $\mathrm{Alldiff}(X_1,\dots ,X_k)$ exige valores diferentes para cada par. Seu conjunto de soluções é igual ao conjunto definido por $k(k-1)\mathrm{/}2$ desigualdades entre pares. Para nove células de Sudoku, isso equivale a 36 restrições binárias.

A forma global também dá ao resolvedor acesso ao raciocínio sobre o grupo. Três variáveis restritas a dois valores distintos não podem ser todas diferentes, embora cada par separadamente tenha uma atribuição compatível. Conjuntos de soluções iguais não garantem a mesma força de redução dos domínios.

Uma regra de capacidade também pode ser global. Aqui, $\mathrm{Atmost}(10,P_1,P_2,P_3)$ significa $P_1+P_2+P_3\le 10$: o número total de pessoas atribuídas às três tarefas não pode ultrapassar dez. Os argumentos representam quantidades que são somadas, então essa regra permite, por exemplo, $(3,4,3)$.

Converta uma restrição finita para a forma binária

Introduza uma variável auxiliar U cujos valores sejam as triplas permitidas para $X+Y+Z=10$. Um valor possível é $(2,3,5)$. Adicione três restrições binárias: o primeiro componente de U é igual a X, o segundo é igual a Y e o terceiro é igual a Z. Portanto, selecionar esse valor para U exige $X=2$, $Y=3$ e $Z=5$.

Toda tripla original válida corresponde a um valor de U, e toda atribuição consistente que envolve U produz uma tripla original válida. Essa construção permite que métodos binários tratem uma restrição finita de ordem superior. Seu custo é o domínio de tuplas potencialmente grande, motivo pelo qual os resolvedores frequentemente mantêm a regra global ou de ordem superior original.

Exigências e preferências

Com restrições flexíveis, a tarefa se torna um problema de otimização com restrições, ou COP: satisfaça todas as regras rígidas e minimize o custo total das preferências. Ramificação e limitação e busca local podem ser usadas para otimização.

Teste o modelo com uma atribuição reconhecidamente válida e outra reconhecidamente inválida. Uma desigualdade inventada entre oficinas sem relação elimina programações legítimas; uma restrição omitida sobre um instrutor compartilhado admite programações impossíveis. Preferências também exigem cuidado: transformar “tarde preferida” em “tarde obrigatória” pode eliminar toda programação viável.

Um modelo deve descrever as decisões de maneira suficientemente direta para que as regras sejam fáceis de expressar. Comece identificando o que deve ser escolhido, depois atribua domínios e traduza cada exigência sobre as variáveis que ela realmente envolve.

Construa uma programação de oficinas

Cinco oficinas que ocupam um horário cada compartilham três horários: 1 manhã, 2 meio-dia e 3 tarde. Seja A Fundamentos de Python, B Python Avançado, C Estatística, D Bancos de Dados e E Ética. Cada oficina é uma variável com domínio inicial $\{1,2,3\}$.

Participantes compartilhados exigem $A\mathrm{\ne }C$, $A\mathrm{\ne }D$, $C\mathrm{\ne }D$, $B\mathrm{\ne }C$, $C\mathrm{\ne }E$ e $D\mathrm{\ne }E$. Fundamentos deve preceder Avançado, então $A<B$. O instrutor de Ética chega ao meio-dia, então $E\mathrm{\ne }1$. Isso produz sete arestas binárias e uma regra unária; C tem quatro vizinhas.

A atribuição $A=2,B=3,C=1,D=3,E=2$ satisfaz todas as regras: cada par com participantes compartilhados tem horários diferentes, Fundamentos precede Avançado e Ética não ocorre no horário 1. Ela é a única atribuição válida entre as $3^5=243$ candidatas. As oficinas B e D podem usar o horário 3 porque nenhuma regra exige que sejam diferentes.

Escolher uma variável por horário faria de cada valor um subconjunto de oficinas, com até $2^5=32$ subconjuntos possíveis por horário. As regras teriam então de examinar esses conjuntos e garantir que cada oficina ocorresse uma vez. Escolher oficinas como variáveis mantém as restrições mais simples.

Expresse horários das tarefas e recursos compartilhados

Na programação de tarefas em oficina, use uma variável de horário de início para cada tarefa. Preparar leva 20 minutos, Analisar 40 e Relatar 30. Os horários de início são minutos inteiros não negativos. A ordem e o prazo de 120 minutos fornecem

Os inícios mais cedo são 0, 20 e 60. Trabalhar de trás para frente a partir do prazo fornece os inícios mais tardios 30, 50 e 90. Assim, as janelas são $S_P\in [0,30]$, $S_A\in [20,50]$ e $S_R\in [60,90]$.

Duas tarefas que compartilham uma máquina precisam de uma restrição disjuntiva: $S_X+d_X\le S_Y$ ou $S_Y+d_Y\le S_X$. Qualquer uma das tarefas pode ocorrer primeiro, mas elas não podem se sobrepor. Uma restrição simples de precedência imporia uma ordem específica e eliminaria a outra possibilidade.

Modele atribuições e quebra-cabeças

Para três relatórios atribuídos a três revisores, faça de cada relatório uma variável cujos valores são revisores. Use Alldiff se cada revisor ficar responsável por um relatório. Um conflito de interesse remove um revisor do domínio do relatório correspondente.

Para o problema das n rainhas, seja $Q_i$ a linha da rainha na coluna $i$. Uma rainha por coluna já está incorporada ao modelo. Para cada par, exija $Q_i\mathrm{\ne }{Q}_j$ e $\mathrm{\mid }{Q}_i-Q_j\mathrm{\mid }\mathrm{\ne }\mathrm{\mid }i-j\mathrm{\mid }$ para evitar ataques na mesma linha e diagonal. Para oito rainhas, isso reduz o espaço de candidatos de escolher 8 casas entre 64, $\mathrm{4.426.165.368}$ disposições, para $8^8=\mathrm{16.777.216}$ atribuições. Há 92 soluções.

Para Sudoku, as 81 variáveis das células têm domínios 1–9. Os números fornecidos impõem restrições unárias, e cada uma das 9 linhas, 9 colunas e 9 caixas impõe Alldiff.

Escolha as unidades de tempo menos detalhadas que ainda representem todos os inícios permitidos. Sessões que começam em horas cheias precisam de escolhas por hora; domínios minuto a minuto aumentariam o trabalho sem acrescentar uma programação útil. Termine separando preferências de regras rígidas e verificando um caso pequeno com resposta conhecida.

O retrocesso constrói uma atribuição parcial usando busca em profundidade. Ele escolhe uma variável, testa um valor e continua até encontrar uma solução ou precisar desfazer uma escolha. A busca mantém as escolhas anteriores úteis quando uma escolha posterior falha.

Ramifique por valores, uma variável por vez

Atribuir A e depois B produz a mesma atribuição final que atribuir B e depois A. Essa comutatividade significa que um resolvedor de CSP pode escolher uma variável em cada nível e ramificar sobre seus valores. Permitir todas as ordens de variáveis produziria $n!d^n$ folhas para apenas $d^n$ atribuições completas distintas. Para cinco variáveis com três valores, são 29.160 folhas em vez de 243.

A próxima variável pode depender dos domínios atuais. O que importa é escolher uma única próxima variável em um nó; a busca não precisa de ramos separados para todas as ordens possíveis de atribuição.

Acompanhe as etapas recursivas

1. Se a atribuição estiver completa e consistente, retorne-a.
2. Escolha uma variável sem valor.
3. Teste cada valor do domínio que seja consistente com a atribuição atual.
4. Faça uma chamada recursiva após adicionar um valor. Se a chamada recursiva falhar, remova essa atribuição e tente o próximo valor.
5. Se nenhum valor funcionar, retorne falha à chamada anterior.

O retrocesso simples testa uma restrição quando todas as variáveis em seu escopo têm valores. Com $A=1$ e B sem valor, $A<B$ não tem um par completo a rejeitar. Testar $B=1$ falha imediatamente. Esperar até que todas as variáveis tenham valores adiaria essa rejeição simples.

Acompanhe um beco sem saída

Use as regras das oficinas: $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$. Considere as variáveis na ordem A, B, C, D, E e teste os valores 1, 2, 3.

• Defina $A=1$. Rejeite $B=1$ e escolha $B=2$.
• Rejeite $C=1$ por causa de A e $C=2$ por causa de B; escolha $C=3$.
• Rejeite $D=1$ por causa de A; escolha $D=2$.
• E não tem valor permitido: 1 é proibido, 2 entra em conflito com D e 3 entra em conflito com C.

A falha em E devolve o controle a D. Seu próximo valor, 3, entra em conflito com C. C não tem valor posterior, então o controle retorna a B. Testar $B=3$ acaba produzindo outro beco sem saída com $A=1$. A busca então testa $A=2$ e chega a $A=2,B=3,C=1,D=3,E=2$. Nessa ordem, o retrocesso simples testa 32 valores candidatos ao todo, incluindo os rejeitados.

O que o método garante

Verificar restrições e armazenar o modelo também têm custos. A descrição de memória linear refere-se ao caminho de busca, enquanto a propagação também pode armazenar domínios e registros para desfazer alterações.

O retrocesso cronológico retorna à escolha mais recente. Variantes mais rápidas melhoram quatro decisões distintas: a próxima variável, a ordem de seus valores, as consequências inferidas após uma escolha e a escolha anterior a revisitar após uma falha. Essas melhorias reduzem o trabalho prático sem alterar o que constitui uma solução.

Uma boa ordenação pode revelar uma falha perto do topo de uma árvore de busca ou preservar escolhas úteis para mais tarde. A ordenação de variáveis e a de valores servem a propósitos diferentes, então a direção mais promissora difere entre elas.

Escolha a variável mais restrita

A heurística dos valores mínimos restantes (MRV) seleciona a variável sem valor que tem menos valores atualmente permitidos. Ela também é chamada de heurística da variável mais restrita ou de falhar primeiro. Um domínio quase esgotado provavelmente revelará uma contradição em breve. Se um domínio estiver vazio, o ramo falha imediatamente.

Conte os valores atuais após a redução, não os tamanhos iniciais dos domínios. Sem domínios armazenados, um resolvedor deve determinar quais valores originais ainda são consistentes com a atribuição antes de aplicar a MRV.

A heurística de grau desempata na MRV escolhendo a variável com mais restrições sobre outras variáveis sem valor. Essa escolha afeta mais decisões restantes. Vizinhas já atribuídas não contam para esse grau restante. No início do mapa da Austrália, os domínios iguais de três cores empatam, e as cinco vizinhas de SA dão a ela o maior grau.

Mantenha opções abertas ao escolher um valor

O valor menos restritivo (LCV) testa o valor que remove menos valores dos domínios de vizinhas sem valor. Avaliar valores candidatos acrescenta processamento, mas pode evitar um ramo malsucedido e custoso.

Com WA vermelho e NT verde, SA só pode ser azul, enquanto Q pode ser vermelho ou azul. Escolher Q azul esvaziaria o domínio de SA. Escolher Q vermelho remove vermelho de NSW e preserva o azul de SA. Portanto, a LCV testa Q vermelho.

Toda variável deve receber um valor em algum momento, o que torna útil testar cedo uma variável com poucas opções. Apenas um valor é necessário para completar uma primeira solução, o que favorece um valor que deixe espaço para outras decisões.

Combine ordenação com verificação antecipada

Na programação das oficinas, aplique $E\mathrm{\ne }1$ primeiro. E tem dois valores; A, B, C e D têm três cada uma. A MRV escolhe E. Teste $E=2$, e a verificação antecipada remove 2 de C e D.

C e D agora empatam com domínios $\{1,3\}$. C tem três vizinhas sem valor, A, B e D; D tem duas, A e C. A heurística de grau seleciona C. Escolha $C=1$, deixando $D_D=\{3\}$ e $D_A=D_B=\{2,3\}$. A MRV escolhe $D=3$, o que força $A=2$; a regra de precedência então produz $B=3$. Cinco atribuições encontram a solução sem retrocesso. A ordem fixa de variáveis com verificação antecipada exige 12 atribuições e chega a dois becos sem saída.

A ordenação preserva a completude porque altera a sequência de escolhas sem descartar ramos permitidos. A busca no pior caso continua exponencial. Ao enumerar todas as soluções ou provar a inviabilidade, todos os valores relevantes devem ser explorados em algum momento, então a vantagem da LCV de obter sucesso cedo é reduzida. Seu principal uso é encontrar uma primeira solução mais cedo.

Um beco sem saída frequentemente tem uma causa menor que toda a atribuição atual. O retrocesso com salto usa essa causa para decidir aonde retornar, e o aprendizado de restrições registra uma falha para que ela não precise ser descoberta novamente.

Encontre as escolhas que causaram a falha

No mapa da Austrália, considere a ordem de atribuição Q, NSW, V, T, SA. Sejam Q vermelho, NSW verde, V azul e T vermelho. SA é vizinha de Q, NSW e V, então as três cores são proibidas. Seu conjunto de conflitos é $\{Q,NSW,V\}$: variáveis anteriores cujas escolhas excluem seus valores.

O retrocesso cronológico tentaria alterar T. A Tasmânia não tem uma aresta com SA, então mudar sua cor não pode restaurar nenhuma opção para SA. O retrocesso com salto retorna a V, o membro atribuído mais recentemente no conjunto de conflitos, e ignora T.

Um conjunto de conflitos contém variáveis; uma combinação proibida de atribuições registra atribuições específicas. Essa distinção importa: outra cor para V pode corrigir a falha, embora V continue sendo vizinha de SA.

Propague um conflito por falhas anteriores

O retrocesso com salto simples usa o conjunto de conflitos direto da falha atual. O retrocesso com salto dirigido por conflitos leva informações por vários níveis que falharam. Quando uma variável X que falhou salta para Y, Y absorve o conjunto de conflitos de X com Y removida. Se Y esgotar todos os seus valores depois, seu conjunto combinado identificará uma causa mais atrás na atribuição.

Por exemplo, use a ordem WA, NSW, T, NT, Q, V, SA e comece com WA vermelho, NSW vermelho, T vermelho. WA e NSW não são vizinhas, então essa atribuição parcial é consistente. Suas escolhas removem vermelho de NT, Q e SA. Essas três regiões formam um triângulo, que não pode ser colorido usando apenas verde e azul.

Nenhuma escolha feita para T altera esse triângulo. As informações sobre conflitos podem voltar pelas tentativas que falharam e identificar WA e NSW como a causa subjacente. A busca retorna a NSW, a mais recente dessas duas decisões, em vez de gastar tempo mudando a cor de T.

Aprenda a combinação que falhou

Um resolvedor pode registrar $\{WA=\text{vermelho},NSW=\text{vermelho}\}$ como uma combinação proibida. Sempre que ambas as escolhas se repetirem, seguirá a mesma contradição no triângulo, então o ramo pode ser rejeitado imediatamente. Seria incorreto proibir WA vermelho isoladamente: WA pode ser vermelho em soluções válidas com outra cor para NSW.

O aprendizado acrescenta uma restrição ou uma combinação proibida armazenada em cache. A condição aprendida deve decorrer das restrições originais; uma falha causada apenas por atingir um limite de tempo não fornece tal justificativa lógica. Uma combinação proibida útil mantém atribuições suficientes para explicar a impossibilidade sem incluir escolhas não relacionadas.

Combine antecipação e análise retrospectiva

A verificação antecipada e a consistência de arco removem valores sem suporte antes que ocorra uma falha em níveis profundos. O retrocesso com salto diagnostica uma falha depois que ela ocorre. O retrocesso com salto direto e simples não acrescenta redução além do que a verificação antecipada já detecta, mas métodos dirigidos por conflitos podem combinar explicações de falhas mais profundas. O aprendizado preserva essas explicações em ramos posteriores.

A verificação antecipada identifica o que uma nova atribuição elimina imediatamente para as variáveis vizinhas sem valor. Ela elimina valores incompatíveis antes que a busca chegue a essas variáveis, tornando alguns becos sem saída visíveis vários níveis antes.

Reduza domínios após uma atribuição

Após escolher $X=x$, examine cada Y sem valor que compartilhe uma restrição com X. Elimine de $D_Y$ todo valor que entre em conflito com a escolha. Um domínio vazio significa que o ramo atual não pode ser completado, então retroceda imediatamente.

Para $X\mathrm{\ne }Y$, atribuir $X=2$ remove 2 de Y. Para $X<Y$, atribuir $X=2$ remove todos os valores de Y menores ou iguais a 2. A relação determina o que é removido; a verificação antecipada não se limita a eliminar valores iguais.

A redução altera os domínios do ramo atual. Mantenha um registro de desfazimento, frequentemente chamado de trilha, de cada eliminação causada pela escolha. Quando essa escolha for desfeita, restaure os valores eliminados por ela, mantendo as restrições que pertencem a escolhas anteriores. Cópias dos domínios em cada nível oferecem outra implementação.

Acompanhe os domínios das oficinas

Use os horários 1–3 e as regras $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$. Aplique a regra unária para obter $D_E=\{2,3\}$ e depois use a ordem fixa A, B, C, D, E.

1. $A=1$ deixa B, C e D com $\{2,3\}$.
2. $B=2$ deixa C com $\{3\}$.
3. $C=3$ deixa D e E cada uma com $\{2\}$.
4. $D=2$ remove 2 de E, esvaziando seu domínio. Retroceda.

Restaurar os domínios e testar $B=3$ força C a ser 2. D e E passam a ser 3, então atribuir D esvazia E novamente. A busca precisa alterar A. Com $A=2$, ela pode chegar a $B=3,C=1,D=3,E=2$. Esse percurso testa 12 valores, em comparação com 32 testes de candidatos no retrocesso simples na mesma ordem.

Reconheça o limite da verificação de um passo

Após a etapa 3, D e E têm 2 como único valor e devem ser diferentes. A verificação antecipada ainda não verificou essa restrição: nem D nem E recebeu uma nova atribuição. Ela detecta a falha apenas quando D recebe seu valor.

Esse é o limite central da verificação antecipada. Ela testa a variável atribuída em relação às suas vizinhas sem valor, sem propagar adiante a redução do domínio de uma vizinha. A consistência de arco pode acompanhar essas consequências entre variáveis sem valor.

Use os domínios mantidos

A MRV agora pode selecionar diretamente o menor domínio restante. Um domínio com um único valor frequentemente se torna a próxima escolha; um domínio vazio sinaliza falha sem acrescentar outra atribuição. Manter os domínios atualizados ajuda tanto a inferência quanto a ordenação.

Para no máximo $n-1$ vizinhas e no máximo $d$ valores por vizinha, uma passagem de verificação antecipada usa cerca de $O(nd)$ verificações binárias, supondo um teste da relação em tempo constante. Ela remove apenas valores incompatíveis com a atribuição atual, então o retrocesso continua completo. Esquecer de restaurar um valor eliminado pode fazer um ramo posterior perder uma solução válida; reduzir o domínio de uma variável sem relação pode ter o mesmo efeito.

Um valor precisa de um par compatível em cada domínio vizinho. A consistência de arco torna explícita essa exigência de suporte e acompanha os efeitos das mudanças de domínio em todo um CSP binário.

O suporte tem direção

A consistência de nó primeiro remove valores proibidos por regras unárias. Para uma restrição binária, o arco direcionado $X\to Y$ é consistente quando todo valor em X tem pelo menos um valor compatível em Y. Esse valor em Y é um suporte. Revisar o arco elimina os valores sem suporte de sua cauda, X.

Para $A<B$ com ambos os domínios $\{1,2,3\}$, revisar $A\to B$ elimina 3 de A. Revisar $B\to A$ elimina 1 de B. Os domínios resultantes são $D_A=\{1,2\}$ e $D_B=\{2,3\}$. Um valor restante pode usar um suporte diferente para cada vizinha; os suportes não precisam formar uma solução conjunta.

Execute AC-3

O AC-3 usa uma fila de arcos direcionados:

1. Inicialmente, coloque todos os arcos na fila.
2. Retire $X\to Y$ e revise X usando o domínio de Y.
3. Se o domínio de X ficar vazio, pare com falha.
4. Se o domínio de X diminuir, adicione $Z\to X$ para cada outra vizinha Z de X, exceto Y.
5. Continue até a fila ficar vazia.

Uma eliminação em X pode remover um suporte para Z, então a fila deve receber arcos que apontem para o domínio alterado. O arco de Y não precisa ser verificado novamente de imediato: os valores eliminados de X não davam suporte a nenhum valor de Y, pois nenhum deles era compatível com Y desde o início. Os domínios finais não vazios independem da ordem de processamento; ordens diferentes podem chegar à falha em domínios vazios diferentes.

Propague uma decisão sobre as oficinas

Para as regras das oficinas $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$, o AC-3 inicial remove 3 de A e 1 de B. Ele deixa C e D com $\{1,2,3\}$ e E com $\{2,3\}$.

Agora decida $C=1$. O arco $A\to C$ remove 1 de A, deixando $A=2$. Revisar B em relação a A força $B=3$. D é diferente de C e A, então $D=3$. E é diferente de D e não pode ser 1, então $E=2$. As reduções de domínio foram além das vizinhas imediatas da decisão original.

A manutenção da consistência de arco (MAC) aplica essa inferência após cada decisão de busca. Partindo de domínios consistentes de arco, restringir $X=x$ exige uma fila de arcos que chegam de suas vizinhas sem valor. Os valores eliminados dos domínios devem ser restaurados quando a busca desfaz o ramo.

Interprete o resultado e o custo

Um triângulo com domínios {vermelho, azul} e desigualdades nas três arestas continua consistente de arco, mas não tem solução. Cada aresta tem suportes separadamente, mas as três escolhas não podem funcionar juntas.

Com $c$ restrições binárias e tamanho máximo de domínio $d$, AC-3 leva tempo $O(c{d}^3)$: uma revisão de arco verifica até $d^2$ pares, e cada arco pode exigir até $d$ rodadas à medida que sua cabeça perde valores. MAC gasta mais por nó de busca que a verificação antecipada, frequentemente em troca de uma árvore de busca muito menor.

Suportes separados entre pares podem ocultar uma contradição no grupo. Níveis mais fortes de consistência e propagação global especializada examinam combinações que a consistência de arco não detecta, enquanto limites numéricos podem condensar domínios grandes em intervalos úteis.

Estenda atribuições a outra variável

A consistência de caminho examina triplas. Toda atribuição consistente a duas variáveis deve ter uma extensão a uma terceira que seja compatível com ambas. Em um triângulo colorido de vermelho ou azul, X vermelho e Y azul não deixam nenhum valor para Z. A consistência de caminho remove esse par permitido e acaba revelando a inviabilidade. Ela pode remover tuplas de relações, portanto faz mais do que eliminar valores individuais de domínios.

A consistência de ordem k exige que toda atribuição consistente a quaisquer $k-1$ variáveis possa ser estendida a qualquer variável adicional. Para CSPs binários, a consistência de ordem 1 corresponde à consistência de nó, a de ordem 2 à consistência de arco e a de ordem 3 à consistência de caminho. A consistência forte de ordem k inclui todos os níveis de 1 até k. Com consistência forte de ordem n em n variáveis e domínios não vazios, qualquer atribuição parcial consistente pode ser estendida até se tornar uma solução, sem retrocesso. Estabelecer essa propriedade tem custos de tempo e memória exponenciais no pior caso.

Conte os valores em Alldiff

Alldiff exige valores distintos para todas as variáveis em seu escopo. Se um grupo de m variáveis tiver apenas n valores possíveis distintos e $m>n$, nenhuma atribuição poderá satisfazê-lo.

Para três células com domínios $\{4,7\}$, as desigualdades entre pares são consistentes de arco: cada 4 tem suporte 7 em cada vizinha, e cada 7 tem suporte 4. Ainda assim, a contagem global falha porque são necessários três valores diferentes e existem apenas dois.

Se duas células tiverem o domínio $\{4,7\}$, elas devem usar 4 e 7 entre si. Esses valores podem ser removidos de todas as outras células dessa linha. Esse raciocínio de par nu usa um subconjunto de todo o escopo de Alldiff. Um propagador global simples também pode processar repetidamente variáveis com um único valor, remover seus valores das demais e verificar se restam valores distintos insuficientes. Propagadores mais fortes também reconhecem subconjuntos restritos.

Estreite os limites numéricos

A propagação de limites armazena um domínio por seu mínimo e máximo. A consistência de limites exige que cada extremidade tenha uma extensão que satisfaça cada restrição relevante; ela não verifica cada valor interior.

Para dois ônibus que transportam 100 pessoas, sejam $B_1\in [0,50]$ e $B_2\in [0,70]$, com $B_1+B_2=100$. O segundo ônibus transporta no máximo 70, forçando $B_1\ge 30$. O primeiro transporta no máximo 50, forçando $B_2\ge 50$. As janelas reduzidas são $[30,50]$ e $[50,70]$.

Para Preparar, Analisar e Relatar, que levam 20, 40 e 30 minutos nessa ordem, um prazo de 120 minutos dá os inícios mais tardios 30, 50 e 90. Inícios não negativos dão os inícios mais cedo 0, 20 e 60. A propagação para frente e para trás obtém essas janelas antes de um horário de início ser escolhido.

Escolha uma força de inferência útil

Cada célula de Sudoku tem 20 células relacionadas distintas: 8 em sua linha, 8 em sua coluna e mais 4 em sua caixa. Nas 81 células, isso produz $81\times 20\mathrm{/}2=810$ pares distintos que devem ser diferentes. Restrições globais preservam as mesmas soluções que esses pares, mas podem revelar pares nus e falta de valores mais cedo. Uma inferência mais forte custa mais por passagem; resolvedores práticos equilibram esse custo com a busca economizada, frequentemente combinando consistência de arco com propagação especializada de restrições globais e de limites.

A busca local começa com um valor para cada variável, mesmo quando algumas restrições falham. A heurística de conflitos mínimos repara essa atribuição completa mudando uma variável em conflito para um valor com o menor número possível de conflitos.

Escolha um reparo

1. Construa uma atribuição completa, aleatoriamente ou de forma gulosa.
2. Se nenhuma restrição for violada, retorne a solução.
3. Escolha aleatoriamente uma variável envolvida em uma restrição violada.
4. Avalie cada valor de seu domínio em relação às outras variáveis, que permanecem fixas.
5. Escolha um valor com o menor número de conflitos, desempate aleatoriamente e repita até obter sucesso ou atingir um limite de passos.

Uma variável em conflito participa de pelo menos uma restrição violada. Ela não é necessariamente a variável com o maior número de violações. A escolha aleatória entre variáveis em conflito e valores empatados ajuda a evitar uma sequência rígida e repetida.

Repare um tabuleiro de 4 rainhas

Use uma rainha por coluna, com variáveis de linha $Q_1,Q_2,Q_3,Q_4$. Um par entra em conflito se suas linhas forem iguais ou se a diferença entre suas linhas for igual à diferença entre suas colunas. Comece com $(2,4,2,3)$. As colunas 1 e 3 compartilham a linha 2; as colunas 3 e 4 se atacam na diagonal. As variáveis em conflito são Q1, Q3 e Q4.

Escolha Q3 e avalie as linhas enquanto Q1, Q2 e Q4 permanecem fixas:

A linha 1 produz $(2,4,1,3)$, uma solução. Se Q1 tivesse sido escolhida, suas contagens para as linhas 1–4 seriam 0, 1, 2 e 2. Movê-la para a linha 1 produz $(1,4,2,3)$, deixando o conflito diagonal Q3–Q4. Portanto, um reparo localmente melhor pode levar a um processo de reparo ainda incompleto.

Conte as restrições que envolvem a variável selecionada. Contar todas as violações em cada tabuleiro resultante produz a mesma ordenação, pois as restrições sem relação com a variável contribuem com uma constante para cada candidato. Isso simplesmente exige mais trabalho. Use uma definição consistente de conflito ao comparar candidatos.

Repare uma programação existente

Quando um instrutor fica indisponível, a programação atual já é uma atribuição completa. A heurística de conflitos mínimos pode começar nela e mover sessões até que as restrições novas e existentes sejam respeitadas. Uma pequena mudança frequentemente exige poucos reparos, embora um movimento possa criar novos conflitos em outro lugar. Se preservar o plano antigo for importante, atribua um custo explícito à mudança de uma atribuição; minimizar apenas as violações não minimiza as alterações na programação.

Experimentos com uma boa atribuição inicial exigiram relativamente poucos passos de reparo mesmo para um milhão de rainhas. Tabuleiros maiores ainda tornam cada passo mais custoso. A heurística de conflitos mínimos também foi usada na programação do Hubble, com uma redução relatada de cerca de três semanas para cerca de 10 minutos para programar uma semana de observações.

Interprete o comportamento da busca

Muitas famílias de CSPs aleatórios passam de majoritariamente solucionáveis para majoritariamente sem solução à medida que a razão entre restrições e variáveis aumenta. Perto dessa transição, decidir como as escolhas interagem costuma ser mais difícil. Problemas com poucas restrições podem ter muitas soluções fáceis de alcançar. Problemas sem solução e com muitas restrições podem ser rejeitados rapidamente por resolvedores completos baseados em propagação.

Atingir um limite de passos da heurística de conflitos mínimos significa que nenhuma solução foi encontrada naquela execução. O problema ainda pode ter solução. A força prática do método vem de reparos eficientes, incluindo movimentos entre valores com a mesma pontuação, embora as soluções sejam uma fração minúscula de todas as atribuições possíveis.

Uma busca por reparos pode parar de melhorar enquanto ainda há conflitos. Para continuar, o resolvedor precisa de uma maneira de percorrer estados de mesma pontuação ou alterar quais movimentos parecem compensar. O resultado necessário também importa: um reparo viável e rápido e uma prova de inviabilidade exigem métodos diferentes.

Atravesse um platô

Um mínimo local tem violações, mas nenhum movimento de uma única variável reduz sua contagem. Um platô é uma região conectada de atribuições com a mesma pontuação. Movimentos que apenas diminuem a pontuação podem ficar presos; um movimento lateral muda o estado sem diminuí-la.

No problema das 4 rainhas, $(1,4,2,3)$ tem um conflito entre Q3 e Q4. Com as outras rainhas fixas, as contagens de Q3 para as linhas 1–4 são 1, 1, 3 e 2; as de Q4 são 2, 2, 1 e 2. Nenhuma das variáveis tem um movimento que melhore a pontuação.

Mover Q3 para a linha 1 produz $(1,4,1,3)$, ainda com um conflito, agora Q1–Q3 compartilhando uma linha. Nesse novo estado, as contagens de Q1 são 1, 0, 3 e 1. Mover Q1 para a linha 2 produz $(2,4,1,3)$ e elimina o conflito. O movimento lateral alterou quais movimentos de melhoria estavam disponíveis.

Mantenha a busca em andamento

Uma lista tabu é uma memória de curta duração. Ela desencoraja o retorno imediato a um estado que acabou de ser deixado. Um reinício explora outra região, enquanto o recozimento pode atravessar uma região com mais conflitos na execução atual.

Com a ponderação de restrições, comece cada peso em 1 e pontue um estado pela soma dos pesos de suas restrições violadas. Escolha uma mudança que reduza essa pontuação ponderada e depois aumente os pesos das restrições que continuam violadas. Falhas repetidas ficam mais custosas, remodelando a paisagem da busca. Uma pontuação ponderada zero ainda significa que toda restrição rígida com peso positivo é satisfeita.

Escolha a evidência de que você precisa

A busca local é incompleta: ela pode deixar de encontrar uma solução existente, e uma execução finita malsucedida não resolve a questão da inviabilidade. O retrocesso com propagação em domínios finitos é completo: em algum momento encontra uma solução ou esgota todas as complementações possíveis.

Use a busca local quando um problema grande com poucas restrições precisar de uma atribuição viável ou de um reparo rápido. O retrocesso com MRV e MAC é uma escolha forte para quebra-cabeças com muitas restrições e sempre que a tarefa exigir um resultado de inviabilidade. O tempo de execução ainda depende da instância; essas escolhas de método se baseiam em suas garantias.

A programação das oficinas tem a solução única $A=2,B=3,C=1,D=3,E=2$. Acrescentar $C\mathrm{\ne }1$ a elimina. A heurística de conflitos mínimos pode tentar reparos até seu limite, mas apenas uma busca completa que esgote os casos restantes estabelece que o organizador precisa mudar uma exigência, por exemplo, acrescentando outro horário.

Um grafo de restrições pode revelar problemas menores dentro de um problema grande. Componentes independentes podem ser resolvidos separadamente, e componentes sem ciclos admitem um algoritmo particularmente eficiente, com uma passagem de redução dos filhos para os pais e uma passagem de atribuição dos pais para os filhos.

Separe componentes desconectados

Um componente conectado é independente quando nenhuma restrição liga suas variáveis a outro componente. Resolva cada componente e depois combine uma solução de cada um. Se algum componente não tiver solução, o CSP completo não terá solução. No mapa da Austrália, a Tasmânia é independente da parte continental.

Com n variáveis divididas em grupos independentes de tamanho c, encontrar uma atribuição completa exige trabalho da ordem de $O((n\mathrm{/}c)d^c)$ em vez de $O(d^n)$. Para 60 variáveis binárias divididas em três grupos de 20, buscas exaustivas separadas consideram no máximo $3\times 2^{20}=\mathrm{3.145.728}$ atribuições em vez de cerca de $\mathrm{1,15}\times {10}^{18}$. Enumerar todas as soluções combinadas ainda exigiria listar as combinações; a economia descreve a resolução dos problemas dos componentes.

Ordene uma árvore a partir da raiz

Um CSP binário tem estrutura de árvore quando seu grafo de restrições não tem ciclos. Uma árvore conectada tem um caminho entre cada par de variáveis; uma floresta contém árvores separadas. Primeiro aplique as restrições unárias. Escolha qualquer raiz e ordene as variáveis de modo que cada pai apareça antes de seus filhos.

A consistência de arco direcionada nessa ordem exige que cada variável anterior tenha suporte em cada vizinha posterior. Em uma árvore, essas vizinhas posteriores são seus filhos. A direção do suporte é do pai para o filho, embora o algoritmo processe os filhos antes dos pais.

Reduza dos filhos para os pais, atribua dos pais para os filhos

1. Leia a ordem de trás para frente, excluindo a raiz. Para cada filho, revise o arco de seu pai para esse filho. Elimine do domínio do pai os valores sem suporte.
2. Se um domínio ficar vazio, informe que não há solução.
3. Leia a ordem de frente para trás. Escolha qualquer valor restante para a raiz e depois atribua a cada filho um valor compatível com o valor atribuído ao pai.

Os descendentes do filho já foram processados quando seu pai é revisado. Portanto, um valor restante do pai tem suporte em cada filho, e cada valor do filho já tem suporte nos níveis abaixo. Ramos de filhos diferentes não têm arestas que os conectem, então esses suportes podem ser escolhidos independentemente. Por isso, a passagem dos pais para os filhos não precisa de retrocesso.

Acompanhe a árvore das oficinas

Fixe $C=1$ na programação das oficinas e remova 1 dos domínios das outras oficinas. O grafo restante é o caminho B–A–D–E, com domínios $\{2,3\}$ e restrições $A<B,A\mathrm{\ne }D,D\mathrm{\ne }E$.

Escolha a raiz A e a ordem A, B, D, E. A passagem dos filhos para os pais revisa $D\to E$ e depois $A\to D$, sem alterações. Por fim, $A\to B$ remove 3 de A porque B não tem valor maior. Atribuir dos pais para os filhos produz $A=2,B=3,D=3,E=2$. Restaurar $C=1$ produz a programação completa.

Para n variáveis com tamanho máximo de domínio d, a passagem dos filhos para os pais revisa $n-1$ arcos a um custo de até $O(d^2)$ cada, resultando em tempo $O(n{d}^2)$. A garantia depende da ausência de ciclos. Um ciclo pode conectar ramos de filhos separados e invalidar a independência que tornava seguras essas escolhas locais.

Um grafo com poucos ciclos ainda pode estar próximo o suficiente de uma árvore para ser resolvido eficientemente. O condicionamento por conjunto de corte atribui valores primeiro a variáveis selecionadas; a decomposição em árvore agrupa variáveis em partes sobrepostas. Ambos fazem com que a coordenação restante tenha estrutura de árvore.

Condicione por um conjunto de corte de ciclos

Um conjunto de corte de ciclos é um conjunto de variáveis cuja remoção deixa uma árvore ou floresta. Verifique todos os ciclos restantes, não apenas o mais visível. Para o mapa da Austrália, remover SA deixa o caminho WA–NT–Q–NSW–V e T isolada. Para o grafo das oficinas, remover C deixa B–A–D–E.

Para cada atribuição ao conjunto de corte que satisfaça suas restrições internas:

1. Remova valores incompatíveis dos domínios restantes.
2. Resolva cada árvore restante usando a redução dos filhos para os pais e a atribuição dos pais para os filhos.
3. Se todas tiverem sucesso, combine suas atribuições com os valores do conjunto de corte. Caso contrário, tente outra atribuição do conjunto de corte.

No problema das oficinas, $C=1$ deixa uma árvore solucionável. Com $C=2$, A e B devem vir de $\{1,3\}$ e $A<B$ força $A=1,B=3$. D deve ser diferente de A e C, produzindo $D=3$. E não pode ser 1 e deve ser diferente de C e D, ficando sem valor. Com $C=3$, A e B devem ser 1 e 2; D deve então ser 2, deixando E sem valor novamente.

Para um conjunto de corte de tamanho c, há no máximo $d^c$ atribuições, cada uma seguida de um problema em árvore de custo $O((n-c)d^2)$. O total é $O(d^c(n-c)d^2)$. Um c pequeno torna isso útil; o custo continua exponencial em c. Encontrar um conjunto de corte mínimo é NP-difícil, mas um conjunto de corte válido que não seja mínimo ainda produz um procedimento correto.

Una bolsas sobrepostas

Uma decomposição em árvore organiza conjuntos de variáveis, chamados bolsas, em uma árvore. Ela deve satisfazer três condições:

• Toda variável aparece em uma bolsa.
• O escopo de toda restrição cabe em pelo menos uma bolsa.
• As bolsas que contêm uma mesma variável formam uma parte conectada da árvore de bolsas.

A terceira regra é a propriedade de interseção contínua. Se X aparece nas duas extremidades de um caminho de bolsas, deve aparecer em todo esse caminho. Caso contrário, bolsas distantes poderiam escolher valores inconsistentes para X sem nenhuma verificação intermediária de concordância.

As atribuições localmente válidas de cada bolsa tornam-se valores de uma megavariável. Bolsas adjacentes devem concordar sobre as variáveis compartilhadas. A árvore resultante coordena as soluções locais. Para um triângulo X–Y–Z–X mais a aresta Z–W, as bolsas $\{X,Y,Z\}$ e $\{Z,W\}$ cobrem todas as arestas e concordam sobre Z.

A largura de árvore da decomposição é o tamanho de sua maior bolsa menos 1. A largura de árvore de um grafo é o mínimo entre as decomposições válidas. Para largura w, o limite padrão de CSP é $O(n{d}^{w+1})$. Uma largura fixa e limitada controla o expoente.

Elimine a simetria de valores

Quando os nomes das cores não têm significado especial, permutar vermelho, verde e azul preserva a validade. As seis soluções da parte continental da Austrália são seis renomeações de um padrão. Fixar a ordem NT antes de SA antes de WA na ordem de cores vermelho, verde, azul mantém um representante. Essa restrição de quebra de simetria só é válida quando a renomeação preserva as regras originais. Uma regra que exige que determinada região seja vermelha torna essa cor especial e altera quais permutações continuam sendo simetrias.