Domínios Finitos
A eficiência das programas em domínios finitos (incluindo
booleanos) podem ainda ser melhoradas pelo uso de
•
Algoritmos de Propagação adequados
•
Heurísticas para escolha da variável e do valor
Antes de investigarmos estes aspectos, nomeadamente a
propagação de restrições, convém formalizar alguns
conceitos tais como
•
restrições e rede de restrições
•
soluções parciais e totais
•
satisfação e consistência
1
Domínios Finitos
Definição (Domínio de Variável):
O domínio de uma variável é o conjunto (finito) de
valores que podem ser atribuídos a uma variável.
Dada uma variável X, o seu domínio será normalmente
denotado por dom(X) ou simplesmente Dx.
Exemplo:
O Problema das n rainhas pode ser modelado através de n
variáveis X1 a Xn, todas com domínio de 1 a n.
Dom(Xi) = {1,2, ..., n}
ou
Xi :: 1..n.
2
Domínios Finitos
Definição (Etiqueta):
Uma etiqueta é um par Variável-Valor, sendo o valor um
dos elementos do domínio da variável.
Com a definição de etiqueta pretende-se formalizar a
atribuição do valor à variável.
Definição (Etiqueta Composta):
Uma etiqueta composta é um conjunto de etiquetas
referentes a variáveis distintas.
Com a definição de etiqueta pretende-se formalizar a
noção de solução (parcial), em que algumas (todas) variáveis
do problema têm valor atribuído.
3
Domínios Finitos
Definição (Restrição):
Dado um conjunto de variáveis, uma restrição é um
conjunto de etiquetas compostas definidas nessas
variáveis.
De facto, uma restrição pode ser vista como um
subconjunto do produto cartesiano dos domínios das
variáveis envolvidas na restrição.
Por exemplo, para qualquer restrição Rijk envolvendo as
variáveis Xi, Xj e Xk, teremos
Rijk  dom(Xi) x dom(Xj) x dom(Xk)
4
Domínios Finitos
Dada uma restrição R, o conjunto de variáveis da restrição
será denotado por Vars(R).
De uma forma simétrica, o conjunto de restrições em que
participa a variável X é denotado por cons(X).
De notar ainda que sendo a restrição uma relação (não um a
função) temos que Rij = Rji.
As restrições podem ser especificadas por
• Extensão: através da enumeração das etiquetas
permitidas; ou
• Intenção: através de um predicado (procedimento)
que determina as etiquetas permitidas
5
Domínios Finitos
Por exemplo, dadas as variáveis X1 e X3 do problema das 4
rainhas, existe uma restrição entre elas, R13, que pode ser
especificada
Por extensão:
R13 = {{X1-1, X3-2}, {X1-1, X3-4}, {X1-2, X3-1}, {X1-2, X3-3},
{X1-3, X3-2}, {X1-3, X3-4}, {X1-4, X3-1}, {X1-4, X3-3}}
ou, omitindo as variáveis
R13 = {<1,2>, <1,4>, <2,1>, <2,3>, <3,2>, <3,4>, <4,1>, <4,3>}
Por intenção:
R13 = (X1  X3)  (1+X1  3+X3)  (3+X1  1+X3)
6
Domínios Finitos
Definição (”Aridade” de uma Restrição):
A aridade de uma restrição R é o número de variáveis
sobre as quais a restrição é definida, ou seja a
cardinalidade do conjunto vars(R).
Apesar das restrições poderem ter uma aridade arbitrária,
um subconjunto muito importante de restrições é
constituído pelas restrições binárias.
A importância dessas restrições advém de que
1. Todas as restrições podem ser convertidas em
restrições binárias.
2. Existem conceitos e algoritmos apropriados para
essas restrições.
7
Domínios Finitos
Conversão para Restrições Binárias
Uma restrição n-ária, R, constituída por k etiquetas
compostas nas suas variáveis X1 a Xn, é equivalente a n
restrições binárias, Bi, através da adição de uma variável
adicional, Z, que tem como domínio os valores de 1 a k.
Com efeito, as k etiquetas
arbitrariamente ordenadas.
n-árias
podem
ser
Cada uma das n restrições binárias Bi relaciona uma das n
variáveis Xi com a nova variável Z.
A etiqueta composta {Xi-vi, Z-z} pertence à restrição Bi sse
Xi-vi pertencer à z-ésima etiqueta composta que define R.
8
Domínios Finitos
Exemplo: Dadas as variáveis X1 a X3, com domínios 1 a 3,
converter em restrições binárias a restrição R que impõe
valores diferentes para as três variáveis.
R(X1, X2, X3) = {<1,2,3>,<1,3,2>,<2,1,3>,<2,3,1> ,<3,1,2>,<3,2,1>}
Associemos a cada etiqueta composta um valor de 1 a 6
1 : <1,2,3>,
2 : <1,3,2>,
... 6: <3,2,1>
As restrições binárias equivalentes à restrição inicial são
B1(Z, X1) = {<1,1>, <2,1>, <3,2>, <4,2>, <5,3>, <6,3>}
B1(Z, X1) = {<1,2>, <2,3>, <3,1>, <4,3>, <5,1>, <6,2>}
B1(Z, X1) = {<1,3>, <2,2>, <3,3>, <4,1>, <5,2>, <6,1>}
9
Domínios Finitos
Definição (Satisfação de Restrição 1):
Uma etiqueta composta satisfaz um restrição se as suas
variáveis (da etiqueta e da restrição) forem as mesmas e
se a etiqueta for um elemento da restrição.
Na prática, é conveniente generalizar a satisfação a
situações em que as etiquetas compostas contêm
estritamente as variáveis da restrição.
Definição (Satisfação de Restrição 2 ):
Uma etiqueta composta satisfaz um restrição se as suas
variáveis incluirem as da restrição e se a sua (da
etiqueta) projecção para as variáveis da restrição fôr um
elemento da restrição.
10
Domínios Finitos
Definição (Problema de Satisfação de Restrições):
Um problema de satisfação de restrições é um triplo
<V,D,R> em que
• V é o conjunto das variáveis do problema
• D é o domínio das variáveis
• R é o conjunto das restrições do problema
Definição (Solução dum Problema):
Uma solução de um problema de satisfação de restrições
P = <V,D,R> é uma etiqueta composta sobre as variáveis V
do problema que satisfaz todas as restrições R.
11
Domínios Finitos
Em muitas situações é conveniente considerar as várias
restrições de um problema sob a forma de um grafo.
Definição (Grafo ou Rede de Restrições):
O grafo ou rede de restrições de um problema de
restrições binárias tem como nós as variáveis do
problema. Para cada restrição não-trivial do problema
envolvendo uma ou duas variáveis, o grafo contém um
arco ligando os nós correspondentes a essas variáveis
Quando os problemas contêm restrições com aridade
arbitrária, elas podem ser convertidas nas suas
equivalentes binárias.
12
Domínios Finitos
Quando por algum motivo não seja conveniente converter
as restrições n-árias em binárias, o problema pode ser
representado por um hiper-grafo.
Definição (Hiper-Grafo de Restrições):
Qualquer problema de restrições n-árias arbitrárias
pode ser representado através de um hiper-grafo, cujos
nós são as variáveis do problema. Para cada restrição do
problema, o grafo contém um hiper-arco ligando os nós
correspondentes às variáveis envolvidas na restrição.
Como é óbvio, se o problema só contém restrições binárias,
o hiper-grafo de restrições degenera num grafo.
13
Domínios Finitos
Exemplo: O problema das 4 rainhas pode ser definido pelo
seguinte grafo:
R12
X2 in 1..4
R24
X1 in 1..4
R23
R14
R13
{<1,2>, <1,4>, <2,1>, <2,3>,
<3,2>, <3,4>, <4,1>, <4,3>}
X3 in 1..4
R34
X4 in 1..4
14
Domínios Finitos
Definição (Grafo de Restrições Completo):
Um grafo de restrições é completo quando existem arcos
ligando qualquer par de nós (isto é, quando existe uma
restrição sobre qualquer par de variáveis).
O problema das 4 rainhas tem um grafo completo. No
entanto, esse não é sempre o caso, podendo os grafos ser
“esparsos” por não conterem alguns arcos potenciais. Nesse
caso importa definir a densidade de um grafo.
Definição (Densidade de um Grafo de Restrições):
A densidade de um grafo de restrições corresponde à
razão entre o número de arcos e o número de arcos de
um grafo completo com o mesmo número de nós.
15
Domínios Finitos
Em princípio, a “dificuldade” de um problema de restrições
está relacionada com a densidade do seu grafo.
Intuitivamente, quanto mais denso fôr o grafo, mais difícil
é o problema, já que há mais “oportunidades” de invalidar
uma etiqueta composta.
Não confundir a dificuldade de um problema com a
dificuldade de resolver um problema. Em particular, um
problema pode ser trivialmente verificado como impossível!
A “dificuldade” de um problema está também relacionada
com a dificuldade de cada restrição. Essa dificuldade pode
ser avaliada através do seu grau de aperto (“tightness”).
16
Domínios Finitos
Definição (Grau de Aperto de uma Restrição):
Dada uma restrição R sobre as variáveis X1 ... Xn, com
domínios D1 a Dn, o grau de aperto da restrição R é dado
pela razão entre o número de etiquetas que a definem e
a cardinalidade do produto cartesiano D1 x D2 x .. Dn.
Por exemplo, a restrição R13 no problemas das 4 rainhas,
definida sobre as variáveis X1 e X3 com domínios 1..4
R13 = {<1,2>, <1,4>, <2,1>, <2,3>, <3,2>, <3,4>, <4,1>, <4,3>}
tem um grau de aperto de 8/(4*4) = 1/2.
Este conceito pode ser generalizado para o problema como
um todo.
17
Domínios Finitos
Definição (Grau de Aperto de um Problema):
O grau de aperto de um problema definido nas variáveis
X1 ... Xn, é obtido pela razão entre o número das suas
soluções e a cardinalidade do produto cartesiano
D1 x D2 x .. Dn.
Por exemplo, o problema das 4 rainhas que admite as
soluções <2,4,1,3> e <3,1,4,2>
tem um grau de aperto de 2/4*4*4*4 = 1/128.
18
Domínios Finitos
A dificuldade de resolver um problema de restrições está
relacionada quer com a densidade do seu grafo, quer com o
seu grau de aperto.
Na realidade, para testar algoritmos de resolução de
problemas de restrições são criadas aleatoriamente
instâncias de problemas parametrizadas pelos valores
escolhidos para a densidade e grau de aperto das
restrições.
O estudo destes aspectos levou a concluir sobre a
existência de uma transição de fase, entre os problemas
trivialmente satisfazíveis e trivialmente insatisfazíveis,
que é necessário ter em conta quando se testam algoritmos
de resolução.
19
Domínios Finitos
Um outro aspecto a considerar na dificuldade de resolver
um problema de restrições está relacionada com a
existência de valores e etiquetas redundantes em
restrições.
Definição (Valor Redundante):
Um valor do domínio de uma variável é redundante, se
não aparece em nenhuma solução do problema.
Definição (Etiqueta Redundante):
Uma etiqueta composta de uma restrição é redundante
se ela não é a projecção para as variáveis da restrição de
qualquer solução do problema.
20
Domínios Finitos
Exemplo: O problema das 4 rainhas só admite as soluções
<2,4,1,3> e <3,1,4,2>.
Desta forma os valores 1 e 4 são redundantes no domínio
das variáveis X1 e X4, e os valores 2 e 3 são redundantes no
domínio das variáveis X2 e X3.
Por outro lado, as etiquetas <2,3> e <3,2> são redundantes
na restrição R13.
21
Domínios Finitos
Exemplo: O problema das 4 rainhas que só admite as
soluções <2,4,1,3> e <3,1,4,2> pode ser “simplificado” por
eliminação dos valores e etiquetas redundantes.
R12
X2 in 1,2,3,4
R24
X1 in 1,2,3,4
R23
R14
R13
{<1,2>, <1,4>, <2,1>, <2,3>,
<3,2>, <3,4>, <4,1>, <4,3>}
X3 in 1,2,3,4
R34
X4 in 1,2,3,4
22
Domínios Finitos
Os problemas inicial e “simplificado” são equivalentes.
Definição (Problemas Equivalentes):
Dois problemas P1 = <V1, D1, R1> e P2 = <V2, D2, R2> são
equivalentes sse têm as mesmas variáveis (i.e. V1 = V2) e
o mesmo conjunto de soluções.
A “simplificação” pode igualmente ser formalizada
Definição (Problema Reduzido):
Um problema P=<V,D,R> é reduzido para P’=<V’, D’, R’> se
a) P e P’ são equivalentes;
b) os domínios D’x estão incluídos em Dx; e
c) as restrições R’ são igualmente ou mais restritivas
que as restrições de R.
23
Resolução Construtiva em Domínios Finitos
Como se viu antes, e independentemente de se poder
reduzir o problema, um processo de geração e teste é
muito ineficiente.
Assim é preferível utilizar um processo de resolução
construtivo e incremental. Neste processo, uma etiqueta
composta vai sendo completada (aspecto construtivo),
variável a variável (aspecto incremental), até se atingir
uma solução.
No entanto há que garantir que em cada passo de
“completamento” da etiqueta composta, a etiqueta
resultante ainda tem potencial para “atingir” uma solução.
24
Resolução Construtiva em Domínios Finitos
Idealmente, uma etiqueta composta deverá ser a projecção
de uma solução do problema. Infelizmente, num processo
de resolução do problema, não se conhecem (geralmente) as
soluções!
Assim, pode recorrer-se a uma noção
nomeadamente a noção de solução parcial
mais
fraca,
Definição (Solução Parcial-k):
Uma solução parcial de um problema de satisfação de
restrições P = <D,V,R> é uma etiqueta composta sobre um
subconjunto de k das variáveis V do problema que
satisfaz todas as restrições de R definidas
completamente por essas variáveis.
25
Resolução Construtiva em Domínios Finitos
Este é o princípio de resolução dos problemas de restrições
de domínios finitos através do retrocesso. Este processo
pode ser visto como uma pesquisa em árvore, em que as
soluções parciais correspondem aos nós da árvore e as
soluções às suas folhas.
1
2
4
3
4
1
1
3
4
2
26
Resolução Construtiva em Domínios Finitos
Quanto mais reduzido fôr um problema mais fácil será, em
princípio resolvê-lo.
Com efeito, dado um problema P=<D,V,R> com n variáveis
(i.e. V = {X1,..,Xn}) o espaço de pesquisa potencial onde se
poderão encontrar soluções (ou seja as folhas da árvore de
pesquisa onde se encontram etiquetas compostas do tipo
{<X1-v1>, ..., <Xn-vn>}), tem uma cardinalidade
#S = #D1 * #D2 * ... * #Dn
Sendo a cardinalidade dos domínios idênticas (#Di = d) o
espaço de pesquisa
#S = d n
é exponencial na dimensão n do problema.
27
Resolução Construtiva em Domínios Finitos
Se em vez de cardinalidade d do problema inicial, se
trabalhar num problema reduzido em que a cardinalidade
dos domínios fôr d’ (<d) o espaço de pesquisa potencial
diminui exponencialmente!
S’/S = d’n / dn = (d’/d)n
Essa diminuiução exponencial pode ser muito significativa
para valores “razoavelmente” grandes de n. Por exemplo:
n
S/S'
7
6
5
4
3
d
6
5
4
3
2
d'
10
4.6716
6.1917
9.3132
17.758
57.665
20
30
21.824 101.95
38.338 237.38
86.736 807.79
315.34 5599.7
3325.3 191751
40
476.29
1469.8
7523.2
99437
1E+07
50
60
70
80
2225 10395 48560 226852
9100.4 56348 348889 2E+06
70065 652530 6E+06 6E+07
2E+06 3E+07 6E+08 1E+10
6E+08 4E+10 2E+12 1E+14
90
1E+06
1E+07
5E+08
2E+11
7E+15
100
5E+06
8E+07
5E+09
3E+12
4E+17
28
Resolução Construtiva em Domínios Finitos
Na prática, esta redução potencial do espaço de pesquisa
tem um custo, correspondente à computação dos valores (e
etiquetas) redundantes.
Uma análise detalhada do processo é extremamente
complexa de uma forma geral, pois o processo depende
muito da instância do problema em causa.
No entanto, em geral, podemos considerar que o esforço
computacional na redução de domínios não é proporcional à
redução obtida tornando-se cada vez menos “eficiente”.
Assim, a partir de um certo ponto a redução do espaço de
pesquisa já não compensa, pois acarreta um maior aumento
da computação para atingir essa redução!
29
Resolução Construtiva em Domínios Finitos
Qualitativamente, este processo pode ser apresentado
através do seguinte gráfico
R+P Custo
Combinado
R - Custo de Redução
P- Custo de Pesquisa
Esforço dispendido na redução do problema
30
Resolução Construtiva em Domínios Finitos
O esforço de redução de domínios deve ser entendida no
esquema de resolução de problema que alterna enumeração
com propagação.
Com efeito, na especificação de um programa (em
Programação em Lógica com Restrições) o lançamento das
restrições antecede a enumeração das variáveis.
Problema ( Vars):Declaração de Variáveis e Domínios,
Lançamento das Restrições,
Enumeração das Variáveis.
No entanto o esquema de execução alterna a enumeração
com a propagação (redução do problema) durante o
completar de uma solução parcial.
31
Resolução Construtiva em Domínios Finitos
Assim dado um problema com n variáveis X1 a Xn o esquema
de execução segue o seguinte padrão:
Declaração de Variáveis e Domínios,
Lançamento das Restrições,
indomain(X1),
% escolha com retrocesso
propagação
indomain(X2),
% escolha com retrocesso
propagação,
...
indomain(Xn-1)
% escolha com retrocesso
propagação
indomain(Xn)
% escolha com retrocesso
Há pois que balancear o esforço na redução com os
resultados obtidos na redução dos domínios.
32
Redução de Domínios
Apesar de se ter definido formalmente a redução de um
problema de restrições não foi apresentada nenhum
procedimento para o obter.
Pior, nem sequer foi definido um procedimento para
reconhecer se um problema é uma redução do problema
inicial.
Com efeito, a definição pressupõe que o problema reduzido
seja equivalente ao inicial, isto é que tenha as mesmas
soluções. No entanto, essas soluções não são, em geral,
conhecidas!
Assim, o que se pode estudar são critérios que permitam
garantir que no processo de redução não se “perdem”
soluções.
33
Redução de Domínios
Esses critérios de consistência permitem estabelecer
valores redundantes nos domínios das variáveis, de uma
forma indirecta, isto é, sem requerer o conhecimento dos
valores que pertencem a soluções do problema.
Mais exactamente, a manutenção destes critérios durante
a resolução do problema permite a eliminação destes
valores redundantes.
Em problemas de restrições binárias, os critérios mais
comuns são, com complexidade crescente, os seguintes
• Consistência dos Nó
• Consistência dos Arco
• Consistência dos Caminho
34
Redução de Domínios
Definição (Consistência de Nó):
Um problema de restrições tem os nós consistentes, se
nenhum valor no domínio das variáveis violar as
restrições unárias.
Este critério pode parecer óbvio e inútil. Ninguém vai
especificar domínios para as variáveis que não satisfaçam à
partida as restrições unárias!
No entanto, este critério deve ser entendido no contexto
do completar de uma solução parcial, tal como discutido
atrás.
35
Redução de Domínios
Exemplo: Após o lançamento das restrições, a rede de
restrições do problema das 4 rainhas é a seguinte:
R12
X1 in 1..4
R23
X2 in 1..4
R14
R13
X3 in 1..4
R34
R24
X4 in 1..4
Após a enumeração da variável X1, com a escolha de X1=1,
as restrições R12, R13 e R14 tornam-se unárias!
X2 
1,2
X2 in 1..4
R24
R23
X3 in 1..4
X3 
1,3
R34
X4 in 1..4
X4 
1,4
36
Redução de Domínios
A manutenção da consistência dos nós deverá retirar do
domínio das variáveis os valores apropriados.
X2 
1,2
R23
X2 in 3,4
X3 in 2,4
X3 
1,3
R34
R24
X4 in 2,3
X4 
1,4
Consegue-se assim uma redução de domínios semelhante à
que se conseguia no caso das restrições booleanas.
1
1
1
1
1
1
X2 
1,2
X3 
1,3
X4 
1,4
37
Redução de Domínios
Manutenção de Consistência de Nós
Dada a simplicidade do critério de consistência de nós, o
algoritmo para proceder à sua manutenção é bastante
simples e de baixa complexidade. Um possível algoritmo
para manter a consistência de nós é o algoritmo NC-1
procedimento
para X in
para v
se
NC-1(V, D, R);
V
in Dx fazer
não satisfaz(X-v, Cx) então
Dx <- Dx \ {v}
fim para
fim para
fim procedimento
38
Redução de Domínios
Complexidade espacial do algoritmo NC-1
Havendo n variáveis no problema, cada qual com d valores
no seu domínio, e assumindo-se uma representação por
extensão dos domínios das variáveis, é necessário um
espaço de nd para guardar os domínios das variáveis.
Por exemplo, o domínio inicial 1..4 das variáveis Xi do
problema das 4 rainhas, é representado pelos vectores
booleanos Xi = [1,1,1,1] ou 1111. Após a enumeração X1=1 e
a manutenção de coerência de nós, os domínios ficam
X1 = 1000, X2 = 0011, X3 = 0101 e X4 = 0110
O algoritmo NC-1 não requer espaço adicional, pelo que
tem uma complexidade espacial O(nd).
39
Redução de Domínios
Complexidade temporal do algoritmo NC-1
Havendo n variáveis no problema, cada qual com d valores
no seu domínio, e tendo em conta que cada valor é
avaliado uma vez, é fácil concluir que o algoritmo tem
uma complexidade O(nd).
Em geral, a baixa complexidade temporal e espacial permite
que o procedimento NC-1 seja
utilizado muito
eficientemente na propagação de restrições.
No entanto, a manutenção de consistência de nós, não
permite detectar todas as reduções possíveis dos domínios
das variáveis.
40
Redução de Domínios
Um critério mais exigente (e complexo) que a consistência
de nós é o de Consistência de Arcos
Definição (Consistência de Arco):
Um problema de restrições tem os arcos consistentes,
(está numa forma consistente de arcos) se,
1. Tiver todos os nós consistentes; e
2. Para qualquer etiqueta Xi-vi de qualquer variável Xi, e
para todas as restrições Rij, envolvendo as variáveis
Xi e Xj, deve existir um valor vj de suporte, isto é,
tal que a etiqueta composta {Xi-vi, Xj-vj} satisfaz a
restrição Rij.
41
Redução de Domínios
Exemplo: Após a enumeração da variável X1, com a escolha
de X1=1, a rede de restrições do problema das 4 rainhas, e
os domínios das suas variáveis são os seguintes:
X2 
1,2
X2 in 3,4
R24
R23
X3 in 2,4
R34
X4 in 2,3
X4 
1,4
X3 
1,3
1
1
1
1
1
1
X2 
1,2
X3 
1,3
X4 
1,4
No entanto a etiqueta X2-3 não tem suporte na variável X3,
já que nem a etiqueta composta {X2-3 , X3-2} nem a
etiqueta {X2-3 , X3-4} satisfazem a restrição R23.
Assim, o valor 3 pode ser removido do domínio de X2.
42
Redução de Domínios
Na realidade, nenhum dos valores de X3 tem suporte nas
variáveis X2 e X4! Com efeito,
1
1
1
1
1
1
X2 
1,2
X3 
1,3
X4 
1,4
• a etiqueta X3-4 não tem suporte na variável X2, já que
nenhuma das etiquetas {X2-3, X3-4} e {X2-4, X3-4}
satisfazem a restrição R23.
• a etiqueta X3-2 não tem suporte na variável X4, já que
nenhuma das etiquetas {X3-2, X4-2} e {X3-2, X4-3}
satisfazem a restrição R34.
43
Redução de Domínios
Como nenhum dos valores de X3 tem suporte nas variáveis
X2 e X4, a manutenção de arco deve tornar vazio o domínio
de X3!
1
1
1
1
1
1
X2 
1,2
X3 
1,3
X4 
1,4
Assim, a simples manutenção de consistência de arco não só
reduz o domínio das variáveis como também antecipa a
detecção de insatisfazibilidade.
Desta forma, o retrocesso de X1=1 pode ser iniciado, sem
se terem atribuído (e retrocedido) valores às restantes
variáveis, nomeadamente à variável X2.
44
Redução de Domínios
Manutenção de Consistência de Arcos
Um algoritmo muito simples para impôr a consistência de
arcos é o algoritmo AC-1, descrito abaixo
procedimento AC-1(V, D, R);
NC-1(V,D,R);
% impõe a consistência de nós
Q = {aij | Rij  R  Rji  R }; % ver nota
repetir
alterado <- falso;
para aij in Q fazer
alterado <- alterado ou rev_dom(aij,V,D,R)
fim para
até não alterado
fim procedimento
Nota: para Rij são considerados os arcos dirigidos aij e a ji
45
Redução de Domínios
Manutenção de Consistência de Arcos (cont.)
O predicado rev_dom(aij,V,D,R) sucede se eliminar valores
do domínio das variáveis (como um efeito lateral).
predicado rev_dom(aij,V,D,R): Booleano;
sucede <- falso;
para vi in dom(Xi) fazer
se não existir vj in dom(Xj)tal que
satisfaz({Xi-vi,Xj-vj},Rij) então
dom(Xi) <- dom(Xi) \ {vi};
sucede <- verdade;
fim se
rev_dom <- sucede;
fim predicado
46
Redução de Domínios
Complexidade temporal do algoritmo AC-1
Assumindo n variáveis no problema, cada com d valores
no seu domínio, e sendo os arcos em número de a, no pior
caso, o predicado rev_dom, verifica d2 pares de valores.
O número de arcos aij na fila Q é de 2a (para cada
restrição Rij são considerados arcos dirigidos aij e aji).
Por cada valor removido, rev_dom é chamado 2a vezes.
No pior caso, por cada ciclo é removido um valor de uma
só variável, pelo que o ciclo pode ser executado nd vezes.
Tendo em conta estes factores, a complexidade
temporal do AC-1 , no pior caso, é O( d2 * 2a * nd), i.e.
O(nad3)
47
Redução de Domínios
Complexidade espacial do algoritmo AC-1
O algoritmo AC-1 tem de manter uma fila Q, com
comprimento máximo de 2a. Assim a complexidade
espacial inerente do algoritmo AC-1 é O(a).
A este espaço há que acrescentar o espaço destinado à
representação dos domínios O(nd) e para representar as
restrições do problema. Existindo a restrições e d
valores no domínio de cada variável o espaço necessário é
de O(ad2), sendo o total de O(nd + ad2).
Para redes de restrições “densas”, a  n2/2. Pelo que
este termo domina a complexidade espacial total que é
O(ad2).
48
Redução de Domínios
Ineficiência do algoritmo AC-1
Cada vez que um valor vi é removido do domínio de uma
variável Xi, pelo predicado rev_dom(aij,V,D,R), todos os
arcos são reexaminados.
Na realidade, apenas os arcos aki (para k  i e k  j )
deveriam ser reexaminados.
Com efeito, a remoção de vi pode eliminar o suporte de
um valor vk de uma variável Xk para a qual existe uma
restrição Rki (ou Rik).
Essa ineficiência é eliminada no algoritmo AC-3.
49
Redução de Domínios
procedimento AC-3(V, D, R);
NC-1(V,D,R);
% impõe a consistência de nós
Q = {aij | Rij  R  Rji  R };
enquanto Q   fazer
Q = Q \ {aij}
% remove um elemento de Q
se rev_dom(aij,V,D,R) então
Q = Q  {aki | Rki  R  k  i  k  j}
até não alterado
fim procedimento
Como é intuitivo, e para além de uma melhor complexidade
típica, a complexidade para o pior caso do algoritmo AC-3 é
melhor que a do AC-1.
50
Redução de Domínios
Complexidade temporal do algoritmo AC-3
Cada arco aki só é inserido quando um valor vi é eliminado
do domínio de Xi.
No total, cada um dos 2a arcos pode ser inserido (e
removido) d vezes da fila Q.
Cada vez que é removido um arco, é chamado o predicado
rev_dom, que verifica no máximo d2 pares de valores.
Tendo em conta todos estes, e em contraste com o
algoritmo AC-1 de complexidade temporal O(nad3), a
complexidade temporal do algoritmo AC-3, pior caso, é
O(2ad * d2), ou seja
O(ad3)
51