Download ppt - Domínios Finitos

Transcript
Page 1: Domínios Finitos

1

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

Page 2: Domínios Finitos

2

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.

Page 3: Domínios Finitos

3

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.

Page 4: Domínios Finitos

4

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)

Page 5: Domínios Finitos

5

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

Page 6: Domínios Finitos

6

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)

Page 7: Domínios Finitos

7

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.

Page 8: Domínios Finitos

8

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 n-árias podem ser arbitrariamente ordenadas.

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.

Page 9: Domínios Finitos

9

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

Page 10: Domínios Finitos

10

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.

Page 11: Domínios Finitos

11

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.

Page 12: Domínios Finitos

12

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.

Page 13: Domínios Finitos

13

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.

Page 14: Domínios Finitos

14

Domínios Finitos

Exemplo: O problema das 4 rainhas pode ser definido pelo seguinte grafo:

X1 in 1..4

X4 in 1..4

X3 in 1..4X2 in 1..4

R12

R23

R14

R24

R34

R13{<1,2>, <1,4>, <2,1>, <2,3>,

<3,2>, <3,4>, <4,1>, <4,3>}

Page 15: Domínios Finitos

15

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.

Page 16: Domínios Finitos

16

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

Page 17: Domínios Finitos

17

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.

Page 18: Domínios Finitos

18

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.

Page 19: Domínios Finitos

19

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.

Page 20: Domínios Finitos

20

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.

Page 21: Domínios Finitos

21

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.

Page 22: Domínios Finitos

22

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.

X1 in 1,2,3,4

X4 in 1,2,3,4

X3 in 1,2,3,4X2 in 1,2,3,4

R12

R23

R14

R24

R34

R13

{<1,2>, <1,4>, <2,1>, <2,3>,

<3,2>, <3,4>, <4,1>, <4,3>}

Page 23: Domínios Finitos

23

Domínios FinitosOs 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’> sea) 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.

Page 24: Domínios Finitos

24

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.

Page 25: Domínios Finitos

25

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 mais fraca, nomeadamente a noção de solução parcial

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.

Page 26: Domínios Finitos

26

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.

2

4

1

3

31 4

1

4

2

Page 27: Domínios Finitos

27

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.

Page 28: Domínios Finitos

28

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:

10 20 30 40 50 60 70 80 90 100

7 6 4.6716 21.824 101.95 476.29 2225 10395 48560 226852 1E+06 5E+06

6 5 6.1917 38.338 237.38 1469.8 9100.4 56348 348889 2E+06 1E+07 8E+07

5 4 9.3132 86.736 807.79 7523.2 70065 652530 6E+06 6E+07 5E+08 5E+09

4 3 17.758 315.34 5599.7 99437 2E+06 3E+07 6E+08 1E+10 2E+11 3E+12

3 2 57.665 3325.3 191751 1E+07 6E+08 4E+10 2E+12 1E+14 7E+15 4E+17

d d'

S/S'

n

Page 29: Domínios Finitos

29

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!

Page 30: Domínios Finitos

30

Resolução Construtiva em Domínios FinitosQualitativamente, este processo pode ser apresentado através do seguinte gráfico

Cus

to c

ompu

taci

onal

R - Custo de Redução

P- Custo de Pesquisa

R+P Custo Combinado

Esforço dispendido na redução do problema

Page 31: Domínios Finitos

31

Resolução Construtiva em Domínios FinitosO 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.

Page 32: Domínios Finitos

32

Resolução Construtiva em Domínios FinitosAssim 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.

Page 33: Domínios Finitos

33

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.

Page 34: Domínios Finitos

34

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

Page 35: Domínios Finitos

35

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.

Page 36: Domínios Finitos

36

Redução de DomíniosExemplo: Após o lançamento das restrições, a rede de restrições do problema das 4 rainhas é a seguinte:

X1 in 1..4

X4 in 1..4

X3 in 1..4X2 in 1..4

R12

R23

R14

R24

R34

R13

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!

X4 in 1..4

X3 in 1..4X2 in 1..4R23

R24

R34

X2 1,2

X3 1,3

X4 1,4

Page 37: Domínios Finitos

37

Redução de DomíniosA manutenção da consistência dos nós deverá retirar do domínio das variáveis os valores apropriados.

Consegue-se assim uma redução de domínios semelhante à que se conseguia no caso das restrições booleanas.

X4 1,4

1 1

1 1

1 1

X2 1,2X3 1,3

X4 in 2,3

X3 in 2,4X2 in 3,4R23

R24

R34

X2 1,2

X3 1,3

X4 1,4

Page 38: Domínios Finitos

38

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 NC-1(V, D, R); para X in V para v in Dx fazer se não satisfaz(X-v, Cx) então Dx <- Dx \ {v} fim para fim parafim procedimento

Page 39: Domínios Finitos

39

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

Page 40: Domínios Finitos

40

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.

Page 41: Domínios Finitos

41

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.

Page 42: Domínios Finitos

42

Redução de DomíniosExemplo: 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:

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.

X4 in 2,3

X3 in 2,4X2 in 3,4R23

R24

R34

X2 1,2

X3 1,3

X4 1,4

X4 1,4

1 1

1 1

1 1

X2 1,2X3 1,3

Page 43: Domínios Finitos

43

Redução de DomíniosNa realidade, nenhum dos valores de X3 tem suporte nas variáveis X2 e X4! Com efeito,

• 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.

X4 1,4

1 1

1 1

1 1

X2 1,2X3 1,3

Page 44: Domínios Finitos

44

Redução de DomíniosComo 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!

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.

X4 1,4

1 1

1 1

1 1

X2 1,2X3 1,3

Page 45: Domínios Finitos

45

Redução de DomíniosManutençã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 alteradofim procedimento

Nota: para Rij são considerados os arcos dirigidos aij e a ji

Page 46: Domínios Finitos

46

Redução de DomíniosManutençã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

Page 47: Domínios Finitos

47

Redução de DomíniosComplexidade 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)

Page 48: Domínios Finitos

48

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

Page 49: Domínios Finitos

49

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.

Page 50: Domínios Finitos

50

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 alteradofim 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.

Page 51: Domínios Finitos

51

Redução de DomíniosComplexidade 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)


Recommended