Problemas de Satisfação de Restrições

Até agora, abordámos dois estilos de procura distintos: as procuras cega e informada. Ambas as abordagens partilham uma base entre si: a ideia do estado ser algo atómico, possuindo apenas as funções de avaliação e de sucessores, e podendo responder a um teste objetivo, contudo sem uma estrutura interna adicional. Ora, esta parece ser uma falha relativamente relevante nas abordagens anteriores, já que um estado pode potencialmente armazenar pormenores bastante importantes para a (re)solução do problema: se pegarmos no problema das 8 rainhas, o estado em si pode até guardar as linhas e colunas das peças colocadas no tabuleiro, por exemplo.

Nesta secção, vamos então aprofundar esta ideia de estados não atómicos, com conteúdo no seu interior, um conjunto de variáveis: dizemos que chegámos a uma solução para o problema proposto quando todas as variáveis estiverem associadas a valores que satisfaçam as restrições impostas pelo mesmo. Dizemos que os problemas resolvidos desta forma são Problemas de Satisfação de Restrições (do inglês Constraint Satisfaction Problems, CSP). Idealmente, algoritmos de procura que assentem nesta ideia irão progressivamente eliminando ramos da nossa árvore de procura, tornando-a assim mais eficiente.

Definir CSPs

CSP

Podemos definir um CSP como um conjunto de três componentes:

  • um conjunto de variáveis: seja ele X={X1,X2,,Xn}X = \{X_1, X_2, \cdots, X_n\};
  • um conjunto de domínios, onde um domínio corresponde ao conjunto de valores que podem ser associados a uma variável: seja ele D={Dx1,Dx2,,Dxn}D = \{D_{x_1}, D_{x_2}, \cdots, D_{x_n}\};
  • um conjunto de restrições, que especifica todas as combinações possíveis de valores que podemos ser associados às variáveis ao mesmo tempo numa solução correta: seja ele CC.

Temos ainda que as restrições podem ser explícitas, quando especificam diretamente todas as combinações possíveis de valores que podem ser associados às variáveis, ou implícitas, quando o fazem através de expressões matemáticas ou equivalente.

Um exemplo relativamente simples é o de, num problema binário (ou seja, onde o domínio é {0,1}\{0,1\} para duas variáveis X1X_1 e X2X_2), se quisermos que a solução para o problema seja "estas duas variáveis têm de ter valores diferentes", podemos fazê-lo de duas maneiras: uma, afirmando explicitamente que os pares de atribuições possíveis são {0,1}\{0, 1\} e {1,0}\{1, 0\}, e outra recorrendo a notação formal: X1X2X_1 \neq X_2.

Um estado será, portanto, definido como um conjunto de correspondências entre variáveis e valores, correspondências essas que não deverão violar qualquer das restrições impostas pelo problema. Estas correspondências, ou atribuições, podem ser parciais ou completas, claro: uma atribuição diz-se completa caso todas as variáveis em XX tenham um valor associado. Mais ainda, diz-se consistente caso todas as atribuições respeitem o conjunto CC. Dizemos que temos em mãos uma solução para o CSP quando temos uma atribuição completa e consistente: não existem variáveis sem atribuições, estando todas elas atribuídas de acordo com o que o problema nos impõe.

Tal como o exemplo Arad-Bucareste acompanhou as secções das procuras cega e informada, o exemplo seguinte - colorir um mapa australiano com cores diferentes, sem que duas regiões adjacentes partilhem uma cor - acompanhar-nos-á ao longo desta secção.

Considere-se o seguinte mapa da Austrália (que está obviamente realista e não está assim só porque dava jeito ter um SVG):

Podemos considerar o problema de colorir o mapa australiano como um CSP: aqui, temos que XX corresponderá ao conjunto de regiões do mapa, DD corresponderá ao conjunto de cores disponíveis para as pintar, e CC corresponde ao conjunto de restrições impostas. Teríamos, portanto, algo como:

X={WA,NT,Q,SA,NSW,V,T}D={{vermelho,verde,azul},{vermelho,verde,azul},,{vermelho,verde,azul}}C={SAWA,SANT,}X = \{WA, NT, Q, SA, NSW, V, T\} \\ D = \{\{vermelho, verde, azul\}, \{vermelho, verde, azul\}, \cdots, \{vermelho, verde, azul\}\} \\ C = \{SA \neq WA, SA \neq NT, \cdots\}

Pode ser útil procurar visualizar este tipo de problemas sob o ponto de vista de um grafo de restrições. Se olharmos para o grafo abaixo, as restrições que envolvem um dado par de nós, as variáveis, correspondem a arcos entre os mesmos.

Seguindo as restrições impostas, uma solução possível para o problema seria:

Porquê usar CSP's

Bem, em primeiro lugar, é importante realçar que muitos dos problemas que vamos querer resolver são, por natureza, modelados à volta de restrições: o problema das 88 rainhas, por exemplo, baseia-se nas restrições "uma rainha não pode atacar a outra", não podendo, portanto, partilhar linha, coluna ou diagonal.

Mais ainda, tal como referido na introdução desta secção, algoritmos baseados em CSPs são, na prática, mais eficientes que algoritmos de procura tradicionais, já que podem ignorar rapidamente ramos da árvore de procura que não satisfazem as restrições requeridas. Basta pensar no exemplo do mapa australiano, onde se a nossa primeira opção fosse colorir South Australia com verde, estaríamos a eliminar a possibilidade de 55 outras regiões serem pintadas com verde - passando a contar ao todo com 25=322^5 = 32 possibilidades restantes, ao invés de 35=2433^5 = 243, um pruning substancial feito à árvore!

Para além disso, se numa procura clássica a única análise qualitativa que fazíamos eram testes-objetivo, sendo tudo o resto quantitativo, em CSPs tal não é o caso: podemos claramente inferir não só que nn ramos podem ser descartados da procura, como o porquê de tal acontecer!

