Restrições Indexicais
Em sistemas de programação por restrições, há que definir
uma metodologia de implementação dos resolvedores de
restrições que estão na sua base. Em particular, há que ter
em conta aspectos tais como:
• A facilidade de representação de domínios e restrições
de uso geral;
• A possibilidade de controlar a propagação de
restrições nos modos mais adequados;
• A possibilidade de combinar essas primitivas em
restrições mais complexas;
• A transparência (glass-box) da implementação,
permitindo ao utilizador acesso às “primitivas” para
implementação de restrições complexas e heurísticas
de enumeração.
1
Restrições Indexicais
Uma das formas mais adequadas de satisfazer os
requisitos enunciados é a consideração de resolvedores de
resrições baseados em restrições indexicais.
Esta é, por exemplo, a metodologia utilizada na
implementação do sistema SICStus, especificamente no
seu módulo de restrições em domínios finitos.
Estas restrições indexicais pressupõem que os domínios
das variáveis sejam ordenados. Na realidade, o SICStus
impõe que o domínio das variáveis tenha de ser um
subconjunto dos números inteiros.
As restrições indexicais permitem de uma forma sintética
resolver os problemas de representação e de propagação
de restrições nesses domínios.
2
Restrições Indexicais
Exemplo de Introdução:
Consideremos a restrição de desigualdade não estrita , ,
aplicada às variáveis A e B com os domínios iniciais de 2000
a 5000 e de 1000 a 4000, respectivamente. Na sintaxe
adoptada pelo SICStus
A in 2000..5000, B in 1000..4000, A #=< B
Este exemplo vai permitir analisar as vantagens e
desvantagens das várias hipóteses de implementação
possíveis, nomeadamente para aspectos tais como:
• A manutenção dos domínios das variáveis;
• A representação das restrições,
• A propagação adequada dessas restrições.
3
Restrições Indexicais
A in 2000..5000, B in 1000..4000, A #=< B
Quanto aos domínios, há que optar por uma representação
por intensão ou por extensão. Note-se que a propagação de
restrições só pode reduzir os domínios das variáveis.
A representação por extensão mantem explicitamente,
numa estrutura de dados, todos os valores correntes no
domínio. Como os domínios só podem ser reduzidos, essa
estrutura de dados pode ser feita através de uma
estrutura estática, tipo vector de booleanos (bit array).
Tal opção apresenta várias desvantagens. Por exemplo, a
detecção de falhas (i.e. um domínio vazio) implica, ou um
percurso do domínio da variável (no caso, 3000 posições de
memória !), ou a manutenção de contadores de bits.
4
Restrições Indexicais
A in 2000..5000, B in 1000..4000, A #=< B
Dada a importância da detecção eficiente de falhas e o
desperdício de memória (os valores presentes no domínio
podem normalmente ser descritos de uma forma sintética)
é preferível, para um resolvedor de uso geral uma
representação por intensão.
De início, podem ser explicitados os valores limites dos
domínios, única informação significativa na sua declaração.
A detecção de falhas é muito simples: o limite superior de
um domínio não pode ser inferior ao seu limite inferior.
Esta representação é particularmente eficiente enquanto
os domínios se mantiverem convexos (isto é, sem “buracos”
no seu interior).
5
Restrições Indexicais
A in 2000..5000, B in 1000..4000, A #=< B
Muitas das restrições mais habituais mantêm essa
convexidade, como é o caso da restrição de desigualdade.
A satisfação da restrição é possível se se verificar que o
limite superior da variável A não é inferior ao limite
inferior da variável B.
Por outro lado, nenhum valor no domínio da variável A pode
ser superior ao limite superior da variável B, ou seja, o
limite superior da variável A não pode ser superior ao da B
( e o limite inferior de B não pode ser inferior ao de A).
A
B
1000
A #=< B
5000
2000
A
B
1000
4000
5000
6
Restrições Indexicais
A in 2000..5000, B in 1000..4000, A #=< B
Como estas operações nos limites são muito frequentes, é
necessário fazer uma ligação à representação das restrições
e aos limites dos domínios das variáveis, de forma a garantir
a propagação adequada.
Nas restrições indexicais, esta ligação é feita através da
especificação dos limites de variáveis em função dos limites
de outras variáveis.
As restrições ficam assim representadas por expressões
que definem os limites das variáveis. Como os limites só
podem ser reduzidos, a introdução de restrições é feita por
operações de máximo/mínimo nos limites inferior/superior,
implementando a intersecção dos domínios
7
Restrições Indexicais
A in 2000..5000, B in 1000..4000, A #=< B
A introdução da restrição A #=< B altera os domínios
originais das variáveis A e B
Domínio de A
... ou seja
2000 .. 5000  inf .. max(B)
Domínio de B
... ou seja
1000 .. 4000  min(A) .. sup
A
B
1000
max(A) = min(5000, max(B)) = max(B)
min(B) = max(1000, min(A)) = min(A)
A #< B
5000
2000
A
B
1000
Internamente a restrição fica representada por
A in 2000 .. 4000  inf ..max(B)
B in 2000 .. 4000  min(A) ..sup
4000
5000
8
Restrições Indexicais
A in 2000..5000, B in 1000..4000, A #=< B
A representação da restrição da forma que é feita, isto é
A in 2000 .. 4000  inf ..max(B)
B in 2000 .. 4000  min(A) ..sup
permite a propagação adequada. Logo que o limite superior
de B diminuir, essa diminuição é propagada para a variável A,
cujo limite superior baixa do valor corrente (4000). A
comparação com o limite inferior de A (2000) permite
imediatamente verificar se A ficou com o domínio vazio!
A propagação de A para B é feita da mesma forma. A
alteração do limite superior de A não tem efeito no domínio
de B, ao contrário da modificação do limite inferior, que é
propagada.
9
Restrições Indexicais
Os efeitos da propagação podem ser vistos na introdução da
nova variável C e da restrição C in 3000..3500,B #= C
A in 2000 .. 4000  inf ..max(B)
B in 2000 .. 4000  min(A) ..sup
Após C in 3000..3500
1
C in 3000 .. 3500
Após C #=< B
2a
C in 3000 .. 3500  min(B) .. max(B)
2b
B in 2000 .. 4000  [min(C).. max(C)  min(A)..sup)]
2000 .. 4000  max(min(C),min(A)) .. min(max(C),sup)
3000 .. 3500  max(min(C),min(A)) ..
max(C)
2c
A in 2000 .. 3500  inf ..max(B)
0
Se possível são feitas simplificações. O limite superior de B
é simplificado, mas não o seu limite inferior (o maior dos
limites inferiores de A e C não é ainda determinado.
10
Restrições Indexicais
Naturalmente, o utilizador da linguagem não tem, em geral,
que lidar com as restrições a tão baixo nível.
As restrições mais habituais, nomeadamente as operações
aritméticas e os operadores relacionais, são directamente
compiladas nas restrições indexicais.
Por exemplo a restrição A
restrições indexicais
C in min(A)+min(B)
A in min(C)-max(B)
B in min(C)-max(A)
+ B #= C é compilada nas
.. max(A)+max(B)
.. max(C)-min(B)
.. max(C)-min(A)
De notar a monotonia das operações de domínio. O limite
inferior de A aumenta com o aumento do limite inferior de
C e com a diminuição do limite superior de B.
11
Restrições Indexicais
Os exemplos anteriores permitem perceber que o tipo de
coerência mantido pelas restrições indexicais nas
restrições de igualdade (#=) e desigualdade estrita ou não
estrita (#<, #=<, #> e #>=) é, geralmente, a coerência de
intervalo.
Com efeito a implementação das restrições indicada apenas
altera os limites dos domínios das variáveis.
Existe no entanto a possibilidade de impôr outros tipos de
coerência nas restrições que o justificarem, nomeadamente
a coerência de nó e a coerência de domínio.
Este tipo de coerências só tem interesse quando se
consideram domínios côncavos, isto é “com buracos”.
12
Restrições Indexicais
As concavidades podem ser introduzidas, por exemplo, por
uma restrição de diferença (#\=). Consideremos, por
exemplo, a situação
A in 1..9, B in 3..5, A #\= B
Esta restrição de diferença tem de ser representada
através da complementação dos domínios e não da sua
intersecção, ou seja (usando a sintaxe do SICStus)
A in \dom(B)
e
B in \dom(A)
Esta operação levanta no entanto problemas quanto à
monotonia, no sentido em que quanto mais se reduz o
domínio de uma variável, mais aumenta o domínio da outra !
A in 1 .. 9  \dom(B)
13
B in 3 .. 5  \dom(A)
Restrições Indexicais
A in 1..10, B in 3..5, A #\= B
A in 1 .. 9  \dom(B)
B in 3 .. 5  \dom(A)
Por esse motivo estas restrição indexicais de complemento
são “congeladas” até o domínio da variável se reduzir ao
máximo, isto é a um só elemento. A coerência de nó é assim
implementada, e as restrições de diferença não são
sujeitas a outro tipo, inútil, de coerência.
Se um domínio se reduzir a um só elemento, por exemplo se
se instanciar B a 3, o domínio de A torna-se côncavo, sendo
representado por união de domínios. Na sintaxe SICStus
?- A in 1..9, B in 3..5, A #\= B, B #=3,fd_dom(B,S).
B = 3,
S = {3},
A in(1..2)\/(4..9) ?
14
Restrições Indexicais
A coerência de arco, requer que numa restrição, sempre
que o domínio de uma variável seja reduzido, seja
verificado se as outras variáveis continuam a ser
suportadas.
A consistência de arco pode ser mantida especificando-se
nas restrições indexicais o domínio de outras variáveis. Por
exemplo, na sintaxe usada pelo SICSTus, se se pretender
que a soma mantenha a coerência de arco, essa restrição
pode ser especificada directamente pelo utilizador através
da definição da soma como um predicado FD
soma(A,B,C)+:
A in dom(C) - dom(B),
B in dom(C) - dom(A),
C in dom(A) + dom(B).
15
Restrições Indexicais
A definição de uma restrição (predicado FD) pelo utilizador
no SICStus é assim semelhante à definição de um predicado,
tendo no entanto algumas limitações, nomeadamente não há
“cláusulas” alternativas (pelo que não há retrocesso!).
Por exemplo, usando a definição anterior, obtemos o
seguinte comportamento
?- A in 1..6, A#\=3,A#\=4,A#\=5, B in 1..2, soma(A,B,C).
A in(1..2)\/{6},
B in 1..2,
C in(2..4)\/(7..8) ?
% A+B#= C  C in 1..8
?- C in 1..9, C#\=5,C#\=6,C#\=7, B in 0..2, soma(A,B,C).
C in(1..4)\/(8..9),
B in 0..2,
A in(-1..4)\/(6..9) ? % A+B#= C  A in -1..9
16
Restrições Indexicais
As expressões indexicais só podem aparecer na definição de
predicados FD. Essa limitação é devida aos diferentes
mecanismos de execução da linguagem de base(Prolog) e do
módulo FD no sistema SICStus. Com efeito, dada a definição
soma(A,B,C)+:
A in dom(C) - dom(B),
B in dom(C) - dom(A),
C in dom(A) + dom(B).
pretende-se que no módulo FD, os domínios de A/B/C sejam
reavaliados por alterações dos domínios de C,B / C,A / A,B.
Ao contrário da execução do Prolog, as primitivas que
aparecem nas expressões indexicais (dom, max, min, etc)
devem assim ser vistas como agentes reactivos a mudança.
17
Restrições Indexicais
Para além das primitivas já exemplificadas, as expressões
indexicais podem ser obtidas através de termos FD. Sendo
X uma variável de domínio, e D(X) o domínio corrente de X
os termos FD básicos são os seguintes
min(X)
mínimo de D(X)
max(X)
máximo de D(X)
card(X)
cardinalidade de D(X)
X
valor (inteiro) de X. A expressão só é
avaliada quando X é instanciado
I
um valor inteiro
inf
mais infinito
sup
menos infinito
18
Restrições Indexicais
Os termos FD, básicos ou não, podem ser combinados em
termos complexos através dos operadores aritméticos.
Sendo T1/T2 termos FD arbitrários, e representando por
D(T1)/D(T2) os seus “domínios” correntes, os seguintes
termos compostos podem ser considerados , sendo avaliados
pelas operações correspondentes na aritmética de intervalos
-T1
negação-I de D(T1)
T1+T2
soma-I de D(T1) e D(T2)
T1-T2
diferença-I de D(T1) e D(T2)
T1*T2
produto-I de D(T1) e D(T2) com D(T2) >= 0
T1/>T2
T1/<T2
D(T1) div D(T2), com arredondamento para
cima/baixo, sendo D(T2) >= 0
T1 mod T2
D(T1) mod D(T2)
19
Restrições Indexicais
Os termos FD são usados nas restrições indexicais, que
definem “domínios” (ranges) para as variáveis de domínio, a
ser “intersectados” com os domínios correntes das variáveis.
As restrições indexicais têm a forma
X in R
em que R é um range definido pela seguinte gramática. Os
ranges básicos são os seguintes (X denota uma variável de
domínio e Ti um termo FD)
dom(X)
D(X)
{T1,...,Tn}
conjunto de termos Ti
T1..T2
intervalo entre os termos Ti
Para além dos ranges básicos, outros mais complexos podem
20
ser obtidos por composição.
Restrições Indexicais
Denotando Ri um range, e D(Ri) o seu “domínio”, a
combinação de ranges é expressa pela seguinte gramática
R1/\R2
interseção de D(R1) e D(R2)
R1\/R2
\R1
R1+R2 (T2)
união de D(R1) e D(R2)
complemento de D(R1)
soma-I de D(R1) e D(R2) ou D(T2)
-R1
negação-I de D(R1)
R1-R2 e R1-T2 diferença-I de D(R1) e D(R2) ou D(T2)
R1 mod R2 (T2) mod-I de D(R1) e D(R2) ou D(T2)
R1 ? R2
se R1 \=  então D(R2) senão 
unionof(X,R1,R2) união dos D(Sk): cada Sk é obtido de R2
substituindo X pelo k-ésimo elemento de
R1.
21
Restrições Indexicais
Exemplo 1: ajuste(X,Z,K,N)
Para variáveis Z e N, com domínio 1 a N, garantir que X fique
desviada de um valor K (0=<K<N) de Z, com retorno ao início.
O interesse deste tipo de ajuste é abrir a possibilidade de
usando uma enumeração up/down numa variável “espelho”
obter uma enumeração não standard na variável “real”.
Por exemplo, no problema das 25 rainhas, para enumerar uma
rainha X a partir de 16, isto é, na ordem
11, 12, ..., 24, 25, 1, 2, ...10
basta usar N= 25 e K = 10, com as correspondências
Z=1X=11
Z=15  X=25
Z=16  X=1
Algebricamente, X = (Z+K+N-1) mod N + 1.
Z=25  X=10
22
Restrições Indexicais
Exemplo 1: ajuste(X,Z,K,N)
Usando directamente a igualdade X = (Z+K+N-1) mod N + 1, e
a correspondente Z = (X-K+N-1) mod N + 1, obtemos
Solução 1:
ajuste(X,Z,K,N)+:
X in ((dom(Z)+K+N-1) mod N)+1,
Z in ((dom(X)-K+N-1) mod N)+1.
Na realidade a operação mod é desnecessária, se X e Z
estão definidas no intervalo 1..N, usando-se em alternativa,
sendo um dos disjuntos “filtrados”.
Solução 2:
ajuste(X,Z,K,N)+:
X in (dom(Z)+ K) \/(dom(Z)+ K - N),
Z in (dom(X)- K) \/(dom(X)- K + N).
Desafio: Enumerar com valores de N/2 para as pontas.
23
Restrições Indexicais
Exemplo 2: nao_ataca(L1,C1,L2,C2)
Pretende-se que duas rainhas, colocadas nas linhas L1 e L2
(constantes) e colunas C1 e C2 (variáveis de domínio) não se
ataquem, isto é
C1 \= C2, L1+C1 \= L2+C2 e L1+C1 \= L2+C2.
Solução 1:
nao_ataca(L1,C1,L2,C2)+:
C1 in \({C2}\/{C2+L2-L1}\/{C2+L1-L2}),
C2 in \({C1}\/{C1+L1-L2}\/{C1+L2-L1}).
Nesta abordagem, como as variáveis de domínio aparecem
num contexto “negativo” (in \ {C}) a restrição é suspensa
até a variável C ser instanciada. A propagação que se obtem
é pois a que garante a manutenção da consistência de nó. Em
alternativa, pode manter-se a consistência de arco.
24
Restrições Indexicais
Solução 2:
nao_ataca(L1,C1,L2,C2)+:
C1 in unionof(Y,dom(C2),\({Y}\/{Y+L2-L1}\/{Y+L1-L2})),
C2 in unionof(X,dom(C1),\({X}\/{X+L1-L2}\/{X+L2-L1})).
Nesta abordagem, obtem-se a consistência de arco, por união
de todos os valores de uma variável na outra.
Por exemplo, na primeira restrição indexical, o domínio de C1
é obtido por união de todos os valores compatíveis com os
valores actuais de C2.
Assim estes valores, referidos como Y, já aparecem
instanciados em expressões idênticas às anteriores. O
tratamento é naturalmente simétrico na outra restrição
indexical.
25
Restrições Indexicais
Solução 3:
nao_ataca(L1,C1,L2,C2)+:
C1 in (4..card(C2)) ? (inf..sup) \/
unionof(Y,dom(C2),\({Y} \/ {Y+L2-L1} \/ {Y+L1-L2})),
C2 in (4..card(C1)) ? (inf..sup) \/
unionof(X,dom(C1),\({X} \/ {X+L1-L2} \/ {X+L2-L1})).
A terceira abordagem é semelhante à anterior mas só
executa a propagação quando o domínio da variável tem
cardinalidade menor que 4.
Com efeito a restrição indexical C1 é avalidada como a união
(V) da restrição unionof(Y,... )com
•  se a cardinalidade de C2 for =< 4 (i.e. 4..card(C2)= )
• inf..sup no caso contrário
26
Restrições Disjuntivas e Indexicais
Restrições Disjuntivas e Retrocesso
Em geral um problema de restrições inclui uma fase de
pesquisa com retrocesso, nomeadamente quando as
restrições e a sua propagação não são suficientes para
eliminar valores redundantes do valor dos domínios.
Esse retrocesso ocorre na fase de enumeração, quando
todas as restrições já estão impostas.
No entanto quando as restrições são definidas por intensão,
a forma mais “natural” de as definir é através da disjunção
de várias alternativas.
Neste caso há que identificar a melhor forma de impôr
essas disjunções.
27
Restrições Disjuntivas e Indexicais
Exemplo: Dadas duas tarefas T1 e T2, com início nos tempos
S1 e S2 e durações D1 e D2, garantir que elas não se
sobrepõem.
Uma modelação natural desta restrição é a implementação
da disjunção equivalente
• T1 termina antes de T2 começar; ou
• T2 termina antes da T1 começar
A definição desta restrição, nomeadamente a disjunção
destas alternativas, pode usar o mecanismo de retrocesso do
Prolog
disjuntas(S1, S2, D1, D2) :- S1 + D1 #=< S2.
disjuntas(S1, S2, D1, D2) :- S2 + D2 #=< S2.
28
Restrições Disjuntivas e Indexicais
Problema ( Vars):Declaração de Variáveis e Domínios,
Lançamento das Restrições,
Enumeração das Variáveis.
Esta formulação levanta o problema da interacção dos
retrocessos feitos durante
1. a definição e lançamento das restrições
2. a enumeração (exploração do espaço de pesquisa).
Com efeito, havendo k tarefas de que se pretende garantir a
não sobreposição, há que definir k*(k-1)/2 restrições de não
sobreposição entre pares das k tarefas.
Para 50 tarefas, K = 50, temos 50*49/2 = 1225 restrições.
29
Restrições Disjuntivas e Indexicais
Problema ( Vars):Declaração de Variáveis e Domínios,
Lançamento das Restrições,
Enumeração das Variáveis.
A questão que se coloca é que, em vez de se resolver
• 1 só problema com 2K variáveis
uma formulação como a anterior vai conduzir à resolução de
• 2k*(k-1)/2 problemas com as mesmas 2K variáveis.
Cada problema corresponde à escolha feita na fase de
lançamento das restrições de umas das alternativas para a
não sobreposição. Com os valores anteriores o número de
problemas a resolver é astronómico 21225, mesmo que a
maioria destes problemas seja trivialmente “eliminado”.
30
Reificação de Restrições
Uma melhor formulação corresponde a garantir a formulação
de todas as alternativas das restrições numa só definição,
em vez do número exponencial de definições.
Esta formulação pode ser obtida através da reificação de
restrições.
A ideia de base da reificação de restrições é fazer
corresponder a cada restrição o seu valor booleano 0/1, e
tornar acessível ao nível do programa esse valor de verdade.
Por exemplo se associarmos as restrições R1 e R2 os
booleanos B1 e B2, a disjunção destas restrições pode
impôr-se pela simples imposição da restrição
B1 + B2 #>= 1.
31
Reificação de Restrições
Uma vez definido o mecanismo de reificação de restrições
pode-se alargar o seu âmbito para outras combinações de
restrições, nomeadamente as que envolvem contagens.
Por exemplo se pretendermos que de 20 retrições R1,..., R20
pelo menos 10 sejam satisfeitas, em vez de se definirem
• as 20 restrições, R1 a R20
• C1020 = 184 756 conjuntos alternativos das 20 restrições
definem-se simplesmente
• as 20 restrições, R1 a R20
• a sua correspondência com variáveis booleanas B1 a B20
• a restrição B1 +B2 + B20 #>= 10
32
Reificação de Restrições
Para que a correspondência entre uma variável B e uma
restrição R seja explorada eficientemente e propagada, há
que definir mecanismos de Ask & Tell, que permitam
Mecanismos Tell
• Tell(R) - Impôr a satisfação da restrição
• Tell(~R) - Impôr a insatisfação da restrição
Mecanismos Ask
• Ask(R) - Verificar a satisfação da restrição
• Ask(~R) - Verificar a insatisfação da restrição
Com efeito se se pretender satisfazer uma e uma só das
restrições R1 e R2, várias situações podem ocorrer que
requerem todos os mecanismos acima.
33
Reificação de Restrições
• Ask(R1) / Ask(R2) sucede
Uma vez detectada uma situação que garanta a satisfação de
R1/R2, deve ser imposta a restrição de que R2/R1 não seja
satisfeita - tell(~R2)/tell(~R1).
• Ask(~R1) / Ask(~R2) sucede
Uma vez detectada uma situação que garante a não
satisfação de R1/R2, deve ser imposta a restrição de que
R2/R1 seja satisfeita (tell(R2)/tell(R1).
Desta forma, há que definir como é que estes 4 mecanismos
de Ask&Tell podem ser disponibilizados ao utilizador, quer
para restrições pré-definidas de uso geral, quer para
restrições definidas pelo utilizador.
34
Reificação de Restrições
No SICStus a correspondência entre restrições e variáveis
booleanas é feita através do operador pré-definido
R #<=> B.
sendo B é a variável booleana 0/1 e R a restrição.
Várias restrições pré-definidas são reificáveis. Tal é o caso
das restrições lineares (comparação de expressões lineares).
Desta forma a não sobreposição de tarefas atrás descrita
pode ser feitas através das restrições
disjuntas(S1, S2, D1, D2) :S1 + D1 #=< S2 #<=> B1, % T1 antes de T2
S1 + D1 #=< S2 #<=> B2, % T2 antes de T1
B1 + B2 #>= 1.
35
Reificação de Restrições
Quando se definem restrições específicas, há que definir
para elas os mecanismos de Ask e Tell adequados.
Por exemplo, consideremos o exemplo da restrição de
diferença ‘\\=’ entre duas variáveis de domínio.
Os mecanismos de Ask são impostos por restrições
indexicais de propagação (propagating indexicals), que
incluem as definições positivas (‘+:’), já conhecidas
’x\\=y’(X,Y) +:
X in \{Y},
Y in \{X}.
e as definições negativas (‘-:’)
’x\\=y’(X,Y) -:
X in dom(Y),
Y in dom(X.
36
Reificação de Restrições
Os mecanismos de Tell são impostos por restrições
indexicais de verificação (checking indexicals), quer
positivas (‘+?’)
’x\\=y’(X,Y)+?
X in \dom(Y).
quer negativas (‘-:’)
’x\\=y’(X,Y) +:
X in {Y}.
O comportamento pretendido das restrições indexicais de
propagação e de verificação impõe regras de execução e
limitações às expressões utilizadas nas definições.
Algumas dessas limitações são apresentadas de seguida.
37
Reificação de Restrições
Restrições Indexicais de Propagação (“Disparo”)
Uma restrição indexical de propagação X in R é escalonada
para execução nas seguintes condições
• É avaliada inicialmente logo que se torne monótona
• É reavalidada sempre que, para outra variável Y que
aparece em R
• o domínio de Y fôr alterado e Y aparece em R na
forma card(Y) ou dom(Y);
• O limite superior/inferior do domínio de Y fôr
alterado e Y aparece como max(Y)/min(Y) em R.
38
Reificação de Restrições
Restrições Indexicais de Propagação (Resultado)
Dada uma variável X referida numa restrição indexical, e
denominando por M(X) o valor da restrição indexical no
estado corrente da memória, e I(X) o intervalo entre os
limites inferior e superior do domínio de X, então
• Se M(X) é disjunto de I(X), existe contradição.
• Se I(X) está contido em M(X), então não há ainda valores
no domínio corrente de X incompatíveis com a restrição
indexical, cuja execução suspensa, até a situação se
tornar “ground” .
• Caso contrário, a restrição indexical é acrescentada às
restrições sobre X, cujo domínio vai sofrer cortes.
39
Reificação de Restrições
Exemplo: Restrições Indexicais de Propagação
A restrição X in \{Y} na propagação positiva é suspensa
até se tornar monótona, isto é até Y estar instanciada.
Neste caso a restrição ou é contraditória, ou é propagada,
sendo retirado o valor de Y do domínio de X.
A restrição X in dom(Y), na propagação negativa, é
inerentemente monótona. Enquanto Y tiver vários valores no
seu domínio, X vai sendo cortado. Se os domínios de X e Y
se tornarem disjuntos, então a negação da restrição de
diferença falha! Quando o domínio de Y ficar ground então
o de X tambem fica e a restrição (isto é, a negação de que X
e Y são diferentes) sucede.
40
Reificação de Restrições
Restrições Indexicais de Verificação (“Disparo”)
Uma restrição indexical de propagação X in R é escalonada
para execução nas seguintes condições
• É avaliada inicialmente logo que se torne anti-monótona
• É reavalidada sempre que
• O domínio de X tenha sido cortado ou atribuído um
valor a X;
• o domínio de uma variável Y, que apareça em R na
forma card(Y) ou dom(Y), seja cortado;
• O limite superior/inferior do domínio de Y fôr
alterado e Y aparece como max(Y)/min(Y) em R.
41
Reificação de Restrições
Restrições Indexicais de Verificação (Execução)
Dada uma variável X referida numa restrição indexical, e
denominando por M(X) o valor da restrição indexical no
estado corrente da memória, e I(X) o intervalo entre os
limites inferior e superior do domínio de X, então
• Se I(X) está contido em M(X), então nenhum valor de X
pode tornar a restrição falsa, pois M(X) só pode crescer
(anti-monotonia). Assim a restrição é verificada
positivamente (entailed)
• Se I(X) é disjunto de M(X) e M(X) está “definido”
(ground) então a .restrição já não pode ser satisfeita e é
verificada negativamente (disentailed).
• Nos outros casos a restrição de verificação é suspensa.
42
Reificação de Restrições
Exemplo: Restrições Indexicais de Verificação
A restrição X in \dom(Y) na verificação positiva é
inerentemente anti-monótona (os valores de \dom(Y)só
podem aumentar pois dom(Y) só pode ser reduzido). Assim a
verificação positiva sucede logo que Y ficar grounded e X
não tiver elementos em comum com o domínio de Y.
A restrição X in {Y}, só se torna anti-monótona quando Y
ficar instanciada a um qualquer valor. Enquanto X tiver esse
valor no domínio a restrição suspende. Se X só tiver esse
valor no domínio a verificação negativa sucede, ou seja o
único valor de X é o mesmo do único valor de Y, caso em que
a restrição de diferença falha.
43
Reificação de Restrições
Exemplo 2: Restrição de Desigualdade Estrita
Como se poderá verificar facilmente as seguintes definições
de indexicais de propagação e verificação são os adequados
para reificar uma restrição de desigualdade estrita na
forma
’x\\<y’(X,Y) #<=> B
’x\\<y’(X,Y)+:
X in inf .. max(Y)-1,
Y in min(X)+1 .. sup.
’x\\<y’(X,Y)+?
X in inf .. min(Y)-1,
Y in max(X)+1 .. sup.
’x\\<y’(X,Y)-:
X in min(Y)+1 .. sup,
Y in inf .. aax(X)+1.
’x\\<y’(X,Y)-?
X in max(Y).. sup,
Y in inf .. min(X).
44
Meta-Restrição de Cardinalidade
Vários tipos de problemas, nomeadamente de escalonamento
de tarefas com várias precedências
requerem a
especificação de que de entre uma lista de restrições
Lr = [R1, R2, ... , Rn]
o número de restrições a satisfazer deve estar entre um
limite inferior I e superior S, inclusivé. Sintaticamente, a
meta-restrição pode ser especificada como
#(I,S, [R1, R2, ... , Rn])
Este tipo de restrições são usuais em problemas de gestão
de recursos, em que se pretendem alocar pessoas/recursos
de uma forma “flexível”.
45
Meta-Restrição de Cardinalidade
Exemplo (Escalas de Pessoal): De entre as 7 enfermeiras de
um Serviço Hospitalar, pelo menos 4 devem estar de serviço
no 1º turno.
A modelação desta restrição pode ser feita considerando-se
uma variável booleana Xij para modelar o turno j feito pela
enfermeira i. A modelação pode usar, para cada turno, a
meta-restrição de cardinalidade
#(4,7, [X1i=1, X2i=1, ... , X7i=1, ])
Noutra alternativa de modelação, consideram-se 7 variáveis
Xij para cada turno i, cujo domínio são as enfermeiras,
reservando-se o valor 0 para o caso de a variável não ser
instanciada a nenhuma enfermeira, o que conduz à restrição
#(4,7, [Xi10, Xi20, ... , Xi70, ])
46
Meta-Restrição de Cardinalidade
A semântica operacional desta meta-restrição pode ser
especificada por um conjunto de regras de reescrita, que
utilizam os mecanismos de Ask & Tell apresentados. As
primeiras duas regras reescrevem a restrição inicial numa
forma simplificada.
Regra 1: Se uma das restrições fôr satisfeita então o
número de restrições a satisfazer é reduzido até 1.
#(I,S, [R1, R2, ... , Ri, ... , Rn]), ask(Ri)
#(I-1,S-1, [R1, R2,...,Ri-1,Ri+1,..., Rn])
Regra 2: Se uma das restrições fôr satisfeita então o
número de restrições a satisfazer é reduzido até 1.
#(I,S, [R1, R2, ... , Ri, ... , Rn]), ask(~Ri)
#(I,S, [R1, R2,...,Ri-1,Ri+1,..., Rn])
47
Meta-Restrição de Cardinalidade
As duas regras seguintes referem-se a situações em que a
satisfação ou não das restrições restantes tem de se
imposta.
Regra 3: Se o número de restrições a satisfazer é igual ao
limite superior, todas as restrições têm de ser satisfeitas.
#(I,S, [R1, R2, ... , Ri, ... , Rn]), S = n
tell(R1), tell(R2), ..., tell(Rn)
Regra 4: Se o limite superior de restrições a satisfazer é
igual a 0, nenhuma das restrições pode ser satisfeitas.
#(I,S, [R1, R2, ... , Ri, ... , Rn]), I = 0
tell(~R1), tell(~R2), ..., tell(~Rn)
48
Meta-Restrição de Cardinalidade
Finalmente, a meta-restrição pode ser trivialmente verificada
por redução dos limites superiores e inferiores e do número
de restrições a satisfazer por via das regras 1 e 2.
Regra 5: Se já não há restrições a satisfazer e o seu número
não é superior ao limite superior, a meta-restrição sucede.
#(I,S, [R1, R2, ... , Rn]), I = 0, S >= n
true
Regra 6: Se o número de restrições a satisfazer é inferior
ao limite superior, então a meta-restrição falha.
#(I,S, [R1, R2, ... , Rn]), S > n
false
49
Meta-Restrição de Cardinalidade
Embora se possa implementar esta meta-restrição a partir da
especificação, os mecanismos de Ask&Tell do SICStus
baseados na reificação das restrições permitem-no fazer de
forma mais eficiente por meio da contagem das restrições
satisfeitas (por soma das correspondentes variáveis
booleanas) .
cardinal(I,S,L):sats(L,C),
I #=< C,
C #=< S.
sats([],0).
sats([R1|Resto],C):H #<=> B,
C #= D+B,
sats(Resto,D).
50
Restrições Condicionais
A meta-restrição de cardinalidade pode ser aplicada
genericamente a combinações de restrições que envolvam
contagem de restrições. Existem outras situações bem
modeladas através das variáveis booleanas associadas às
restrições reificadas.
Entre outras situações, refiram-se as restrições condicionais,
que só fazem sentido caso outras se verifiquem.
Por exemplo, no contexto do escalonamento de tarefas, pode
acontecer que apenas umas das tarefas T1 e T2 se deva
realizar antes do limite Z. Se fôr a tarefa T2, então a tarefa
T3 deverá começar com um intervalo de I após o fim da
tarefa T2.
51
Restrições Condicionais
A garantia de que uma só das tarefas T1 e T2 termina antes
de Z pode ser especificada pela meta-restrição de
cardinalidade
Card(1,1, [S1+D1 #<= Z, S1+D1 #<= Z])
No entanto a restrição condicional entre T2 e T3 não envolve
contagens, pois o número de restrições satisfeitas nas
tarefas T2 e T3 pode ser 0, 1 ou 2).
Estas condições podem ser modeladas através das variáveis
booleanas associadas às restrições reificadas. Assim, e
considerando as reificações
S1+D1 #<= Z #<=> B1
S2+D2 #<= Z #<=> B2
S3 #> S2+D2+I #<=> S
52
Restrições Condicionais
Assim, e considerando as reificações anteriores, podemos
exprimir quer a restrição de cardinalidade
B1 + B2 #= 1
quer a restrição de condicionalidade, através de
B3 #>= B2
Desta forma logo que se verificar que a restrição R2 não é
satisfeita (B2 = 0) a restrição acima é trivialmente satisfeita
e a restrição R3 não é imposta.
No caso de a restrição R2 fôr satisfeita, então B3 fica
restringido ao valor 1 e a restrição R3 é imposta.
53
Outras Combinações de Restrições
Em vez de trabalhar com os valores booleanos associados às
restrições reificadas, o SICStus permite a sua utilização
directa em restrições proposicionais.
Por exemplo, as restrição tarefas T1, T2 e T3 podiam ser
direcatmente especificadas com as restrições proposicionais
seguintes
Cardinalidade (apenas 1 das tarefas T1 e T2)
S1+D1 #<= Z
#\
S2+D2 #<= Z
Condição ( se T2 então T3)
S3 #> S2+D2+I
#<=
S2+D2 #<= Z
54
Outras Combinações de Restrições
As restrições proposicionais permitidas são as seguintes
#\ R1
B1 #= 0
R1 #/\ R2
B1+B2 #= 2
R1 #\ R2
B1+B2 #= 1
R1 #\/ R2
B1+B2 #>=1
R1 #=> R2
R2 #<= R1
B2 #>= B1
R1 #<=>R2
restrições R1 e R2 são
R1 deve ser falsa
R1 e R2 devem ser ambas
verdadeiras
Uma e uma só de das R1 e R2
deve ser verdadeira
Pelo menos uma de R1 e R2
deve ser verdadeira
Se R1 fôr verdadeira, então
R2 também o deve ser.
B1 #= B2
As
ambas verdadeiras ou falsas.
55
Disjunção Construtiva
As combinações de restrições através das restrições
proposicionais seguem uma filosofia de menor compromisso
Não se comprometer com uma restrição até que,
durante a enumeração os domínios das variáveis
sejam reduzidos de tal forma que se possa
garantir a imposição da restrição.
No entanto esta estratégia ao “suspender” a imposição de
restrições pode não auxiliar a tarefa de enumeração das
variáveis, já que não lhes limita os domínios.
Em certas circunstâncias, podem ser retiradas ilações sobre
os domínios das variáveis envolvidas em restrições, mesmo
sem se saber com exactidão quais. Tal é o caso da
disjunção construtiva.
56
Disjunção Construtiva
Exemplo:
Consideremos as duas restrições R1 e R2 sobre a variável X,
com domínio 1 a 100, das quais queremos que uma delas pelo
menos se verifique (disjunção)
R1 : X #>= 50
R2 : X #=< 20
As restrições proposicionais anteriores esperariam até o
domínio de X se reduzir abaixo de 50 ou acima de 20 para
desistir da restrição que assim se tornaria impossível, e
comprometer-se com a outra.
Por exemplo, logo que X se reduzisse para 3..40, R2 poderia
ser imposta, reduzindo-se o domínio para 3..20.
No entanto, o intervalo 21..49 poderia ter sido retirado,
57
desde o início, do domínio de X.
Disjunção Construtiva
Tal antecipação da redução dos domínios é o objectivo da
disjunção construtiva. A sua implementação pode ser feita
através da especificação dos indexicais adequados.
disjunção1(X, S1, S2) :X in S2 .. Sup \/ inf .. S1.
?- X in 1..100, disjunção1(X,20,50).
X in(1..20)\/(50..100)
e comparada com a implementação de menor compromisso
disjunção2(X, S1, S2) +:
X #>= S2 #\/ X #=< S1.
?- X in 1..100, disjunção2(X,20,50).
X in 1..100
58