Algoritmo AC-4

1

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.

2

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 % X2-4 não ataca X1-1

c(2,X1,X3) = 2 % X3-1 e X3-3 não atacam X1-1

c(2,X1,X4) = 3 % X4-1, X4-3 e X4-4 não atacam X1-1

3

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]

4

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.

5

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.

6

Algoritmo AC-4Algoritmo 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 parafim procedimento

7

Algoritmo AC-4Algoritmo 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

8

Algoritmo AC-4Complexidade 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).

9

Algoritmo AC-4Complexidade 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)

10

Algoritmo AC-4Complexidade 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.

11

Algoritmo AC-4Complexidade espacial do algoritmo AC-4

No total o algoritmo AC-4 mantémContadores: Como discutido atrás, em número de

2adConjuntos 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 arcosMatriz 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)

12

Algoritmo AC-4O 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!

13

Algoritmo AC-6Deficiê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 estruturas é muito pesada, nomeadamente quando os domínios têm grande cardinalidade.

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.

14

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!

15

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]

16

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 sefim enquantosuporte_seguinte <- sup;

fim predicado.

17

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 parafim para

fim procedimento

18

Algoritmo AC-6Algoritmo 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 enquantofim procedimento

19

Algoritmo AC-6

Complexidade espacial do algoritmo AC-6

No total o algoritmo AC-6 mantémConjuntos 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 arcosMatriz 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)).

20


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.

.

21

Algoritmo AC-6Complexidade 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.

22

Algoritmo AC-6

Complexidade típica dos algoritmos AC-3, AC-4 e AC-6 no problema das N-rainhas

0

2000

4000

6000

8000

10000

12000

14000

16000

4 5 6 7 8 9 10 11

# t

est

es

e o

pera

ções

AC-3

AC-4

AC-6

# rainhas

23

Algoritmo AC-6Complexidade típica dos algoritmos AC-3, AC-4 e AC-6

em problema gerado aleatoriamente n = 12 variáveis, d= 16 valores, densidade = 50%

02000400060008000

10000120001400016000180002000022000

5 10 15 20

25

30

35

40

45

50

60

70

80

# t

este

s e

oper

açõe

s

AC-3

AC-4

AC-6

Grau de Aperto (em %)

24

Algoritmo AC-7Deficiê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.

25

Algoritmo AC-7Exemplo:

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-38 testes

AC-68 testes

AC-75 testes

2 inferências

AC-418 testes

26

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.

27

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 fazerpara 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 parafim para

fim procedimento

28

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 enquantofim procedimento

29

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 sefim função

De notar, que as funções procuraSuporte podem retornar o valor “artificial” top.

30

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 sefim fazerinfereSuporte <- descoberto

fim predicado.

31

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;

32

Algoritmo AC-7

Complexidade espacial do algoritmo AC-7

No total o algoritmo AC-6 mantémConjuntos 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)).

33


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.

.

34

Algoritmo AC-7Dadas 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 ; oub)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.

35

Algoritmo AC-7Complexidade 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)

variáveis domínios densidade Aperto# # % %

P1 150 50 4.5 50P2 150 50 4.5 94P3 150 50 4.5 91.8P4 50 50 100 87.5

Problema

36

Algoritmo AC-7

Comparação das complexidades típicas (# de checks)

0

1000000

2000000

3000000

4000000

5000000

6000000

7000000

8000000

9000000

Prob 1 Prob 2 Prob 3a Prob 3b Prob 4a Prob 4b

AC-3AC-4AC-6AC-7

37

Algoritmo AC-7Comparação das complexidades típicas

(tempo CPU em ms num PC Pentium 200 MHz)

0

1000

2000

3000

4000

5000

6000


AC-3AC-4AC-6AC-7

38

Algoritmo AC-3dIdeias 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).

39

Algoritmo AC-3d

Comparação das complexidades típicas (# de checks) nos problemas aleatórios anteriores

0

1000000

2000000

3000000

4000000

5000000

6000000

7000000

8000000

9000000


AC-3AC-4AC-6AC-7AC-3d

40

Algoritmo AC-3dComparação das complexidades típicas nos problemas

aleatórios anteriores (tempo CPU equivalente num PC Pentium 200 MHz)

0

1000

2000

3000

4000

5000

6000


AC-3AC-4AC-6AC-7AC-3d

41

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

42

Algoritmo AC-3d

Complexidades típicas (# de checks) nos problemas RFLAP

0

200000

400000

600000

800000

1000000

1200000

#3 #5 #8 #11

AC-3AC-6AC-7AC-3d

43

Algoritmo AC-3d

Comparação das complexidades típicas nos problemas aleatórios anteriores

(tempo CPU equivalente num PC Pentium 200 MHz)

0

500

1000

1500

2000

2500

# 3 # 5 # 8 # 11

AC-3AC-6AC-7AC-3d

44

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.

45


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.

46


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.

47


Exemplo: 4 rainhas

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

Matriz Booleana, M12, relativa à restrição entre as variáveis X1 e X2 (ou entre duas variáveis em linhas consecutivas)

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

M12[1,3] = M12[3,1] = 1

Matriz Booleana, M13, relativa à restrição entre as variáveis X1 e X3 (ou entre duas variáveis com uma linha de intervalo)

M12[3,4] = M12[4,3] = 0

M13[1,2] = M13[2,1] = 1M13[2,4] = M13[4,2] = 0

48

Consistência de CaminhoVerificaçã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 domínio da variável Xk.

49

Consistência de CaminhoExemplo (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

50

Consistência de CaminhoConsistê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!

51


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

52


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

53

Consistência de CaminhoConsistê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.

54

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 <- Mij

k-1 Mikk-1 Mkk

k-1 Mkjk-1

fim para

fim para

fim para

até Mn = M0

R <- Mn

fim procedimento

55

Algoritmo PC-1Complexidade temporal do algoritmo PC-1

Cada operaçãoMij

k <- Mijk-1 Mik

k-1 Mkkk-1 Mkj

k-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).

56

Algoritmo PC-1Complexidade 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 mantida pelo PC-1.

57

Outros Algoritmos PC-XAlgoritmo 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)

58

Outros Algoritmos PC-XAlgoritmo 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)

59

Algoritmo PC-1Complexidade 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

60

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.

0 0

Rede consistente nos nós mas não no arco

61

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

62

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.

63

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.

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} !

0 0

0,1

B

CA

64

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.

65

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]).

66

Consistência de Arco GeneralizadaNo 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 hiper-arcos (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 de arco generalizada, por adaptação dos AC-X !

67

GAC-3Como 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 alteradofim procedimento

68

GAC-3Complexidade 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

O(k2adk+1)

69

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!

70

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

71

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)

Documents

Algoritmo AC-4