Aplicação do Algoritmo de
Dijkstra - Matching
3ª reunião do Grupo de Estudos – UP&D
Fernando Sales e Danilo Lage
22 de fev de 2008
Enunciado do Problema
Idéias Iniciais
Curva 1
Curva 2
1
1
2
2
3
4
5
3
6
7
8
4
9
10
11
12
• Condições do problema:
– n(1) < n(2);
• Obs:
– n(1) = n(2): trivial;
– n(1) > n(2): raciocínio análogo ao caso n(1) < n(2), basta “inverter” as curvas;
– Ligações não podem se cruzar;
Construção do Grafo
0
0
1
1
2
1
3
1
4
1
1
2
2
2
3
2
4
2
1
3
2
3
3
3
4
3
2
12
: Nó Inicial
3
12
i
j
Ex: Seja i =1.
Então, temos: j(max) = 09 [12 – 4+1].
...
...
0
0
...
...
1
12
• Condições de Contorno:
– Ramos: j prox  jant
4
12
i: Curva 1
j: Curva 2
=|k(i)-k(j)|
– Nós:
• 1 por coluna;
Construção do Grafo
Esboço:
1
Curva 2
2
3
4
5
6
7
8
9
10 11 12
Curva 1
1
2
3
4
i
Custo do Ramo:
i
j
=|k(i)-k(j)|
j
Matriz de Custos
 a11




 
a12
a13
a14
a22

a23
a33
a24
a34


a44
a19
a29

a210


a39
a310
a311
a49
a410
a411
 

 
 

a412 
Para o i-ésimo elemento, temos o intervalo dos nós possíveis: [a,b]
a: max {i, col(i-1) +1}
b: min {n2 – n1 + i, col(i-1) +1}
, se : i  j ou j  n2  n1  i
aij  
 k (i )  k ( j ) , c.c.
i 1, n1 
j 1, n2 
Proposta
1. Dadas as curvas, cria-se a matriz de custos;
2. Constrói-se o grafo;
3. Inicia-se o algoritmo de Dijkstra, no entanto, a
determinação dos ramos será feita através das
restrições dadas no slide anterior;
4. O caminho fornecido deverá ser o ótimo,
dadas as restrições;
Conclusões
• Abordagem válida para: n1 < n2;
– Se n1 > n2: “trocar” as curvas;
– Se n1 = n2: problema trivial;
• Restrições devem ser inseridas/computadas no
momento da seleção dos possíveis ramos;
• Generalização do algoritmo:
– Construção do grafo;
– Cálculo dos custos;
– Seleção dos vizinhos;