Baixe o app para aproveitar ainda mais
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 * * * * * * * * * * * * * * * * * * * * * *
Compartilhar