Podemos ter restrições unárias, binárias e de ordem superior. As duas primeiras são relativamente simples - restrições unárias relacionam uma variável com valores do respetivo domínio que podem ou não tomar (como South Australia != verde), e restrições binárias relacionam duas variáveis (aqui seria algo como South Australia != Tasmania). As restrições de ordem superior, que envolvem 3 ou mais variáveis, podem não ser tão intuitivas e, se as quisermos representar sob a forma de grafo, vamos precisar de um hipergrafo de restrições, uma generalização do grafo de restrições tradicional onde podemos, através de um nó auxiliar, ligar mais que dois vértices.

Pensemos, por exemplo, no Sudoku: todas as variáveis de uma linha/coluna/diagonal vão ter de tomar valores diferentes. Assim sendo, podemos representar essa restrição de ordem superior (ordem 99 para o sudoku clássico) da seguinte forma:

A restrição utilizada acima é a allDiff, uma das mais comuns quando abordamos hipergrafos de restrições - corresponderia a algo como XiXj,i,jX_i \neq X_j, \forall_{i, j}. Existem também outras restrições globais clássicas, como a atmost ou restrição de recursos, que tal como o nome indica restringe os valores das variáveis a "as variáveis têm de ter atribuições que, somadas, não ultrapassem este valor".

Podemos ainda ter restrições de preferências, que diferem das três anteriores por não serem absolutas - todas as anteriores eram invioláveis, e qualquer solução teria de as respeitar; restrições de preferências ajudam a modelar o problema em volta de um conjunto de coisas que gostávamos que acontecessem (e damos um peso a cada uma, conforme sejamos mais ou menos firmes quanto a que tal aconteça ou não), mas cuja obrigatoriedade não está set in stone.

Podemos pensar, por exemplo, no problema da organização de horários dos professores de Inteligência Artificial: temos, claro, restrições invioláveis, como o facto de um professor não poder estar a dar duas aulas presenciais ao mesmo tempo. Existem, contudo, conjuntos de restrições que idealmente se verificariam, mas caso tal não seja possível a solução não deixa de ser aceitável. Temos, claro, o facto de os professores idealmente não terem horários em que num dia terminam as aulas às 20h e no dia seguinte têm logo uma aula às 8h - pode ter de acontecer, mas idealmente não. Cada professor poderá ainda preferir dar aulas em certos dias da semana, ou em certos horários (manhã/tarde), e todas essas preferências poderão ser introduzidas num conjunto à parte, o conjunto de restrições de preferências do problema, onde cada uma destas preferências seria devidamente pesada e resolvida como um problema de otimização de restrições.

Inferência

Os algoritmos abordados para as procuras cega e informada limitavam-se a andar pela árvore de procura, à procura da "melhor solução" possível para o problema em mãos. No caso de algoritmos baseados em CSPs, para além de podermos fazer uma procura clássica, temos ainda a noção de restrições; mais importante ainda, temos a noção de propagação de restrições, uma forma de fazer inferência quanto a uma dada situação, atualizando progressivamente os caminhos que podemos tomar. Temos como exemplo mais direto desta propagação o caso do mapa australiano, onde, à medida que íamos colorindo o mapa, íamos ficando progressivamente com cada vez menos opções que satisfizessem as restrições impostas, tendo em conta o que já foi feito. As restrições podem ser-nos úteis logo no pré-processamento inicial do problema, podendo, inclusive, fazer com que não tenha de haver procura: num Sudoku fácil, por exemplo, existe sempre um movimento "obrigatório" (leia-se "aquele número tem de estar ali") à medida que vamos avançando no jogo, pelo que o pré-processamento leva a uma propagação sucessiva de restrições que levam a uma solução direta, sem recorrer a procura/tentativas sem garantias.

A propagação tem por objetivo, assim, utilizar as restrições a seu favor por forma a reduzir o tamanho dos domínios das variáveis (idealmente a 11, nunca a 00), garantindo, assim, que "aquela variável tem de estar associada àquele valor para uma solução consistente". Vai, aqui, voltar a ser relevante aquela visualização do problema como um grafo mencionada mais acima.

Consistência de Nó

Dizemos que uma variável é nó-consistente caso todos os valores no seu domínio satisfaçam as suas restrições unárias. Pensando no exemplo do mapa australiano, caso pintemos South Australia de verde, Western Australia vai deixar de poder ser pintada com essa cor, pelo que para esta ser nó-consistente vamos ter de "atualizar" o seu domínio, removendo verde. Adicionalmente, dizemos que um grafo é nó-consistente caso todas as suas variáveis também o sejam.

Consistência de Arcos

Dizemos que uma variável é arco-consistente caso todos os valores no seu domínio satisfaçam as suas restrições binárias. Dizemos que uma variável XX é consistente em arco para YY caso, para todos os valores no domínio de XX, exista um valor no domínio de YY que satisfaça a restrição binária que as liga. O exemplo clássico é a restrição Y=X2Y = X^2, onde com domínios tais que:

DX={0,1,2,3}DY={0,1,4,9}D_X = \{0, 1, 2, 3\}\\ D_Y = \{0, 1, 4, 9\}

vamos ter XX consistente em arco para YY: para 00, 11, 22 e 33 existem, respetivamente, 00, 11, 44 e 99 como valores no domínio de YY que satisfazem a restrição binária para o respetivo valor de XX.

Temos que um grafo é arco-consistente caso qualquer variável seja arco-consistente com todas as outras variáveis.

O algoritmo mais conhecido para tratar a consistência de arcos é o AC-3\text{AC-3}. É utilizado mais frequentemente que outros algoritmos dentro do mesmo âmbito, já que os seus antecessores são muito menos eficientes e os seus sucessores têm implementações bastante mais complexas.

