Buscar

Caminho Mínimo

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Prof.: Lamounier Josino de Assis
*
CAMINHO MÍNIMO
O mapa da malha rodoviária de uma região de seu estado, com a respectiva quilometragem entre as cidades, encontra-se na figura abaixo. A cidade 1 possui a fabrica de sapatos Otoni, que fornece seus produtos para as demais cidades da região. A empresa de transportes união foi contratada para fazer a entrega desses produtos. Qual é o percurso que a transportadora deverá seguir, para efetuar a entrega dos sapatos nas varias cidades, supondo que cada uma delas fique com todo o estoque do caminhão?
1
2
3
4
5
80
65
100
200
40
60
40
15
6
65
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
CAMINHO MÍNIMO 
Modelagem:
Cada cidade da região é representada por um vértice
Aresta v,w liga duas cidades
Atribuir valores às arestas do grafo, correspondendo ao grau de dificuldade para percorrer as arestas a ela associadas.
Problema
Determinação do menor caminho entre o vértice 1 e os demais vértices do grafo valorado G.
Solução
A solução do problema exige o estabelecimento de um processo para determinar o caminho mínimo entre pares de vértices do grafo.
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
MÉTODO DA MULTIPLICAÇÃO MATRICIAL
Considerações:
Sendo um grafo valorado, é imprescindível encontrar uma forma para registrar os valores de suas arestas.
Espera-se obter o custo do caminho mínimo entre pares de vértices do grafo, bem como a seqüência de arestas que formam esse caminho.
Um grafo ou dígrafo sendo valorado necessita de uma representação mais completa que a matriz de adjacências.
Seja V m x n a matriz de valores das arestas, assim definida para grafos e dígrafos simples.
Vii= 0;
Vij = valor da aresta (i,j), se (i,j) E
	= ∞,caso (i,j)  E 
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
MATRIZ V
V=
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
Vij armazena o custo do caminho mínimo entre i e j
Como o grafo é valorado, o custo do caminho mínimo entre dois vértices i e j, utilizando P arestas, pode ser superior a outro que possua P + K, K>0 arestas.
A busca de um caminho de custo mínimo inferior ao encontrado deve ser continuada, até que se tenha certeza da obtenção do caminho mínimo.
Questão
“ Como determinar o custo do caminho mínimo entre 1 e 2, utilizando até duas arestas? 
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
Todos os caminhos de 1 a 2 utilizando-se até duas arestas devem ser analisados.
L1 [ 0 80 ∞ ∞ 40 60 ] representa os custos dos caminhos de menor custo entre o vértice 1 e os demais vértices, utilizando até uma aresta.
C2 representa os custos dos caminhos de menor custo de todos os vértices do grafo até o ´vértice 2,utilizando-se até uma aresta
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
Custo do menor caminho entre 1 e 2,utilizando-se até duas arestas.
min { 0+80, 80+0, ∞+65, ∞+ ∞, 40+ ∞, 60+15 } = 75
Obs:
Esse cálculo deverá ser efetuado para os demais pares de vértices do grafo .
V2 = V♦V,cujos elementos possuem a seguinte definição
 
V2iJ = min { Vik + VkJ } 
 = min{ Vi1+V1J,Vi2+V2J,Vi3+V3J,Vi4+V4J, Vi5+V5J,Vi6+V6J } 
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
Generalizando, a matriz Vp armazena os custos dos menores caminhos entre cada par de vértices do grafo ou digrafo, utilizando até p arestas.
V1 = V. Deve-se determinar V2,V3,. . . Vp = Vp-1♦V,... até Vn-1, já que, como a estrutura possui n vértices, no pior caso, o caminho mínimo terá n-1 arestas.
É preciso definir a forma do caminho mínimo pela seqüência de vértices, e como será posteriormente resgatada. 
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
Matriz R( vértices adjacentes)→ No final do processamento, armazenará o vértice que antecede J no caminho mínimo encontrado.
INICIALIZAÇÃO DE R.
		rii = 0 indica que não existe vértice que antecede o 	vértice i no caminho mínimo de i para i, já que tal 	caminho é nulo.
		riJ = i, caso a aresta (i,j) Є E.
		riJ = ∞, caso a aresta (i, j) E, indicando que ainda não foi encontrado caminho algum entre os vértices i e j.
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
1
2
3
4
5
80
65
100
200
40
60
40
15
6
65
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
Obs:
Qualquer alteração sofrida pelo valor de VpiJ, durante processamento, é conseqüência da obtenção de um novo caminho de custo inferior ao que havia sido encontrado anteriormente
Esse fato deve ser ser registrado na posição da matriz R, atribuindo-lhe o valor do vértice K, responsável pela alteração ViJ.
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
Exemplo:
r12 = 1 menor caminho entre 1 e 2 utilizando-se até uma aresta (1,2) possui custo 80.
Para V212 = 75 = V16 + V62 = 60 + 15 → significa caminho mínimo de 1 a 2 com até duas arestas é formado pelas arestas <(1,6) (6,2)> e tem custo inferior ao anteriormente calculado.
O vértice 6 é o responsável por essa alteração e antecede o vértice 2 no novo caminho, e o valor de r12 = 1 deve ser atualizado para 6.
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
MÉTODO DA MULTIPLICAÇÃO MATRICIAL
	( MÉTODO ITERATIVO)
