Pesquisa e Heurísticas
Os algoritmos que mantêm um qualquer critério de
consistência ao eliminar valores redundantes dos domínios
reduzem, mas não eliminam a necessidade de pesquisa.
Com efeito se uma rede é consistente isto não implica que
qualquer enumeração não esteja sujeita a falhas.
Na realidade, uma rede de restrições consistente não é
sequer necessáriamente satisfazivel (tal como uma rede
satisfazível não é necessáriamente consistente).
Tudo o que se pode garantir ao manter um qualquer critério
de consistência é que “não se perdem soluções” isto é,
todas as soluções da rede de restrições original são
igualmente soluções da rede consistente.
1
Pesquisa e Heurísticas
Desta forma a redução de domínios não implica em geral a
eliminação da pesquisa.
Em geral essa pesquisa será feita organizando o espaço de
pesquisa numa árvore, havendo lugar a um retrocesso se se
detectar uma falha (insatisfazibilidade).
Como vimos antes, na árvore de pesquisa cada nível
corresponde a uma atribuição de valor a uma variável, pelo
que a pesquisa em árvore pretende construir uma etiqueta
composta completa (incluido todas as variáveis) de uma
forma incremental, isto é, completando sucessivamente
uma etiqueta inicialmente vazia.
2
Pesquisa e Heurísticas
Em termos do esquema de programação em lógica com
restrições (ou mais geralmente, em qualquer algoritmo de
pesquisa entrelaçado com propagação de restrições)
Problema ( Vars):Declaração de Variáveis e Domínios,
Lançamento das Restrições,
Enumeração das Variáveis.
a enumeração das variáveis determina a árvore a ser
pesquisada, porque os nós a pesquisar são condicionados
pela ordem em que as variáveis são enumeradas.
Com efeito, consideremos duas enumerações distintas das
variáveis X in 1..2,Y in 1..3 e Z in 1..4 com os domínios
indicados, que têm diferente cardinalidade.
3
Pesquisa e Heurísticas
enum([X,Y,Z]):indomain(X)
propagação
indomain(Y),
propagação,
indomain(Z).
# de nós = 32
(2 + 6 + 24)
1
1
1
2
2
2
3
4
1
2
3
3
4
1
2
1
3
4
1
2
2
3
4
1
2
3
3
4
1
2
3
4
4
Pesquisa e Heurísticas
enum([X,Y,Z]):indomain(Z),
propagação
indomain(Y),
propagação,
indomain(X).
# de nós = 32
(4 + 12 + 24)
1
1
1
2
2
2
1
3
2
1
1
2
1
3
3
2
2
1
2
1
1
2
1
4
2
2
1
3
2
1
1
2
1
3
2
2
1
2
1
5
2
Pesquisa e Heurísticas
A ordem de enumeração das variáveis pode ter uma enorme
influência na eficiência da pesquisa em árvore, pois
• O número de nós das árvores é diferente, apesar do
espaço de pesquisa ser O( #Xi).
• As falhas podem ser detectadas de forma diferente,
consoante as ordenações das variáveis.
• Durante a propagação, diferentes ordens podem
conduzir a diferentes cortes no espaço de pesquisa.
A ordem de escolha dos valores não tem influência no
espaço de pesquisa, embora possa ter influência na
detecção da primeira solução.
Desta forma o estudo das heurísticas vai incidir
fundamentalmente na ordem de escolha das variáveis. 6
Escolha Heurística da Variável
A heurística na escolha da ordem de enumeração das
variáveis pode ser
• Estática - determinada antes de se começar a
enumeração e não tendo em consideração os efeitos da
propagação
• Dinâmica - escolha que é determinada por análise do
estado do problema após a enumeração de cada
variável.
Nas heurísticas estáticas que iremos abordar, são tidas em
conta na ordenação das variáveis as características da rede
de restrições, nomeadamenta a sua largura e largura de
banda, pelo que a sua explicação será antecedida de
algumas definições.
7
Heurística para Árvores de Restrições
Antes ainda vamos estudar um caso especial de redes de
restrições, constituído pelas redes em que as restrições
(binárias) se podem representar numa árvore (não
confundir com pesquisa em árvore !).
A
B
Se se enumerar a variável A
em
primeiro
lugar,
por
exemplo com um valor a do seu
domínio (A = a), o problema
reduz-se a três problemas
independentes.
E
C
F
B
E
G
D
H
C
F
G
I
D
H
I
8
Heurística para Árvores de Restrições
Neste caso, para garantir que esta enumeração não conduz
“imediatamente” a qualquer inconsistência, o valor a da
variável A deve ter suporte nas variáveis B, C e D.
B
E
C
F
G
D
H
I
Mas este raciocínio pode ser continuado recursivamente,
para cada uma das sub-árvores independentes, com raízes
B, C e D. Por exemplo a enumeração de B não conduz a
qualquer inconsistência, se o valor b que fôr escolhido (isto
é B = b) tiver suporte em E e F.
9
Heurística para Árvores de Restrições
De uma forma geral, fazendo-se a
variáveis de uma forma descendente na
escolhidos para as variáveis nunca
contradições se os valores mantidos
suporte em todos os seus descendentes.
enumeração das
árvore, os valores
irão conduzir a
num nó tiverem
A
B
E
C
F
G
D
H
I
Assim uma boa heurística para a escolha da variável para
árvores de restrições é a escolha de variáveis de forma
descendente na árvore.
10
Heurística para Árvores de Restrições
Embora este não seja o caso geral, como já foi visto
anteriormente, no caso das árvores a consistência de arco
é equivalente à satisfazibilidade das restrições!
Com efeito,
Usando uma qualquer heurística descendente na
enumeração das variáveis, a escolha dos valores nunca
conduz a contradições, pois estes têm suporte nos nós
descendentes, que se tormam as raízes de sub-problemas
independentes.
Na realidade, a direccionalidade na enumeração, permite
utilizar um algoritmo de manutenção de consistência de
arco direccionado, e menos custoso que os AC-X.
11
Heurística para Árvores de Restrições
Voltando ao exemplo anterior,
não é necessário que todos os
valores nos domínios de B, C e
D tenham suporte nos valores
do domínio de A. Apenas é
necessário que todos os
valores de A tenham suporte
nos domínios de B, C e D.
Quando um valor de A fôr
escolhido, os valores não
compatíveis com esse valor
são eliminados pela simples
manutenção de consistência
de nó.
A
B
E
C
F
B
E
G
D
H
C
F
G
I
D
H
I
12
Heurística para Árvores de Restrições
Duma forma geral, pode definir-se um critério de
consistência de arco dirigida se, ao contrário do que temos
feito, considerarmos um grafo dirigido para representar a
rede de restrições. Mais especificamente, se arbitrarmos
uma direcção para cada restrição do problema.
Definição (Consistência de Arco Dirigida): Um problema de
restrições tem os seus arcos dirigidos consistentes sse
1. Tiver todos os nós consistentes; e
2. Para qualquer etiqueta Xi-vi de qualquer variável Xi, e
para todas os arcos aij dirigidos correspondentes a
restrições Rij, existe um valor vj de suporte, isto é, a
etiqueta composta {Xi-vi, Xj-vj} satisfaz a restrição Rij.
13
Algoritmo DAC
Manutenção de Consistência de Arcos
O algoritmo descrito abaixo assume que as variáveis estão
“ordenadas” de 1 a n, sendo os arcos dirigidos da “menor”
para a “maior” variável, e limita-se a impôr a consistência
em todos os arcos dirigidos, começando pelas maiores
variáveis, e sem posterior reavaliação
procedimento DAC(V, D, R);
para i de n até 1 com passo -1 fazer
para Rij in R fazer
se i < j então rev_dom(aij,V,D,R) fim se
fim para
fim para
fim procedimento
Nota: rev_dom(aij,V,D,R) é o usado nos algoritmos AC-1 e AC-3.
14
Algoritmo DAC
Complexidade temporal do algoritmo DAC
Como habitual, vamos assumir que os arcos são em número
de a, e que as n variáveis do problema têm cada com d
valores no seu domínio.
O algoritmo visita cada um dos a arcos exactamente uma
vez. Em cada arco aij, cada um dos d valores da variável Xi é
testado com d valores da variável Xj.
Tendo em conta estes factores, a complexidade temporal do
DAC , no pior caso, é, tal como nos AC-4/6/7
O(ad2)
não apresentando o algoritmo quaisquer requisitos de
espaço. Numa árvore, a = n, e a complexidade é
15
O(nd2)
Algoritmo DAC
Naturalmente, o algoritmo DAC descrito não garante a
eliminação de todos os valores redundantes numa rede
dirigida genérica, por não reavaliar as consequências das
reduções de domínios.
No entanto ele é suficiente para o caso das árvores se os
arcos forem dirigidos no sentido descendente e analisados
(revistos) no sentido ascendente, isto é, se as variáveis
forem ordenadas de forma a que cada nó seja “menor” que
os seus descendentes.
Assim, todos os valores de um nó têm garantido suporte
nos seus descendentes, embora não nos seus ascendentes!
Quando estes são enumerados, a consistência de nó elimina
os valores que não conduzam a soluções.
16
Algoritmo DAC
Exemplo: Consideremos a árvore de restrições abaixo
X1 in {1, 3, 5, 7, 9},
>
X2 in {2, 4, 6}, X5 in {3, 9}, X6 in {4, 8},
X3 in {1, 5, 7}, X7 in {3, 9},
X4 in {1, 5, 8}, X8 in {3, 7}, X9 in {2, 9}
Após revisão do arco X2 -> X5
X2 -> X6
X3 -> X7
X4 -> X8
X4 -> X9
X1 -> X2
X1 -> X3
X1 -> X4
>
5
2
>
6
X2 in {2, 4, 6}
X2 in {2, 4, 6}
X3 in {1, 5, 7}
X4 in {1, 5, 8}
X4 in {1, 5, 8}
X1 in {1, 3, 5, 7, 9}
X1 in {1, 3, 5, 7, 9}
X1 in {1, 3, 5, 7, 9}
1
>
3
>
7
% X5
% X6
% X7
% X8
% X9
% X6
% X3
% X4
>
>
4
8
>= 3
>= 3
>= 3
>= 3
>= 2
>= 5
>= 5
>= 8
>
9
17
Algoritmo DAC
Exemplo(cont): A enumeração não está sujeita a retrocesso
X1 in {7, 9},
>
X2 in {6}, X5 in {3, 9}, X6 in {4, 8},
X3 in {5, 7}, X7 in {3, 9},
X4 in {5, 8}, X8 in {3, 7}, X9 in {2, 9}
>
5
2
>
1
>
3
6
>
7
>
>
4
8
9
X1 = 7 NC impõe X2 in {6}, X3 in {5}, X4 in {4}
X2 = 6 NC impõe X5 in {3}, X4 in {6},
X3 = 5 NC impõe X5 in {3},
X4 = 4 NC impõe X8 in {3}, X9 in {2},
X1 = 9 NC impõe X2 in {6}, X3 in {3}, X4 in {4, 8}
X2 = 6 ...., X3 = 5, ....
X4 = 4 NC impõe X8 in {3}, X9 in {2}
ou X4 = 8 NC impõe X8 in {3, 7}, X9 in {2}
>
18
Largura de Grafos
O caso especial das árvores pode ser generalizado para
outros tipos de redes de restrições binárias, se tivermos
em conta que as árvores são um caso especial de grafos.
Definição (Largura de Nó, segundo uma ordem O):
Para uma ordenação total, O, dos nós de um grafo G, a
largura de um nó N, segundo O é o número de nós
anteriores que lhe são adjacentes.
>
>
5
2
>
6
1
>
3
7
>
>
>
8
4
>
9
Como é imediato constatar,
com qualquer ordenação
crescente, da raíz para as
folhas, todos os nós de uma
árvore (excepto a raíz) têm
largura igual a 1.
19
Largura de Grafos
Definição (Largura de um grafo G, segundo uma ordem O):
Para uma ordenação total, O, dos nós de um grafo G, a
largura do grafo segundo O, é a máxima largura dos seus
nós, segundo essa ordem.
Definição (Largura de um grafo G):
A largura de um grafo G, é sua menor largura, para
qualquer ordenação total, O, que seja considerada para os
seus nós.
>
>
5
2
>
6
1
>
3
7
>
>
>
8
4
>
9
Como é imediato por estas
definições, uma árvore é um
caso especial de um grafo
com largura igual a 1.
20
Largura de Grafos
Exemplo: No grafo abaixo poderemos considerar várias
ordenações dos nós, conducentes a diferentes larguras. A
largura do grafo é 3 (é a largura obtida, por exemplo, pela
ordenação O1dir).
1
2
3
4
5
6
1
7
2
< wO1dir = 3 (nós 4, 5, 6 e 7)
> wO1inv = 5 (nó 1)
3
4
5
4
3
2
< wO2dir = 5 (nó 1)
5
6
7
1
> wO1inv = 6 (nó 4)
6
7
21
Largura de Grafos
Para evitar retrocessos, na enumeração, da raiz para as
folhas, de uma rede de restrições (binárias) com a forma
de árvore bastaria garantir que para cada nó existissem
valores nos seus nós descendentes que os suportassem.
A generalização para o caso de redes arbitrárias deverá
ter em conta a ordenação considerada na enumeração. Se
nessa ordenação, cada nó tiver no máximo k nós vizinhos
enumerados antes de si, bastará manter consistência-k+1
forte, para garantir que não serão necessários retrocessos
na enumeração.
Na realidade, e tal como nas árvores, bastará manter uma
consistência-k+1 forte ordenada, se o algoritmo que a
mantiver visitar os grupos de k nós por ordem
22
“decrescente”.
Largura de Grafos
Exemplo:
Com a ordenação Lo1dir, bastará garantir consistência-4 forte. A
consistência-4 forte garante que qualquer etiqueta de até 3 variáveis
que satisfaz as restrições relevantes, pode ser estendida com uma
quarta variável que satisfaça as restrições relevantes.
Por um lado, qualquer valor v1 do domínio da variável 1 pode ser
escolhido (uma etiqueta-1 pode ser estendida, pois o sistema é
fortemente consistente-4).
Por outro lado, um algoritmo que mantenha a consistência-4 forte,
elimina eventualmente valores dos domínios das variáveis, mas não
“esvazia” o domínio de nenhuma variável (ver adiante).
1
2
1
2
3
4
5
6
3
4
7
5
6
7
23
Largura de Grafos
Exemplo (cont.):
Assim o sistema de 6 variáveis é fortemente consistente-4 e tem
menos uma variável que o anterior.
Por recursão, pode verificar-se que não haverá lugar a retrocesso na
enumeração das outras variáveis. Com efeito, podem ir-se enumerando
as variáveis por ordem crescente. Após cada enumeração obtem-se um
sistema, fortemente consistente-4, e com menos uma variável.
Eventualmente atinge-se um sistema fortemente consistente-4, com
apenas 4 variáveis, em que pode naturalmente ser feita uma
enumeração sem retrocesso.
1
2
1
2
3
4
5
6
3
4
7
5
6
7
24
Largura de Grafos
Há que mostrar que, após enumeração da menor variável (segundo uma
ordenação que garante uma largura w) de um sistema fortemente
consistente-k (com k > w), o sistema resultante mantem valores no
domínio de todas as outras variáveis (2 a n).
Sendo o sistema fortemente consistente-k, as variáveis 2, ... , k tem
valores compatíveis com o valor v1, escolhido arbitrariamente para a
primeira variável. Um algoritmo que mantenha a consistência-4 forte
pode eliminar os valores não compatíveis.
A variável k+1 só pode estar ligada a w das variáveis anteriores (no
exemplo, a variável 5 está ligada a 1, 2 e 4). Assim, qualquer triplo de
valores dessas variáveis, nomeadamente os que não foram eliminados,
tem um valor compatível na variável 5. O algoritmo que mantem a
consistência-4 forte pode eliminar os valores não compatíveis.
Continuando o raciocínio recursivamente, as variáveis 6, ..., n manterão
valores no domínio, como se pretendia mostrar.
25
Largura de Grafos
Fica assim demonstrado (informalmente) o seguinte
Teorema: Uma rede de restrições fortemente consistentek, pode ser enumerada em profundidade sem retrocesso, se
existir uma ordenação O segundo a qual o grafo tem uma
largura w inferior a k.
Em termos práticos, a enumeração livre de retrocesso fazse por ordem crescente (segundo O) das variáveis,
mantendo-se a consistência-k forte no problema resultante
após a enumeração de cada variável.
26
Heurística de Mínima Largura (MWO)
A manutenção de consistência-k forte é muito custosa
computacionalmente, e não é em geral mantida.
No entanto, especialmente em redes pouco densas e em que
os graus dos nós variem significativamente, as ordens dos
nós do grafo conducentes à sua menor largura podem ser
usadas como heurística para a escolha da variável a
enumerar. Mais especificamente, pode definir-se a
Heurística MWO (Minimum Width Ordering):
A heurística MWO (ordem de minima largura) determina
que num problema de restrições as variáveis sejam
enumeradas por ordem crescente duma enumeração que
conduza à menor largura do grafo primal do problema.
27
Heurística de Mínima Largura (MWO)
A definição dada refere o grafo primal de um problema. No
caso das restrições serem binárias, o grafo de restrições é
o grafo primal. No caso de restrições n-árias, o grafo
primal inclui um arco entre quaiquer variáveis ligadas por
uma restrição n-ária.
Por exemplo, o grafo que temos vindo a utilizar, pode ser o
grafo primal do problema com 2 restrições quaternárias
(R1245 e R1346) e 3 restrições ternárias (R123, R457 e R467 ).
R123
R1245
R1346
R457
R467
-->
-->
-->
-->
-->
arcos a12, a13 e a23
arcos a12, a14, a15, a24, a25 e a45
arcos a13, a14, a16, a34, a36 e a46
arcos a45, a47 e a57
arcos a46, a47 e a67
1
2
3
4
5
6
7
28
Heurística de Mínima Largura (MWO)
Para se aplicar a heurística MWO, há que determinar a
ordenação O dos nós, conducente à menor largura do grafo
(primal) de restrições. O seguinte algoritmo pode ser
utilizado para esse efeito
função vars_ordenadas(V,R): Lista de nós;
se V = {N} então
% N é o único nó
vars_ordenadas <- N
senão
N <- arg Vi min {grau(Vi,R) | Vi in V}
% N é um dos nós com menor número de vizinhos
R’<- R \ arcos(N,R)
V’<- V \ {N}
vars_ordenadas <- vars_ordenadas(V’,R’) & N
fim se
29
fim função
Heurística de Mínima Largura (MWO)
Exemplo: No grafo anterior o nó 7 é o de menor grau (=3).
1
2
3
4
5
Retirado o nó 7, os nós 5 e 6
são os de menor grau (=3).
1
2
3
4
6
Retirando-se o nó 6 obtem-se
7
6
5
São de seguida retirados sucessivamente os nós 5 e 4 (grau 3), e ainda
os nós 3 (grau 2) e 2 (grau 1).
1
2
1
3
4
2
1
3
2
1
3
2
4
5
Obtem-se assim, por ordem crescente, a ordenação [1,2,3,4,5,6,7] e
verifica-se que a largura do grafo é 3.
30
Heurística de Mínimo Grau (MDO)
Um aproximação da heurística MWO é a heurística MDO
em que se evita o cálculo da ordem que conduz à mínima
largura do grafo
Heurística MDO (Maximum Degree Ordering):
A heurística MDO (ordenação pelo maior grau) determina
que num problema de restrições as variáveis sejam
enumeradas por valor decrescente do seu grau no grafo
primal do problema.
1
Exemplo: A heurística MDO usaria uma
ordenação começada pelos nós 4 (g=6)
e 1(5) e terminada no nó 7(3). Os nós 2,
3, 5 e 6, todos com grau 4, seriam
escolhidos arbitrariamente.
2
3
4
5
6
7
31
Heurísticas MWO e MDO
As heurísticas MWO e MDO baseiam-se no mesmo
princípio - começar a enumeração pelas variáveis que têm
mais variáveis ligadas a si por restrições, com o objectivo
de detectar mais rapidamente as falhas na enumeração.
(de notar que no algoritmo para determinar a ordem de
largura mínima, as últimas variáveis são as de menor grau).
As ordenações não são coincidentes
necessariamente e podem ser usadas
para desempate. Por exemplo as duas
ordenações MDO
O1 = [4,1,5,6,2,3,7]
O2 = [4,1,2,3,5,6,7]
induzem diferentes larguras (4 e 3).
1
2
3
4
5
6
7
32
Conjuntos Corta-Ciclos
A heurística MWO é particularmente útil quando se
mantêm níveis “elevados” de consistência, e baseia-se no
Teorema que generaliza para redes de restrições
arbitrárias as heurísticas usadas para as árvores.
Uma alternativa quando não se se pretendem manter níveis
elevados de consistência, é enumerar as variáveis por uma
ordem que torne o grafo de restrições numa árvore, a
partir do qual, a coerência de arco dirigida garante a
eliminação do retrocesso.
Esta é a ideia por detrás da determinação dos conjuntos
corta-ciclos (“Cycle-cut sets”).
33
Conjuntos Corta-Ciclos
1
Enumerando-se inicialmente os nós
1 e 4 no exemplo que temos usado,
obtem-se o grafo.
2
3
4
5
6
7
Desta forma, a adição de qualquer nó ao conjunto {1,4}
elimina o ciclo 2-3-6-7-5-2 (tornando os restantes 4 nós
numa árvore). Os conjuntos {1,4,2}, {1,4,3}, {1,4,5},
{1,4,6} e {1,4,7}, são pois conjuntos corta-ciclos.
1
2
3
4
5
6
7
Ao enumerar os nós do conjunto
corta-ciclos {1,4,7}, o grafo
resultante é uma árvore!
34
Conjuntos Corta-Ciclos
Obviamente, o que se pretende é obter os conjuntos
corta-ciclos de menor cardinalidade. Com efeito, numa
rede de restrições, com n variáveis com domínios de
dimensão d, se se determinar um conjunto corta-ciclos
com k nós, a complexidade da pesquisa fica reduzida à
pesquisa dum tuplo nos k nós, com complexidade temporal
O(dk)
E à manutenção de consistência de arco dirigida na árvore
de n-k nós, com complexidade O(ad2).
Tendo em atenção que a = n-k-1, e para k “pequeno”, a
complexidade temporal global é de
O(n dk+2).
35
Conjuntos Corta-Ciclos
Pode portanto definir-se a
Heurística CCS (Cycle-Cut Sets)
Segundo a heurística CCS (Conjunto Corta-Ciclos), as
primeiras variáveis a enumerar devem ser os elementos de
um conjunto corta-ciclos de cardinalidade mínima.
Infelizmente, não parece haver bons algoritmos para
determinar os conjuntos corta-ciclos com cardinalidade
mínima, ficando a utilidade da heurística dependente das
aproximações utilizadas.
Duas aproximações correspondem a utilizar o algoritmo
vars_ordenadas,
com
a
ordenação
inversa,
ou
simplesmente começar pelos nós com maior grau.
36
Conjuntos Corta-Ciclos
Usando o algoritmo vars_ordenadas mas seleccionando os
nós com maior grau obteríamos a seguinte ordenação
1
Nó 4 - grau(6) ficando o grafo
2
3
4
5
6
1
7
Nó 1 - grau(4) ficando o grafo
2
3
4
5
6
7
Nesta altura, a inclusão de qualquer dos outros nós
(todos de grau 2) converte o sistema numa árvore.
Escolhendo o nó 2, obtem-se um dos conjuntos cortaciclos, {1,2,4}, que é mínimo.
37
Heurística MBO
Em contraste com as heurísticas MWO e MDO que
pretendem detectar mais rapidamente as falhas na
enumeração, a heurística MBO tem como objectivo eliminar
o retrocesso irrelevante.
Para esse efeito pretende-se, na medida do possível,
garantir que se uma variável X não pode ser enumerada
então as variáveis que possam estar em conflito com X lhe
sejam imediatamente anteriores, na ordem de enumeração.
A ideia é que se o retrocesso fôr feito para uma variável Y
que não está ligada a X por uma restrição, então é natural
que a mudança de valor de Y não resolva a impossibilidade
de enumeração de X.
Tais ideias são captadas na noção de Largura de Banda.
38
Largura de Banda de Grafos
Definição (Largura de Banda de G, segundo uma ordem O):
Para uma ordenação total, O, dos nós de um grafo G, a
largura de banda do grafo segundo O, é a máxima distância
nessa ordem entre dois nós adjacentes.
Exemplo:
Com a ordem O1, ao lado, a largura de
banda é 5, distância entre os nós
adjacentes 1/2 e 6/7. Se a escolha do
valor da variável X1 fôr determinante
para a escolha do valor de X6, a alteração
de X1 só se faz após retrocesso das
variáveis X5, X4, X3 e X2.
1
2
3
4
5
1
2
6
7
3
5
4
6
7
39
Largura de Banda de Grafos
Definição (Largura de Banda de um grafo G):
A largura de banda de um grafo G, é menor largura de
banda que pode ser obtida por uma qualquer ordenação
total dos seus nós considerada.
Exemplo:
Com a ordem O2, ao lado, a largura de
banda é 3, distância entre os nós
adjacentes 2/3/4 e 5/6/7.
Não há ordenação que induza uma largura
de banda inferior a esta, pelo que a
largura de banda do grafo é 3.
1
2
3
4
5
1
2
3
5
4
6
7
6
7
40
Heurística MBO
Com base no conceito de Largura de Banda define-se a
Heurística MBO (Minimum Bandwidth Ordering):
Segundo a heurística MBO (ordenação pela menor largura
de banda) as variáveis de um problema de restrições devem
ser enumeradas de acordo com uma ordem que induza uma
largura de banda mínima no grafo primal do problema.
1
Exemplo:
2
A
heurística
MBO
usaria
uma
ordenação como a O2 que induz uma
largura de banda 3.
3
5
4
6
7
1
2
3
4
5
6
7
41
Heurística MBO
A utilização da heurística MBO em conjunto com a
propagação de restrições é algo problemática já que:
1. Os grafos de restrições em que é mais útil devem ser
esparsos e não ter nós com elevedo grau. Havendo um
nó com grau elevado, a sua distância ao “último”
vizinho domina a largura de banda.
2. O princípio em que se baseia, evitar retrocesso
irrelevante
é
atingido,
eventualmente
mais
eficientemente, pela propagação de restrições.
3. Não há algoritmos eficientes para calcular a largura
de banda de um grafo (ver [Tsan93], cap. 6, para
referências).
42
Heurística MBO
Caso 1: Os grafos de restrições em que é mais útil devem
ser esparsos e não ter nós com elevado grau. Havendo um
nó com grau elevado, a sua distância ao “último” vizinho
domina a largura de banda.
Exemplo:
O nó interior, de grau 6, determina
que não pode haver uma largura
inferior a 3 (3 nós antes e 3 depois).
Há muitas ordenações com essa
largura de banda, e se 3 estivesse
ligado a 7 não havia hipótese de evitar
uma largura de banda 4.
3
5
6
4
1
2
7
43
Heurística MBO
Caso 2: O retrocesso irrelevante
propagação de restrições.
é
eliminado
Exemplo:
por
1
Se a escolha do valor da variável X1 fôr
determinante para a escolha do valor de
X6, é muito natural que a propagação de
restrições determine o esvaziamento do
domínio de X6 sem necessitar do
retrocesso das variáveis X5, X4, X3 e X2.
1
2
3
4
2
6
7
3
5
4
5
6
7
A heurística MBO é mais apropriada se os algoritmos de
44
retrocesso não usarem propagação de restrições.
Heurística MBO
Caso 3: Não há algoritmos eficientes para calcular a largura
de banda de um grafo .
Em geral, menores larguras correspondem a menores
larguras de banda, mas as ordenações que obtêm as menores
larguras e larguras de banda não são coincidentes.
C
D
A
B
Largura (mínima) = 2;
E
F
G
H
C
D
Largura de Banda = 5
A
C
D
Largura = 3;
E
A
B
F
G
H
Largura de Banda (mínima) = 4
E
B
F
G
H
45
Heurísticas Dinâmicas para Escolha da Variável
Para além das heurísticas estáticas analizadas, MWO,
MDO, CCS e MBO) a escolha da ordem de enumeração das
variáveis pode ser determinada dinamicamente, isto é, em
vez de fixada antes de começar a enumeração a escolha da
variável é determinada (ou ajustada) durante a mesma.
Para além de heurísticas dependentes do problema, existe
um princípio genérico, first-fail, que se tem revelado muito
eficiente.
A ideia é muito simples: quando um problema se decompõe
em vários sub-problemas relacionados, deveremos começar
pelos mais difíceis. Não vale a pena resolver vários
problemas simples com hipóteses irrealistas que depois
serão desmentidas na resolução dos mais difíceis.
46
Heurísticas First-Fail
Há várias maneiras de interpretar e implementar este
princípio genérico de first-fail.
Em primeiro lugar, identificamos no problema de satisfação
das restrições os vários sub-problemas como sendo os de
enumerar valores para as diversas variáveis. Como medir a
dificuldade destes problemas?
Como enumerar é imediato (uma escolha), o que torna os
problemas “difíceis” é garantir que após a propagação de
restrições a escolha do valor é viável. Esta avaliação é
difícil em geral, pelo que devermos considerar
características das variáveis fáceis de determinar, como
• O domínio das variáveis
• O número de restrições em que participam.
47
Heurísticas First-Fail
O domínio das variáveis
Intuitivamente, se tivermos uma variável X1 com m1 valores
no seu domínio e outra X2 com m2 valores, é mais difícil
atribuir valores à variável X1, porque a escolha é mais
reduzida!
No limite, se a variável X1 só tiver um valor no seu domínio
(m1 = 1), não há escolha possível e o melhor a fazer é mesmo
atribuir o valor disponível à variável.
Outra forma de ver a questão é a seguinte:
• Por um lado, a hipótese de “acertar” num valor de X1 que
pertence a uma solução é maior do que no caso de X2.
• Por outro lado se esse valor se vier a revelar errado,
pode eliminar-se um maior espaço de pesquisa.
48
Heurísticas First-Fail
Exemplo:
Na situação ao lado do
problema da 8 rainhas em que
já foram enumeradas as
rainhas Q1, Q2 e Q3, temos
para domínio das restantes
rainhas
1
1
1
2
1
2
1
2
1
1
2
3
2
1
2
3
2
3
1
2
3
1
2
3
1
2
1
2
3
1
3
1
Q4 in {2,7,8}, Q5 in {2,4,8}, Q6 in {4}, Q7 in {2,4,8}, Q8 in {2,4,6,7}.
Desta forma, a variável a enumerar de seguida deverá ser a
variável Q6, e não Q4, que se seguiria na ordem “natural”.
De notar que a consistência de nó, com a escolha de
variáveis de domínio unitário, atinge o mesmo efeito da
consistência de arco, sem os seus custos computacionais!
49
Heurísticas First-Fail
O número de restrições em que participam as variáveis
Esta heurística é basicamente a heurística MDO, mas em
que o grau das restrições é avaliado dinâmicamente.
Como a heurística pretende resolver primeiro as variáveis
mais difíceis, a enumeração torna-se mais difícil com o
número de restrições em que participa a variável, já que
uma restrição só pode limitar as possibilidades de atribuir
valores a uma variável.
Naturalmente, e tal como no caso do domínio, esta decisão
é puramente heurística. O efeito das restrições depende
muito da sua propagação, que é em geral muitodependente
(da instância) do problema .
50
Outras Heurísticas Dinâmicas
Em certos tipo de problemas podem utilizar-se heurísticas
especialmente adequadas para a estrutura do problema.
Por exemplo em problemas de escalonamento de tarefas,
em que elas têm de se fazer num determinado período e
não se podem “sobrepôr”, convem espalhá-las o mais
possível no período em causa.
Isto sugere que se comecem por enumerar (as variáveis que
modelam) as tarefas que podem começar primeiro ou que
podem acabar em ultimo lugar, de forma a dar “espaço”
para acomodar as restantes tarefas.
Neste caso, convém uma escolha dinâmica da variável que
tenha em conta os valores existentes no domínio.
51
Heurísticas Mistas
Tendo em conta as características das várias heurísticas
descritas, poder-se-ão considerar estratégias híbridas, que
integrem várias destas heurísticas.
Por exemplo, a heurística estática CCS (Conjunto CortaCiclos), determina um conjunto de variáveis que devem ser
enumeradas em primeiro lugar, de forma a converter o
grafo de retsrições numa árvore. Dentro deste conjunto de
nós, pode aplicar-se uma heurística dinâmica first-fail.
Por outro lado, quando um conjunto de variáveis é
enumerado de acordo com uma heurística estática, essa
heurística pode ser reavalida tendo em conta a propagação
já efectuada, tornando-a mais “dinâmica”
52
Heurísticas de Escolha de Valor
Uma vez seleccionada uma variável para enumerar, há que
escolher um valor dentro do seu domínio corrente.
Neste caso, existem poucos métodos de aplicação
generalizada. Existe no entanto um princípio genérico, que
corresponde a escolher o valor que aumente a
probabilidade do sucesso.
A razão para isto é óbvia. Ao contrário da escolha da
variável, a escolha do valor não vai influir no espaço de
pesquisa, e portanto há que tentar descobrir o mais
eficientemente possível o caminho para uma solução.
A aplicação deste princípio depende muito do tipo de
problema em consideração.
53
Heurísticas de Escolha de Valor
Algumas heurísticas para escolha de valor são as seguintes:
Escolha ad hoc: Em problemas de escalonamento de tarefas
referidos, uma vez seleccionada uma variável com
menores/maiores valores no seu domínio, a essa variável
deverá ser atribuído o menor/maior valor desse domínio
que é o que aumneta a possibilidade de sucesso.
Antevisão de Sucesso: Pode-se tentar prever (lookahead) a
probabilidade de sucesso, avaliando para os vários valores
possíveis, e após a sua propagação, essa probabilidade
através de medidas agregadas da cardinalidade dos
domínios das variáveis ainda não enumeradas(como é feito
na medida kappa), escolhendo-se naturalmente o valor que
maximize essa medida.
54
Heurísticas de Escolha de Valor
Optimização: Em problemas nos quais se pretenda
optimizar uma função objectivo, podem obter-se limites
(bounds) dessa função para os valores ainda permitidos nas
variáveis não enumeradas, e verificar como eles se alteram
com a atribuição dois vários valores possíveis para a
variável escolhida.
Naturalmente, a heurística optará pelo valor que optimize
os limites da função em causa.
De notar que neste caso, tanto se poderá fazer o cálculo
dos limites antes da propagação (menos computação, mas
também menos informação) ou após essa propagação ser
efectuada.
55
Heurísticas no SICStus
Baseado no paradigma da programação em lógica com
restrições, um programa em SICStus tem a estrutura
atrás descrita
Problema ( Vars):Declaração de Variáveis e Domínios,
Lançamento das Restrições,
Enumeração das Variáveis.
Na enumeração das variáveis pretende
variáveis X1, X2, ..., Xn, de uma lista Lx,
domínio.
A implementação das heurísticas depende
são seleccionadas as variáveis Xi da lista,
seus valores.
atribuir-se às
valores no seu
da forma como
e escolhidos os
56
Heurísticas no SICStus
O SICStus permite controlar a enumeração de várias
maneiras. A enumeração pode ser feita através de um único
predicado predefinido, labeling/2, em que
• o 1º argumento é a lista de opções, eventualmente vazia
• o 2º argumento é a lista Lx de variáveis a enumerar.
Por omissão, a chamada de labeling([], Lx)selecciona
as variáveis X1, X2, ..., Xn, da lista Lx, de acordo com a sua
posição, da esquerda para a direita. O valor escolhido à
variável é o menor valor do seu domínio.
Este predicado pode ser usado sem quaisquer opções para
heurísticas estáticas, desde que as variáveis sejam
previamente ordenadas, de forma adequada, na lista Lx.
57
Heurísticas no SICStus
Com a lista de opções vazia, o predicado labeling([],L)
é equivalente ao predicado enumera(L) abaixo
enumera([]).
enumera([Xi|T]):indomain(Xi),
enumera(T).
Em que o predicado, pré-definido, indomain(Xi), escolhe
para a variável Xi valores no domínio por ordem crescente.
Há alternativas para escolha do valor, que passam pela
análise do domínio corrente da variável, disponibilizado pelo
predicado fd_dom/2. Por exemplo
?- X in 1..5, X #\=3, fd_dom(X,D).
D = (1..2)\/(4..5),
X in(1..2)\/(4..5) ?
58
Heurísticas no SICStus
Geralmente, não é necessário descer a esse nível de
programação, usando-se as opções pré-definidas no
predicado labeling/2.
As opções de interesse para a escolha do valor da variável
seleccionada são up e down permitindo a atribuição por
ordem crescente e decrescente de valores.
Se se pretender garantir que os valores de algumas das
variáveis Xi são escolhidos de forma decrescente, poderse-á, para as variáveis em causa , substituir a chamada do
predicado
indomain(Xi) por
labeling([down],[Xi])
59
Heurísticas no SICStus
As opções de interesse para a escolha da variável são
leftmost, min, max, ff, ffc e variable(Sel)
•leftmost - é o modo por omissão.
Escolhe as variáveis pela sua ordem na lista.
• min, max - escolhe a variável com menor/maior valor no
seu domínio.
Pode ser útil por exemplo, para problemas de
escalonamento de tarefas em que se pretende ir
alocando as tarefas “sequencialmente”.
• ff, ffc - implementa e heurística first-fail, escolhendo
a variável com domínio de menor cardinalidade, com
desempate pelo número de restrições.
60
Heurísticas no SICStus
•variable(Sel)
Sel deve ser definido no programa como um predicado,
cujos últimos 3 últimos parâmetros são Vars,
Selected, Rest em que dada a lista Vars de variáveis
a atribuir, Selected é a variável seleccionada, sendo
Rest uma lista com as restrantes variáveis. Outros
parâmetros podem ser incluídos, antes destes três.
Por exemplo, se se usar opção
variable(contem(5))
dever-se-á especificar o predicado
contem(V,Vars, Selected, Rest)
que deverá escolher, na lista Vars, uma variável
Selected, que contenha o valor V no seu domínio.
61
Heurísticas no SICStus
De notar que todas estas opções do predicado labeling/2
podem ser programadas a mais baixo nível, usando as
primitivas adequadas disponibilizadas pelo SICStus para
inspecção do domínio das variáveis (Predicados Reflexivos)
nomeadamente os predicados
fd_min(?X, ?Min)
fd_max(?X, ?Max)
fd_size(?X, ?Size)
fd_degree(?X, ?Degree)
com o significado óbvio. Por exemplo
?- X in 3..8, Y in 1..5, X #< Y,
fd_size(X,S), fd_max(X,M), fd_degree(Y,D).
D = 1,
M = 4,S = 2,
X in 3..4,
Y in 4..5 ?
62
Exemplo no SICStus
O programa rainhas_fd_h resolve o problema das rainhas
rainhas(N,M,O,S,F) com várias opções de enumeração:
Escolha da Variável
• A opção ff é utilizada.
• As variáveis passadas para o predicado labeling/2
podem/não (com M=2/1) ser ordenadas do meio para as
pontas (por exemplo, [X4,X5,X3,X6,X2,X7,X1,X8]) através
do predicado ordena(2,Lx,Lo).
Escolha do Valor
• Em vez de começar a enumeração das variáveis pelo valor
1, pode ser especificado um offset (valor do parâmetro
O) começando a enumeração “a meio” do domínio.
63
Variantes à Pesquisa em Profundidade
O paradigma da Programação em Lógica com Restrições,
utiliza pesquisa em profundidade do espaço de soluções.
Apesar de “entrelaçado” com a propagação de restrições, e
da utilização de heurísticas, a eficiência da pesquisa
depende criticamente das primeiras escolhas, isto é dos
valores atribuídos às primeiras variáveis seleccionadas.
Com efeito, o retrocesso destes valores, dito cronológico,
apenas tem efeito quando todo os valores das restantes k
variáveis são “visitados”, num tempo O(2k).
Desta forma têm sido estudadas variantes à pesquisa em
profundidade com retrocesso cronológico, nomeadamente o
retrocesso inteligente, alargamento iterativo, discrepância
limitada, e duração incremental.
64
Retrocesso Inteligente
No retrocesso cronológico, a falha na enumeração de uma
variável causa o retrocesso com a escolha do valor seguinte
na variável enumerada imediatamente antes, mesmo que não
seja esta a causa da falha.
As várias técnicas de retrocesso inteligente, ou dirigido
por dependências, (dependency directed backtracking)
tentam identificar essas causas, de forma a retroceder
directamente para a primeira variável com alguma
participação na falha.
Algumas das variantes de retrocesso inteligente são:
• Backjumping ;
• Backchecking ; e
• Backmarking .
65
Retrocesso Inteligente
Backjumping
Ao falhar a atribuição de valores
para uma variável são analisadas
todas as variáveis que contribuem
para a falha de cada um dos valores,
sendo o retrocesso feito para a
“maior” das “menores” variáveis.
1 23 25 45 35 1
2
3
No exemplo ao lado, ao analisar-se a causa da falha na
atribuição devalores à variável Q6, verifica-se que o
retrocesso deve ser feito para a variável Q4, já que é a
maior das menores variáveis que aparece nas variáveis em
conflito.
66
Retrocesso Inteligente
Backchecking e Backmarking
Estas técnicas podem ser útil quando os testes de
compatibilidade entre os valores de duas variáveis são
“custosos”. A ideia base é memorizar conflitos, de forma a
evitar calculá-los repetidamente.
• Em backchecking, são memorizados apenas as
atribuições que entraram em conflito.
• Em backmarking são adicioanalmente memorizadas as
atribuições que não entraram em conflito.
Em geral, a utilidade destas técnicas é limitada se existir
propagação de restrições (há algumas excepções como em
alguns sistemas SAT), já que a propagação antecipa, de
alguma forma, o retrocesso e evita retrocesso irrelevante!
67
Alargamento Iterativo
No alargamento iterativo (iterative broadening) é atribuído
um limite b ao número de vezes que um nó é visitado (a
visita inicial mais as vezes em retrocesso). Se esse limite é
atingido, o nó e os seus descendentes não são mais
explorados.
1
No exemplo, assumindo-se
que b=2, o espaço de solucões
a sombreado não é visitado.
1
1
2
2
3
4
1
2
3
3
4
1
2
3
4
Naturalmente, se a pesquisa falhar para um dado valor de
b, ele pode ser aumentado incrementalmente, pelo que o
espaço percorrido vai-se iterativamente alargando.
68
Discrepância Limitada
A discrepância limitada, pressupõe que a heurística de
atribuição de valores pode falhar um número pequeno de
vezes, e dirige a pesquisa para a zona onde potencialmente
estão as soluções, limitando a um valor d, o número de
vezes que a sugestão da heurística não é seguida.
No exemplo, assumindo-se as
opções “certas” à esquerda e
d=3, o espaço de solucões a
sombreado não é visitado.
d=3
d=2
1
1
1
2
2
3
4
1
2
3
3
4
1
2
3
4
Naturalmente, se a pesquisa falhar para um dado valor de
b, ele pode ser aumentado incrementalmente, pelo que o
espaço percorrido vai-se iterativamente alargando.
69
Duração Incremental
A objectivo é semelhante ao alargamento iterativo,
discrepância limitada mas implementado de forma
diferente. Escolhidas os valores para as primeiras k
variáveis, para cada etiqueta {X1-v1, ... , Xk-vk} é permitida
uma pesquisa durante um tempo T.
Se após esse limite não fôr encontrada solução, é testada
outra etiqueta. Naturalmente, se a pesquisa falhar para um
dado valor de T, ele pode ser aumentado incrementalmente
nas próximas iterações, pelo que o espaço percorrido vai-se
igualmente alargando iterativamente.
Apesar de em todos estes algoritmos (alargamento
iterativo, discrepância limitada e duração incremental) se
repetir a pesquisa de partes do espaço de soluções, esse
efeito não aumenta a complexidade (pior caso).
70
Duração Incremental
Com efeito, e para o caso da duração incremental se as
sucessivas iterações (falhadas) tiverem um aumento a de
tempo entre iterações, isto é Tj+1 = a Tj, as sucessivas
iterações duram
T1 + T2 + ... + Tj
= T ( 1+ a + a2 + ...+ aj-1) =
= T(aj-1)/(a -1)  T aj
Assim, se uma solução fôr encontrada na j+1-ésima
iteração, o tempo desperdiçado nas iterações anteriores é
de apenas T aj. Em média, a solução encontrada nessa
iteração demoraria metade do tempo dessa iteração
(T aj) /2
pelo que o tempo “desperdiçado” é da ordem de grandeza
do tempo “útil”.
71