O seu funcionamento é relativamente simples: mantemos um set de arcos (que inicialmente tem todos os arcos do CSP em questão), e vamos aleatoriamente removendo um arco do set (seja o arco (X,Y)(X, Y)); fazemos com que XX seja consistente em arco com YY, e daí vamos ter três cenários possíveis:

  • Caso DXD_X não tenha sido alterado, XX já era consistente em arco com YY, pelo que o arco é só removido e não acontece nada;
  • Caso DXD_X tenha visto o seu tamanho reduzido (com DX0|D_X| \neq 0), adicionamos todos os outros arcos (X,Xj)(X, X_j) de volta ao set - temos restrições adicionais, pelo que podemos agora encontrar outras maneiras de reduzir o tamanho do domínio de XX;
  • Caso DXD_X tenha visto o seu domínio reduzido ao conjunto vazio, podemos afirmar que não existe solução consistente para o problema, pelo que o algoritmo retorna failure.

O algoritmo termina quando verifica que o domínio de uma das variáveis passa a ser o conjunto vazio, retornando failure, ou quando o set de arcos fica vazio, retornando true. Note-se, contudo, que este algoritmo não resolve por si só o problema: pode ajudar (bastante até), dado que reduz o tamanho dos domínios das variáveis o máximo possível, mas, por vezes, termina sem que todos os domínios fiquem com tamanho 11: nesse caso, vamos precisar de métodos adicionais para resolver os problemas em questão.

Exemplo AC-3\text{AC-3}: Sudoku

Considere-se o seguinte tabuleiro de Sudoku:

Se quisermos modelar "preencher o tabuleiro" como um CSP, vamos ter:

X={A1,A2,,I8,I9}D={DA1,DA2,,DI8,DI9},DA1=DA2=={1,,9}C=allDiff(A1,,A9),allDiff(A1,,I1),X = \{A_1, A_2, \cdots, I_8, I_9\} \\ D = \{D_{A_1}, D_{A_2}, \cdots, D_{I_8}, D_{I_9}\}, D_{A_1} = D_{A_2} = \cdots = \{1, \cdots, 9\} \\ C = \text{allDiff}(A_1, \cdots, A_9), \text{allDiff}(A_1, \cdots, I_1), \cdots

Procuremos ver como 2 passos de AC-3\text{AC-3} permitem reduzir o tamanho dos domínios de 2 variáveis.

  • Escolhendo a variável E6E_6 (que corresponde ao nó E6E_6 no grafo de restrições), vamos ter:

    • Quanto à coluna, E6E_6 não vai poder tomar os valores 5,6,2,8,9,35, 6, 2, 8, 9, 3;
    • Quanto à linha, E6E_6 não vai poder tomar os valores 7,87, 8;
    • Quanto à "caixa", E6E_6 não vai poder tomar os valores 1,2,7,81, 2, 7, 8;

    Temos, portanto, que o domínio de E6E_6 deve ser reduzido para DE6={4}D_{E_6} = \{4\}. Chegámos, portanto, a um "movimento obrigatório" aqui! O que faríamos de seguida era adicionar todas os arcos (E6,Ej),j6(E_6, E_j), j \neq 6 ao set de arcos mantidos pelo algoritmo, para ver se podíamos reduzir mais domínios.

  • Escolhendo a variável I6I_6 (que corresponde ao nó I6I_6 no grafo de restrições), vamos ter:

    • Quanto à coluna, I6I_6 não vai poder tomar os valores 5,6,2,4,8,9,35, 6, 2, \smartcolor{red}{4}\smartcolor{yellow}{^*}, 8, 9, 3;
    • Quanto à linha, I6I_6 não vai poder tomar os valores 5,1,35, 1, 3;
    • Quanto à "caixa", I6I_6 não vai poder tomar os valores 1,2,3,6,91, 2, 3, 6, 9;

    *Note-se que devido a termos descoberto que E6E_6 apenas pode tomar o valor 44, 44 é adicionado às restrições de todas as variáveis da sexta coluna.

    Temos, portanto, que o domínio de I6I_6 deve ser reduzido para DI6={7}D_{I_6} = \{7\}. Chegámos a mais um movimento "obrigatório"!

Podíamos, realizando os vários passos a que AC-3\text{AC-3} nos levaria, resolver de uma assentada o problema, sem recorrer a procuras adicionais. O resultado final seria o seguinte:

Como referido anteriormente, há situações em que o algoritmo AC-3\text{AC-3} não resolve sozinho o problema - nem todos os tabuleiros Sudoku conseguem ser completados seguindo unicamente este algoritmo, pelo que, para resolver problemas mais complexos, precisamos de misturar procura com inferência, procurando propagar restrições através de "tentativas" (i.e "não sei se 66 é o valor certo aqui, mas é bastante provável, por isso vou tentar"), ou até mesmo usando outros algoritmos de consistência.

Considerando cc como o número total de restrições binárias do problema e dd como o tamanho máximo do domínio de uma variável, podemos afirmar que a consistência de um arco pode ser analisada em tempo d2d^2 - na pior das hipóteses, verificamos cada par de variáveis 11 a 11. Mais, como um arco pode ser inserido no set de arcos no máximo dd vezes (já que o domínio só tem dd valores que podem ser removidos, e no pior caso são removidos 11 a 11), havendo cc restrições binárias, vamos ter que

TIME(AC-3)O(cdd2)=O(cd3).\text{TIME(AC-3)} \in O(c \cdot d \cdot d^2) = O(c \cdot d^3).

Consistência de Caminhos