Tem como objetivo determinar o caminho mínimo entre todos os pares de vértices de um grafo valorado simples, com arestas de valores positivos. Ele também pode ser utilizado para digrafos valorados simples sem ciclos negativos.
Caracterização do Algoritmo 
Realiza uma iteração
Em cada uma das iterações, ele utiliza como operando os resultados obtidos na iteração anterior.
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
Obs:
Devido ao caráter repetitivo desse método, torna-se obrigatória a definição de um critério de parada que garanta a finalização do processo.
Como grafos e digrafos possuem n vértices, no pior caso, o caminho entre vértices terá n-1 arestas. Assim diJ = Vn-1iJ, viJ.
Resolução
Após a determinação dos valores iniciais das matrizes, faz-se p=2 e os valores de V2 devem ser calculados segundo a fórmula:
VpiJ = min{ Vp-1ik + V1kJ }
				 k = 1,2, 3, ...,n	
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
0	80	 ∞	 ∞	40	60
80	 0	65	 ∞	 ∞	15
∞	 65	 0	100	 ∞	65
∞	 ∞	100	 0	 ∞	200
40	 ∞	 ∞	 ∞	 0	40
60	15	65	200	40	 0
V = 
0	 1 	 ∞	 ∞	 1	1
2	 0	2	 ∞	 ∞	2
∞	 3	 0	 3	 ∞	3
∞	 ∞	4	 0	 ∞	4
5	 ∞	 ∞	 ∞	 0	5
6	6	6	6	6	0
R = 
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
0	75	 125	 260	40	60
75	 0	65	 165	 55	15
125	 65	 0	100	 105	65
260	 165	100	 0	 240	165
40	 55	 105	 240	 0	40
60	15	65	165	40	 0
V2 = 
125= V16 + V63 < (1,6) (6,3)>
260= V16 + V64 <(1,6) (6,4)>
40= V11 + V15 <(1,1) (1,5)>
60= V11 + V16 <(1,1) (1,6)>
Obs: Nenhum vértice é antecessor de si mesmo no final do processamento.
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
0	75	 125	 260	40	60
75	 0	65	 165	 55	15
125	 65	 0	100	 105	65
260	 165	100	 0	 240	165
40	 55	 105	 240	 0	40
60	15	65	165	40	 0
V2 = 
0	 6 	 6	 6	 1	1
6	 0	2	 3	 6	2
6	 3	0	 3	 6	3
6	 3	4	 0	 6	3
5	 6	6	 6	 0	5
6	 6	6	6	6	0
R = 
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
 0	75	125	 225	 40	 60
75	 0	65	 165	 55	 15
125	65	 0	 100	 105	 65
225	165	100	 0	 205 165
40	55	105	 205	 0	 40
60	15	 65	 165	 40	 0
V3 = 
R314 = 3 → [ 0 75 125 260 40 60 ] 
V314 = 225 = V213 + V34→ < 1,2,3,4 >
ou < 1,6, 3,4 >
 ∞
 ∞
100
0
 ∞
200
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
0	75	 125	 225	40	60
75	 0	65	 165	 55	15
125	 65	 0	100	 105	65
225	 165	100	 0	 205 165
40	 55	 105	 205	 0	40
60	15	65	165	40	 0
V3 = 
0	 6 	 6	 3	 1	1
6	 0	2	 3	 6	2
6	 3	 0	 3	 6	3
6	 3	4	 0	 6	3
5	 6	 6	 3	 0	5
6	6	6	3	6	0
R = 
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
0	75	 125	 225	40	60
75	 0	65	 165	 55	15
125	 65	 0	100	 105	65
225	 165	100	 0	 205 165
40	 55	 105	 205	 0	40
60	15	65	165	40	 0
V4 = 
0	 6 	 6	 3	 1	1
6	 0	2	 3	 6	2
6	 3	 0	 3	 6	3
6	 3	4	 0	 6	3
5	 6	 6	 3	 0	5
6	6	6	 3	 6	0
R = 
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
0	75	 125	 225	40	60
75	 0	65	 165	 55	15
125	 65	 0	100	 105	65
225	 165	100	 0	 205 165
40	 55	 105	 205	 0	40
60	15	65	165	40	 0
V5 =D 
0	 6 	 6	 3	 1	1
6	 0	2	 3	 6	2
6	 3	 0	 3	 6	3
6	 3	4	 0	 6	3
5	 6	 6	 3	 0	5
6	6	6	 3	 6	0
R = 
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
D = V5 = V4 = V3 → R
A matriz D informa que o custo do caminho mínimo entre os vértices 1 e 3 é 125.
Questão: “ Como esse caminho pode ser resgatado?
A matriz R contém a resposta.
R13= 6 significa que 6 é o antecessor de 3 no caminho mínimo de 1 a 3. Logo, esse caminho é formado pelo caminho mínimo de 1 a6 e pela aresta(6,3).
Tem-se, então, que resgatar os vértices do caminho mínimo de 1 a 6.
R16= 1, logo, 1 é o antecessor de 6 (1,6).
Caminho mínimo de 1ª 3 é < 1,6,3 > .
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
Obs: Não há necessidade de obrigatoriamente chegar até a ( n -1 )ésima i iteração do método. No momento em que a matriz Vq foi idêntica à matriz V(q-1), a solução já foi encontrada e o processo pode ser interrompido.
SOLUÇÃO
Para atender as cidades 2,3,4,5 e 6, a transportadora União deverá seguir respectivamente os seguintes caminhos
< 1,6,2 >, < 1,6,3 >, < 1,6,3,4 >, < 1,5 > e < 1,6 >.
1
5
3
4
6
2
Prof.: Lamounier Josino de Assis
Prof.: Lamounier Josino de Assis
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*

Teste o Premium para desbloquear

Aproveite todos os benefícios por 3 dias sem pagar! 😉
Já tem cadastro?

Outros materiais