Embed Size (px)
Citation preview
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Defesa de dissertação de mestradok -menores caminhos
Fábio Pisaruk
Instituto de Matemática e EstatísticaUniversidade de São Paulo
16 de Julho de 2009
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Sumário
1 Motivação
2 k -menores caminhos
3 Partições
4 YEN
5 KIM
6 Implementação
7 Conclusões
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema
Provisionamento de sinais
Serviço de interligação de sinais.Permite que sinais do ponto a sejam enviados ao ponto b.
Figura: Destacamos um possível caminho interligando a e b.
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema
Processo de provisionamento
Requisitos do clienteQuantidade de sinais.Tipos de sinais.Origem e destino.Qualidade de serviço.
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema
Processo de provisionamento
ConsideraçõesCusto é função do número de equipamentos usados.Número de caminhos depende da quantidade de sinais.Critério de desempate é a distância total.
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Definição
Problema k -menores caminhos
Problema k-MC(V ,A, c, s, t , k):Dados:
Grafo: (V ,A)Função custo: cVértices: s e tInteiro positivo: k
Encontrar os k-menores caminhos de s a t.
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Definição
Exemplo
sb
g l tt
f
e
h
i
c
a
j
d
Caminhos
〈s,a, i , t〉〈s,b, f , l , t〉〈s,b,g, l , t〉〈s,b,h, l , t〉〈s,b,h, i , t〉〈s,a, i ,h, l , t〉
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Definição
Exemplo
sb
g l tt
f
e
h
i
c
a
j
d
Caminhos〈s,a, i , t〉
〈s,b, f , l , t〉〈s,b,g, l , t〉〈s,b,h, l , t〉〈s,b,h, i , t〉〈s,a, i ,h, l , t〉
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Definição
Exemplo
sb
g l tt
f
e
h
i
c
a
j
d
Caminhos〈s,a, i , t〉〈s,b, f , l , t〉
〈s,b,g, l , t〉〈s,b,h, l , t〉〈s,b,h, i , t〉〈s,a, i ,h, l , t〉
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Definição
Exemplo
sb
g l tt
f
e
h
i
c
a
j
d
Caminhos〈s,a, i , t〉〈s,b, f , l , t〉〈s,b,g, l , t〉
〈s,b,h, l , t〉〈s,b,h, i , t〉〈s,a, i ,h, l , t〉
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Definição
Exemplo
sb
g l tt
f
e
h
i
c
a
j
d
Caminhos〈s,a, i , t〉〈s,b, f , l , t〉〈s,b,g, l , t〉〈s,b,h, l , t〉
〈s,b,h, i , t〉〈s,a, i ,h, l , t〉
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Definição
Exemplo
sb
g l tt
f
e
h
i
c
a
j
d
Caminhos〈s,a, i , t〉〈s,b, f , l , t〉〈s,b,g, l , t〉〈s,b,h, l , t〉〈s,b,h, i , t〉
〈s,a, i ,h, l , t〉
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Definição
Exemplo
sb
g l tt
f
e
h
i
c
a
j
d
Caminhos〈s,a, i , t〉〈s,b, f , l , t〉〈s,b,g, l , t〉〈s,b,h, l , t〉〈s,b,h, i , t〉〈s,a, i ,h, l , t〉
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Soluções
Algoritmo existente na empresaBusca exaustiva
Consumo elevado de memória.
a c
b
d
e
〈a,b〉〈a, c〉〈a,d〉
〈a,b, c〉〈a,b,e〉〈a, c,b〉〈a, c,e〉〈a, c,d〉〈a,d , c〉〈a,d ,e〉
〈a,b, c,e〉〈a,b, c,d〉〈a, c,b,e〉〈a, c,d ,e〉〈a,d , c,e〉〈a,d , c,b〉
〈a,b, c,d ,e〉〈a,d , c,b,e〉
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Soluções
Algoritmo existente na empresaBusca exaustiva
Consumo elevado de memória.
a c
b
d
e
〈a,b〉〈a, c〉〈a,d〉
〈a,b, c〉〈a,b,e〉〈a, c,b〉〈a, c,e〉〈a, c,d〉〈a,d , c〉〈a,d ,e〉
〈a,b, c,e〉〈a,b, c,d〉〈a, c,b,e〉〈a, c,d ,e〉〈a,d , c,e〉〈a,d , c,b〉
〈a,b, c,d ,e〉〈a,d , c,b,e〉
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Soluções
Algoritmo existente na empresaBusca exaustiva
Consumo elevado de memória.
a c
b
d
e
〈a,b〉〈a, c〉〈a,d〉
〈a,b, c〉〈a,b,e〉〈a, c,b〉〈a, c,e〉〈a, c,d〉〈a,d , c〉〈a,d ,e〉
〈a,b, c,e〉〈a,b, c,d〉〈a, c,b,e〉〈a, c,d ,e〉〈a,d , c,e〉〈a,d , c,b〉
〈a,b, c,d ,e〉〈a,d , c,b,e〉
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Soluções
Algoritmo existente na empresaBusca exaustiva
Consumo elevado de memória.
a c
b
d
e
〈a,b〉〈a, c〉〈a,d〉
〈a,b, c〉〈a,b,e〉〈a, c,b〉〈a, c,e〉〈a, c,d〉〈a,d , c〉〈a,d ,e〉
〈a,b, c,e〉〈a,b, c,d〉〈a, c,b,e〉〈a, c,d ,e〉〈a,d , c,e〉〈a,d , c,b〉
〈a,b, c,d ,e〉〈a,d , c,b,e〉
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Soluções
Algoritmo existente na empresaBusca exaustiva
Consumo elevado de memória.
a c
b
d
e
〈a,b〉〈a, c〉〈a,d〉
〈a,b, c〉〈a,b,e〉〈a, c,b〉〈a, c,e〉〈a, c,d〉〈a,d , c〉〈a,d ,e〉
〈a,b, c,e〉〈a,b, c,d〉〈a, c,b,e〉〈a, c,d ,e〉〈a,d , c,e〉〈a,d , c,b〉
〈a,b, c,d ,e〉〈a,d , c,b,e〉
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Soluções
Algoritmo existente na empresaBusca exaustiva
Consumo elevado de memória.
a c
b
d
e
〈a,b〉〈a, c〉〈a,d〉
〈a,b, c〉〈a,b,e〉〈a, c,b〉〈a, c,e〉〈a, c,d〉〈a,d , c〉〈a,d ,e〉
〈a,b, c,e〉〈a,b, c,d〉〈a, c,b,e〉〈a, c,d ,e〉〈a,d , c,e〉〈a,d , c,b〉
〈a,b, c,d ,e〉〈a,d , c,b,e〉
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Soluções
Primeiro algoritmo implementadoBusca em profundidade iterativa
a c
b
d
e
nível 1
nível 2〈a,b,e〉〈a, c,e〉〈a,d ,e〉
nível 3〈a,b, c,e〉〈a, c,b,e〉〈a, c,d ,e〉〈a,d , c,e〉
nível 4〈a,b, c,d ,e〉〈a,d , c,b,e〉
Menor consumo de memória e maior consumo de processador.
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Soluções
Primeiro algoritmo implementadoBusca em profundidade iterativa
a c
b
d
e
nível 1 nível 2〈a,b,e〉〈a, c,e〉〈a,d ,e〉
nível 3〈a,b, c,e〉〈a, c,b,e〉〈a, c,d ,e〉〈a,d , c,e〉
nível 4〈a,b, c,d ,e〉〈a,d , c,b,e〉
Menor consumo de memória e maior consumo de processador.
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Soluções
Primeiro algoritmo implementadoBusca em profundidade iterativa
a c
b
d
e
nível 1 nível 2〈a,b,e〉〈a, c,e〉〈a,d ,e〉
nível 3〈a,b, c,e〉〈a, c,b,e〉〈a, c,d ,e〉〈a,d , c,e〉
nível 4〈a,b, c,d ,e〉〈a,d , c,b,e〉
Menor consumo de memória e maior consumo de processador.
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Soluções
Primeiro algoritmo implementadoBusca em profundidade iterativa
a c
b
d
e
nível 1 nível 2〈a,b,e〉〈a, c,e〉〈a,d ,e〉
nível 3〈a,b, c,e〉〈a, c,b,e〉〈a, c,d ,e〉〈a,d , c,e〉
nível 4〈a,b, c,d ,e〉〈a,d , c,b,e〉
Menor consumo de memória e maior consumo de processador.
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Soluções
Primeiro algoritmo implementadoBusca em profundidade iterativa
a c
b
d
e
nível 1 nível 2〈a,b,e〉〈a, c,e〉〈a,d ,e〉
nível 3〈a,b, c,e〉〈a, c,b,e〉〈a, c,d ,e〉〈a,d , c,e〉
nível 4〈a,b, c,d ,e〉〈a,d , c,b,e〉
Menor consumo de memória e maior consumo de processador.
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Soluções
Método genérico
Método GENÉRICO (V ,A, c, s, t , k)
0 P ← conjunto dos caminhos de s a t
1 para i = 1, . . . , k faça
2 Pi ← caminho de custo mínimo em P
3 P ← P − Pi
4 devolva 〈P1, . . . ,Pk 〉
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Soluções
P
P1 P2
P3 P4 P5
Pk Pk+1 . . .
Q
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Soluções
P
P2
P3
P4
P5
Pk
Pk+1
. . .
Q
P1
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Soluções
P
P3 P4 P5
Pk Pk+1 . . .
Q
P1 P2
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Soluções
P
Pk+1 . . .
Q
P1
P2
P3
P4
P5
. . .
Pk
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo de construção
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
g
l
t3
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
i
t5
s
a
i
t1h
l
t6
b
f
l
t2
g
l
t3
h
l
t4
i
t5
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo de construção
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
g
l
t3
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
i
t5
s
a
i
t1h
l
t6
b
f
l
t2
g
l
t3
h
l
t4
i
t5
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo de construção
sb
g l tt
f
e
h
i
c
a
jd s
a
i
t1
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
g
l
t3
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
i
t5
s
a
i
t1h
l
t6
b
f
l
t2
g
l
t3
h
l
t4
i
t5
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo de construção
sb
g l tt
f
e
h
i
c
a
jd s
a
i
t1
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
g
l
t3
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
i
t5
s
a
i
t1h
l
t6
b
f
l
t2
g
l
t3
h
l
t4
i
t5
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo de construção
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
g
l
t3
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
i
t5
s
a
i
t1h
l
t6
b
f
l
t2
g
l
t3
h
l
t4
i
t5
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo de construção
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
g
l
t3
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
i
t5
s
a
i
t1h
l
t6
b
f
l
t2
g
l
t3
h
l
t4
i
t5
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo de construção
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
g
l
t3
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
i
t5
s
a
i
t1h
l
t6
b
f
l
t2
g
l
t3
h
l
t4
i
t5
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo de construção
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
g
l
t3
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
i
t5
s
a
i
t1h
l
t6
b
f
l
t2
g
l
t3
h
l
t4
i
t5
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo de construção
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
g
l
t3
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
i
t5
s
a
i
t1h
l
t6
b
f
l
t2
g
l
t3
h
l
t4
i
t5
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo de construção
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
g
l
t3
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
i
t5
s
a
i
t1h
l
t6
b
f
l
t2
g
l
t3
h
l
t4
i
t5
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo de construção
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
g
l
t3
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
i
t5
s
a
i
t1h
l
t6
b
f
l
t2
g
l
t3
h
l
t4
i
t5
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo de construção
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
g
l
t3
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
i
t5
s
a
i
t1h
l
t6
b
f
l
t2
g
l
t3
h
l
t4
i
t5
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo de construção
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
g
l
t3
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
i
t5
s
a
i
t1h
l
t6
b
f
l
t2
g
l
t3
h
l
t4
i
t5
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo de construção
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
g
l
t3
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
i
t5
s
a
i
t1h
l
t6
b
f
l
t2
g
l
t3
h
l
t4
i
t5
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Questões
k é, potencialmente, exponencial no número de vértices
um grafo completo com 15 vértices possui 16.926.797.485de caminhos entre dois vértices fixadosparticionar os caminhos utilizando a árvore dos prefixos
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Questões
k é, potencialmente, exponencial no número de vérticesum grafo completo com 15 vértices possui 16.926.797.485de caminhos entre dois vértices fixados
particionar os caminhos utilizando a árvore dos prefixos
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Questões
k é, potencialmente, exponencial no número de vérticesum grafo completo com 15 vértices possui 16.926.797.485de caminhos entre dois vértices fixadosparticionar os caminhos utilizando a árvore dos prefixos
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
DescriçãoQ: coleção de caminhos(N,E , f ): árvore dos prefixos de QPara cada nó u da árvore temos uma partição πu
Π = {πu,u ∈ (N,E , f )}
Partição πu
caminhos com ponta inicial na raizcompartilham o prefixo f (Ru)
não possuem arcos em Au
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Π contém todos os caminhos de s a t
Π
P1 P2
P3 P4 P5
Pk Pk+1 . . .
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Q ← P1 = 〈s,a, i , t〉
Π
πs
πa πi
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Q ← 〈s,a, i , t〉 ∪ 〈s,b, f , l , t〉
Ππs
πa πi
πb πl
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
b...
t
a
i
t1
c
...
t
s
a
i
t1h
...
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
...
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
...
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
...
t
s
a
i
t1
b
f
l
g
...
t
t2
h...
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
b...
t
a
i
t1
c
...
t
s
a
i
t1h
...
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
...
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
...
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
...
t
s
a
i
t1
b
f
l
g
...
t
t2
h...
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo
sb
g l tt
f
e
h
i
c
a
jds
a
i
t1
s
b...
t
a
i
t1
c
...
t
s
a
i
t1h
...
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
...
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
...
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
...
t
s
a
i
t1
b
f
l
g
...
t
t2
h...
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo
sb
g l tt
f
e
h
i
c
a
jds
a
i
t1
s
b...
t
a
i
t1
c
...
t
s
a
i
t1h
...
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
...
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
...
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
...
t
s
a
i
t1
b
f
l
g
...
t
t2
h...
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo
sb
g l tt
f
e
h
i
c
a
jds
a
i
t1
s
b...
t
a
i
t1
c
...
t
s
a
i
t1h
...
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
...
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
...
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
...
t
s
a
i
t1
b
f
l
g
...
t
t2
h...
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo
sb
g l tt
f
e
h
i
c
a
jds
a
i
t1
s
b...
t
a
i
t1
c
...
t
s
a
i
t1h
...
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
...
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
...
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
...
t
s
a
i
t1
b
f
l
g
...
t
t2
h...
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
b...
t
a
i
t1
c
...
t
s
a
i
t1h
...
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
...
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
...
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
...
t
s
a
i
t1
b
f
l
g
...
t
t2
h...
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
b...
t
a
i
t1
c
...
t
s
a
i
t1h
...
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
...
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
...
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
...
t
s
a
i
t1
b
f
l
g
...
t
t2
h...
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
b...
t
a
i
t1
c
...
t
s
a
i
t1h
...
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
...
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
...
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
...
t
s
a
i
t1
b
f
l
g
...
t
t2
h...
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
b...
t
a
i
t1
c
...
t
s
a
i
t1h
...
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
...
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
...
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
...
t
s
a
i
t1
b
f
l
g
...
t
t2
h...
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
b...
t
a
i
t1
c
...
t
s
a
i
t1h
...
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
...
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
...
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
...
t
s
a
i
t1
b
f
l
g
...
t
t2
h...
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
s
b...
t
a
i
t1
c
...
t
s
a
i
t1h
...
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
...
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
...
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
...
t
s
a
i
t1
b
f
l
g
...
t
t2
h...
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
Método YEN-GENÉRICO
Método YEN-GENÉRICO (V ,A, c, s, t , k)
0 Π← {conjunto dos caminhos de s a t}
1 Q ← ∅
2 para i = 1, . . . , k faça
3 L ← {Pπ : Pπ é caminho mínimo na parte π de Π}
4 Pi ← caminho de custo mínimo em L
5 Q ← Q∪ {Pi}
6 Π← ATUALIZE-GENÉRICO (V ,A, s, t ,Q)
7 devolva 〈P1, . . . ,Pk 〉
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
ATUALIZE-GENÉRICO
Algoritmo ATUALIZE-GENÉRICO (V ,A, s, t ,Q)
0 Π← ∅ P ← Pst −Q
1 (N,E , f )← árvore dos prefixos de Q
2 para cada u ∈ N que não é uma folha faça
3 πu ← {caminhos em P com prefixo f (Ru)
e que não possuem arcos em Au}
4 Π← Π ∪ {πu}
5 devolva Π
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
Exemplo
sb
g l tt
f
e
h
i
c
a
jdf (Ru) = 〈s,b〉
Au
s
a
i
t1
f (u)=b
f
l
t2
g
l
t3
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
Exemplo
sb
g l tt
f
e
h
i
c
a
jdf (Ru) = 〈s,b〉
s
a
i
t1
f (u)=b
f
l
t2
g
l
t3
c
. . .
t
d
. . .
t
h
. . .
t
πu
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
Exemplo
sb
g l tt
f
e
h
i
c
a
jdf (Ru) = 〈s,b〉
s
a
i
t1
f (u)=b
f
l
t2
g
l
t3
c
. . .
t
d
. . .
t
h
l
t
πu
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1h
l
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
b
f
l
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
l
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
l
t
s
a
i
t1
b
f
l
g
...
t
t2
h
i
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1h
l
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
b
f
l
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
l
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
l
t
s
a
i
t1
b
f
l
g
...
t
t2
h
i
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
Exemplo
sb
g l tt
f
e
h
i
c
a
jds
a
i
t1
s
a
i
t1h
l
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
b
f
l
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
l
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
l
t
s
a
i
t1
b
f
l
g
...
t
t2
h
i
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
Exemplo
sb
g l tt
f
e
h
i
c
a
jds
b...
t
a
i
t1
c
...
t
s
a
i
t1h
l
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
b
f
l
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
l
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
l
t
s
a
i
t1
b
f
l
g
...
t
t2
h
i
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
Exemplo
sb
g l tt
f
e
h
i
c
a
jds
b
f
l
t
a
i
t1
c
...
t
s
a
i
t1h
l
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
b
f
l
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
l
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
l
t
s
a
i
t1
b
f
l
g
...
t
t2
h
i
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
Exemplo
sb
g l tt
f
e
h
i
c
a
jds
a
i
t1h
l
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
b
f
l
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
l
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
l
t
s
a
i
t1
b
f
l
g
...
t
t2
h
i
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1h
l
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
b
f
l
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
l
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
l
t
s
a
i
t1
b
f
l
g
...
t
t2
h
i
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1h
l
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
b
f
l
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
l
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
l
t
s
a
i
t1
b
f
l
g
...
t
t2
h
i
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1h
l
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
b
f
l
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
l
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
l
t
s
a
i
t1
b
f
l
g
...
t
t2
h
i
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1h
l
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
b
f
l
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
l
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
l
t
s
a
i
t1
b
f
l
g
...
t
t2
h
i
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1h
l
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
b
f
l
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
l
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
l
t
s
a
i
t1
b
f
l
g
...
t
t2
h
i
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de Yen
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1h
l
t
s
a
i
t1
b
f
l
t2
s
a
i
t1
b
f
l
t2
c
b
f
l
t
s
a
i
t1
b
c
...
t
d...
t
f
l
t2
g
l
t
h...
t
s
a
i
t1
b
f
e
...
t
l
t2
g
l
t
s
a
i
t1
b
f
l
g
...
t
t2
h
i
t
j
...
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de YEN
Método de YEN
Algoritmo YEN (V ,A, c, s, t , k)
1 P1 ← um caminho de custo mínimo de s a t
2 (N,E , f )← árvore dos prefixos de P1
3 para i = 2, . . . , k faça
4 Pi ← caminho de custo mínimo em L
5 (N,E , f ,L)←ATUALIZE-YEN (V ,A, c, s, t ,Pi ,N,E , f ,L)
6 devolva 〈P1, . . . ,Pk 〉
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de YEN
ATUALIZE-YEN
Algoritmo ATUALIZE-YEN (V ,A, c, s, t ,P,N ′,E ′, f ′,L′)
0 L ← L′ − {P}
1 RP ← maior caminho em (N ′,E ′) com ponta inicial na
raiz tal que QP := f (RP) é prefixo de P
2 (N,E , f )← ÁRVORE-DOS-PREFIXOS(N ′,E ′, f ′,P)
3 Seja f (〈u0, . . . ,uk , . . . ,uq〉) = P e RP = 〈u0, . . . ,uk 〉.
4 para cada u ∈ {uk , . . . ,uq−1} faça
5 Pu ← st-caminho de custo mínimo com prefixo f (Ru)e que não possui arcos em Au
6 L ← L ∪ {Pu}
7 devolva (N,E , f ,L)
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de YEN
Exemplo
sb
g l tt
f
e
h
i
c
a
jd f (Ru) = 〈s,b〉
Au
s
a
i
t1
f (u)=b
f
l
t2
g
l
t3
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Método de YEN
Exemplo
sb
g l tt
f
e
h
i
c
a
jd
s
a
i
t1
b
f
l
t2
g
l
t3
h
l
t4
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Algoritmo de Katoh, Ibaraki e Mine
Específico para grafos simétricos
Método eficiente para o problema do desvio mínimoDiminuição do número de caminhos candidatos gerados acada iteraçãoBaseado no método de YenPartições definidas apenas para nós com mais de um filhoDepende rotina para o problema CM: T (n,m)
Melhor desempenho assintótico: Θ(kT (n,m))
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Algoritmo de Katoh, Ibaraki e Mine
Específico para grafos simétricosMétodo eficiente para o problema do desvio mínimo
Diminuição do número de caminhos candidatos gerados acada iteraçãoBaseado no método de YenPartições definidas apenas para nós com mais de um filhoDepende rotina para o problema CM: T (n,m)
Melhor desempenho assintótico: Θ(kT (n,m))
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Algoritmo de Katoh, Ibaraki e Mine
Específico para grafos simétricosMétodo eficiente para o problema do desvio mínimoDiminuição do número de caminhos candidatos gerados acada iteração
Baseado no método de YenPartições definidas apenas para nós com mais de um filhoDepende rotina para o problema CM: T (n,m)
Melhor desempenho assintótico: Θ(kT (n,m))
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Algoritmo de Katoh, Ibaraki e Mine
Específico para grafos simétricosMétodo eficiente para o problema do desvio mínimoDiminuição do número de caminhos candidatos gerados acada iteraçãoBaseado no método de Yen
Partições definidas apenas para nós com mais de um filhoDepende rotina para o problema CM: T (n,m)
Melhor desempenho assintótico: Θ(kT (n,m))
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Algoritmo de Katoh, Ibaraki e Mine
Específico para grafos simétricosMétodo eficiente para o problema do desvio mínimoDiminuição do número de caminhos candidatos gerados acada iteraçãoBaseado no método de YenPartições definidas apenas para nós com mais de um filho
Depende rotina para o problema CM: T (n,m)
Melhor desempenho assintótico: Θ(kT (n,m))
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Algoritmo de Katoh, Ibaraki e Mine
Específico para grafos simétricosMétodo eficiente para o problema do desvio mínimoDiminuição do número de caminhos candidatos gerados acada iteraçãoBaseado no método de YenPartições definidas apenas para nós com mais de um filhoDepende rotina para o problema CM: T (n,m)
Melhor desempenho assintótico: Θ(kT (n,m))
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Algoritmo de Katoh, Ibaraki e Mine
Específico para grafos simétricosMétodo eficiente para o problema do desvio mínimoDiminuição do número de caminhos candidatos gerados acada iteraçãoBaseado no método de YenPartições definidas apenas para nós com mais de um filhoDepende rotina para o problema CM: T (n,m)
Melhor desempenho assintótico: Θ(kT (n,m))
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo árvore dos menores caminhos
a b
c
d
f
e1 1 1
10 10 1
1 1
a
b
d
e1
c1
1
f1
1
e
d
b
a1
1
c
1f
1
1
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo árvore dos menores caminhos
a b
c
d
f
e1 1 1
10 10 1
1 1
a
b
d
e1
c1
1
f1
1
e
d
b
a1
1
c
1f
1
1
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Exemplo árvore dos menores caminhos
a b
c
d
f
e1 1 1
10 10 1
1 1
a
b
d
e1
c1
1
f1
1
e
d
b
a1
1
c
1f
1
1
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Definição
Problema do desvio de custo mínimo (V ,A, c, s, t):Dados:
Grafo simétrico com custo: (V ,A, c)Vértices: s e tP = 〈s = a1, . . . ,an = t〉 um caminho de custo mínimode s a t
Encontrar um caminho de custo mínimo, diferente deP, entre s e t.
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Exemplo
s t
s δ
u ...
t
t
arco δu ∈ Ts
s −→Ts
u −→Tt
t
arco δu /∈ Ts
s −→Ts
u →∈A
v −→Tt
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Exemplo
s δ
u ...
t
t
arco δu ∈ Ts
s −→Ts
u −→Tt
t
arco δu /∈ Ts
s −→Ts
u →∈A
v −→Tt
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Exemplo
s δ
u ...
t
t
arco δu ∈ Ts
s −→Ts
u −→Tt
t
arco δu /∈ Ts
s −→Ts
u →∈A
v −→Tt
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Exemplo
s δ
u ...
t
t
arco δu ∈ Tss −→
Tsu −→
Ttt
arco δu /∈ Ts
s −→Ts
u →∈A
v −→Tt
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Exemplo
s δ
u ...
t
t
arco δu ∈ Tss −→
Tsu −→
Ttt
arco δu /∈ Tss −→
Tsu →∈A
v −→Tt
t
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Tipos de caminhos
Um novo caminho de custo mínimo construído através deu ∈ V é de um dos dois tipos definidos a seguir:
tipo I : s −→Ts
u −→Tt
t .
tipo II : s −→Ts
u →∈A
v −→Tt
t .
Ts uma árvore de menores caminhos com raiz em sTt uma árvore de menores caminhos com raiz em tPr = 〈t = an, . . . ,a1 = s〉P ∈ Ts e Pr ∈ Tt
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Desvio de custo mínimo
s b
c
d
f
t1 1 1
10 10 1
1 1
Tipo I
〈s,b, f ,d , t〉
Tipo II
〈s, c,d , t〉〈s,b, c,d , t〉
s
b
d
t1
c1
1
f1
1
t
d
b
s1
1
c
1f
1
1
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Desvio de custo mínimo
s b
c
d
f
t1
1 1
11
10 10 1
Tipo I〈s,b, f ,d , t〉
〈s,b, f ,d , t〉
Tipo II
〈s, c,d , t〉〈s,b, c,d , t〉
s
b
d
t1
c1
1
f1
1
t
d
b
s1
1
c
1f
1
1
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Desvio de custo mínimo
s b
c
d
f
t1 1 1
10 10 1
1 1
Tipo I〈s,b, f ,d , t〉
Tipo II〈s, c,d , t〉
〈s, c,d , t〉〈s,b, c,d , t〉
s
b
d
t1
c1
1
f1
1
t
d
b
s1
1
c
1f
1
1
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Desvio de custo mínimo
s b
c
d
f
t1 1 1
10 10 1
1 1
Tipo I〈s,b, f ,d , t〉
Tipo II〈s, c,d , t〉〈s,b, c,d , t〉
s
b
d
t1
c1
1
f1
1
t
d
b
s1
1
c
1f
1
1
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Rotulações ε e ζ
P = 〈a,b,d ,e〉
Rotulação ε
ε(a) = 1Se u ∈ P então ε(u) = ε(ψ(u)) + 1Se u /∈ P então ε(u) = ε(ψ(u))
a ε = 1
b 2
d 3
e4 c 3
f 2
Rotulação ζ
ζ(e) = |P|Se u ∈ P então ζ(u) = ζ(ψ(u))− 1Se u /∈ P então ζ(u) = ζ(ψ(u))
e ζ = 4
d 3
b2
a1
c 3f 3
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Desvio de custo mínimo com rotulações
s b
c
d
f
t1 1 1
10 10 1
1 1
Tipo I
〈s,b, f ,d , t〉
Tipo II
〈s,b, c,d , t〉
s ε = 1
b 2
d 3
t4
1
c 3
1
1
f 2
1
1
t ζ = 4
d 3
b2
s11
1
c 3
1f 3
1
1
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Desvio de custo mínimo com rotulações
s b
c
d
f
t1
1 1
11
10 10 1
Tipo I〈s,b, f ,d , t〉
〈s,b, f ,d , t〉
Tipo II
〈s,b, c,d , t〉
s ε = 1
b 2
d 3
t4
1
c 3
1
1
f 2
1
1
t ζ = 4
d 3
b2
s11
1
c 3
1f 3
1
1
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Desvio de custo mínimo com rotulações
s b
c
d
f
t1 1 1
10 10 1
1 1
Tipo I〈s,b, f ,d , t〉
Tipo II〈s, c,d , t〉
〈s,b, c,d , t〉
s ε = 1
b 2
d 3
t4
1
c 3
1
1
f 2
1
1
t ζ = 4
d 3
b2
s11
1
c 3
1f 3
1
1
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Desvio de custo mínimo com rotulações
s b
c
d
f
t1 1 1
10 10 1
1 1
Tipo I〈s,b, f ,d , t〉
Tipo II〈s,b, c,d , t〉
s ε = 1
b 2
d 3
t4
1
c 3
1
1
f 2
1
1
t ζ = 4
d 3
b2
s11
1
c 3
1f 3
1
1
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Problema do desvio de custo mínimo
Disposição esquemática das partições
s tP1
P2
Pc
Pb
Pa
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Implementação
Implementação
Codificação em Java
Biblioteca open source JUNG: 1.7 e 2.0Diversos algoritmos já implementados, incluindo o DijkstraVisualização de grafos
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Implementação
Implementação
Codificação em JavaBiblioteca open source JUNG: 1.7 e 2.0
Diversos algoritmos já implementados, incluindo o DijkstraVisualização de grafos
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Implementação
Implementação
Codificação em JavaBiblioteca open source JUNG: 1.7 e 2.0Diversos algoritmos já implementados, incluindo o Dijkstra
Visualização de grafos
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Implementação
Implementação
Codificação em JavaBiblioteca open source JUNG: 1.7 e 2.0Diversos algoritmos já implementados, incluindo o DijkstraVisualização de grafos
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Variáveisn: número de vérticesm: número de arestasd : densidade=m/
(n2
)k : quantidade de menores caminhos
MetodologiaGrafos simétricos conexos com custos positivos5 pontas iniciais e finaisUm grafo por densidade
Consumo de tempoKIM: Θ(kT (n,m)) = Θ(km log n) usando-se DIJKSTRA
KIM: Θ(km log n) = Θ(kdn2 log n)
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Variáveisn: número de vérticesm: número de arestasd : densidade=m/
(n2
)k : quantidade de menores caminhos
MetodologiaGrafos simétricos conexos com custos positivos5 pontas iniciais e finaisUm grafo por densidade
Consumo de tempoKIM: Θ(kT (n,m)) = Θ(km log n) usando-se DIJKSTRA
KIM: Θ(km log n) = Θ(kdn2 log n)
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Variáveisn: número de vérticesm: número de arestasd : densidade=m/
(n2
)k : quantidade de menores caminhos
MetodologiaGrafos simétricos conexos com custos positivos5 pontas iniciais e finaisUm grafo por densidade
Consumo de tempoKIM: Θ(kT (n,m)) = Θ(km log n) usando-se DIJKSTRA
KIM: Θ(km log n) = Θ(kdn2 log n)
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Tempo em função do número de caminhos
Consumo de tempo KIM: Θ(kT (n,m))
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Tempo em função do número de caminhos
0
1000
2000
3000
4000
5000
6000
7000
100 200 300 400 500 600 700 800 900 1000
Tem
po(s
)
Quantidade de caminhos gerados(k)
Tempo de execução em função do número de caminhos. n=900
densidade0.10.51.0
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Tempo em função do número de vértices
Consumo de tempo KIM usando DIJKSTRA "min-heap":Θ(kdn2 log n)
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Tempo em função do número de vértices
0
100
200
300
400
500
600
700
100 200 300 400 500 600 700 800 900
Tem
po(s
)
Tempo em função do número de vértices. Densidade 0.1
número de caminhos(k)k=100k=200k=300k=400k=500k=600k=700k=800k=900
k=1000
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Tempo em função do número de vértices
0
500
1000
1500
2000
2500
3000
100 200 300 400 500 600 700 800 900
Tem
po(s
)
Tempo em função do número de vértices. Densidade 0.5
número de caminhos(k)k=100k=200k=300k=400k=500k=600k=700k=800k=900
k=1000
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Tempo em função do número de vértices
0
1000
2000
3000
4000
5000
6000
7000
100 200 300 400 500 600 700 800 900
Tem
po(s
)
Tempo em função do número de vértices. Densidade 1.0
número de caminhos(k)k=100k=200k=300k=400k=500k=600k=700k=800k=900
k=1000
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Principais rotinas
RotinasProblema do desvio mínimo, rotina SEPProblema CM, algoritmo Dijkstra
Consumo de tempoSEP: Θ(m + n)
DIJKSTRA com "min-heap": Θ(m log n)
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Fatia de tempo utilizada pelas principais rotinas.
0.978
0.98
0.982
0.984
0.986
0.988
0.99
0.992
0.994
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Pro
porç
ão
Densidade
Proporção de tempo utilizada pelas duas principais subrotinas para cada densidade. n=900
número de caminhosk=100k=200k=300k=400k=500k=600k=700k=800k=900
k=1000
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Fatia de tempo utilizada pelas execuções do Dijkstra.
0.35
0.4
0.45
0.5
0.55
0.6
0.65
0.7
0.75
0.8
0.85
0.9
100 200 300 400 500 600 700 800 900
Pro
porç
ão
Número de vértices
Proporção de tempo utilizada pelas execuções do algoritmo Dijkstra. Densidade=0.1
número de caminhosk=100k=200k=300k=400k=500k=600k=700k=800k=900
k=1000
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Fatia de tempo utilizada pelas execuções do Dijkstra.
0.5
0.55
0.6
0.65
0.7
0.75
0.8
0.85
0.9
100 200 300 400 500 600 700 800 900
Pro
porç
ão
Número de vértices
Proporção de tempo utilizada pelas execuções do algoritmo Dijkstra. Densidade=0.5
número de caminhosk=100k=200k=300k=400k=500k=600k=700k=800k=900
k=1000
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Fatia de tempo utilizada pelas execuções do Dijkstra.
0.55
0.6
0.65
0.7
0.75
0.8
0.85
0.9
100 200 300 400 500 600 700 800 900
Pro
porç
ão
Número de vértices
Proporção de tempo utilizada pelas execuções do algoritmo Dijkstra. Densidade=1.0
número de caminhosk=100k=200k=300k=400k=500k=600k=700k=800k=900
k=1000
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Fatia de tempo utilizada pelas execuções do algoritmo de desviomínimo.
0.1
0.15
0.2
0.25
0.3
0.35
100 200 300 400 500 600 700 800 900
Pro
porç
ão
Número de vértices
Proporção de tempo utilizada pelas execuções da rotina SEP. Densidade=0.1
número de caminhosk=100k=200k=300k=400k=500k=600k=700k=800k=900
k=1000
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Fatia de tempo utilizada pelas execuções do algoritmo de desviomínimo.
0.1
0.15
0.2
0.25
0.3
0.35
100 200 300 400 500 600 700 800 900
Pro
porç
ão
Número de vértices
Proporção de tempo utilizada pelas execuções da rotina SEP. Densidade=0.5
número de caminhosk=100k=200k=300k=400k=500k=600k=700k=800k=900
k=1000
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Experimentos
Fatia de tempo utilizada pelas execuções do algoritmo de desviomínimo.
0.1
0.12
0.14
0.16
0.18
0.2
0.22
0.24
0.26
0.28
0.3
100 200 300 400 500 600 700 800 900
Pro
porç
ão
Número de vértices
Proporção de tempo utilizada pelas execuções da rotina SEP. Densidade=1.0
número de caminhosk=100k=200k=300k=400k=500k=600k=700k=800k=900
k=1000
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Conclusões
No algoritmo KIM a rotina para o problema CM consome amaior fatia do tempo de execução do algoritmo.
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
Trabalhos futuros
Representar caminhos usando TRIEAnalisar idéia de reconstrução de árvoresImplementar algoritmo de Hershberger
Motivação k -menores caminhos Árvore dos prefixos Partições YEN KIM Implementação Conclusões
FIM
"Não basta ensinar ao homem uma especialidade,porque se tornará assim uma máquina utilizável e nãouma personalidade.É necessário que adquira um sentimento, sensoprático daquilo que vale a pena ser empreendido,daquilo que é belo, do que é moralmente correto."
Albert Einstein
Apêndice
8 ApêndiceKIMÁrvore dos prefixos
Apêndice
KIM
Custo zero nas arestas
a b
c
d e1.0 0.0 1.0
1.0 1.0
a ε = 1
b ε = 2
d ε = 3
eε = 4
1.0
c ε = 3
1.0
0.0
1.0
e ζ = 4
d ζ = 3
b ζ = 2
a ζ = 1
1.0
cζ = 2
1.0
0.0
1.0
Problemaε(c) > ζ(c)
Não consegue gerar ocaminho 〈a,b, c,d ,e〉
Apêndice
KIM
Custo zero nas arestas
a b
c
d e1.0 0.0 1.0
1.0 1.0
a ε = 1
b ε = 2
d ε = 3
eε = 4
1.0
c ε = 3
1.0
0.0
1.0
e ζ = 4
d ζ = 3
b ζ = 2
a ζ = 1
1.0
cζ = 2
1.0
0.0
1.0
Problemaε(c) > ζ(c)
Não consegue gerar ocaminho 〈a,b, c,d ,e〉
Apêndice
KIM
Custo zero nas arestas
a b
c
d e1.0 0.0 1.0
1.0 1.0
a ε = 1
b ε = 2
d ε = 3
eε = 4
1.0
c ε = 3
1.0
0.0
1.0
e ζ = 4
d ζ = 3
b ζ = 2
a ζ = 1
1.0
cζ = 2
1.0
0.0
1.0
Problemaε(c) > ζ(c)
Não consegue gerar ocaminho 〈a,b, c,d ,e〉
Apêndice
KIM
Pa
Na figura temos os caminhos Pj e Pk , 1 <= j < k onde Pj é paide Pk e que compartilham o prefixo 〈s, . . . ,u〉 diferenciando-sea partir de u.
s
u
a
tj
b
tk
Apêndice
KIM
Pa
Esquema dos caminhos na partição Pa.
s
u
a
tj
b
tk
Apêndice
KIM
Pb
s
u
tj
b
tk
Apêndice
KIM
Pb
s
u
v
il
ij
b
ik
Apêndice
KIM
Pb
s
u
v
tl tj
b
tk
Apêndice
KIM
Pc
s
. . .
u
tk tj
Apêndice
KIM
Pc
s
. . . vtl
u
tk tj
Apêndice
KIM
Pc
s
v
. . .
u
tk tj
tl
Apêndice
Árvore dos prefixos
DefiniçãoQ, (N,E), f ,V (Q),A(Q)
Q: uma coleção de caminhos
Caminhos〈s,a, i , t〉〈s,b, f , l , t〉〈s,b,g, l , t〉〈s,b,h, l , t〉〈s,b,h, i , t〉〈s,a, i ,h, l , t〉
V (Q): conjunto de vérticesA(Q): conjunto de arcos
Apêndice
Árvore dos prefixos
DefiniçãoQ, (N,E), f ,V (Q),A(Q)
(N,E): uma arborescência
ae
c
b
Grafo acíclico (N,E)|N| = |E |+ 1raiz
Todo vértice, exceto a raiz, é ponta final de exatamenteum arco.
Apêndice
Árvore dos prefixos
DefiniçãoQ, (N,E), f ,V (Q),A(Q)
f : uma função rótulo
Associa nós e arestas do grafo aos nós e arestas daárvore de prefixos.
Se
R = 〈u0,e1,u1, . . . ,et ,ut〉for um caminho em (N,E), então
f (R) := 〈f (u0), f (e1), f (u1), . . . , f (et ), f (ut )〉será uma seqüência de vértices e arcos dos caminhos emQ.