Como verificámos acima, há problemas para os quais a consistência de arcos é imensamente útil. Temos, contrastando, problemas em que esta noção acaba por ser praticamente irrelevante: basta pensar no exemplo do mapa australiano, onde os domínios têm 22 em vez de 33 cores. É claro que é impossível resolver o problema com apenas 22 cores: se pensarmos no tridente SAWANT\text{SA} - \text{WA} - \text{NT}, vamos ter que ter necessariamente 33 cores diferentes (visto que são todos adjacentes entre si) para obter uma solução consistente para o problema. Ora, mas a consistência de arcos não nos permite aferir nada quanto a isso: se formos a ver, as variáveis acabam por ser consistentes em arco umas com as outras, não retornando failure (como idealmente aconteceria); mais, também não ocorre redução de domínio, pelo que efetivamente terminamos a execução do algoritmo tal como começámos. Precisamos, portanto, de uma noção extra de consistência, que nos permita tratar este tipo de problemas: vamos recorrer à consistência de caminhos.

Se, ao falar na consistência em nó, tocámos em restrições unárias, e na consistência em arco abordámos as restrições unárias, parece fazer todo o sentido que aqui abordemos restrições de ordem superior. Bem, sim e não: de facto, vamos tocar em restrições que envolvem mais que 22 variáveis (33, neste caso), mas não sob o contexto de restrições ternárias diretamente.

Consistência de Caminhos

Dizemos que um par de variáveis (Xi,Xj)(X_i, X_j) é consistente em caminho para uma terceira variável, seja ela XkX_k, caso qualquer atribuição possível que seja consistente com as restrições que envolvem (Xi,Xj)(X_i, X_j) seja também consistente com as restrições que englobam (Xi,Xk)(X_i, X_k) e (Xk,Xj)(X_k, X_j). Falamos em caminho porque, se pensarmos bem, é de um caminho que se trata: estamos a criar um caminho entre XiX_i e XjX_j que passa por XkX_k, e a dizer que "tudo o que está entre elas tem de bater certo".

Bem, já que acima referimos que AC-3\text{AC-3} não era adequado para o exemplo do mapa australiano com 22 cores, faz sentido que verifiquemos se a consistência de caminhos é adequada para o mesmo. Considerem-se novamente as variáveis WA, SA\text{WA, SA} e NT\text{NT}, sendo que vamos querer verificar se (WA, SA)(\text{WA, SA}) é consistente em caminho para NT\text{NT}. Tal como referido acima, vamos verificar se todas as combinações de atribuições consistentes em arco também o são em caminho:

{{WA = vermelho, SA = azul},{WA = azul, SA = vermelho}}\{\{\text{WA = vermelho, SA = azul}\}, \{\text{WA = azul, SA = vermelho}\}\}

Ora, peguemos na primeira atribuição: para (WA, SA)(\text{WA, SA}) ser consistente em caminho com NT\text{NT}, esta atribuição terá de respeitar todas as restrições em (WA, NT)(\text{WA, NT}) e (NT, SA)(\text{NT, SA}). Ora, para WA = vermelho\text{WA = vermelho} ser consistente em arco com NT\text{NT}, teremos de ter NT = azul\text{NT = azul}; contudo, da mesma maneira, para NT = azul\text{NT = azul} ser consistente em arco com SA\text{SA}, teremos de ter SA = vermelho\text{SA = vermelho}: não é o caso, nesta atribuição, já que SA = azul\text{SA = azul}, por premissa. Assim sendo, esta atribuição é removida do conjunto de atribuições consistentes em caminho possíveis, verificando-se o mesmo para a outra atribuição, pelo que são ambas removidas. Podemos, assim, garantir que não existe solução consistente para este problema!

Para a consistência de caminhos, temos um algoritmo bastante semelhante ao AC-3\text{AC-3}, o PC-2\text{PC-2}.

Consistência K

Podemos generalizar as noções de consistência supra-abordadas através da noção de kk-consistência - um problema diz-se kk-consistente se, para todo o conjunto de k1k-1 variáveis (seja esse conjunto KK), para qualquer atribuição consistente para as suas variáveis, podemos sempre atribuir um valor que não torne o problema inconsistente a uma nova variável kk. A consistência em nó é, portanto, a 11-consistência, a consistência em arco é a 22-consistência, etc.

Temos ainda a noção de CSP fortemente kk-consistente: todo o CSP que seja kk-consistente, e (k1)(k-1)-consistente, ..., 11-consistente diz-se fortemente kk-consistente. É bastante importante, já que se tivermos um CSP com nn variáveis e este for fortemente nn-consistente, então podemos facilmente atingir a solução: basta escolher um valor consistente para X1X_1, qualquer que seja X1X_1; como o CSP é 22-consistente, podemos escolher um valor consistente para X2X_2; como é 33-consistente, também o vamos poder fazer para X3X_3, e assim sucessivamente.

Existe, contudo, um catch: tornar um CSP kk-consistente é um processo moroso, com complexidade exponencial (tanto temporal como espacial). Assim sendo, acabamos por usar a abordagem acima indicada apenas quando conseguimos verificar empiricamente a kk-consistência do grafo, já que caso contrário "acaba por nem valer a pena".

Procura em CSPs

Nem sempre conseguimos resolver CSPs utilizando exclusivamente inferência - basta pensar no problema das 88 rainhas, onde inicialmente acabamos por ter que "atirar ao calhas" e tentar proceder a partir daí (fazendo uma procura, portanto). Temos, claro, diferentes maneiras de fazer as procuras, cada uma delas com as respetivas vantagens e desvantagens - vamos, nesta secção, procurar entender maneiras boas e más de aliar procuras às nossas estratégias de resolução de problemas, tentando simultaneamente perceber porque é que funcionam melhor em certos contextos em comparação com outras.

