Pesquisa com propagação de restrições
Pesquisa para problemas de atribuição
Nos problemas de atribuição pretende-se atribuir valores a um conjunto de variáveis, respeitando um conjunto de restrições.
Exemplos:
Problema das 8 rainhas - distribuir 8 rainhas num tabuleiro de xadrez de forma a que haja uma e uma só rainha em cada linha e em cada coluna e não haja mais do que uma rainha em cada diagonal.
Invenção de palavras cruzadas – dada uma matriz de palavras cruzadas vazia, preencher os espaços brancos com letras, de forma a que a matriz possa ser usada como passatempo de palavras cruzadas.
Técnicas de resolução de problemas de atribuição:
Método construtivo – usando técnicas de pesquisa em árvore.
Em cada passo da pesquisa atribui-se um valor a uma variável.
Método construtivo combinado com propagação de restrições.
Resolução por melhorias sucessivas.
Pesquisa com propagação de restrições em problemas de atribuição
Construir um grafo de restrições:
Em cada nó do grafo está uma variável.
Um arco dirigido liga um nó i a um nó j se o valor da variável de j impõe restrições ao valor da variável de i.
Um arco (i,j) é consistente se, para cada valor da variável i, existe um valor da variável j que não viola as restrições.
Tipicamente, usa-se uma estratégia de pesquisa em profundidade; em cada iteração da pesquisa, faz-se o seguinte:
Seleciona-se arbitrariamente um dos valores possíveis para uma das variáveis (descartam-se os restantes).
Restringem-se os conjuntos de valores possíveis das restantes variáveis por forma a que os arcos do grafo de restrições continuem consistentes.
Nota: Neste caso, cada estado da pesquisa não representa uma situação ou configuração possível do mundo, como acontece no problema dos blocos; o estado é constituído pelos conjuntos de valores possíveis para as variáveis.
Algoritmo
Inicialização: o nó inicial da árvore de pesquisa é composto por todas as variáveis e todos os valores possíveis para cada uma delas.
Se pelo menos uma variável tem um conjunto de valores vazio, falha e retrocede; se não puder retroceder, a pesquisa falha.
Se todas as variáveis têm exactamente um valor possível, tem-se uma solução; retornar com sucesso.
Expansão: Escolher arbitrariamente uma variável Vk e, de entre os valores possíveis, um dado valor Xkl – descartar os restantes valores possíveis dessa variável.
Propagação de restrições: para cada arco (i,j) no grafo de restrições, remover os valores na variável Vi por forma a que o arco fique consistente.
Caso tenha sido preciso remover valores na origem de algum arco, voltar a repetir o passo 5.
Voltar ao passo 2.
Propagação de restrições
Algoritmo
Os passos 5 e 6 do algoritmo anterior executam a propagação de restrições.
Esta parte do processo é suportada por uma fila de arestas do grafo de restrições.
Inicialmente, a fila contém as arestas que apontam para a variável cujo valor foi fixado.
Tipos de restrições
Restrições unárias – envolvem apenas uma variável.
Podem ser satisfeitas através de pré-processamento do domínio de valores da variável – aproveitam-se apenas os valores que satisfazem a restrição.
Restrições binárias – envolvem duas variáveis.
Uma restrição binária é directamente representada por uma aresta no grafo de restrições.
Restrições de ordem superior – envolvem três ou mais variáveis.
Através da introdução de variáveis auxiliares, uma restrição de ordem superior pode ser transformada num conjunto de restrições binárias e/ou unárias.
Exemplo
Quebra-cabeças critpoaritmético
Restrições:
Conversão para restrições binárias
No exemplo anterior, a restrição ternária 2∙O = R + 10∙X1 pode ser transformada no seguinte conjunto de restrições:
Restrições binárias:
O = primeiro(Aux)
R = segundo(Aux)
X1 = terceiro(Aux)
Restrição unária:
2∙ primeiro(Aux) = segundo(Aux) + 10∙ terceiro(Aux)
Aux é uma variável auxiliar cujo domínio é o produto cartesiano dos domínios de O, R e X1.
A restrição unária sobre Aux pode ser satisfeita através de pré- processamento.
Last updated
