CLP – (Constraint Logic Programs)
Programação Lógica com Restrições

Ruben Carlo Benante







Doutorando em Ciência da
Computação pelo
CIn – UFPE, Recife-PE
Mestre em Filosofia pela UNESP,
Marília-SP
Bacharel em Ciência da
Computação pela UNESP, S.J.Rio
Preto-SP
[email protected]
Disciplina de MCI
Prof. Jacques Robin
Baseado nas transparências
disponibilizadas na internet
por Marriott & Stuckey
Capítulo 4: Programação
Lógica com Restrições
Restrições Definidas pelo Usuário
 Programando com Regras
 Avaliação
 Árvores de Derivação e Falhas
Finitas
 Avaliação de Objetivos
 Árvores de Derivação Simplificadas
 O esquema CLP

Capítulo 5: Modelos Simples
Modelando
 Modelando Escolhas
 Otimização

Capítulo 7: Controle de
Busca
Estimando a eficiência de um
programa CLP
 Ordenando as Regras
 Ordenando os Literais
 Adicionando Restrições Redundantes
 Minimização

Capítulo 8: Modelos com
Domínios Finitos
Domínios e Rótulos
 Restrições Complexas
 Rotulando (Labelling)
 Modelando Problemas Diferentes

Capítulo 4: Restrições
Definidas pelo Usuário (RDU)

Muitos exemplos de modelagem podem
ser particionados em duas partes:




Uma descrição geral do objeto ou processo
Uma informação específica sobre uma
situação real
O programador deve ser capaz de definir
suas próprias restrições específicas ao
problema
As Regras permitem isso
Regras
+
V
R1
Uma RDU para definir o
modelo de circuito
elétrico:
R2
V
I1
I
parallel_resistors(V,I,R1,R2)
-3_
--
I2
-
E uma regra definindo-a:
parallel_resistors(V,I,R1,R2) :V = I1 * R1, V = I2 * R2, I1 + I2 = I.
Usando Regras
parallel_resistors(V,I,R1,R2) :V = I1 * R1, V = I2 * R2, I1 + I2 = I.
Comportamento com resistores de 10 e 5 Ohms
parallel_resistors(V , I , R1, R2)  R1  10  R2  5
Comportamento com bateria de 10V, com resistores iguais
parallel_resistors(10, I , R, R)
Isso representa a restrição: (substituição macro)
10  I 1  R  10  I 2  R  I 1  I 2  I
Restrições Definidas pelo
Usuário (RDU)





RDU: p(t1,...,tn) onde p é um predicado
n-ário e t1,...,tn são expressões
literal: uma restrição primária ou RDU
objetivo (goal): uma seqüência de
literais L1,...,Lm
regra: A :- B onde A é RDU e B é um
objetivo
programa: uma seqüência de regras
Renomeação (Renamings)





Uma renomeação r é um mapa bijetivo
de variáveis em variáveis
Um objeto sintático é uma restrição,
um RDU, um objetivo ou uma regra
Aplicar uma renomeação em um objeto
sintático nos dá um objeto com cada
variável x substituída por r(x)
variante o’ de um objeto o tem sua
renomeação como r(o’)=o
Não é substituição de macros
Reescrita de RDU

objetivo G da forma (ou vazio m=0 [])





L1, ..., Li-1, Li, Li+1, ..., Lm
Li é da forma p(t1,...,tn)
R é da forma p(s1,...,sn) :- B
r é a renomeação das variáveis em r(R) e
não em G
A reescrita de G com Li por R usando a
renomeação r é

L1,...,Li1,t1=r(s1),...,tn=r(sn),r(B),Li+1,...,Lm
Programando com Regras
1
if N  0

N! 
 N  ( N  1)! if N  1