Procuras mais básicas (pensemos, por exemplo, numa DFSDFS limitada) têm o defeito de ignorar o contexto do problema, acabando por não se aperceber de padrões repetitivos na árvore de procura, levando a travessias redundantes: pensando no caso de um CSP com nn variáveis, onde o respetivo domínio pode ter até dd valores, vamos ter uma árvore de procura com ramificação no primeiro nível igual a ndnd, definitivamente longe do ideal. Mais, cada nível da árvore vai apenas removendo uma variável do conjunto de variáveis por atribuir, pelo que o nível seguinte terá ramificação de ordem (n1)d(n - 1)d, e assim sucessivamente. Vamos, portanto, poder afirmar que uma árvore de procura naive que procure resolver um CSP poderá ter n!dnn!d^n folhas! Ora, a redundância entra precisamente aqui: porque é que havemos de precisar de n!dnn!d^n folhas na nossa árvore, quando só existem dnd^n atribuições completas possíveis*? Esta procura não parece, portanto, aperceber-se da possibilidade de variáveis atribuídas por ordens diferentes poderem ir dar a um conjunto de atribuições final igual - basta ver o exemplo abaixo, onde três caminhos da mesma árvore vão dar ao mesmo, sendo a única diferença a ordem da atribuição das variáveis:

* Basta pensar que se tivermos 55 caixinhas que podem ser preenchidas com 00 ou 11, vamos ter 252^5 atribuições completas diferentes (e posteriormente generalizar para nn caixinhas com dd valores possíveis). Existem, claro, 5!5! maneiras de chegar à mesma configuração completa da caixinha, mas não é isso que nos interessa!

Parece que voltámos ao secundário, quando aprendemos a diferença entre permutações e combinações: CSPs são comutativos, e como tal, a ordem das atribuições é irrelevante, tal como nas combinações. Idealmente, devemos conseguir remover esta redundância das nossas árvores de procura, efetivamente fazendo um pruning bastante significativo das mesmas, passando a considerar apenas uma variável por nível da árvore, conseguindo, assim, eliminar os tais ramos desnecessários da nossa árvore, tendo, no máximo, dnd^n folhas. Adaptando o exemplo acima, ficaríamos com algo como:

É de realçar que aqui todas as soluções estão a profundidade nn, já que cada nível trata de todas as atribuições possíveis para apenas 11 variável!

Mais uma abordagem de procura bastante simples, funciona como uma DFS que vai avançando pela árvore atribuindo valores à variável correspondente ao nível em que está, verificando sempre se a solução é consistente - se não for, parte para um dos seus irmãos (e caso não haja irmãos restantes, retrocede para o nível anterior). Dizemos que não existe solução completa consistente para o problema caso tenhamos de retroceder de volta à raiz.

Esta procura é, contudo, cega, tal como as que vimos inicialmente no contexto de Inteligência Artificial: fará, portanto, sentido introduzir heurísticas às nossas procuras, por forma a que sejam (idealmente) mais eficientes. No contexto de CSPs, contudo, e tentando manter o padrão de "abstração de implementação" quanto ao domínio que temos tentado manter nestas procuras, vamos querer utilizar também heurísticas independentes do problema em mãos: heurísticas que sabemos que estão mais que testadas, e que devemos (em princípio) poder utilizar à confiança. Podemos dividir a "abordagem das heurísticas" consoante o respetivo foco: servem para escolher a próxima variável a ser atribuída, ou o próximo valor a atribuir? Ambas as abordagens têm o seu mérito, pelo que vamos de seguida tentar perceber as vantagens de cada uma (e os métodos mais comuns de o fazer).

Escolher a Próxima Variável

Numa árvore de procura como as supra-mencionadas, não existe uma "ordem pré-determinada" para cada nível corresponder a uma dada variável específica - tanto podemos só respeitar a ordem pelas quais estão definidas em XX, como podemos associar cada nível à variável que preferirmos - esta escolha é bastante poderosa, podendo tornar as nossas procuras substancialmente mais eficientes. Encontram-se abaixo dois exemplos da mesma procura, que seguem ordenações das variáveis por nível diferentes, por forma a ilustrar as diferenças que pequenas alterações podem surtir. Note-se que, para o mesmo problema (problema este relativamente simples, com poucas variáveis e restrições), conseguimos reduzir em 50%50\% o número de testes de consistência realizados!

Uma das heurísticas clássicas para fazer esta escolha é, a cada instante, escolher a variável que apresenta atualmente o menor número de possibilidades, e delegar todo o nível à "expansão" dessa variável. Esta é a Heurística dos Valores Remanescentes Mínimos, MRV\text{MRV}, que tem por base a lógica de que "quanto menos valores possíveis tiver para tratar, mais rápido começo a falhar", acabando assim por fazer pruning da árvore mais cedo (e evitando pelo meio processamento desnecessário) - se um passo mais acima tiver falhado, em princípio fico a saber mais cedo se estou a ir por um caminho errado ou não. Esta heurística não ajuda, contudo, em todas as nossas procuras: em casos onde as restrições iniciais não permitam ter variáveis mais restringidas que outras, podemos utilizar uma heurística adicional, a Heurística do Maior Grau, por forma a procurar reduzir o fator de ramificação da árvore no futuro. Tal como tínhamos notado mais acima ao falar do exemplo do mapa australiano, colorir South Australia leva a que um grande número de variáveis fique, de repente, com o respetivo domínio mais pequeno, já que tem um grande número de adjacências. Esta heurística pega nessa lógica e formaliza-a: a cada nível, escolhemos a variável envolvida no maior número de restrições (num grafo, a variável com maior grau), já que atribuir valores a essa variável deverá criar um "efeito dominó" sobre uma área maior do problema.

Note-se, claro, que podemos usar estas heurísticas em conjunto no mesmo problema. Quando o fazemos, por norma, aplicamos MRV\text{MRV} primeiro, utilizando a de maior grau como forma de desempate.

Escolher o Próximo Valor

Escolhida a variável, podemos ainda escolher a ordem do valor que pretendemos atribuir primeiro - da mesma maneira que há escolhas de variáveis que nos permitem fazer um pruning antecipado à árvore, também deverão haver heurísticas para escolhas de valores que permitam procuras mais eficientes.

