Seminários de Informática
Pesquisa e Optimização
Programação por Restrições
Pedro Barahona
Junho de 2005
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
1
Pesquisa e Optimização
Alguns exemplos de Problemas de Decisão que envolvem
pesquisa e optimização:
• Testes em circuitos digitais (para detecção de avarias)
• Gestão de Redes de Telecomunicações
• Sequenciação de Tarefas (Scheduling)
• Gestão de Frotas
• Gestão da Produção
• Geração de Horários
• “Colocação” ou “preenchimento”
– 2D: corte de peças (tecido, tábuas, etc...)
– 3D: prenchimento de contentores
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
2
Problemas de Pesquisa e Optimização
O que têm em comum estas aplicações:
• Muitas soluções “potenciais”
• Restrições entre as variáveis do problema
• Nenhuma forma de as obter de uma forma “óbvia”
• Recurso: pesquisa das várias soluções
• Espaço de pesquisa ENORME
• Necessidade de pesquisa eficiente
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
3
Exemplo: Circuitos Digitais
Objectivo:
Verificar se a gate G2 está
“stuck-at-1”.
A
G1
G4
H
G5
I
B
Possibilidades:
G2
Valores 0/1 nas várias
entradas
E
F
C
Restrições (binárias):
D
G3
G
Exemplo: F = nand(B,C)
Espaço de Pesquisa:
• As 4 entradas, A, B, C e D, podem tomar valores 0 ou 1,
• Existem 2*2*2*2 = 24soluções potenciais
• Se o circuito tiver n entradas há que testar 2n possibilidades!
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
4
Exemplo: Gestão de Redes (de Telecomunicações)
Objectivo:
3
Enviar k pacotes de A a Z.
B
Possibilidades:
5
0 a C pacotes em cada troço
C- capacidade do troço
Restrições:
H
3
6
E
4
9
5
7
A
8
C
4
3
6
D
5
G
7
Z
7
F
2
Não se perdem pacotes
AE + BE + CE = EH + EZ
Espaço de Pesquisa:
• Os m troços (m=17 neste caso) com 0 a C pacotes
• Neste caso 6*5*8*9 * ....* 7*10*8*3 possibilidades
• Em geral, com n nós, existem até n*(n-1)/2 troços. Se assumirmos a
mesma capacidade c em todos os troços temos cn(n-1)/2 possibilidades.
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
5
Exemplo: Escalonamento de tarefas
Objectivo (job-shop):
Executar k tarefas até um tempo T.
Possibilidades:
Cada tarefa começa entre 0 e T
Restrições (binárias):
J1
J2
1
2
1
J3
Precedência de algumas tarefas;
J12 >= J11+D11
Não sobreposição de tarefas
J22 >= J12+D12 ou J12 >= J22+D22
J4
3
2
1
1
3
2
2
3
3
Espaço de Pesquisa:
• As k tarefas têm duração inteira e começam entre os tempos 0 e T.
• Em geral teremos de considerar T*T* ... * T = Tk possibilidades.
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
6
Exemplo: Gestão de Produção e de Frotas
• Problemas semelhantes aos anteriores, mas em que se
devem considerar algumas restrições adicionais
• Gestão de Produção
– Atribuir tarefas a trabalhadores /máquinas
– Capacidade máxima de cada trabalhador
– Possibilidades da tarefa requerer vários trabalhadores
– ...
• Gestão de Frotas
– As tarefas têm um ponto de partida e de chegada
– Existem capacidades máximas para os camiões
– ...
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
7
Exemplo: Geração de Horários
• Para as várias aulas necessárias de um conjunto de cursos
atribuir-lhes professores e salas de forma a que se
satisfaçam algumas restrições obrigatórias
– 2 aulas com o mesmo professor não podem ser leccionadas ao
mesmo tempo
– 2 aulas não podem ser leccionadas na mesma sala
• Há ainda que tentar satisfazer restrições opcionais tais
como
–
–
–
–
Evitar furos
Evitar aulas isoladas
Teóricas de manhã e Práticas à tarde
....
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
8
Exemplo: “Colocação” ou “preenchimento”
• Objectivo:
Colocar os vários rectângulos num
rectângulo maior (2D).
Colocar os vários paralelipípedos
num paralelipípedo maior (3D)
Restrições:
F
K
I
E
A
D
C
G
– Não sobreposição dos rectângulos i e j, isto é
Xi > Xj + aj (i à direita de j) ou
Xj > Xi + ai (i à esquerda de j) ou
Yi > Yj + bj (i acima de j) ou
Yj > Yi + bi (i abaixo de j) ou
B
J
H
• Espaço de pesquisa
– Canto inferior esquerdo de cada uma das n peças em qualquer
das k = l*h posições.
– O número de possibilidades é pois de k*k* ...*k = kn
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
9
Relevância destes Problemas
• Custos e Produção numa grande empresa
–
–
–
–
–
–
2 000 trabalhadores a 50 000 €/ano (≈ 3 570 € /mês)
Custos pessoal de 100 000 000 €/ano
Outros Custos de 20 000 000 €/ano
Produção de 70 000 €/ano/trabalhador
Receitas totais de 140 000 000 €/ano
Lucro de 20 000 000 €/ano
• Melhoria de Produtividade
– Redução de Pessoal
• Mesma Produção com menos trabalhadores
– Aumento da Produção
• Mesmos trabalhadores, mas produzindo mais
– Cenários intermédios
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
10
Relevância destes Problemas
• Cenário: Aumento de eficiência de 5%
• Melhoria de Produtividade
– Redução de Pessoal
• Menos 5 000 000 €
• Aumento dos Lucros de 25% (20 M€ para 25 M€)
– Aumento da Produção
• Produção de 73 500 € por trabalhador (em vez de 70 K€)
• Lucros aumentam 2000 * 3 500 = 7 M€
• Aumento de Lucros de 35%
– Cenários intermédios
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
11
Relevância destes Problemas
• Outros custos envolvidos - Material
• Cenário: Melhoria de Eficiência de 5%
• Gestão de Frotas (1)
– 1000 camiões TIR * 250 000 € cada TIR
– Poupança de 50 camiões: 12 500 000 €
• Gestão de Frotas (2)
– 100 aviões * 5 000 000 € cada avião
– Poupança de 5 aviões: 25 000 000 €
• Gestão de Redes de Telecomunicações
– 200 antenas de telemóveis * 500 000 € por antena
– Poupança de 10 antenas: 5 000 000 €
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
12
Integração em Sistemas Informáticos
• Todos os problemas envolvem a análise dos dados de uma
empresa
– Sistemas de Informação “Sofisticados”
– Bases de Dados + DataWarehousing
• Sistemas de Apoio à Decisão
– Integrar algoritmos nos sistemas de Informação
– Adaptação (parametrização) de algoritmos existentes
• Papel de um Engenheiro Informático
– Integrar informação para usar Produtos existentes
– Melhorar as soluções existentes
• Melhores Modelos
• Melhores Algoritmos
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
13
Formalização de Problemas de Decisão
• Um problema de satisfação de restrições é um triplo
<V,D,R>, em que
• V é um conjunto de variáveis
• D é o domínio das variáveis
• R é o conjunto de restrições entre as variáveis
• Um problema de optimização é um quádruplo <V,D,R,F>, em
que
• V, D e R são como os anteriores
• F é uma função das variáveis que se pretende optimizar
• Para ilustrar os algoritmos de resolução destes problemas
e a sua complexidade podemos enunciar problemas
“teóricos” cuja resolução segue os mesmos métodos de
problemas mais “realistas”.
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
14
Exemplos de Problemas (Satisfação)
• Exemplos “simples”
– N - rainhas
Q
• Colocar n rainhas num tabuleiro de
n*n casas de forma a que nenhumas
rainhas se ataquem mutuamente
(i.e. estejam na mesma linha, coluna
ou diagonal).
Q
Q
Q
– Criptografia
• Atribuir números a letras (números
diferentes a letras diferentes) de
forma a que as operações indicadas
sejam válidas
1 Junho 2005
S
E
N
D
+
M
O
R
E
M
O
N
E
Y
Seminários de Informática – Pesquisa e Optimização
15
Exemplos de Problemas (Satisfação)
• 4 - rainhas
Q1
– Variáveis:
Q2
• V: {Q1, Q2, Q3, Q4}
Q3
– Domínio
Q4
• D : {1,2,3,4}
– Restrições R:
% Colunas Diferentes:
Solução:
Q1 = 2, Q2 = 4, Q3 = 1, Q4 = 3
Q1 ≠ Q2, Q1 ≠ Q3, Q1 ≠ Q4, Q2 ≠ Q3, Q2 ≠ Q4, Q3 ≠ Q4,
% Diagonais / Diferentes:
Q1+1 ≠ Q2+2, Q1+1 ≠ Q3+3, Q1+1 ≠ Q4+4,
Q2+2 ≠ Q3+3, Q2+2 ≠ Q4+4, Q3+3 ≠ Q4+4,
% Diagonais \ Diferentes:
Q1-1 ≠ Q2-2, Q1-1 ≠ Q3-3, Q1-1 ≠ Q4-4,
Q2-2 ≠ Q3-3, Q2-2 ≠ Q4-4, Q3-3 ≠ Q4-4,
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
16
Exemplos de Problemas (Satisfação)
• Send More Money
– Variáveis:
• V: {S, E, N, D, M, O, R, Y}
– Domínio
S
E
N
D
+
M
O
R
E
M
O
N
E
Y
• D : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
– Restrições R:
% Valores diferentes para letras diferentes :
S ≠ E, S ≠ N, ... , R ≠ Y
% Conta Certa:
1000*S + 100*E + 10*N + D
+ 1000*M + 100*O + 10*R + E =
10000*M + 1000*O + 100*N + 10*E + Y
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
17
Complexidade dos Problemas
• Solução obtida por algoritmos não deterministas
– Envolvem escolhas eventualmente erradas!
• Consequência
– Complexidade Exponencial e não Polinomial
• Algoritmo Determinístico – Ordenação
– “Bubble sort” aplicado a um vector c/ n elementos
• 1ª passagem:
n-1 comparações
• 2ª passagem:
n-2 comparações
• (n-1)ª passagem: 1 comparação
– Total: n-1 + n-2 + ... + 1 = (n-1)[1+ (n-1)] / 2 = n (n-1)/2
– Complexidade Polinomial do algoritmo: O(n2)
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
18
Complexidade dos Problemas
• “Bubble sort” aplicado a um vector c/ 5 elementos
Comparações
9 7 5 3 1
1-2
7 9 5 3 1
2-3
7 5 9 3 1
3-4
7 5 3 9 1
4-5
7 5 3 1 9
1-2
5 7 3 1 9
2-3
5 3 7 1 9
3-4
5 3 1 7 9
1-2
3 5 1 7 9
2-3
3 1 5 7 9
1-2
1 3 5 7 9
ok
1 Junho 2005
• Pior caso
– 4+3+2+1 comparações
= 4*(1+4)/2 = 10
– Em geral
• (n-1) n /2
– Complexidade
• O(n2)
Seminários de Informática – Pesquisa e Optimização
19
Complexidade dos Problemas
• Algoritmo Não Determinístico
– Escolha de Entradas (binárias)
– Pior caso: testar todas as combinações
– n entradas – combinações possíveis
• 2*2*...* 2 = 2n
Exemplo: 3 entradas
• Complexidade Exponencial : O(2n)
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
20
Complexidade Polinomial vs Exponencial
• Algoritmos Determinísticos: Complexidade Polinomial
nk
2
3
4
5
10
100
20
30
400
900
40
50
60
1 600
2 500
3 600
0.1 mseg
0.4 mseg
0.9 mseg
1.6 mseg
2.5 mseg
3.6 mseg
1 000
8 000
27 000
64 000
125 000
216 000
1 mseg
8 mseg
27 mseg
64 mseg
125 mseg
216 mseg
10 000
160 000
810 000
2 560 000
6 250 000
12 960 000
10 mseg
160 mseg
810 mseg
2.6 seg
6.3 seg
13 seg
100 000
3 200 000
24 300 000
102 400 000
312 500 000
777 600 000
100 mseg
3.2 seg
24 seg
1.7 min
5.2 min
13 min
• Algoritmos Não-Determinísticos: Complexidade Exponencial
kn
10
20
30
40
50
60
1 024
1 048 576
1 073 741 824
1.10E+12
1.13E+15
1.15E+18
1 mseg
1 seg
18 min
12.7 dias
35.7 anos
365 séculos
59 049
3 486 784 401
2.06E+14
1.22E+19
60 mseg
1 hora
6.5 anos
3400 séculos
4
1 048 576
1.10E+12
1.15E+18
1 seg
12.6 dias
365 séculos
5
9 765 625
9.54E+13
9.31E+20
10 seg
1103 dias
295 Kséc
2
3
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
21
Algoritmos de Resolução
• A resolução de problemas de decisão não triviais pode ser
feita através de duas abordagens diferentes:
• Métodos Construtivos
– Os valores das várias variáveis vão sendo atribuídos tendo de ser
revistos quando se detecta uma contradição.
– Exemplo: Se Q1 = 2 e Q3 = 2 há contradição porque Q1 ≠ Q3
• Métodos Reparativos
– Uma “pseudo-solução” que não satisfaz algumas restrições é
reparada de forma a tornar-se uma solução.
– Exemplo: V = [1,2,3,4] não satisfaz as restrições (Q1 -1 ≠ Q2 -2).
Trocar Q1 com Q4 ficamos com V = [4,2,3,1] e a rainha Q1 já não
ataca Q2.
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
22
Métodos Construtivos – Pesquisa em árvore
• Os métodos construtivos utilizam em geral um algoritmo
de pesquisa em árvore.
• Normalmente utiliza-se a pesquisa em profundidade da
esquerda para a direita
• Exemplo: Pesquisa Binária com 4 variáveis
V1 = 0
V2 = 0
V2 = 1
V1 = 1
V2 = 0
V2 = 1
V3 = 0
V4 = 0
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
23
Pesquisa com Retrocesso
• Em cada nó é verificado se vale a pena continuar.
• Nessa situação, executa-se um retrocesso (backtracking)
evitando-se testar todos os valores!
• Se V1=0 é imcompatível com V2 = 0, eliminam-se todas as
soluções [0,0,x,x]!
V1 = 0
V2 = 0
V2 = 1
V1 = 1
V2 = 0
V2 = 1
V3 = 0
V4 = 0
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
24
Pesquisa Heurística
• Em cada nó, vale a pena “pensar” para decidir:
– Qual a próxima variável a atribuir valor;
– Que valor atribuir
• Por exemplo, após atribuir V1 = 1, é preferível escolher a variável V3,
e atribuir-lhe o valor 1 em primeiro lugar.
V1 = 0
V2 = 0
V2 = 1
V1 = 1
V3 = 1
V3 = 0
V3 = 0
V4 = 0
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
25
Retrocesso
Testes 0
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
26
Retrocesso
Q1 \= Q2,
Q1+1 \= Q2+2, Q1-1 \= Q2-2
Testes 0 + 1 = 1
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
27
Retrocesso
Q1 \= Q2,
Q1+1 \= Q2+2, Q1-1 \= Q2-2
Testes 1 + 1 = 2
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
28
Retrocesso
Q1 \= Q2,
Q1+1 \= Q2+2, Q1-1 \= Q2-2
Testes 2 + 1 = 3
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
29
Retrocesso
Testes 3 + 1 = 4
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
30
Retrocesso
Testes 4 + 2 = 6
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
31
Retrocesso
Testes 6 + 1 = 7
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
32
Retrocesso
Testes 7 + 2 = 9
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
33
Retrocesso
Testes 9 + 2 = 11
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
34
Retrocesso
Testes 11 + 1 + 3 = 15
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
35
Retrocesso
Testes 15 + 1 + 4 + 2 + 4 = 26
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
36
Retrocesso
Testes 26 + 1 = 27
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
37
Retrocesso
Testes 27 + 3 = 30
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
38
Retrocesso
Testes 30 + 2 = 32
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
39
Retrocesso
Testes 32 + 4 = 36
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
40
Retrocesso
Testes 36 + 3 = 39
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
41
Retrocesso
Testes 39 + 1 = 40
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
42
Retrocesso
Testes 40 + 2 = 42
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
43
Retrocesso
Testes 42 + 3 = 45
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
44
Retrocesso
Falha
6
Retrocede
5
Testes 45
1 Junho 2005
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
45
Retrocesso
Testes 45
1 Junho 2005
Retrocessos 1
Seminários de Informática – Pesquisa e Optimização
46
Retrocesso
Testes 45 + 1 = 46
1 Junho 2005
Retrocessos 1
Seminários de Informática – Pesquisa e Optimização
47
Retrocesso
Testes 46 + 2 = 48
1 Junho 2005
Retrocessos 1
Seminários de Informática – Pesquisa e Optimização
48
Retrocesso
Testes 48 + 3 = 51
1 Junho 2005
Retrocessos 1
Seminários de Informática – Pesquisa e Optimização
49
Retrocesso
Testes 51 + 4 = 55
1 Junho 2005
Retrocessos 1
Seminários de Informática – Pesquisa e Optimização
50
Retrocesso
Falha
6
Retrocede
5e4
Testes 55+1+3+2+4+3+1+2+3 = 74
1 Junho 2005
Retrocessos 1
Seminários de Informática – Pesquisa e Optimização
51
Retrocesso
Testes 74+2+1+2+3+3= 85
1 Junho 2005
Retrocessos 1+2 = 3
Seminários de Informática – Pesquisa e Optimização
52
Retrocesso
Testes 85 + 1 + 4 = 90
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
Retrocessos 3
53
Retrocesso
Testes 90 +1+3+2+5 = 101
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
Retrocessos 3
54
Retrocesso
Testes 101+1+5+2+4+3+6= 122
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
Retrocessos 3
55
Retrocesso
Falha
8
Retrocede
7
Testes 122+1+5+2+6+3+6+4+1= 150
1 Junho 2005
Retrocessos 3+1=4
Seminários de Informática – Pesquisa e Optimização
56
Retrocesso
Falha
7
Retrocede
6
Testes 150+1+2= 153
1 Junho 2005
Retrocessos 4+1=5
Seminários de Informática – Pesquisa e Optimização
57
Retrocesso
Falha
6
Retrocede
5
Testes 153+3+1+2+3= 162
1 Junho 2005
Retrocessos 5+1=6
Seminários de Informática – Pesquisa e Optimização
58
Retrocesso
Testes 162+2+4= 168
1 Junho 2005
Retrocessos 6+1=7
Seminários de Informática – Pesquisa e Optimização
59
Retrocesso
Falha
6
Retrocede
5
Testes 168+1+3+2+5+3+1+2+3= 188
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
Retrocessos 7
60
Retrocesso
Falha
5
Retrocede
4
Testes 188+1+2+3+4= 198
1 Junho 2005
Retrocessos 7+1=8
Seminários de Informática – Pesquisa e Optimização
61
Retrocesso
Testes 198 + 3 = 201
1 Junho 2005
Retrocessos 8+1=9
Seminários de Informática – Pesquisa e Optimização
62
Retrocesso
Testes 201+1+4 = 206
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
Retrocessos 9
63
Retrocesso
Testes 206+1+3+2+5 = 217
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
Retrocessos 9
64
Retrocesso
Testes 217+1+5+2+5+3+6 = 239
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
Retrocessos 9
65
Retrocesso
Falha
8
Retrocede
7
Testes 239+1+5+2+4+3+6+7+7= 274
1 Junho 2005
Retrocessos 9+1=10
Seminários de Informática – Pesquisa e Optimização
66
Retrocesso
Falha
7
Retrocede
6
Testes 274+1+2= 277
1 Junho 2005
Retrocessos 10+1=11
Seminários de Informática – Pesquisa e Optimização
67
Retrocesso
Falha
6
Retrocede
5
Testes 277+3+1+2+3= 286
1 Junho 2005
Retrocessos 11+1=12
Seminários de Informática – Pesquisa e Optimização
68
Retrocesso
Testes 286+2+4= 292
1 Junho 2005
Retrocessos 12
Seminários de Informática – Pesquisa e Optimização
69
Retrocesso
Falha
6
Retrocede
5
Testes 292+1+3+2+5+3+1+2+3= 312
1 Junho 2005
Retrocessos 12+1=13
Seminários de Informática – Pesquisa e Optimização
70
Retrocesso
Falha
5
Retrocede
4e3
Testes 312+1+2+3+4= 322
1 Junho 2005
Retrocessos 13+2=15
Seminários de Informática – Pesquisa e Optimização
71
Retrocesso
X1=1
X2=3
X3=5
Impossível
Testes 322 + 2 = 324
1 Junho 2005
Retrocessos 15
Seminários de Informática – Pesquisa e Optimização
72
Olhar para Trás ou para a Frente?
• Nesta altura da pesquisa determinou-se que não se podem
construir soluções a partir da solução “parcial”
Q1 = 1, Q2 =3 , Q3 = 5
• Para essa determinação foram feitos
– 15 Retrocessos de valores de variáveis
– 324 testes de verificação
• De notar que nesta pesquisa foi tida em consideração
apenas as atribuições passadas de valores a variáveis.
• Na realidade, é geralmente mais favorável “olhar” para a
frente, isto é, para as variáveis futuras, que ainda não têm
valores atribuídos.
• Esse é o objectivo da “propagação de restrições”.
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
73
Propagação de Restrições
• O objectivo da propagação de restrições é o de retirar do
domínio das variáveis futuras os valores que são
contraditórios com as atribuições já efectuadas.
• Por exemplo, se a primeira rainha for colocada na posição
mais à esquerda (Q1 = 1), podem retirar-se o valor 1 do
domínio das outras variáveis, já que colocariam as
respectivas rainhas na mesma coluna!
• Os valores incompatíveis por estarem nas mesmas
diagonais devem ser igualmente eliminados.
• Este mecanismo de propagação de restrições pode ser
igualmente ilustrado para as 8 rainhas.
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
74
Propagação
Testes 0
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
Retrocessos 0
75
Propagação
Q1 #\= Q2,
1
Q1+1 #\= Q2+2,
Q1-1 #\= Q2-2.
1
1
1
1
1
1
1
1
1
1
1
1
Testes 8 * 7 = 56
1 Junho 2005
1
Seminários de Informática – Pesquisa e Optimização
Retrocessos 0
76
Propagação
1
1
1
2
1
2
1
2
1
1
2
1
2
1
2
1
2
Testes 56 + 6 * 6 = 92
1 Junho 2005
2
1
2
1
2
1
Seminários de Informática – Pesquisa e Optimização
2
1
Retrocessos 0
77
Propagação
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
Testes 92 + 4 * 5 = 112
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
1
Retrocessos 0
78
Propagação de Restrições
• Neste ponto vale a pena precisar uma outra forma de
propagação de restrições.
• Para além de retirar valores incompatíveis com valores já
atribuídos (consistência de nó), podem ser retirados
valores do domínio de variáveis que não tenham suporte no
domínio de outras variáveis.
• Por exemplo consideremos as variáveis A e B, com domínio
{1,2,3,4} e a restrição A > B. Neste caso,
– A não pode ser 1, pois não há valor de B tal que B <1.
– B não pode ser 4, pois não há valor de A tal queA > 4.
• A propagação de restrições neste caso, mantendo a
consistência de arco, reduz os domínios para DA = {2,3,4}
e DA = {1,2,3}.
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
79
Redes de Restrições
• Um problema de satisfação de restrições pode ser
modelado através de um grafo (ou rede) de restrições em
que os nós são as variáveis e os arcos as restrições.
• Por exemplo, o problema das 4 rainhas pode ser modelado
através da seguinte rede
Q1 in 1..4
≠
≠
≠
Q2 in 1..4
≠
≠
1 Junho 2005
Q3 in 1..4
≠
Q4 in 1..4
Seminários de Informática – Pesquisa e Optimização
80
Redes de Restrições
• Para manter consistência de arco pode assim olhar-se para
cada arco e analisar os domínios das variáveis nos seus
extremos.
• Podemos analisar a situação na continuação do problema
das 8 rainhas.
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
81
Propagação 2
Q6 só pode
tomar o valor
4
1
1
1
2
Retirar valores
incompatíveis
nas outras
variáveis
1 Junho 2005
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
Seminários de Informática – Pesquisa e Optimização
1
82
Propagação 2
1
1
1
2
1
2
1
6
2
1
2
3
2
6
1
2
3
3
1
2
3
1
2
1
1
3
1
1
1 Junho 2005
6
2
2
6
3
2
6
3
6
Seminários de Informática – Pesquisa e Optimização
1
83
Propagação 2
Agora é Q8
que só pode
tomar o
valor 7
1
1
1
2
1
2
1
6
2
1
2
3
2
6
1
2
3
3
1
2
3
1
2
1
1
3
1
1
1 Junho 2005
6
2
2
6
3
2
6
3
6
Seminários de Informática – Pesquisa e Optimização
1
84
Propagação 2
Retiremos pois
os valores
incompatíveis
1
1
1
2
1
2
1
6
2
1
2
3
8
2
6
1
2
3
3
1
2
3
1
2
1
1
3
1
1
1 Junho 2005
6
2
2
6
3
8
2
6
3
6
Seminários de Informática – Pesquisa e Optimização
1
85
Propagação 2
Q4 só pode
tomar o
valor 8
1
1
1
2
1
2
1
6
2
1
2
3
8
2
6
1
2
3
4
3
1
2
3
1
2
1
1
3
1
1
1 Junho 2005
6
2
2
6
3
8
2
6
3
6
Seminários de Informática – Pesquisa e Optimização
1
86
Propagação 2
Propagando
verifica-se
que Q5 só
pode tomar
o valor 2
1
1
1
2
1
2
1
6
2
1
2
3
8
2
6
1
2
3
4
3
1
2
3
1
2
1
1
3
1
1
1 Junho 2005
6
2
2
6
3
8
2
6
3
6
Seminários de Informática – Pesquisa e Optimização
1
87
Propagação 2
Mas agora
Q7 não
pode tomar
nenhum
valor!
1
1
1
2
1
2
1
6
2
1
2
3
8
2
6
1
2
3
4
3
1
2
3
1
2
1
1
3
1
1
1 Junho 2005
6
2
2
6
3
8
2
6
3
6
Seminários de Informática – Pesquisa e Optimização
1
88
Propagação 2
Há que
retroceder
para a
última
rainha
atribuída,
Q3.
1 Junho 2005
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
Seminários de Informática – Pesquisa e Optimização
1
89
Heurísticas – First Fail
• No caso de restrições de diferença, só faz sentido a sua
propagação se uma das variáveis tiver um só valor no
domínio.
• Mas nessa situação, é mais conveniente utilizar esse facto
através da heurística first-fail.
• Em geral a heurística indica que se devem tratar primeiro
as situações mais difíceis, que não se podem evitar.
• Em particular, enter atribuir valores a uma variável com 8
valores no domínio e outra com apenas 2 é mais difícil
atribuir valores a esta (são menos valores).
• No caso em causa, se uma variável só tem um valor no
domínio há que atribuir imediatamente esse valor !
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
90
Propagação 2
Q6 só pode
tomar o
valor 4
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
Testes 92 + 4 * 5 = 112
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
1
Retrocessos 0
91
Propagação 2
1
1
1
2
1
2
1
6
2
1
2
3
2
6
1
2
3
3
1
2
3
1
2
1
1
3
1
1
6
2
2
6
3
2
6
3
Testes 112+3+3+3+4 = 125
1 Junho 2005
6
Seminários de Informática – Pesquisa e Optimização
1
Retrocessos 0
92
Propagação 2
Q8 só pode
tomar o
valor 7
1
1
1
2
1
2
1
6
2
1
2
3
2
6
1
2
3
3
1
2
3
1
2
1
1
3
1
1
Testes 125
1 Junho 2005
6
2
2
6
3
2
2
3
6
Seminários de Informática – Pesquisa e Optimização
1
Retrocessos 0
93
Propagação 2
1
1
1
2
1
2
1
6
2
1
2
3
2
6
1
2
3
3
1
2
3
1
2
1
1
3
1
1
Testes 125
1 Junho 2005
6
2
2
6
3
2
2
3
6
Seminários de Informática – Pesquisa e Optimização
1
Retrocessos 0
94
Propagação 2
1
1
1
2
1
2
1
6
2
1
2
3
8
2
6
1
2
3
3
1
2
3
1
2
1
1
3
1
1
6
2
2
6
3
8
2
2
3
6
Testes 125+2+2+2=131
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
1
Retrocessos 0
95
Propagação 2
Q4 só pode
tomar o
valor 8
1
1
1
2
1
2
1
6
2
1
2
3
8
2
6
1
2
3
3
1
2
3
1
2
1
1
3
1
1
Testes 131
1 Junho 2005
6
2
2
6
3
8
2
2
3
6
Seminários de Informática – Pesquisa e Optimização
1
Retrocessos 0
96
Propagação 2
1
1
1
2
1
2
1
6
2
1
2
3
8
2
6
1
2
3
3
1
2
3
1
2
1
1
3
1
1
Testes 131
1 Junho 2005
6
2
2
6
3
8
2
2
3
6
Seminários de Informática – Pesquisa e Optimização
1
Retrocessos 0
97
Propagação 2
1
1
1
2
1
2
1
6
2
1
2
3
8
2
6
1
2
3
4
3
1
2
3
1
2
1
1
3
1
1
6
2
2
6
3
8
2
2
3
6
Testes 131+2+2=135
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
1
Retrocessos 0
98
Propagação 2
Q5 só pode
tomar o
valor 2
1
1
1
2
1
2
1
6
2
1
2
3
8
2
6
1
2
3
4
3
1
2
3
1
2
1
1
3
1
1
Testes 135
1 Junho 2005
6
2
2
6
3
8
2
2
3
6
Seminários de Informática – Pesquisa e Optimização
1
Retrocessos 0
99
Propagação 2
1
1
1
2
1
2
1
6
2
1
2
3
8
2
6
1
2
3
4
3
1
2
3
1
2
1
1
3
2
1
5
2
6
3
8
1
6
2
2
3
6
Testes 135+1=136
1 Junho 2005
1
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
100
Propagação 2
1
1
Falha
1
2
1
2
7
1
6
2
1
2
3
8
Retrocede
1
2
6
1
2
3
4
3
1
2
3
1
2
3!
1
3
2
1
5
2
6
3
8
1
6
2
2
3
6
Testes 136
1 Junho 2005
1
Retrocessos 0
Seminários de Informática – Pesquisa e Optimização
101
Eficiência da Propagação c/ First -Fail
• Nesta altura da pesquisa determinou-se que não se podem
construir soluções a partir da solução “parcial”
Q1 = 1, Q2 =3 , Q3 = 5
• De notar que com retrocesso puro tal conclusão foi tirada
após se terem efectuado
– 15 retrocessos de valores de variáveis
– 324 testes de verificação
• Neste caso, a combinação de propagação de restrições
(simples – consistência de nó) com heurística permitiu
chegar à mesma conclusão com
– 0 retrocessos de valores de variáveis
– 136 testes de verificação
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
102
Outros Métodos de Propagação
• Existem métodos mais “fortes” de propagação, tais como a
manutenção da consistência de caminho
• Exemplo:
{0,1}
≠
≠
{0,1}
≠
{0,1}
• A impossibilidade deste problema não é obtida por
manutenção de consistência de arco, mas é-o por
consistência de caminho.
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
103
Restrições Globais
• Em geral quanto mais forte é a propagação mais pesada é
a sua implementação.
• Existem alguns casos particulares de restrições,
envolvendo “muitas” variáveis, que têm métodos de
resolução muito apropriados e que podem ser integrados
nas linguagens de resolução destes problemas.
• Este é o caso da restrição all_different([X1,X2,X3]) que
não usando consistência de arco consegue detectar a
inconsitência do problema anterior.
• Outra restrição global importante é a restrição
cumulative, útil para problemas de alocação de recursos.
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
104
Restrições Globais - Cumulative
• História: Uma instância 10*10 do problema de Job-shop
foi proposta no livro Industrial Scheduling [MuTh63].
• Durante 30 anos, não foi encontrada nenhuma solução
óptima para o “makespan” (terminação mais rápida da
última tarefa). Melhor solução era 935 unidades de
tempo.
• Em 1985, tinha sido provado que não havia solução com
menos de 930 unidades de tempo..
• Em 1987, o problema foi resolvido com um algoritmo
altamente especializado, que decobriu uma solução com
930 unidades de tempo, após algumas horas de execução.
• Com a restrição “cumulative”, o problema foi resolvido em
1993 em 1506 segundos (numa SUN/SPARC) !
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
105
Métodos Reparativos – Pesquisa Local
• Um método alternativo de resolução corresponde a partir
de uma “solução” qualquer e ir reparando-a para obter
outra melhor.
• Este método é útil para problemas de optimização em que
há várias soluções possíveis, embora não óptimas.
• Em problemas de satisfação, pode tentar minimizar-se o
número de restrições violadas.
• Para ser utilizável há que definir:
– Quais os vizinhos de uma solução
– Qual o vizinho a escolher
• No caso das rainhas os vizinhos são obtidos por troca de
duas rainhas, de preferência envolvidas em restrições
violadas, como ilustrado de seguida.
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
106
Pesquisa Local - Reparação
4
7
Solução
1
Permutação
6
3
Vizinhança
5
Troca
8
2
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
107
Pesquisa Local - Reparação
4
7
1
2 Ataques
6
3-5
3
4-8
5
8
2
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
108
Pesquisa Local - Reparação
4
7
1 2
2 Ataques
6
3-5
3
4-8
5
8
2 1
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
109
Pesquisa Local - Reparação
4
7
2
3 Ataques
6
1-3
3
2-8
5
3-6
8
1
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
110
Pesquisa Local - Reparação
4 1
7
2
3 Ataques
6
1-3
3
2-8
5
3-6
8
1 4
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
111
Pesquisa Local - Reparação
1
7
2
1 Ataque
6
3-6
3
5
8
4
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
112
Pesquisa Local - Reparação
1
7
28
1 Ataque
6
3-6
3
5
8 2
4
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
113
Pesquisa Local - Reparação
1
7
8
3 Ataques
6
2-3
3
2-7
5
3-6
2
4
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
114
Pesquisa Local - Reparação
1
75
8
3 Ataques
6
2-3
3
2-7
57
3-6
2
4
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
115
Pesquisa Local - Reparação
1
5
0 Ataques
8
6
3
7
2
4
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
116
Métodos Reparativos – Pesquisa Local
• Estes métodos têm em geral o problema de fugir dos
óptimos locais, tal como acontecem neste caso.
2
3 1 3
0
• Por vezes, é necessário escolher um vizinho pior!
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
117
Métodos Reparativos – Pesquisa Local
• Para escapar a óptimos locais existem várias técnicas:
– Recomeços aleatórios
– Simulated Annealing
– Tabu Search
– Algoritmos Genéticos
• Um outro problema com estes métodos, relacionado com o
anterior, é não serem completos, isto é descobrem
óptimos locais, mas não o óptimo global.
• No entanto, para os problemas mais complexos não há
esperança de obter a solução óptima!
• Existe ainda a possibilidade de hibridizar os métodos
reparativos com métodos construtivos!
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
118
Disciplinas da LEI
• Algoritmos e Estruturas de Dados
– Pesquisa em árvore
• Métodos Quantitativos
– Problemas de decisão
• Programação em Lógica
– Paradigma de Programação que inclui o retrocesso
• Programação por Restrições
– Estende o paradigma para propagação de restrições
• Bases de Dados e DataWareHousing
– Integração de dados em Sistemas de Informação que podem ser
posteriormente utilizados nestes modelos
1 Junho 2005
Seminários de Informática – Pesquisa e Optimização
119