Algoritmo AC-4
Ineficiência do algoritmo AC-3
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 que conduzem a essa variável são reexaminados.
Na realidade, apenas alguns desses arcos aki (para k  i e
k  j ) deveriam ser reexaminados.
Com efeito, apesar de a remoção de vi poder eliminar um
suporte de um valor vk de uma variável Xk para a qual
existe uma restrição Rki (ou Rik), outros valores da
variável Xi podem manter o par Xk-vk suportado!
Essa ineficiência é eliminada no algoritmo AC-4.
1
Algoritmo AC-4
Algoritmo AC-4 (Contadores)
O algoritmo AC-4 mantém estruturas de dados
(contadores) para contabilizar o número de valores de
uma variável Xi que suportam um valor vk de uma variável
Xk, entre as quais exista uma restrição Rik.
Por exemplo, no problema das 4 rainhas os
contadores que indicam o suporte para o
valor X1= 2 são inicializados como
c(2,X1,X2) = 1
c(2,X1,X3) = 2
c(2,X1,X4) = 3
% X2-4 não ataca X1-1
% X3-1 e X3-3 não atacam X1-1
% X4-1, X4-3 e X4-4 não atacam X1-1
2
Algoritmo AC-4
Algoritmo AC-4 (Conjuntos de suporte)
Para actualizar os contadores quando um valor é
eliminado do domínio de uma variável, é útil conhecer
quais os pares Variável-Valor suportados por cada valor.
Assim, o algoritmo AC-4 mantém igualmente um conjunto
de apontadores para contabilizar os pares Variável-Valor
suportados por cada par Variável-Valor.
sup(2,X1) = [X2-4,X3-1,X3-3,X4-1,X4-3,X4-4]
% X2-2 suporta (não ataca) X2-4, X3-1,...
sup(1,X1) = [X2-2, X2-3 , X3-2, X3-4, X4-2, X4-3]
sup(3,X1) = [X2-1, X3-2 , X3-4, X4-1, X4-2, X4-4]
sup(4,X1) = [X2-1, X2-2 , X3-1, X3-3, X4-2, X4-3]
3
Algoritmo AC-4
Algoritmo AC-4 (Propagação)
Cada vez que se detecta que um valor de uma variável
não tem suporte noutra variável, esse valor é retirado do
domínio da variável, e é colocado numa Lista para
posterior propagação.
No entanto, e apesar de o valor poder perder o suporte
várias vezes a sua remoção só pode ser propagada uma
vez de forma útil.
Para controlar bem esta situação o algoritmo AC-4
mantém uma matriz de booleanos M. O valor 1/0 do
booleano M[X,v] representa o facto de o valor v
estar/não estar presente no domínio da variável X.
4
Algoritmo AC-4
Algoritmo AC-4 (Estrutura geral)
O algoritmo AC-4 faz uso das estruturas definidas da
forma previsível.
Numa primeira fase, o algoritmo inicializa as estruturas
de dados (contadores, conjuntos de suporte, matriz e
lista de remoções).
Numa segunda fase, não só executada posteriormente à
primeira fase, mas após qualquer passo de enumeração, o
algoritmo estabelece a propagação das restrições,
ajustando os valores das estruturas de dados.
5
Algoritmo AC-4
Algoritmo AC-4 (Fase 1 - Inicialização)
procedimento inicializa_AC-4(V,D,R);
M <- 1; sup <- ; Lista = ;
para Rij in R fazer
para vi in dom(Xi) fazer
ct <- 0;
para vj in dom(Xj) fazer
se satisfaz({Xi-vi, Xj-vj}, Rij) então
ct <- ct + 1; sup(vj,Xj)<- sup(vj,Xj)  {Xi-vi}
fim se
fim para
se ct = 0 então
M[Xi,vi] <- 0; Lista <- Lista  {Xi-vi}
dom(Xi) <- dom(Xi)\{vi}
senão c(vi, Xi, Xj) <- ct;
fim se
fim para
fim para
6
fim procedimento
Algoritmo AC-4
Algoritmo AC-4 (Fase 2 - Propagação)
procedimento propaga_AC-4(V,D,R);
enquanto Lista   fazer
List <- Lista \ {Xi-vi} % remove elemento da Lista
para Xj-vj in sup(vi,Xi) fazer
c(vj,Xj,Xi) <- c(vj,Xj,Xi) - 1;
se c(vj,Xj,Xi) = 0  M[Xj,vj] = 1 então
Lista = Lista  {Xj-vj};
M[Xi,vi] <- 0;
dom(Xj) <- dom(Xj) \ {vj}
fim se
fim para
fim procedimento
7
Algoritmo AC-4
Complexidade temporal do algoritmo AC-4 (Inicialização)
Analizando os ciclos executados pelo procedimento
inicializa_AC-4,
para Rij in R fazer
para vi in dom(Xi) fazer
para vj in dom(Xj) fazer
e assumindo que o número de restrições (arcos) do
problema é a, e que as variáveis no problema tem cada
uma d valores no seu domínio, o ciclo interno do
procedimento é executado 2ad2 vezes, pelo que a
complexidade temporal da fase 1 do algoritmo AC-4 é de
O(ad2).
8
Algoritmo AC-4
Complexidade temporal do algoritmo AC-4 (Propagação)
No ciclo interior do procedimento de propagação é
decrementado um contador relativo ao par Xj-vj
c(vj,Xj,Xi) <- c(vj,Xj,Xi) - 1;
Ora havendo 2a arcos e tendo cada variável d valores no
seu domínio, existem 2ad contadores. Cada contador é
inicializado a um valor não superior a d, já que cada par
Xj-vj só pode ter d valores de suporte noutra variável Xi.
Assim o número máximo de vezes que o ciclo interno é
executado é de 2ad2, o que determina que a
complexidade temporal da fase 2 do algoritmo AC-4 é de
O(ad2)
9
Algoritmo AC-4
Complexidade temporal do algoritmo AC-4
Desta forma, a complexidade temporal global do
algoritmo AC-4, é de
O(ad2)
quer no início (inicialização + propagação) quer na sua
utilização após cada enumeração.
Esta complexidade assintótica de pior caso é melhor que
a obtida no algoritmo AC-3 que era de O(ad2).
Infelizmente esta melhoria da complexidade temporal é
obtida à custa de uma complexidade espacial bastante
menos favorável.
10
Algoritmo AC-4
Complexidade espacial do algoritmo AC-4
No total o algoritmo AC-4 mantém
Contadores: Como discutido atrás, em número de 2ad
Conjuntos de Suporte: No pior caso, em cada uma das
a restrições Rij, cada um dos d pares Xi-vi suporta d
valores vj de Xj. (e vice-versa). Assim o espaço para
manter as listas de suporte é de ordem O(ad2).
Lista: Contém no máximo 2a arcos
Matriz M: mantém nd valores booleanos.
O espaço necessário para os conjuntos de suporte
domina os restantes. Comparado com o algoritmo AC-3
(O(a)) o algoritmo AC-4 tem pior complexidade espacial
O(ad2)
11
Algoritmo AC-4
O algoritmo AC-4 é óptimo?
A complexidade assintótica do algoritmos AC-4, não pode
ser ultrapassada por nenhum algoritmo! Com efeito, para
um problema consistente nos arcos, é necessário testar,
para cada uma das restrições Rij a, que os d2 pares de
valores Xi-vi e Xj-vj satisfazem Rij, ou seja fazer ad2
testes, que é a complexidade assintótica do AC-4.
No entanto, é preciso ter em conta que a complexidade
pior caso é assintótica. Para pequenos valores dos
parâmetros, as constantes podem ser não negligenciáveis.
Por outro lado, em termos típicos, toda a artilharia usada
pode tornar-se desnecessária. De facto, o algoritmo AC-3
é tipicamente mais eficiente que o AC-4!
12
Algoritmo AC-6
Deficiências do Algoritmo AC-4
Apesar de optimo assintoticamente, o algoritmo AC-4
apresenta má complexidade típica. De facto, as estruturas
de dados, e em particular os contadores, que permitem
melhorar a detecção de suporte são muito pesadas.
A inicialização destas
nomeadamente quando
cardinalidade.
estruturas é muito
os domínios têm
pesada,
grande
O espaço requerido pelo AC-4 é igualmente problemático,
especialmente quando as restrições são representadas por
intenção e não por extensão.
13
Algoritmo AC-6
Alterações ao AC-4 - Algoritmo AC-6
O algoritmo AC-6 evita estas ineficiências com uma ideia
base: em vez de manter os valores vi da variável Xi que
suportam um par Xi-vi , apenas mantém o menor valor vi.
A inicialização fica mais “leve”, já que ao primeiro valor vi
encontrado se pára de procurar outros valores de suporte.
Por outro lado, o AC-6 não precisa de inicializar, para uma
variável Xi, a lista de todos os conjuntos de pares Xi-vi
suportados por um par Xj-vj, mas apenas o menor dos vis.
A contrapartida, é que os valores “seguintes” têm de ser
determinados durante a fase de propagação!
14
Algoritmo AC-6
Estruturas de dados do Algoritmo AC-6
A Lista e a matriz M de booleanos do AC-4 mantêm-se;
Os contadores do AC-4 desaparecem;
Os conjuntos de suporte apenas contêm uma entrada por
variável, assumindo-se que os domínios das variáveis são
ordenados
sup(2,X1) = [X2-4,X3-1,X3-3,X4-1,X4-3,X4-4]
% X2-2 suporta (não ataca) X2-4, X3-1,...
sup(1,X1) = [X2-2, X2-3 , X3-2, X3-4, X4-2, X4-3]
sup(3,X1) = [X2-1, X3-2 , X3-4, X4-1, X4-2, X4-4]
sup(4,X1) = [X2-1, X2-2 , X3-1, X3-3, X4-2, X4-3]
15
Algoritmo AC-6
Ambas as fases do AC-6 utilizam o predicado
suporte_seguinte (Xi,vi,Xj,vj, out v) que sucede se existir na
variável Xj um valor “seguinte”, v, que é o menor valor, não
inferior a vj, tal que Xj-v suporta Xi-vi.
predicado suporte_seguinte(Xi,vi,Xj,vj,out v): booleano;
sup_s <- falso; v <- vj;
enquanto não sup_s e v =< max(dom(Xj)) fazer
se não satisfaz({Xi-vi,Xj-v},Rij) então
v <- seguinte(v,dom(Xj))
senão
sup_s <- verdade
fim se
fim enquanto
suporte_seguinte <- sup;
fim predicado.
16
Algoritmo AC-6
Algoritmo AC-6 (Fase 1 - Inicialização)
procedimento inicializa_AC-6(V,D,R);
Lista <- ; M <- 0; sup <- ;
para Rij in R fazer
para vi in dom(Xi) fazer
v = min(dom(Xj))
se suporte_seguinte(Xi,vi,Xj,v,vj) então
sup(vj,Xj)<- sup(vj,Xj)  {Xi-vi}
senão
dom(Xi) <- dom(Xi)\{vi}; M[Xi,vi] <- 0;
Lista <- Lista  {Xi-vi}
fim se
fim para
fim para
fim procedimento
17
Algoritmo AC-6
Algoritmo AC-6 (Fase 2 - Propagação)
procedimento propaga_AC-6(V,D,R);
enquanto Lista   fazer
Lista <- Lista \ {Xj-vj} % remove elemento da Lista
para Xi-vi in sup(vj,Xj) fazer
sup(vj,Xj) <- sup(vj,Xj) \ {Xi-vi} ;
se M[Xi,vi] = 1 então
se suporte_seguinte(Xi,vi,Xj,vj,v) então
sup(v,Xj)<- sup(v,Xj)  {Xi-vi}
senão
dom(Xi) <- dom(Xi)\{vi}; M[Xi,vi] <- 0;
Lista <- Lista  {Xi-vi}
fim se
fim se
fim para
fim enquanto
18
fim procedimento
Algoritmo AC-6
Complexidade espacial do algoritmo AC-6
No total o algoritmo AC-6 mantém
Conjuntos de Suporte: No pior caso, para cada uma das a
restrições Rij, cada um dos d pares Xi-vi é suportado
por um só valor vj de Xj (e vice-versa). Assim o espaço
para manter as listas de suporte é de ordem O(ad).
Lista: Contém no máximo 2a arcos
Matriz M: mantém nd valores booleanos.
O espaço necessário para os conjuntos de suporte é
dominante e o algoritmo AC-6 apresenta uma complexidade
O(ad)
intermédia entre a do AC-3 (O(a)) e do AC-4 (O(ad2)).
19
Algoritmo AC-6
Complexidade temporal do algoritmo AC-6
Quer na inicialização, quer na propagação, o ciclo interno
chama o predicado suporte_seguinte(Xi,vi,Xj,v,vj).
Para cada par Xi-vi, a variável Xj é verificada, no máximo
d vezes.
Para cada arco correspondente a uma restrição Rij, são
considerados, no máximo, d pares Xi-vi .
Existindo 2a arcos (2 por cada restrição Rij), a
complexidade temporal, no pior caso, de qualquer das
fases do AC-6 é pois
O(ad2).
que, tal como no AC-4, é uma complexidade óptima.
.
20
Algoritmo AC-6
Complexidade típica do algoritmo AC-6
As complexidades do pior caso que se podem inferir por
análise dos algoritmos, não dão uma ideia precisa de
como é que eles se comportam em situações típicas.
Para
esse
estudo,
recorre-se
normalmente
a
“benchmarks”, ou seja em problemas que se pretendem
representativos.
Para estes algoritmos, ou se recorrem a instâncias de
problemas bem conhecidos (por exemplo, as n rainhas) ou
a problemas aleatórios parametrizados pelo número de
variáveis, cardinalidade dos domínios, densidade e grau
de aperto.
21
Algoritmo AC-6
Complexidade típica dos algoritmos AC-3, AC-4 e AC-6
no problema das N-rainhas
# testes e operações
16000
14000
12000
10000
AC-3
8000
AC-4
6000
AC-6
4000
2000
0
4
5
6
7
8
# rainhas
9
10
11
22
Algoritmo AC-6
AC-3
AC-4
Grau de Aperto (em %)
80
70
60
50
45
40
35
30
25
20
15
AC-6
10
22000
20000
18000
16000
14000
12000
10000
8000
6000
4000
2000
0
5
# testes e operações
Complexidade típica dos algoritmos AC-3, AC-4 e AC-6 em
problema gerado aleatoriamente
n = 12 variáveis, d= 16 valores, densidade = 50%
23
Algoritmo AC-7
Deficiências do Algoritmo AC-6 - Algoritmo AC-7
O AC-6 (tal como a AC-4 e o AC-3) duplica
desnecessariamente a detecção de suportes, por não
entrar em conta com o facto de que o suporte é
bidireccional, isto é,
se Xi-vi suporta Xj-vj então Xj-vj suporta Xi-vi
O algoritmo AC-7 vai usar esta propriedade para inferir
suporte em vez de pesquisar suporte.
Outros tipos de inferência poderiam ser usados (p.
exemplo, as propriedades de reflexividade, simetria, e
transitividade de certas restrições), mas o AC-7 limita-se
a explorar a bidireccionalidade do suporte.
24
Algoritmo AC-7
Exemplo:
Consideremos 2 países que podem ser coloridos por 3
cores. A pesquisa feita pelos vários algoritmos AC-x para
inicializar a consistência de arco é a seguinte
AC-3
8 testes
AC-4
18 testes
AC-6
8 testes
AC-7
5 testes
2 inferências
25
Algoritmo AC-7
Estruturas de dados do Algoritmo AC-7
O algoritmo AC-7 mantem, para cada par Xi-vi um
conjunto CS(vi,Xi,Xj), que é o conjunto de valores do
domínio de Xj presentemente suportados pelo par Xi-vi.
Mantém ainda, para cada triplo (vi,Xi,Xj) um valor
ultimo(vi,Xi,Xj) que representa o último (por ordem
crescente) valor do domínio de Xj que foi testado para
suporte do par Xi-vi.
Para qualquer variável, o domínio é ordenado e
introduzem-se os valores “artificiais” bottom e top,
repectivamente menores e maiores que qualquer elemento
do domínio.
26
Algoritmo AC-7
Algoritmo AC-7 (Fase 1 - Inicialização)
procedimento inicializa_AC-7(V,D,R out Rem);
Rem <- ;
para Rij  R e vi  dom(Xi) fazer
CS(vi,Xi,Xj) <- ; ultimo(vi,Xi,Xj) <- bottom;
fim fazer
para Xi  V fazer
para vi  dom(Xi)
para Xj |  Rij  R fazer
v <- procuraSuporte(vi,Xi,Xj);
se v  top então
CS(v,Xj,Xi) <- CS(v,Xj,Xi)  {vi}
senão
dom(Xi) <- dom(Xi)\{vi}; Rem <- Rem  {Xi-vi}
fim se
fim para
fim para
fim para
fim procedimento
27
Algoritmo AC-7
Algoritmo AC-7 (Fase 2 - Propagação)
procedimento propaga_AC-7(V,D,R,Rem);
enquanto Rem   fazer
Rem <- Rem \ {Xj-vj}
para Xi |  Rij  R fazer
enquanto CS(vj,Xj,Xi)   fazer
CS(vj,Xj,Xi) <- CS(vj,Xj,Xi) \ {vi}
se vi  dom(Xi) então
v <- procuraSuporte(vi,Xi,Xj);
se v  top então
CS(v,Xj,Xi) <- CS(v,Xj,Xi)  {vi}
senão
dom(Xi) <- dom(Xi)\{vi};
Rem <- Rem  {Xi-vi}
fim se
fim se
fim enquanto
fim para
fim enquanto
fim procedimento
28
Algoritmo AC-7
Algoritmo AC-7 (Função auxiliar procuraSuporte)
A função procuraSuporte procura, no domínio de Xj, um valor
vj que suporte o par Xi-vi. Em primeiro lugar tenta inferir
esse suporte nos pares Xi-vi que suportam um par Xj-vj
(explorando a bidireccionalidade do suporte). Caso contrário
pesquisa vj no domínio de Xj na forma habitual.
função procuraSuporte(vi,Xi,Xj): valor;
se infereSuporte(vi,Xi,Xj,v) então
procuraSuporte <- v;
senão
procuraSuporte <- pesquisaSuporte(vi,Xi,Xj)
fim se
fim função
De notar, que as funções procuraSuporte podem retornar o
29
valor “artificial” top.
Algoritmo AC-7
Algoritmo AC-7 (Predicado auxiliar infereSuporte)
Explorando a bidireccionalidade do suporte, o predicado
auxiliar infereSuporte, procura um valor vj da variável Xj que
suporte o par Xi-vi, nos valores do domínio de Xj suportados
pelo par Xi-vi.
predicado infereSuporte(vi,Xi,Xj,out vj): booleano;
descoberto <- falso;
enquanto CS(vi,Xi,Xj)   e não descoberto fazer
CS(vi,Xi,Xj) = {v}  Z;
se v in dom(Xj) então
descoberto <- verdade; vj <- v;
senão
CS(vi,Xi,Xj) = CS(vi,Xi,Xj) \ {v};
fim se
fim fazer
infereSuporte <- descoberto
30
fim predicado.
Algoritmo AC-7
Algoritmo AC-7 (Função auxiliar pesquisaSuporte)
função pesquisaSuporte(vi,Xi,Xj): valor;
b <- ultimo(vi,Xi,Xj);
se b = top então pesquisaSuporte <- b
senão
descoberto = falso; b <- seguinte(b,dom(Xj))
enquanto b  top e não descoberto fazer
se ultimo(b,Xj,Xi) =< vi e
satisfaz({Xi-vi,Xj-b}, Rij) então
descoberto <- verdade
senão
b <- seguinte(b,dom(Xj))
fim se
fim enquanto
ultimo(vi,Xi,Xj) <- b;
pesquisaSuporte <- b;
fim se
fim função;
31
Algoritmo AC-7
Complexidade espacial do algoritmo AC-7
No total o algoritmo AC-6 mantém
Conjuntos de Suporte CS(vi,Xi,Xj): Tal como no AC-6, para
cada uma das a restrições Rij, para cada um dos d pares
Xi-vi só é calculado um valor vj do domínio de Xj (que é
suportado por Xi-vi (e vice-versa). Assim o espaço para
manter as listas de suporte é de ordem O(ad).
Valores ultimo(vi,Xi,Xj): Idem
O espaço necessário para estas estruturas é dominante, e
tal como o algoritmo AC-6, o AC-7 apresenta complexidade
O(ad)
intermédia entre a do AC-3 (O(a)) e do AC-4 (O(ad2)).
32
Algoritmo AC-7
Complexidade temporal do algoritmo AC-7
Quer na inicialização, quer na propagação, o ciclo interno
chama o predicado procuraSuporte(vi,Xi,Xj).
Existem no máximo 2ad triplos (vi,Xi,Xj), já que existem
2a arcos correspondentes às restrições Rij e o domínio
de Xi tem no máximo d valores.
Em cada chamada de procuraSuporte(vi,Xi,Xj ) são
testados, no máximo d valores do domínio de Xj.
Assim a complexidade temporal, no pior caso, de
qualquer das fases do AC-7 é, como no AC-6, de
O(ad2).
que, tal como no AC-4, é uma complexidade óptima.
.
33
Algoritmo AC-7
Dadas as idênticas complexidades, em que é que o AC-7
melhora o AC-6 (e os outros AC-x)? Consideremos pois,
algumas propriedades do algoritmo AC-7.
1. Nunca testa Rij(vi,vj) se existe um v’j ainda no domínio de
Xj tal que Rij(vi, v’j) foi testado com sucesso.
2. Nunca testa Rij(vi,vj) se existe um v’j ainda no domínio de
Xj tal que Rij(v’j, vi) foi testado com sucesso.
3. Nunca testa Rij(vi,vj) se
a) já foi testado ; ou
b) Se Rij(vi,vj) já foi testado
4. Tem complexidade espacial O(ad)
Por comparação, o AC-3 só goza da propriedade 4; o AC-4 só
goza da propriedade 3a; o AC-6 goza de 1, 3a e 4.
34
Algoritmo AC-7
Complexidade típica do algoritmo AC-7
As características não podem ser detectadas na análise
de complexidade do pior caso, que não detectam pois
diferenças entre o AC-6 e o AC-7.
Os resultados seguintes consideram problemas de teste
gerados aleatoriamente com os parâmetros indicados. Os
primeiros são “fáceis” (under- e over-constrained). Os
dois últimos estão na transição de fase, sendo
desdobrados os resultados das instâncias consistentes
(a) e não consistentes (b)
Problema
P1
P2
P3
P4
variáveis
#
150
150
150
50
domínios
#
50
50
50
50
densidade
%
4.5
4.5
4.5
100
Aperto
%
50
94
91.8
87.5
35
Algoritmo AC-7
Comparação das complexidades típicas (# de checks)
9000000
8000000
7000000
6000000
AC-3
AC-4
AC-6
AC-7
5000000
4000000
3000000
2000000
1000000
0
Prob 1
Prob 2
Prob 3a Prob 3b Prob 4a Prob 4b
36
Algoritmo AC-7
6000
Comparação das complexidades típicas
(tempo CPU em ms num PC Pentium 200 MHz)
5000
4000
AC-3
AC-4
AC-6
AC-7
3000
2000
1000
0
Prob 1
Prob 2
Prob 3a
Prob 3b Prob 4a Prob 4b
37
Algoritmo AC-3d
Ideias semelhantes de explorar a bidireccionalidade do
suporte foram adoptadas numa adaptação, não do algoritmo
AC-6 mas sim do algoritmos AC-3, obtendo-se o algoritmos
AC-3d.
A principal diferença entre o AC-3 e o AC-3d consiste em
que quando se retira o arco aij da lista Q, é também retirado
o arco Aji no caso de ele estar lá presente.
Neste caso são revistos simultaneamente os domínios de Xi
e Xj, o que evita bastante trabalho repetido.
Apesar de não melhorar a complexidade do pior caso, a
complexidade típica parece interessante (pelo menos em
alguns problemas de teste estudados).
38
Algoritmo AC-3d
Comparação das complexidades típicas (# de checks) nos
problemas aleatórios anteriores
9000000
8000000
7000000
AC-3
AC-4
AC-6
AC-7
AC-3d
6000000
5000000
4000000
3000000
2000000
1000000
0
Prob 1
Prob 2 Prob 3a Prob 3b Prob 4a Prob 4b
39
Algoritmo AC-3d
Comparação das complexidades típicas nos problemas
aleatórios anteriores
(tempo CPU equivalente num PC Pentium 200 MHz)
6000
5000
AC-3
AC-4
AC-6
AC-7
AC-3d
4000
3000
2000
1000
0
Prob 1
Prob 2
Prob 3a Prob 3b Prob 4a Prob 4b
40
Algoritmo AC-3d
Os resultados parecem ainda mais interessantes para
problemas em que o AC-7 se mostrou bastante superior ao
AC-6, quer em número de testes quer em tempo.
O problema (RLFAP - Radio Link Frequency Assignment
Problem) consiste em atribuir Radio Frequências de uma
forma segura, sendo estudadas instâncias com 3, 5, 8 e 11
antenas.
O seu código ( e de outros problemas de teste) pode ser
obtido a partir de um arquivo de problemas de teste
disponível pela Internet no URL
http://ftp.cs.unh.edu/pub/csp/archive/code/benchmarks
41
Algoritmo AC-3d
Complexidades típicas (# de checks) nos problemas RFLAP
1200000
1000000
800000
AC-3
AC-6
AC-7
AC-3d
600000
400000
200000
0
#3
#5
#8
#11
42
Algoritmo AC-3d
Comparação das complexidades típicas nos problemas
aleatórios anteriores
(tempo CPU equivalente num PC Pentium 200 MHz)
2500
2000
AC-3
AC-6
AC-7
AC-3d
1500
1000
500
0
#3
#5
#8
# 11
43
Consistência de Caminho
Para além da consistência de arco, podem definir-se outros
tipos de consistência para redes de restrições binárias.
Um tipo de consistência “clássico”, que é mais forte que a
consistência de arco, é a consistência de caminho.
A ideia é que para além de avaliar a existência de suportes
nos arcos da rede entre as variáveis Xi e Xj, deverá ser
ainda verificada a existência de suporte nas variáveis Xk1,
Xk2... Xkm que constituam um caminho entre Xi e Xj, ou seja,
que haja restrições Rik1, Rk1,k2, ..., Rkm-1, km e Rkm,j.
Na realidade, prova-se que esta definição é equivalente a
obter suporte em qualquer variável Xk ligada quer a Xi quer
a Xj .
44
Consistência de Caminho
Definição (Consistência de Caminho):
Um problema de restrições tem os caminhos consistentes
se,
1. Tiver todos os arcos consistentes; e
2. Para todas as restrições Rij envolvendo as variáveis
Xi e Xj, no caso de existirem restrições Rik e Rjk
dessas variáveis com uma terceira variável Xk, para
todas as etiquetas compostas {Xi-vi , Xj-vj} deve
existir um valor vk tal que as etiquetas compostas
{Xi-vi,Xk-vk} e {Xj-vj,Xk-vk} satisfazem as restrições
Rik e Rjk.
45
Consistência de Caminho
A manutenção deste tipo de consistência tem naturalmente
mais custos computacionais que a simples consistência de
arco.
Para a manter é conveniente manter uma representação por
extensão das restrições binárias, na forma de uma matriz
booleana.
Assumindo que as variáveis Xi e Xj têm di e dj valores no
seu domínio, a restrição Rij é mantida como uma matriz Mij
de di*dj booleanos.
O valor 1/0 do elemento Mij[k,l] indica se o par {Xi-vk, Xj-vl}
satisfaz/não satisfaz a restrição.
46
Consistência de Caminho
Exemplo: 4 rainhas
Matriz Booleana, M12, relativa à restrição entre as variáveis
X1 e X2 (ou entre duas variáveis em linhas consecutivas)
1\2 1
2
3
4
1
0
0
1
1
2
0
0
0
1
3
1
0
0
0
4
1
1
0
0
M12[1,3] = M12[3,1] = 1
M12[3,4] = M12[4,3] = 0
Matriz Booleana, M13, relativa à restrição entre as variáveis
X1 e X3 (ou entre duas variáveis com uma linha de intervalo)
1\3 1
2
3
4
1
0
1
0
1
2
1
0
1
0
3
0
1
0
1
4
1
0
1
0
M13[1,2] = M13[2,1] = 1
M13[2,4] = M13[4,2] = 0
47
Consistência de Caminho
Verificação da Consistência de Caminho
Para eliminar da matriz Mij os valores que não satisfaçam a
consistência de caminho através de uma terceira variável
Xk, pode recorrer-se a operações semelhantes à
multiplicação e soma de matrizes.
MIJ <- MIJ  MIK  MKJ
Em que a operação  corresponde à conjunção dos valores
booleanos correspondentes, e a operação  corresponde à
multiplicação de matrizes em que as operações
multiplicação/soma sobre reais
são substituídas pelas
operações conjunção/disjunção sobre booleanos.
Considera-se ainda a matriz diagonal Mkk para representar o
48
domínio da variável Xk.
Consistência de Caminho
Exemplo (4 rainhas):
Verificação da inconsistência de caminho da etiqueta
composta {X1-1 e X3-4}, devido à variável X2.
M13[1,4] <- M13[1,4]  M12[1,X]  M23[X,4]
Ora M12[1,X]  M23[X,4] = 0 pois
M12[1,1]  M23[1,4] % o valor X2- 1 não suporta {X1-1,X3-4}
 M12[1,2]  M23[2,4] % o valor X2-2 não suporta {X1-1,X3-4}
 M12[1,3]  M23[3,4] % o valor X2-3 não suporta {X1-1,X3-4}
 M12[1,4]  M23[4,4] % o valor X2-4 não suporta {X1-1,X3-4}
1\2 1
2
3
4
2\3 1
2
3
4
1\3 1
2
3
4
1\3 1
2
3
4
1
0
0
1
1
1
0
0
1
1
1
0
1
0
1
1
0
1
0
0
2
0
0
0
1
2
0
0
0
1
2
1
0
1
0
2
1
0
0
0
3
1
0
0
0
3
1
0
0
0
3
0
1
0
1
3
0
0
0
1
4
1
1
0
0
4
1
1
0
0
4
1
0
1
0
4
0
0
1
0
49
Consistência de Caminho
Consistência de Caminho
A consistência de caminho é mais forte que a consistência
de arco, no sentido que a sua manutenção permite, em geral,
eliminar mais valores redundantes dos domínios das
variáveis do que a simples manutenção de consitência de
arco.
Em particular, no problema das 4 rainhas, a manutenção da
consistência de caminho permite eliminar dos domínio das
variáveis todos os valores que não pertencem a nenhuma
solução, antes de se fazer qualquer atribuição de variáveis.
Como consequência importante, consegue resolver-se o
problema com uma enumeração livre de retrocesso!
50
Consistência de Caminho
Consistência de Caminho no problema das 4 rainhas
1\2 1
2
3
4
2\3 1
2
3
4
1\3 1
2
3
4
1\3 1
2
3
4
1
0
0
1
1
1
0
0
1
1
1
0
1
0
1
1
0
1
0
0
2
0
0
0
1
2
0
0
0
1
2
1
0
1
0
2
1
0
0
0
3
1
0
0
0
3
1
0
0
0
3
0
1
0
1
3
0
0
0
1
4
1
1
0
0
4
1
1
0
0
4
1
0
1
0
4
0
0
1
0
1\3 1
2
3
4
3\4 1
2
3
4
1\4 1
2
3
4
1\4 1
2
3
4
1
0
1
0
0
1
0
0
1
1
1
0
1
1
0
1
0
0
0
0
2
1
0
0
0
2
0
0
0
1
2
1
0
1
1
2
0
0
1
1
3
0
0
0
1
3
1
0
0
0
3
1
1
0
1
3
1
1
0
0
4
0
0
1
0
4
1
1
0
0
4
0
1
1
0
4
0
0
0
0
X1 e X3 via
X2
X1 e X4 via
X3
51
Consistência de Caminho
1\4 1
2
3
4
4\2 1
2
3
4
1\2 1
2
3
4
1\2 1
2
3
4
1
0
0
0
0
1
0
1
0
1
1
0
0
1
1
1
0
0
0
0
2
0
0
1
1
2
1
0
1
0
2
0
0
0
1
2
0
0
0
1
3
1
1
0
0
3
0
1
0
1
3
1
0
0
0
3
1
0
0
0
4
0
0
0
0
4
1
0
1
0
4
1
1
0
0
4
0
0
0
0
1\2 1
2
3
4
2\3 1
2
3
4
1\3 1
2
3
4
1\3 1
2
3
4
1
0
0
0
0
1
0
0
1
1
1
0
1
0
0
1
0
0
0
0
2
0
0
0
1
2
0
0
0
1
2
1
0
0
0
2
1
0
0
0
3
1
0
0
0
3
1
0
0
0
3
0
0
0
1
3
0
0
0
1
4
0
0
0
0
4
1
1
0
0
4
0
0
1
0
4
0
0
0
0
1\2 1
2
3
4
2\4 1
2
3
4
1\4 1
2
3
4
1\4 1
2
3
4
1
0
0
0
0
1
0
1
0
1
1
0
0
0
0
1
0
0
0
0
2
0
0
0
1
2
1
0
1
0
2
0
0
1
1
2
0
0
1
0
3
1
0
0
0
3
0
1
0
1
3
1
1
0
0
3
0
1
0
0
4
0
0
0
0
4
1
0
1
0
4
0
0
0
0
4
0
0
0
0
X1 e X2 via
X4
X1 e X3 via
X2
X1 e X4 via
X2
52
Consistência de Caminho
Consistência de Caminho
Obviamente, a contrapartida do maior poder de corte da
manutenção de consistência de caminho é o seu maior custo
computacional em relação à manutenção da consistência de
arco.
Os algoritmos para obter a consistência de arco, PC-x, são
naturalmente mais “pesados” que os AC-y.
A título de exemplo, estudamos o algoritmo PC-1 (muito
elementar) e discutimos os mais sofisticados PC-2 e PC-4
que o optimizam no sentido de evitar repetições de testes e
testes redundantes.
53
Algoritmo PC-1
Algoritmo PC-1
procedimento PC-1(V,D,R);
n <- #Z; Mn <- R;
repetir
M0 <- Mn;
para k de 1 a n fazer
para i de 1 a n fazer
para j de 1 a n fazer
Mijk <- Mijk-1  Mikk-1  Mkkk-1  Mkjk-1
fim para
fim para
fim para
até Mn = M0
R <- Mn
fim procedimento
54
Algoritmo PC-1
Complexidade temporal do algoritmo PC-1
Cada operação
Mijk <- Mijk-1  Mikk-1  Mkkk-1  Mkjk-1
envolve O(d3) operações binárias, ja que por cada um dos d2
elementos se executam d operações  e d-1 operações 
binárias.
Combinando estes factores obtemos uma complexidade
temporal O(n2d2 * n3 * d3), isto é
O(n5d5)
muito superior à complexidade dos algoritmos AC-x. O AC-1
tem complexidade O(nad3), o que para redes densas em que
a  n2 corresponde a O(n3d3).
55
Algoritmo PC-1
Complexidade espacial do algoritmo PC-1
A complexidade espacial do PC-1 corresponde a manter
• n3 matrizes Mijk, correspondentes aos conjuntos de
restrições Rij nas várias iterações atarvés do caminho
passando por Xk.
• cada matriz contem d2 elementos.
Assim a complexidade espacial do algoritmo PC-1 é de
O(n3d2)
Naturalmente, esta complexidade é a resultante de
representar por extensão e de uma forma matricial as
restrições, não havendo mais nenhuma estrutura de dados
56
mantida pelo PC-1.
Outros Algoritmos PC-X
Algoritmo PC-2
O algoritmo PC-2 mantém uma lista dos caminhos que têm
de ser reavaliados por via da remoção de valores das
matrizes Mij, de forma a só reactivar os testes de
consistência de caminho que podem ser alterados por essas
remoções.
Em contraste com a complexidade O(n5d5) do PC-1, a
complexidade temporal do PC-2 é
O(n3d5)
A complexidade espacial é igualmente melhor que a do PC-1,
O(n3d2), sendo para o algoritmo PC-2 de
O(n3+n2d2)
57
Outros Algoritmos PC-X
Algoritmo PC-4
O algoritmo PC-4, por analogia com o AC-4, mantém um
conjunto de contadores e de apontadores para melhorar o
mecanismo de avaliação da influência de remoções nos
caminhos a reavaliar.
Em contraste com as complexidades O(n5d5) do PC-1 e
O(n3d5), a complexidade temporal do PC-4 é
O(n3d3)
A complexidade espacial é, como esperado, pior que a do
PC-2, O(n3+n2d2), sendo para o PC-4 idêntica à do PC-1
O(n3d2)
58
Algoritmo PC-1
Complexidade temporal do algoritmo PC-1 (cont)
O procedimento realiza um ciclo
repetir
...
até Rn = R0
Havendo n2 restrições Rij e tendo a matriz de cada uma d2
elementos, o pior caso ocorre quando em cada ciclo se
elimina um só desses valores. O ciclo pode pois ser
executado um máximo de n2d2 vezes.
Em cada ciclo repetir são efectuados n3 ciclos para
encadeados
para K de 1 a n fazer
para I de 1 a n fazer
para J de 1 a n fazer
59
Consistência-k
As consistências de nó, arco e caminho são casos
particulares da consistência k.
Informalmente, uma rede de restrições é consistente k, se
para u grupo de variáveis Xi1, Xi2, Xik cada variável tiver
valores consistentes com as outras variáveis considerando
as restrições que as ligam de uma forma “global”.
Os exemplo seguintes mostram a importância de se ter
essa visão global das restrições.
Rede consistente nos nós mas não no arco

0
0
60
Consistência-k
Rede consistente nos arcos mas não nos caminhos

0,1
0,1


0,1
Rede consistente nos caminhos mas não consistente-4

0..2

0..2



0..2

0..2
61
Consistência-k
Definição (Consistência-k):
Um problema de restrições é consistente-1 se todos os
valores de todas as variáveis verificam as restrições
unárias.
Um problema é consistente-k, sse todas as etiquetas-k,
(i.e. compostas com k-1 pares X-v) que satisfazem as
restrições relevantes poderem ser estendidas por
inclusão de qualquer variável adicional, formando uma
etiqueta-k que satisfaz as restrições relevantes.
62
Consistência-k
Definição (Consistência-k forte):
Um problema de restrições é fortemente consistente-k
forte, sse fôr consistente-i, para todo o i  1 .. k.
Por exemplo, a rede abaixo é consistente-3, mas não
consistente-2, pelo que não é fortemente consistente-3.
A
C
0
0


0,1
B
As etiquetas-2 que satisfazem as restrições de
desigualdade () relevantes são
{A-0,B-1}, {A-0,C-0}, e {B-1, C-0}
que podem ser estendidas para {A-0,B-1,C-0}.
No entanto a etiqueta-1 {A-0} não pode ser
estendida para {A-0,B-0} !
63
Consistência-k
Como se pode verificar, as consistências anteriormente
estudadas (de nó, de arco e de caminho) são casos
particulares da consistência-k forte.
Assim
• A consistência de uma rede de restrições nos nós é
equivalente à sua consistência-1 forte.
• A consistência de uma rede de restrições nos arcos é
equivalente à sua consistência-2 forte.
• A consistência de uma rede de restrições nos caminhos
é equivalente à sua consistência-3 forte.
64
Consistência - (i, j)
A consistência-k pode ainda ser generalizada para a noção
de consistência - (i, j).
Um problema é consistente-(i, j) sse k, sse todas as
etiquetas-i (i.e. composta por i pares X-v) que satisfazem
as restrições relevantes poderem ser estendidas por
inclusão de j variáveis adicionais, para formar uma
etiqueta - k (k=i+j) que satisfaz as restrições relevantes.
Naturalmente, a consistência-k de uma rede de restrições
é equivalente à sua consistência-(k-1,1).
Apesar de interessante teoricamente, o critérios de
consistência-(i,j) (tal como o de consistência-k), não são
impostos na prática (ver algoritmo KS-1 [Tsan93]).
65
Consistência de Arco Generalizada
No caso de redes de restrições não binárias, podemos
manter a noção e o algoritmo de consistência de nó, em que
só são relevantes as restrições unárias.
A generalização de consistência de arco para redes de
restrições n-árias (n>2) é óbvia, considerando-se hiperarcos (em vez de arcos) nessas restrições, e garantindo que
cada valor de uma variável é suportado por valores das
outras variáveis que participam na restrição.
Apesar de não ser óbvia a generalização de consistência de
caminho, (a noção de caminho não é “clara”), ela pode ser
definida a partir da consistência-3 forte para essas redes.
Na prática, só se mantém a consistência
generalizada, por adaptação dos AC-X !
de
arco
66
GAC-3
Como ilustração, podemos considerar o algoritmo GAC-3,
uma generalização do algoritmo AC-3. A cada restrição kária correspondem agora k hiper-arcos dirigidos que
representam os suportes.
procedimento GAC-3(V, D, R);
NC-1(V,D,R);
% impõe a consistência de nós
Q = {hai..j | Ri..j  R  Rj..i  R };
enquanto Q   fazer
Q = Q \ {hai..j }
% remove um elemento de Q
se rev_dom(hai..j,V,D,R) então
Q = Q  {hak1..kn |  Xk  vars(RK1..Kn) 
Xk  vars(Ri..j) 
k1..kn  i .. J
}
até não alterado
fim procedimento
67
GAC-3
Complexidade temporal do algoritmo GAC-3
Por comparação com o algoritmo AC-3, o predicado
rev_dom, verifica no máximo dk pares de valores para
restrições k-árias.
Quando um valor vi é eliminado do domínio de Xi um
número de hiper-arcos relacionado com a aridade das
restrições é inserido na fila Q. Especificamente, k-1
hiper-arcos são inseridos por cada restrição k-ária
envolvendo uma variável de que foi eliminado um valor.
No total, cada um dos ka arcos pode ser inserido (e
removido) (k-1)d vezes da fila Q. Tendo em conta todos
estes, a complexidade temporal do algoritmo GAC-3, pior
caso, é O(k(k-1)2ad * dk), ou seja
68
O(k2adk+1)
Consistências Dependentes das Restrições
Os algoritmos e critérios de consistência estudados não
têm em conta a semântica das restrições, tratando-as
todas de uma forma uniforme.
No entanto, esta abordagem não é muito interessante na
prática, onde se poderão obter ganhos por utilização de
critérios de consistência específicos.
Por exemplo, independentemente de esquemas mais gerais,
para restrições de desigualdade (  ) só faz sentido manter
a consistência de nó.
Com efeito, para Xi  Xj, só se podem eliminar elementos do
domínio de uma variável quando a outra ficar reduzida a um
elemento!
69
Consistências Dependentes das Restrições
Outras consistências mais “específicas” podem ser usadas.
Por exemplo, no problema das rainhas, dada uma restrição
não_ataca(Xi, Xj)
só faz sentido analisar o efeito de se eliminar um valor no
domínio de uma variável se o domínio ficar reduzido a 3 ou
menos valores.
Com efeito, se Xi mantiver 3 valores no domínio, todos os
valores no domínio de Xj terão pelo menos um valor no
domínio de Xi que os suporta, pois a relação é simétrica e
um valor de Xj só pode atacar 3 valores de Xi.
rainhas_fd_xc
70
Consistências de Limite
Outra consistência específica e de grande importância é a
consistência de limites (“bound-consistency”), usada de
preferência com restrições de =< em domínios ordenados.
Com efeito dada a restrição A + B =< C, as verificações que
se podem impôr de uma forma independente da
cardinalidade dos domínios (que pode ser bastante grande,
por exemplo, d=1000 se A in 1..1000, e inviabilizar
consistência de arco com complexidade O(ad3)) são
max dom(C) =< max dom(A) + max dom(B)
min dom(C) >= min dom(A) + min dom(B)
max dom(A) =< max dom(C) - max dom(B)
min dom(A) >= min dom(C) - min dom(B)
max dom(B) =< max dom(C) - max dom(A)
min dom(B) >= min dom(C) - min dom(A)
71