Ora, se o MRV\text{MRV} pretendia que se "falhasse" tão cedo quanto possível, por forma a nunca ter de avançar muito pela árvore sem ser o teoricamente necessário, aqui vamos querer precisamente o oposto: vamos sempre escolher os valores que nos levem a falhar o menos possível - isto porque não só queremos detetar falhas tão cedo quanto possível, como também vamos querer sempre entrar no ramo mais promissor. Esta dicotomia é explicada da seguinte forma por Max Welling:

In all stages of the searching for one solution, we want to enter the most promising branch, but we also want to detect inevitable failure sooner.

MRV\text{MRV}: the variable that is most likely to cause failure in a branch is assigned first. The variable must be assigned at some point, so if it is doomed to fail, we’d better found out soon.

LCV\text{LCV}*: tries to avoid failure by assigning values that leave maximal flexibility for the remaining variables. We want our search to succeed as soon as possible, so given some ordering, we want to find the branch that is more likely to succeed.

Nesta thread, podem encontrar uma resposta mais detalhada sobre o porquê de se utilizarem estas heurísticas (escrita melhor do que eu a conseguiria escrever).

* LCV\text{LCV}, de Least Constraining Value, corresponde à heurística que, entre os valores passíveis de atribuição a uma variável, escolhe aquele que tem menos restrições impostas (eliminando, portanto, menos valores dos domínios de outras variáveis).

Adiciona-se ainda o seguinte trecho do livro que acompanha a cadeira, que também pode ser útil (página 217217, secção 6.3.16.3.1):

Why should variable selection be fail-first, but value selection be fail-last? It turns out that, for a wide variety of problems, a variable ordering that chooses a variable with the minimum number of remaining values helps minimize the number of nodes in the search tree by pruning larger parts of the tree earlier. For value ordering, the trick is that we only need one solution; therefore it makes sense to look for the most likely values first. If we wanted to enumerate all solutions rather than just find one, then value ordering would be irrelevant.

Procura e Inferência

Até agora, vimos como utilizar a inferência a nosso favor no pré-processamento de um CSP. De seguida, vimos como boas procuras (com boas heurísticas) podem fazer um pruning antecipado e cuidado da árvore de procura, levando a que encontremos soluções completas e consistentes. Chegou, agora, a altura de combinar ambas estas noções, por forma a chegar a soluções verdadeiramente ótimas para estes problemas: a inferência já consegue ser de grande utilidade para pré-processar o nosso problema, mas consegue ser ainda mais útil logo após um passo numa procura: se conseguirmos, descendo apenas um nível, determinar que tudo o que está para baixo vai levar a soluções inconsistentes, é da maior relevância usar essas estratégias a nosso favor. Uma das formas de inferência clássicas utilizadas neste contexto é forward checking.

Forward Checking

À medida que vamos atribuindo valores a variáveis, fazemos com que todas as suas adjacências (não atribuídas) sejam consistentes em arco com ela própria. Se uma das variáveis ficar com domínio vazio, ou experimentamos um valor diferente para a variável em mãos, ou fazemos backtrack. Temos, claro, que se fizermos backtrack até à raiz, deduzimos que não existe solução completa e consistente para o problema. Adiciona-se ainda que, como estamos apenas a verificar sucessivamente a consistência de arco de várias variáveis, caso esse tipo de pré-processamento (via AC-3\text{AC-3}, por exemplo) já tenha sido feito, não haverá utilidade em fazê-lo enquanto procuramos.

Abaixo, podemos ver o exemplo de um cenário em que forward checking leva a que encontremos inconsistências relativamente rápido:

Exemplo

Geralmente, combinamos forward checking com o MRV\text{MRV} - vamos sucessivamente restringindo os domínios das variáveis e escolhendo as variáveis mais restritas!

Existe, contudo, um problema com este tipo de abordagem: não consegue detetar inconsistências para lá do "passo diretamente a seguir". Basta pensar, por exemplo, que quando acima pintámos Western Australia a vermelho e Queensland a verde, podíamos empiricamente notar que tínhamos uma inconsistência em mãos, já que South Australia e Northern Territory são adjacentes e os respetivos domínios são constituídos exclusivamente pela cor azul. É aqui que entra o algoritmo MAC\text{MAC}, de Maintaining Arc Consistency, que consegue precisamente "olhar para a frente", conseguindo aperceber-se de mais inconsistências que o forward checking. Em vez de apenas tornar as adjacências consistentes em arco com a variável que estamos agora a atribuir, vamos mais além e aplicamos AC-3\text{AC-3}, partindo de um set inicial que inclui todas as adjacências da variável atual, e que vai fazendo a tal propagação de restrições que AC-3\text{AC-3} realiza, conseguindo, assim, eliminar mais inconsistências e aperceber-se do fracasso mais cedo. Note-se que, tal como em forward checking, MAC\text{MAC} falha caso uma das variáveis alvo da propagação fique com domínio vazio, tendo portanto de recuar na árvore de procura.

Retrocesso Inteligente

Tal como notámos, em forward checking, que fazia todo o sentido olhar para além do "passo seguinte" (recorrendo, para tal, ao algoritmo MAC\text{MAC}), na procura em retrocesso existem abordagens análogas que reaproveitam essa lógica: nem sempre repensar as ações mais próximas (cronologicamente falando) é o mais sensato.

Pensemos, por exemplo, na seguinte ordem de eventos, seguindo uma procura com retrocesso padrão, sem recorrer a forward checking nem MAC\text{MAC}:

Se fôssemos agora tentar colorir South Australia, íamos notar que o seu domínio está agora vazio. Assim sendo, a procura com retrocesso ia dar um passo atrás, procurando colorir Tasmania com as duas outras cores, já que cronologicamente é o evento que antecede colorir SA\text{SA}. Ora, mas empiricamente sabemos que isto não faz qualquer sentido: Tasmania não tem qualquer restrição associada a South Australia, e, além disso, o erro foi feito antes! A ordem cronológica, aqui, acaba por não ser a maneira mais eficiente de chegar a uma solução. Existem várias formas de tentar perceber "onde é que começou a correr mal", por forma a voltar até esse ponto e corrigir o que de mal foi feito. A primeira dessas formas é o backjumping.

Backjumping

O método é bastante simples: mantemos, para cada variável XX, uma pilha de conflito: o conjunto de variáveis (e respetivas atribuições) que retiraram valores ao domínio de XX. Quando encontramos um cenário em que XX tem domínio vazio, retiramos a primeira variável da pilha e fazemos backtrack até lá - note-se que no exemplo supra-referido, backjumping ia permitir que "saltássemos" Tasmania, voltando diretamente para Victoria e fazendo logo aí uma nova atribuição.

Procura em Retrocesso Padrão Procura em Retrocesso com backjumping

Note-se ainda que realizar forward checking e backjumping em simultâneo é redundante: forward checking impediria que chegássemos a nós em conflito antes sequer de lá chegarmos! Bem, assim sendo, esta estratégia aparenta não ter grande utilidade, se forward checking permite um pruning antecipado de tudo o que backjumping consegue ver. A ideia, não o método, é o que importa aqui: poder voltar atrás sem ser por ordem cronológica direta é bastante relevante.

Considere-se o exemplo seguinte, mais interessante que o anterior: vamos procurar colorir primeiro Western Australia, depois New South Wales e por fim Tasmania, todas de vermelho:

Se fôssemos agora tentar colorir NT, Q, V\text{NT, Q, V} e SA\text{SA}, empiricamente conseguimos notar que não existe qualquer atribuição de cores possível que leve a uma solução completa e consistente. O método de backjumping regular, contudo, não deteta a situação logo, acabando por ainda tentar ir atribuir valores a NT\text{NT} (sendo que posteriormente vai descobrir que não se chega a solução, qualquer que seja a subsequente combinação de variáveis) em vez de voltar atrás a NSW\text{NSW} e seguir um rumo diferente. De forma em tudo análoga à relação entre forward checking e o MAC\text{MAC}, vamos ter uma relação entre backjumping e o conflict-directed backjumping: tal como MAC\text{MAC} permitia que olhássemos para lá do passo diretamente à nossa frente, este último método permite que usemos pilhas de conflito de maneira diferente, por forma a aproveitar melhor o contexto atual do problema e verificar antecipadamente se uma dada atribuição leva a cenários sem solução.

Retrocesso com Salto Dirigido ao Conflito

Recupera o conceito de pilha de conflito utilizado pelo backjumping explicado mais acima, com o "retrocesso" a funcionar de maneira um pouco diferente: se anteriormente a pilha de conflito acima na árvore permanece inalterada, mesmo depois do retrocesso, aqui ao subir na árvore recalculamos o conjunto de conflito da variável para a qual estamos a "saltar" como se segue (seja XX a variável mais abaixo e YY a variável mais acima):

conf(Y)=conf(Y)conf(X){Y}conf(Y) = conf(Y) \cup conf(X) - \{Y\}
Exemplo

Consideremos a seguinte extensão ao exemplo ilustrado mais acima, onde para além de colorir WA, NSW\text{WA, NSW} e T\text{T} a vermelho, colorimos ainda NT\text{NT} a azul e Q\text{Q} a verde:

Ora, se quisermos colorir SA\text{SA} a seguir, vamos reparar que o seu domínio está agora vazio; assim sendo, vamos querer fazer um backjump: mas para onde?

Bem, a sua pilha de conflito, conf(SA)conf(SA), é agora {WA,NT,Q}\{WA, NT, Q\} (note-se que NSW\text{NSW} não entra aqui, porque pintar WA\text{WA} de vermelho ocorreu antes de pintar NSW\text{NSW} dessa cor). Recorrendo à expressão mencionada mais acima, vamos buscar QQ à pilha e obter:

conf(Q)=conf(Q)conf(SA){Q}={NSW,NT}{WA,NT}{Q}={WA,NSW,NT}\begin{aligned} conf(Q) &= conf(Q) \cup conf(SA) - \{Q\} \\ &= \{NSW, NT\} \cup \{WA, NT\} - \{Q\} \\ &= \{WA, NSW, NT\} \end{aligned}

Ora, as atribuições associadas a cada variável em conf(Q)conf(Q) são, respetivamente:

WA=vermelhoNSW=vermelhoNT=azul\begin{aligned} WA &= \text{vermelho} \\ NSW &= \text{vermelho} \\ NT &= \text{azul} \end{aligned}

Ora, mas se o backjump veio tentar substituir verde, e não existem outras cores por que possamos descer, vamos ter de voltar a subir, desta vez para NT\text{NT}:

conf(NT)=conf(NT)conf(Q){NT}={WA}{WA,NSW,NT}{NT}={WA,NSW}\begin{aligned} conf(NT) &= conf(NT) \cup conf(Q) - \{NT\} \\ &= \{WA\} \cup \{WA, NSW, NT\} - \{NT\} \\ &= \{WA, NSW\} \end{aligned}

Íamos depois ter apenas a cor verde livre para NT\text{NT}, que obrigaria a que Q\text{Q} ficasse azul - entrávamos no mesmo problema, voltávamos para trás, e ficamos agora sem valores por atribuir, pelo que saltamos novamente para cima, desta vez para NSW\text{NSW}:

conf(NSW)=conf(NSW)conf(NT){NSW}={WA}{WA,NSW}{NSW}={WA}\begin{aligned} conf(NSW) &= conf(NSW) \cup conf(NT) - \{NSW\} \\ &= \{WA\} \cup \{WA, NSW\} - \{NSW\} \\ &= \{WA\} \end{aligned}