Considere a função fatorial. Como poderemos
escrever regras para o predicado fac(N,F) onde
(F = N!) ?
(R1) fac(0,1).
(R2) fac(N,N*F) :- N >= 1, fac(N-1, F).
Note que a definição é recursiva (em termos dela
mesma) e imita a definição matemática
Programando com
Regras
(R1) fac(0,1).
(R2) fac(N,N*F) :- N >= 1, fac(N-1, F).
Reescrevendo o objetivo fac(2,X) (i.e. o que é 2!)
fac
22,,,,XX
fac
fac
XX))))
fac(((2
R
RR2

22
 N
NN,,,X
XX 
 N
NN 
F
FF,,,N
NN 
fac(((N
N
222
1
11,,, fac
fac
N
111,,,F
FF)))
RR22
22 NN,,XX  NN FF,,NN 11,,NN 11 NN'',,FF  NN''FF'',,N
N''11,, fac
fac((N
N''11,,FF''))
 R1
2  N , X  N  F , N  1, N  1  N ' , F  N ' F ' , N '  1, N '1  0, F '  1
Simplificado na variável X, a resposta é X = 2
Avaliação (Evaluation)



Em cada passo da reescrita, deveremos
checar se a conjunção de restrições
primitivas pode ser satisfeita
A derivação faz isso
Em cada passo, os literais…


Restrição primitiva: são adicionados ao lado
direito (das restrições)
RDU: são reescritos
Avaliação


estado: <G1| C1> onde G1 é um
objetivo e C1 é uma restrição
Passo de derivação: G1 é L1, L2, ...,
Lm


L1 é uma restrição primitiva, C2 is C1 /\ L1
• Se solv(C /\ L1) = false então G2 = []
• Senão G2 = L2, ..., Lm
L1 é uma RDU, C2 é C1 e G2 é a reescrita de
G1 com L1 usando alguma regra e a
renomeação
Avaliação

derivação de <G0 | C0>:
G0| C0  G1| C1  G2| C2 
 Onde cada <Gi | Ci> até <Gi+1 |
Ci+1> é um passo de derivação

derivação de G é a derivação do
estado <G | true>
Derivação de fac(1,Y)
fac
true
)|)|true
true
fac((((1111,,,,YY
true
fac
YY)|)|
fac

R
R
RR2222

R
2 fac( N  1, F )| true
11
 N
N
N
F
N
fac
N
YY
 N
N
F
FF,,,,N
N
1111,,,,fac
N
N,,,,YY
N
N 
fac(((N
N 11,,FF)|)|true
true
11

1  N ,Y  N  F , N 

1, fac( N  1, F )| true
N
F
N
fac
N

111,,,F
FF)|
)|)|111
 N
N
YY
 N
N
F
F
N
1111,,,,fac
fac
N
N
F,,,,N
N 
fac((((N
N
N
YY


N
 1
Y
YY 
 N
N
F
FF
 N
N
N
11,,, fac
fac
N
111,,,F
FF)|
)|)|111
N
fac(((N
N
N
N


fac(( N
N
F
F
N
N
 11
Y
N
fac
N
1
1,, F
F )|
)|11 
N
N
Y

R
R11
N
|| 
N
F
F
N
N
 11
N
1
1
0
0,, F
F
 11
11
N
N
Y
Y
N


F
|| 
F
 11
11
N
N
Y
Y
N
N
F
F
N
N
 11 
N
N
 11 
 00

[]|1  N  Y  N  F  N  1  N  1  0  F  1
Resposta simplificada em Y é Y = 1
Derivações






Para a derivação iniciando em <G0 | C0>
Estado de sucesso: <[] | C> onde
solv(C) != false
Derivação de sucesso: o último estado
é de sucesso
resposta: simpl(C, vars(<G0 | C0>))
Estado de falha: <[] | C> onde solv(C)
= false
Derivação falha: o último estado é de
falha
Árvores de derivação

Árvore de derivação para o objetivo G





Raíz é < G | true >
Os filhos de cada estado são estados
alcançáveis em um passo de derivação
Codifica todas as possíveis derivações
Quando o literal mais à esquerda é uma
restrição primitiva, somente há um filho
Caso contrário, os filhos estão ordenados
conforme a ordem das regras
Exemplo de Árvores de
Derivação
fac(1, Y )| true
 R1
 R2
1  0, Y  1| true
1  N , Y  N  F , N  1, fac( N  1, F )| true


[]|1  0
Y  N  F , N  1, fac( N  1, F )| C1  1  N

Derivação falhou
N  1, fac( N  1, F )| C 2  C1  Y  N  F
 R1
 R2
N  1  0, F  1| C 3
N  1  N ' , F  N ' F ' , N '  1, fac( N '1, F ' )| C 3


F  1| C 4  C 3  N  1  0
F  N ' F ' , N '  1, fac( N '1, F ' )| C 6  C 3  N  1  N '


[]| C5  C 4  F  1
N '  1, fac( N '1, F ' )| C 7  C 6  F  N ' F '

resposta: Y = 1

fac( N  1, F )| C 3  C 2  N  1
[]| C8  C 7  N '  1
Derivação
falhou
Árvore de Derivação
O exemplo anterior mostrou três
derivações, 2 falharam e uma foi
bem sucedida
 Falha finita: Se a árvore de
derivação é finita e todas as
derivações falham
 Árvore de Derivação Infinita:
algumas derivações são infinitas

Exemplo de árvore de
derivação infinita
(S1) stupid(X) :- stupid(X).
(S2) stupid(1).
stupid ( X )| true
 S1
 S2
X  X ' , stupid ( X ' )| true

X  1| true

stupid ( X ' )| X  X '
 S1
[]| X  1
 S2
X '  X ' ' , stupid ( X ' ' )| X  X '
X '  1| X  X '


stupid ( X ' ' )| X  X ' X '  X ' '
[]| X  X ' X '  1
 S1
 S2
Derivação Infinita
Resposta: X=1
Resposta: X=1
Avaliação de Objetivos





A Avaliação de um objetivo realiza uma
busca em profundidade, e na direção da
esquerda para a direita
Quando encontra um estado de sucesso,
o sistema retorna a resposta
O usuário pode perguntar por outras
respostas, o que faz a busca continuar
A execução pára quando o usuário não
pede mais respostas ou a árvore inteira é
explorada
A execução entra em laço infinito se a
árvore é infinita e não apresenta resposta
Árvores de Derivação
Simplificadas
As árvores de derivação são muito
grandes
 Uma forma simplificada tem a
informação considerada mais útil

Restrições na forma simplificada
(variáveis na forma do objetivo inicial,
e como parte dos estados do objetivo)
 Remoção de estados sem interesse

Estados Simplificados

Estado simplificado: <G0 | C0> na
derivação de G




substitua C0 por C1=simpl(C0, vars(G,G0))
se x=t em C1 substitua x por t em G0 levando
à G1
substitua C1 por C2=simpl(C1, vars(G,G1))
Exemplo
fac( N '1, F ')|1  N  Y  N  F  N  1  N  1  N ' F  F '
vars  {Y , N ', F '}
fac( N '1, F ')| N '  0  Y  F '
replace N ' by 0 and simplify again
fac( 1, F ')|Y  F '
Derivação Simplificada



Um estado é critico se ele é o primeiro
ou o último estado de uma derivação, ou
se o primeiro literal é uma RDU
Uma derivação simplificada para o
objetivo G contém todos os estados
críticos na forma simplificada
Similarmente para uma árvore de
derivação simplificada
Exemplo de Árvore
Simplificada
fac(1, Y )| true
 R1
 R2
[]| false
 R1
[]|Y  1
fac(0, F )|Y  F
 R2
[]| false
Nota: estados de falha são <[] | false> e estados de
sucesso contém as respostas
O Esquema CLP


O esquema define uma família de
linguagens de programação
Uma linguagem CLP(X) é definida por





Domínio de restrição X
Resolvedor para o domínio de restrição X
Simplificador para o domínio de restrição X
Nos exemplos usamos CLP(Real)
Outro exemplo seria o CLP(Tree)
CLP(R)
Os elementos são árvores contendo
constantes reais
 Restrições são { , }
para árvores
{, , , , }
e
para aritimética

Capítulo 5: Modelando
Escolha as variáveis que serão
usadas para representar os
parâmetros do problema (isto pode
ser trivial ou difícil)
 Modele as relações idealizadas entre
estas variáveis usando as restrições
primitivas disponíveis no domínio

Exemplo de Modelagem
Uma viajante deseja atravessar o rio
infestado de tubarões tão rápido
quanto possível. A rota mais rápida é
atravessar o rio nadando em linha
reta, deixando que a correnteza faça a
parte dela livremente. Ela deseja saber
onde (P) ela vai parar após essa
tarefa?
Largura do rio: W
Velocidade do rio: S
Posição da nadadora: P
Velocidade da nadadora: R
R
P
S
W
Exemplo de Modelagem
Raciocínio: enquanto a nadadora atravessa o rio na
sua largura, gastando um tempo T, ela segue junto
com a correnteza para o rio abaixo uma distância P
dada pela velocidade do rio, com o mesmo tempo T.
Daí o modelo:
river(W, S, R, P) :- T = W/R, P = S*T.
Supondo que ela nade a R=1.5m/s, a velocidade do
rio é de S=1m/s e seu comprimento é de W=24m.
river(24, 1, 1.5, P).
A única resposta é P = 16
Largura do rio: W
Velocidade do rio: S
Posição da nadadora: P
Velocidade da nadadora: R
Exemplo de Modelagem
(cont.)
Se ela nada numa velocidade entre 1 e 1.3 m/s e
não pode se afastar mais que 20m do ponto de
origem, será que ela conseguirá?
1 <= R, R <= 1.3, P <= 20, river(24,1,R,P).
Esta é a flexibilidade do modelo baseado em restrições!
Escolhas mais
complicadas




Uma opção de “call” dá ao seu portador o direito
de comprar 100 ações a um preço de exercício E fixo
Uma opção de “put” dá ao seu portador o direito
de vender 100 ações a um preço de exercício E fixo
O pagamento (lucro ou prejuízo) de uma opção é
determinado por seu custo C e pelo preço corrente
da ação S
e.g. custo do call C=$200, Exercício E=$300

Preço do mercado = $2, não utiliza o call:
• pagamento = -$200

Preço do mercado = $9, utiliza o call:
• pagamento = $400
Opções de Mercado
call C=200, E = 300
200
100
0
-100
-200
0 1 2 3
4 5 6
7
call, selling
call, buying
1
2
butterfly
3
4
5
200
100
0
-100
-200
0 1 2
3 4 5 6
7
100
50
0
-50
-100
0
put C=100, E = 300
6
put, selling
put, buying
Operação Borboleta: Compre um
“call” por C=100 com E=500 e
outro por C=400 com E=100.
Venda dois “calls” por C=200,
com E=300
Opções de Mercado
PG= S – E – C (para compra de “call”)
PG = E + C – S (para venda de “call”)
(C=100,E=500, compra)
PG1 = 100S – 600 p/ S>5
PG1 = – 100 p/ S<=5
(C=400,E=100, compra)
PG2 = 100S – 500 p/ S>1
PG2 = – 100 p/ S<=100
(C=200,E=300, venda)
PG3 = – S100 + 500 p/ S>3
PG3 = 200 p/ S<=3
100
50
0
-50
-100
0
1
2
butterfly
3
4
5
6
Operação Borboleta: Compre um
“call” por C=100 com E=500 e outro
por C=400 com E=100. Venda dois
“calls” por C=200, com E=300
Aplicadas as restrições temos:
PG = PG1 + PG2 + 2PG3
PG = – 100 p/ s>5
PG = – 100 p/ s<1
PG = 100S – 200 P/ 1<S<3
PG = –100S + 400 p/ 3<S<5
Modelando Funções
C
if 0  S  E / 100

call _ payoff ( S , C, E )  
if S  E / 100
100S  E  C
Modelar uma função com n argumentos como um
predicado com n+1 argumentos. Os testes são
restrições, e o resultado é uma equação.
buy_call_payoff(S,C,E,P) :0 <= S, S <= E/100, P = -C.
buy_call_payoff(S,C,E,P) :S >= E/100, P = 100*S - E - C.
Modelando Opções
Acrescente um argumento extra
B=1 (compra), B = -1 (venda)
call_option(B,S,C,E,P) :-
0 <= S, S <= E/100, P = -C * B.
call_option(B,S,C,E,P) :S >= E/100, P = (100*S - E - C)*B.
O objetivo é dado por:
call_option(1, 7, 200, 300, P)
E a resposta é P = 200
Usando o Modelo
butterfly(S, P1 + P2 + 2*P3) :Buy = 1, Sell = -1,
call_option(Buy, S, 100, 500, P1),
call_option(Buy, S, 400, 100, P2),
call_option(Sell, S, 200, 300, P3).
Define a curva dada no gráfico anterior, para lucros:
P >= 0, butterfly(S,P).
Tem duas respostas:
P  100S  200  2  S  S  3
P  100S  400  3  S  S  4
Por quê restrições e não
Linguagem C?




Ambos os programas podem responder o
objetivo
call_option(1, 7, 200, 300, P).
Mas o CLP pode responder, sem muito
esforço, o objetivo:
butterfly(3, P1 + P2 + 2*P3).
P = 100

E até mesmo o objetivo:

P >= 0, butterfly(S,P).
P = 100S – 200 /\ 2<=S /\ S<=3
P = -100S + 400 /\ 3<=S /\ s<=4
Otimização
Muitos problemas requerem a
“melhor” solução
 Literal de minimização:
minimize(G,E)
 Responde as questões sobre o
objetivo G que minimiza a expressão
E (no contexto do estado)

Exemplos de Otimização
p(X,Y) := X = 1.
p(X,Y) :- Y = 1.
X >= 0, Y >= 0, minimize(p(X,Y), X+Y)
Respostas: X = 1 /\ Y = 0 e X = 0 /\ Y = 1
X >= 0, X >= Y, minimize(true, X-Y)
Resposta: X >= 0 /\ X = Y
minimize(butterfly(S,P), -P)
Resposta: S = 3 /\ P = 100
Avaliação de Otimização


Um valor de v é uma solução para um
estado se é alguma das soluções deste
estado
Passo da derivação de uma
minimização: <G1 | C1> para <G2 |
C2> onde G1 = L1,L2,...,Lm, e L1 é
“minimize(G,E)”


existe uma solução v de <G | C1> com v(E) =
m e para todas as outras soluções w temos
que m <= w(E)
• Então G2 é G,L2,...,Lm e C2 é C1 /\ E = m
Senão G2 é [] e C2 é falso
Exemplo de Otimização
X >=
X>=0, Y<=X, m=min(X-Y)
m=X-Y
0, minimize(X >= Y, X-Y) Tomemos X=0, o menor X
m=-Y
Mas Y<=X  Y<=0 
X  0, minimize( X  Y , X  Y )| true
-Y>=0
Tomemos –Y=0, o menor Y

m=0-0  m=0  X-Y=0
minimize( X  Y , X  Y )| X  0

X  Y| X  0
X  Y| X  0  X  Y  0


[]| X  0  X  Y
[]| X  0  X  Y  0  X  Y
Simplificado: X  0  X  Y
Valor mínimo de X-Y é 0
e.g. { X  3, Y  3}
Otimização
A otimização não precisa necessariamente ser um
objetivo:
straddle(S,C1+C2,E,P1+P2) :Buy = 1,
call_option(Buy, S, C1, E, P1),
put_option(Buy, S, C2, E, P2).
best_straddle(C,E,P) :minimize(straddle(S,C,E,P),-P).
Capítulo 7: Estimando
Eficiência


Avaliação é a busca na árvore de
derivação
O tamanho e a forma da árvore de
derivação determinam a eficiência
(ignorando o custo da solução)



Quanto menor: menos busca
Respostas do lado esquerdo da árvore:menos
busca antes de achar a primeira resposta
A árvore de derivação depende do modo
de uso (MU)
Modo de Uso (MU)




modo de uso (MU): define os tipos de
restrições nos argumentos de um
predicado quando avaliado
fixo: o conjunto de restrições implica em
um único valor para todas as soluções
livre: o conjunto de restrições permite
todos os valores
outros: limitado superiormente, limitado
inferiormente
Exemplo de Modo de Uso
sumlist([], 0).
sumlist([N|L], N+S) :- sumlist(L, S).

MU primeiro arg fixo segundo livre



sumlist([1],S).
L=[1,2],S > Z, sumlist(L,S).
Estados na árvore de derivação com a
chamada de sumlist
<sumlist([1], S)|true>
<sumlist(L’,S’)|[1]=[N’|L’]/\S=N’+S’>
<sumlist(L’’,S’’)|[]=[N’’|L’’]/\S’=N’’+S’’>
<N’’=0,S’’=0|/\S’=N’’+S’’>
Exemplo de Controle de
Busca

Pense em escrever um programa para
computar:
S  0  1  2 N

Raciocíne recursivamente:
A soma de N números é a soma de (N-1) + N
 A soma de 0 números é 0
(S1) sum(N, S+N) :- sum(N-1, S).

(S2) sum(0, 0).

Problema: sum(1,S) não tem resposta
Exemplo de Controle de
Busca
sum(1, S )| true
 S1
 S2
sum(0, S ' )| S  1  S '
[]| false
 S1
sum( 1, S ' ')| S  1  S ' '
 S2
[]| S  1
 S1
sum( 2, S '' ' )| S  0  S ' ''
 S2
[]| false
 S1
Árvore de derivação simplificada para sum(1,S).
Note que é infinita no ramo à esquerda, pois N assumiu
valores negativos.
Exemplo de Controle de
Busca

Derivação infinita antes da resposta
(S3) sum(0, 0).
(S4) sum(N, S+N) :- sum(N-1, S).
sum(1,S) resposta: S=1, sum(1,0)| true
 S4
 Mas e sum(1,0)?
sum( 0,1)| true

N=1, S+N=0  S=-1
N’=0, S’+N’=-1  S’=-1
N’’=-1, S’’+N’’=-1  S’’=0
N’’’=-2, S’’’+N’’’=0  S’’’=2
...
 S4
sum( 1,1)| true
 S4
sum( 2,0)| true
 S4
Exemplo de Controle de
Busca

O programa não foi feito para tratar com
números negativos. Corrija para:
(S5) sum(0, 0).
(S6) sum(N, S+N) :- sum(N-1, S), N >= 1.
sum (1,0) true
 S6
sum (0,1),1  1 true
 S6
Ainda não deu: derivação
infinita de sum(N,S+N)
sum ( 1,1),0  1,1  1 true
 S6
Exemplo de Controle de
Busca

Lembre-se do processamento da esquerda
para direita
(S7) sum(0, 0).
(S8) sum(N, S+N) :- N >= 1, sum(N-1, S).


sum(1,S) dá S = 1, sum(1,0) responde no
Métodos:



Reordenamento de regras
Adição de restrições redundantes
Reordenamento de literais
Ordenando Regras

Regra geral



Coloque as regras não-recursivas antes das
regras recursivas
(isto irá evitar derivações infinitas)
Regra heurística


Coloque regras que “parecem levar a
respostas rápidas” antes (acima) das outras
(isto tende a mover os estados de sucesso
para a esquerda da árvore)
Ordenando Literais

Restrições Primitivas


Coloque uma restrição no ponto mais à
esquerda possível no qual ela poderia causar
uma falha (para um determinado MU)
fac(N,F) com N fixo e F livre
fac(N, F) :- N = 0,F = 1.
fac(N, FF) :- N >= 1, FF = N * F,
N1 = N - 1, fac(N1, F).
fac(N, F) :- N = 0,F = 1.
fac(N, FF) :- N >= 1, N1 = N - 1,
fac(N1, F), FF = N * F.
Ordenando Literais

RDU:


Coloque os literais determinísticos antes dos
outros
determinístico: o literal p(s1,...,sn) em
um programa é determinístico para uma
árvore de derivação se a cada ponto de
escolha onde ele é reescrito, todas as
derivações falham, exceto uma, antes da
reescrita da RDU (em outras palavras: no
máximo uma tem sucesso)
Predicados Deterministicos




sumlist(L,S) é determinístico para o MU L
fixo e S livre. Não é para L livre e S fixo.
sum(N,S) é similar
Predicados determinísticos requerem
menos busca para achar uma resposta
CUIDADO! Mover predicados pode mudálo de determinístico para
não_determinístico (o bom é que o
inverso também é válido!)
Adicionando Restrições
Redundantes


Uma restrição que pode ser removida de
uma regra sem alterar as respostas
válidas de uma árvore é chamada de
redundante. (Pode alterar a ordem.)
Restrição de Resposta Redundante
(ARC): o mesmo conjunto de respostas
para:



H :- L1, ..., Li, Li+1, ..., Ln
H :- L1, ..., Li, r, Li+1, ..., Ln
Vantagem (para um conjunto de
restrições C, num MU)

<L1,...,Li,r|C> falha, mas não <L1,...,Li|C>
Adicionando Restrições
Redundantes (ARC)
A restrição N >= 1 adicionada ao programa sum é
uma ARC.
Outro exemplo: sum(N,7) (novo MU)
sum( N ,7)| true
 S8
sum( N ' , S ' )| N  N '1  S '  6  N ' N '  0
 S8
sum( N ' ' , S ' ' )| N  N ' '2  S ' '  4  2 N ' ' N ' '  0
 S8
sum( N ' ' ' , S ' ' ' )| N  N ' ' '3  S ' ' '  1  3 N ' ' ' N ' ' '  0
 S8
sum( N ' ' ' ' , S ' ' ' ' )| N  N ' ' ' '4  S ' ' ' '  3  4 N ' ' ' ' N ' ' ' '  0
Adicionando Restrições
Redundantes (ARC)
Sabemos que cada soma é não-negativa
(S9) sum(0, 0).
(S10) sum(N, S+N) :N >= 1, S >= 0, sum(N-1, S).
sum( N ,7)| true
 S10
sum( N ' , S ' )| N  N '1  S '  6  N ' N '  0  N '  6
 S10
sum( N ' ' , S ' ' )| N  N ' '2  S ' '  4  2 N ' ' N ' '  0  N ' '  2
 S10
sum( N ' ' ' , S ' ' ' )| N  N ' ' '3  S ' ' '  1  3 N ' ' ' N ' ' '  0  N ' ' '  1 / 3
 S10
[]| false
Restrições Redundantes de
Resolvedor

Restrição Resolvedor Redundante
(SRC): uma restrição primitiva r é SRC
se é implicada pelo conjunto de restrições
Vantagem: Se o resolvedor não está
vendo a implicação (resolvedor parcial ou
árvore infinita), adicioná-la pode trazer
informação extra (falha)

F >= 1, N >= 1, FF = N*F, FF >= 1

Exemplo de Restrições
Redundantes de Resolvedor (SRC)
(F1) fac(N, F) :- N = 0,F = 1.
(F2) fac(N, FF) :- N >= 1, N1 = N - 1,
FF = N * F, fac(N, F).
O objetivo fac(N,7) é infinito, como era sum(N,7).
(F3) fac(N, F) :- N = 0,F = 1.
(F4) fac(N, FF) :- N >= 1, N1 = N - 1,
FF = N * F, F >= 1, fac(N, F).
O objetivo fac(N,7) ainda é infinito!
Exemplo de Restrições
Redundantes de Resolvedor (SRC)
fac( N ,7)| true
 F4
fac( N  1, F ' )| F '  1  N  1  7  N  F '
 F4
fac( N  2, F ' ' )| F ' '  1  N  2  7  N  ( N  1)  F ' '
 F4
fac( N  3, F '" ' )| F '" '  1  N  3  7  N  ( N  1)  ( N  2)  F ' ' '
 F4
fac( N  4, F ' ' ' ' )| F ' ' ' '  1  N  4  7  N  ( N  1)  ( N  2)  ( N  3)  F ' ' ' '
Dado que F’’’’ >= 1 e N >= 4 então
N  ( N  1)  ( N  2)  ( N  3)  F ''''
Deve ser pelo menos 24. Esta restrição não foi satisfeita
por não ter sido detectada (resolvedor parcial)
Exemplo de Restrições
Redundantes de Resolvedor (SRC)
Correção: adicione a SRC, N * F >= N
Que é implicada por N >= 1, F >= 1
CUIDADO: 1 = N * F , 2 = N * F tem sucesso ao se
instanciar F, por isso, use um nome único para N*F
(F3) fac(N, F) :- N = 0,F = 1.
(F4) fac(N, FF) :- N >= 1, N1 = N - 1,
FF = N * F, FF >= N, F >= 1,
fac(N, F).
Agora o objetivo fac(N,7) falha em tempo finito!
Minimização



Minimizar literais causam a busca de
respostas em uma árvore de derivação
diferente
Precisamos entender a forma desta
árvore para lidar com ela
minimize(G,E) tem o mesmo MU de
E < m, G

Para um uso eficiente da minimização,
tenha certeza que G é eficiente quando E
é limitado superiormente, por um m
qualquer dado.
Exemplo de Minimização
Programa que acha os nós folhas e seus níveis
L1:leaf(node(null,X,null),X,0).
L2:leaf(node(L,_,_),X,D+1) :leaf(L,X,D).
L3:leaf(node(_,_,R),X,D+1) :leaf(R,X,D).
Objetivo:
a
leaf(t(a),X,D)
Respostas:
(h,3),(j,4),(k,4),
(m,4),(o,5),(p,5),
(f,2),(s,4), (t,4),(r,3)
b
c
d
h
e
i
j
f
l
k
m
q
n
o
g
s
p
r
t
Exemplo de Minimização
Objetivo
minimize(leaf(t(a),X,D), D):
Após encontrar X = h /\ D = 3, o objetivo
fica:
D < 3, leaf(t(a),X,D), o que faz que
nunca se visite nós com profundidade
superior a 3 (?)
a
D  3, leaf (t ( a ), X , D ) true

leaf (t ( a ), X , D ) D  3
 L2
leaf (t (b), X , D  1) D  3
 L2
leaf (t ( d ), X , D  2) D  3
 L3
b
c
d
h
e
i
j
f
l
k
m
leaf (t (i ), X , D  3) D  3
q
n
s
 L3
g
r
r
leaf (t ( k ), X , D  4) D  3
 L1
[] ( D  3  D  4  0)  false
o
p
Exemplo de Minimização
Melhore o leaf para o MU com D limitado
superiormente: adicione uma ARC
D  3, leaf (t (a ), X , D true

leaf (t (a ), X , D) D  3
L4:leaf(node(null,X,null),X,0).
 L5
L5:leaf(node(L,_,_),X,D+1) :leaf (t (b), X , D  1) D  3  D  1
D >= 0, leaf(L,X,D).
 L5
L6:leaf(node(_,_,R),X,D+1) :leaf (t (d ), X , D  2) D  3  D  2
D >= 0, leaf(R,X,D).
 L6
[] ( D  3  D  3)  false
Minimização

A busca pode nem sempre ser
beneficiada pelos limites




e.g. minimize(leaf(t(a),X,D), -D)
Ainda deve visitar todos os nós antes de achar
um nó folha de maior profundidade
A formulação original é superior, uma vez que
envolve menos restrições (a restrição
redundante D>=0 não diminui o espaço de
busca)
Conceito-Chave: lembre-se do MU de
E<m, G, com m fixo.
Capítulo 8: Domínios e
Rótulos

Novos requisitos: precisamos definir os
domínios e as variáveis




aritmético X :: [1,2,3,4] ou X :: [1..4]
não-aritmético X :: [red, blue, yellow]
multiplas variáveis [X,Y,Z] :: [0..10]
Se nenhum domínio é dado, é usado o
padrão, por exemplo [-10000..10000]
Exemplo de Domínios
Objetivo para o problema do peso da sacola do
contrabandista:
[W,P,C] :: [0..9], 4*W + 3*P + 2*C <= 9,
15*W + 10*P + 7*C >= 30.
D(W )  [0..2], D( P)  [0..3], D(C)  [0..4]
O sistema CLP(FD) retorna unknown.
Mas como achar uma solução?
Devemos chamar um resolvedor completo
(com backtracking)
Rótulos (Labelling)


O predicado interno labeling chama
o resolvedor de restrições completo
labeling(Vs) toma uma lista de
variáveis de domínio finito Vs e
encontra uma solução
[W,P,C] :: [0..9], 4*W + 3*P + 2*C <= 9,
15*W + 10*P + 7*C >= 30, labeling([W,P,C]).
Acha as soluções:
W  0  P  1 C  3 W  0  P  3  C  0
W  1 P  1 C  1 W  2  P  0  C  0
Restringe e Gera!

Forma típica de um programa de domínio finito





Variáveis e domínios são definidos
As restrições que modelam o problema são dadas
O labeling é adicionado para chamar o resolvedor
completo
A minimização pode ser aplicada no labeling
Exemplo:
[W,P,C] :: [0..9], 4*W + 3*P + 2*C <= 9,
15*W + 10*P + 7*C >= 30,
minimize(labeling([W,P,C]), -15*W-10*P-7*C).
Exemplo
Send+More=Money
Problema Cripto-aritmético,
cada dígito é diferente, e a
equação deve ficar correta

 M
S
M
O
E
O
N
N
R
E
D
E
Y
smm(S,E,N,D,M,O,R,Y) :[S,E,N,D,M,O,R,Y] :: [0..9],
constrain(S,E,N,D,M,O,R,Y),
labeling([S,E,N,D,M,O,R,Y]).
constrain(S,E,N,D,M,O,R,Y) :S != 0, M != 0,
alldifferent_neq([S,E,N,D,M,O,R,Y]),
1000*S + 100*E + 10*N + D
+
1000*M + 100*O + 10*R + E
= 10000*M + 1000*O + 100*N + 10*E + Y.
Exemplo
Send+More=Money
Após a declaração do domínio, temos:
D( S )  D( E )  D( N )  D( D)  D( M )  D(O)  D( R)  D(Y )  [0..9]
Após S  0  M  0 temos D( S )  D( M )  [1..9]
alldifferent_neq adiciona a desigualdade (não
muda o domínio)
Equação final após uma regra de propagação:
max( D, S ) 
max( D, E ) 
max( D, D)  max( D, R)
M
1
1
1
 10 min( D, O)  100 min( D, N )  9000 min( D, Y )
1
9
91
9000
1
9000
1
900
Considerando o domínio corrente, temos:
M 
9
9
91 9
9000

9
9000

9
900

0
10

0
100

0
9000
 1102
.
Exemplo
Send+More=Money
Portanto D(M) = [1..1]
A propagação continua até que:
D( S )  [9..9]
D( E )  [4..7] D( N )  [5..8] D( D)  [2..8]
D( M )  [1..1] D(O)  [0..0]
D( R)  [2..8]
D(Y )  [2..9]
Observe: 3 variáveis estão fixadas e todos os domínios estão
reduzidos. O labeling tenta S=0, S=1, ..., S=8 (que falham
imediatamente) e então S=9. Depois E=0, E=1, E=2, E=3
(que falham imediatamente) e E=4 (que eventualmente
falha), então E=5 dá como resposta:
D( S )  [9..9]
D( E )  [5..5] D( N )  [6..6] D( D)  [7..7]
D( M )  [1..1] D(O)  [0..0]
D( R)  [8..8]
D(Y )  [2..2]
Gera e Testa!
Método sem restrições:
primeiro gera uma possível solução
então testa a solução
smm(S,E,N,D,M,O,R,Y) :[S,E,N,D,M,O,R,Y] :: [0..9],
labeling([S,E,N,D,M,O,R,Y]),
constrain(S,E,N,D,M,O,R,Y).
Este programa requer 95671082 escolhas antes de
achar a solulção. O anterior requer apenas 35
escolhas (ou 2 que não falham imediatamente)
Restrições Complexas
Restrições Complexas como
alldifferent, cumulative e element
 Modelagem do problema mais
sucinta
 Melhor propagação = mais eficiência



Pois são primitivas! (reveja a definição)
Exemplo:

alldifferent_neq([S,E,N,D,M,O,R,Y])
Rotulagem

Há duas escolhas feitas pelo labeling:



labeling padrão:



Escolha de qual variável instanciar primeiro
Escolha de qual valor do domínio tentar
primeiro
Tenta as variáveis na ordem dada pela lista
Tenta os valores do menor para o maior (dado
pela primitiva dom)
Podemos programar estratégias
diferentes
Escolha de Variáveis
A escolha das variáveis afeta o tamanho da
árvore de derivação
 Heurística: escolha variáveis com o conjunto do
domínio menor (portanto com menos possíveis
respostas)
 Exemplo
D( S )  [9..9] D( E )  [4..7] D( N )  [5..8] D( D)  [2..8]
D( M )  [1..1] D(O)  [0..0] D( R)  [2..8] D(Y )  [2..9]

O labeling tentaria primeiro S, M, O (a escolha já
está dada pelo domínio). Melhor que E ou N.
Muito melhor que Y primeiro.
Escolha do Valor do
Domínio



O valor da variáveis somente afeta a
ordem em que os ramos da árvore é
explorado
Conhecimento específico do problema
pode levar a uma busca mais rápida da
solução
Também é importante para a otimização:

Boas soluções encontradas cedo reduzem a
busca posterior
Eficiência da Rotulagem

Podemos utilizar ambas ordenações
(de variáveis e de valores) juntas
Número de escolhas
diferentes para o
problema das
N-Rainhas com
estratégias diferentes
• Padrão
• Primeira a falhar
• Primeiro no meio
10000
1000
Default
First-fail
Middleout
100
10
1
10-19
30-39
50-59
70-79
Divisão de Domínios
(Domain Splitting)

O labeling não precisa ser do tipo

Ligar uma variável a um valor
Ele simplesmente deve reduzir o
domínio de uma variável
 Divisão de Domínios divide o
domínio corrente de uma
determinada variável pela metade

Modelando diferentemente
o (mesmo) Problema




Visões diferentes de um problema levam
a diferentes modelos
Modelos diferentes = Conjunto de
variáveis diferentes
Dependendo das capacidades do
resolvedor, um modelo pode requerer
menos busca que outro para achar uma
resposta
A comparação empírica pode ser a
medida do tempo ou esforço gasto
Modelando diferentemente
o (mesmo) Problema
Problema de simples atribuição: quatro
trabalhadores w1,w2,w3,w4 e quatro produtos
p1,p2,p3,p4. Atribua um produto a um
trabalhador de modo que o lucro L >= 19
A matriz de Lucro é:
w1
p1 p2
7
1
p3 p4
3
4
w2
w3
8
4
2
3
5
7
1
2
w4
3
1
6
3
Modelo 1: Pesquisa de
Operações
16 variáveis booleanas Bij
significando que o
trabalhador i está com o produto j


4
i 1
4
j 1


4
j 1
4
i 1
Bij  1
Bij  1
7 B11
 B12
 8 B21  2 B22
P
 4 B31  3B32
 3B41  B42
P  19
Somatória de j é 1
(um só produto por trabalhador)
Somatória de i é 1
(um só trabalhador por produto)
 3B13
 5 B23
 7 B33
 6 B43
 4 B14
 B24
 2 B34
 3B44
w1
p1 p2
7
1
p3 p4
3
4
w2
w3
8
4
2
3
5
7
1
2
w4
3
1
6
3
B23
11 restrições primárias,
28 escolhas para achar
todas as quatro soluções
Modelo 2: melhor
Usando a desigualdade e
restrições complexas. Quatro
variáveis W1,W2,W3,W4
correspondendo aos trabalhadores
W1 w1
W2 w2
W3 w3
W4 w4
1 2
3
4
p1 p2
7
1
p3 p4
3
4
8
4
2
3
5
7
1
2
3
1
6
3
alldifferent ([W1, W 2, W 3, W 4]) 
element (W1,[7,1,3,4], WP1) 
element (W 2,[8,2,5,1], WP2) 
element (W 3,[4,3,7,2],WP 3) 
element (W 4,[3,1,6,3], WP4) 
P  WP1  WP2  WP3  WP4 
P  19
7 restrições primárias,
14 escolhas para achar
todas as quatro soluções
Modelo 3: Diferente
T1 T2 T3 T4
Quatro variáveis T1,T2,T3,T4
correspondendo aos produtos.
1 w1
2 w2
3 w3
4 w4
p1 p2
7
1
p3 p4
3
4
8
4
2
3
5
7
1
2
3
1
6
3
alldifferent ([T1, T 2, T 3, T 4]) 
element (T1,[7,8,4,3], TP1) 
element (T 2,[1,2,3,1], TP 2) 
element (T 3,[3,5,7,6], TP 3) 
element (T 4,[4,1,2,3], TP 4) 
P  TP1  TP 2  TP 3  TP 4 
P  19
7 restrições primárias,
7 escolhas para achar
todos as quatro soluções
Comparando os Modelos

A eficiência relativa vem de:




Mapeamento mais direto às restrições primitivas
Menos variáveis
Normalmente requer avaliação empírica
Outro critério de eficiência:


flexibilidade (adicionar restrições novas)
e.g. trabalhador 3 deve trabalhar num produto > que
o do trabalhador 2
B31  0  B24  0 
B32  B21 
B33  B21  B22 
B34  B21  B22  B23 
Modelo 1
W3  W2
Modelo 2
?????
Modelo 3
Combinando Modelos




Combine os modelos relacionando as
variáveis e seus valores em cada um dos
modelos
e.g. B13 = 1 significa W1 = 3 que
significa T3 = 1
Modelos combinados podem ganhar mais
eficiência atráves da informação que é
propagada
A restrição primária iff(V1,D1,V2,D2) é
verdade para V1=D1 se e somente se
V2=D2
Modelos Combinados
alldifferent ([W1, W 2, W 3, W 4]) 
element (W1,[7,1,3,4], WP1) 
element (W 2,[8,2,5,1], WP2) 
element (W 3,[4,3,7,2],WP 3) 
element (W 4,[3,1,6,3], WP4) 
P  WP1  WP2  WP3  WP4 
P  19 
alldifferent ([T1, T 2, T 3, T 4]) 
element (T1,[7,8,4,3], TP1) 
element (T 2,[1,2,3,1], TP 2) 
element (T 3,[3,5,7,6], TP3) 
element (T 4,[4,1,2,3], TP 4) 
P  TP1  TP 2  TP3  TP 4
iff (W11
, , T11
, )  iff (W1,2, T 2,1)  iff (W1,3, T 3,1)  iff (W1,4, T 4,1) 
iff (W 2,1, T1,2)  iff (W 2,2, T 2,2)  iff (W 2,3, T 3,2)  iff (W 2,4, T 4,2) 
iff (W 3,1, T1,3)  iff (W 3,2, T 2,3)  iff (W 3,3, T 3,3)  iff (W 3,4, T 4,3) 
iff (W 4,1, T1,4)  iff (W 4,2, T 2,4)  iff (W 4,3, T 3,4)  iff (W 4,4, T 4,4)
39 restrições prim. 5 escolhas para achar todas soluções
Resolvedor baseado em
Consistência do Arco



Assumimos que o sistema CLP(FD) usa um resolvedor
de propagação de limites
A Consistência do Arco permite que mais valores sejam
eliminados nas relações binárias das variáveis
Exemplo:


Suponha o problema das 8-Rainhas, com uma solução
parcial de D(R1)={2}, D(R2)={4}, D(R3)={6}
O resolvedor de restrições baseado em consistência de
limites determinará os domínios:
• D(R4)=[1..8], D(R5)=[3..5], D(R6)=[1..5], D(R7)=[1..7],
D(R8)=[3..8]

O resolvedor de restrições baseado em consistência de
arcos determinará os valores:
• D(R4)={1,3,8}, D(R5)={3,5}, D(R6)={1,5},
D(R7)={1,3,5,7}, D(R8)={3,5,7,8}
Resolvedor baseado em
Consistência do Arco



O resolvedor baseado em consistência do
arco dá informações muito mais acuradas dos
valores possíveis para as variáveis
Outra vantagem é que este resolvedor
trabalha tão bem com valores limitados
quanto com coleções, enquanto o resolvedor
baseado em limites trabalha bem apenas com
restrições aritméticas
O programador define a RDU como uma
relação binária com múltiplos fatos, e as
rotula com a palavra reservada “consistent”,
que indica ao CLP que ele deve resolver a
relação utilizando consistência de arcos.
Resolvedor baseado em
Consistência do Arco

Por exemplo, o programa:
likes(joaquim, maria).
likes(joaquim, nicole).
likes(joaquim, erica).
likes(pedro, maria).
likes(bernardo, nicole).
likes(bernardo, maria).
likes(bernardo, erica).

E os objetivos:
Obj1:
[N,M,E]::[joaquim, pedro, bernardo], N  M , N  E, M  E
likes(N, neila),likes(M, maria),likes(E, erica).
Obj2:
[N,M,E]::[joaquim, pedro, bernardo], N  M , N  E, M  E
likes(N, neila) consistent, likes(M, maria) consistent,
likes(E, erica) consistent, labeling([N,M,E]).
Resolvedor baseado em
Consistência do Arco


Predicados de aridade maior se resolvem pela consistência de
hiper-arcos e com predicados unários, consistência de nós.
No exemplo anterior, no objetivo 2, ao invés de fazer o
backtracking pelas diferentes regras (caso do objetivo 1), é
utilizada a consistência de arcos para avaliar a relação likes.
Assim, as desigualdades e as restrições levam ao seguinte
domínio:
D(N)={joaquim, bernardo}, D(M)={joaquim, bernardo, pedro},
D(E)={joaquim, bernardo}
A execução do labeling leva
arco devolve
D(N)={joaquim},
e a consistência do
D(M)={pedro}, D(E)={bernardo}
Assim nenhuma outra escolha é necessária para achar a
primeira solução. Se for pedida outra solução, o backtraking faz
imediatamente D(N)={bernardo} e as restrições da consistência do
arco se propagam, não sendo necessária nenhuma outra escolha
para a segunda solução
Restrição Reified
Uma restrição reified r  B
adiciona uma variável booleana B a
uma restrição primitiva r
 Se r ocorre, então B = 1
 Se r não ocorre, então B = 0
 A propagação é em ambas as
direções

Restrição Reified

Usada para construir combinações
complexas sem usar “escolhas”

Imagine que queremos que, das nossas 4
restrições primitivas, sejam satisfeitas apenas
2 ou 3. Isso geraria regras com muitas
combinações…
comb(X,Y):comb(X,Y):comb(X,Y):comb(X,Y):comb(X,Y):.
.
.
c1, c2, ¬c3, ¬c4.
c1, ¬c2, c3, ¬c4.
c1, ¬c2, ¬c3, c4.
¬c1, c2, c3, ¬c4.
¬c1, c2, ¬c3, c4.
C1  B1, C2  B2,
C3  B3, C4  B4,
B = B1 + B2 + B3 + B4,
2<=B, B<=3