Retrocedendo para NSW\text{NSW}, vamos agora ter a possibilidade de experimentar valores que não vermelho; conseguimos, assim, saltar três níveis (em vez de só um), uma melhoria significativa em termos de desempenho, considerando que conseguimos evitar subidas e descidas desnecessárias em ramos intermédios da árvore.

Existe, contudo, algo que continua a faltar à nossa metodologia: o retrocesso inteligente até agora não arranjou maneira de impedir que "cometamos o mesmo erro mais que uma vez". Sempre que temos de fazer backjump, é porque algo de errado aconteceu até lá chegarmos - um subconjunto da pilha de conflito há-de ser responsável pelo erro. Seria fantástico se conseguíssemos perceber que conjunto de atribuições causou o erro, por forma a não voltar a repeti-lo. É aqui que entra a aprendizagem de restrições.

Aprendizagem de Restrições

Para implementar esta noção de subconjunto de atribuições que causou o erro, o no-good, vamos, assim que encontramos uma inconsistência e começamos a subir, procurar manter o conjunto mínimo de variáveis da pilha de conflitos que estão a causar o problema: quanto mais subimos, mais estamos a restringir esse conjunto (que é, aliás, ideal: saber que uma só atribuição leva a que não haja soluções possíveis é muito melhor do que saber que uma combinação de nn atribuições leva a cenários sem solução possível, já que durante uma procura vamos, em média, encontrar muitos mais casos com aquela atribuição específica (que podemos cortar) do que com uma combinação maior de atribuições). Este subconjunto pode ser, depois, utilizado de duas maneiras: tanto mantendo uma lista de conjuntos no-good em cache, como criando restrições de ordem superior envolvendo todas as atribuições em questão.

A noção de no-good é, claro, independente da utilização de saltos para trás ou de forward checking, podendo ser utilizada sem problemas em ambas as abordagens.

Procura Local para CSPs

Por procura local entendemos um algoritmo que anda de solução em solução (num espaço de soluções candidatas) à procura de uma solução considerada ótima. Pensando na árvore de procura, onde as folhas correspondem a atribuições completas, vamos andar a percorrer as várias folhas à procura de uma solução ótima - aqui, corresponderá a uma solução consistente.

Como funciona, então, a procura entre as folhas? Aliada à noção de procura, há-de existir também a ideia de melhores e piores procuras - não vamos fazer procuras aleatórias, mas sim procurar sempre que a "escolha seguinte" apresente uma configuração mais próxima de uma solução consistente que a anterior. A transição entre estados na procura vai, então, para tentar encontrar melhores configurações, procurar re-atribuir variáveis partindo de uma configuração inicial (que pode ou não ser aleatória).

Procura Local em CSPs - Heurística Min-Conflicts

A abordagem-padrão da procura local é relativamente simples: escolhemos de forma aleatória uma das variáveis atualmente em conflito, seja ela XX, e vamos procurar um valor vv tal que, de entre todos os valores passíveis de atribuição para XX, vv é o que viola o menor número de restrições possível. Temos, claro, que se houver vários valores a violar o mínimo número de restrições possível, podemos escolher um deles aleatoriamente e avançar.

O exemplo clássico utilizado para ilustrar a eficiência da procura local em CSPs é o das nn rainhas. Considere-se o seguinte tabuleiro, cuja configuração inicial vai ser a seguinte atribuição aleatória de valores (completa):

Todas as variáveis estão atualmente em conflito, pelo que a solução, já de si aleatória, mais aleatória ficou. Se escolhermos, por exemplo, a rainha na segunda linha e segunda coluna, vamos notar que a atribuição que leva a um menor número de conflitos é subir 11 casa para cima (aqui fica sem conflitos, enquanto que qualquer outro movimento mantém pelo menos um conflito):

Desta vez, três das variáveis estão em conflito - escolhendo, entre elas, uma aleatória (seja ela a variável da terceira linha e terceira coluna), podemos notar que movê-la 11 casa para baixo remove não só todos os seus conflitos como os das outras variáveis, ficando assim com uma solução completa e consistente!

Note-se, claro, que resolver o problema em 22 passos acabou por revelar alguma sorte: caso no segundo passo tivéssemos escolhido outra variável, podíamos precisar de um passo extra por forma a obter uma solução completa e consistente. Não é, contudo, isso que está aqui em causa: o que é relevante é que conseguimos obter uma solução com relativamente pouco esforço. Mais, este método é escalável! Conseguimos inclusive resolver o problema do milhão de rainhas em 5050 passos em média! Para o problema das nn rainhas, o tempo de execução da procura parece quase dissociar-se da dimensão dos domínios, sendo quase realizada em "tempo constante" para tamanhos muito grandes.

A procura local não se adequa, contudo, a todo o tipo de CSPs - caso contrário, tínhamos em mãos o santo Graal das procuras, e nunca mais íamos precisar de fazê-las de maneira diferente. Esta procura funciona principalmente em problemas cujas soluções estão densamente distribuídas pelo espaço de estados, e onde qualquer solução sirva (desde que seja consistente). No entanto, não nos permite provar que não há solução, o que em certos casos pode ser um problema.

Estrutura de Problemas

Página em Construção

Esta secção encontra-se atualmente incompleta.

O conteúdo será adicionado assim que possível.

tl;dr enquanto não se coloca tudo:

  • se um CSP não tiver ciclos, podemos chegar a uma solução em tempo nd2nd^2 (vs dnd^n), linear no número de variáveis;
  • técnicas para transformar CSPs com estrutura de grafo com ciclos em árvores (sem ciclos):
    • remoção de nós
    • colapsagem de nós

coloco explicações em condições quando conseguir <3 até lá vejam os slides e o livro


Adicionamos que esta secção corresponde ao sexto capítulo do livro que acompanha a cadeira (Constraint Satisfaction Problems).