Problema do Caminho Mínimo - Algoritmo de Dijkstra e Modelagem Matemática

Departamento de Engenharia de Produção UFPR 66 Professor Volmir Eugênio Wilhelm Problema do Caminho Mínimo Shortest Path Problem O problema do caminho mínimo ou caminho mais curto consiste em encontrar o melhor caminho entre dois nós Assim resolver este problema pode significar determinar o caminho entre dois nós com o custo mínimo ou com o menor tempo de viagem Numa rede qualquer dependendo das suas características pode existir vários caminhos entre um par de nós definidos como origem e destino Entre os vários caminhos aquele que possui o menor peso é chamado de caminho mínimo Este peso representa a soma total dos valores dos arcos que compõem o caminho e estes valores podem ser o tempo de viagem a distância percorrida ou um custo qualquer do arco Applications of the shortest path problem include those in road networks logistics communications electronic design power grid contingency analysis and community detection httpsdevelopernvidiacomdiscovershortestpathproblem 1 Modelagem matemática O modelo matemático para o problema de caminho mais curto do nó 1 ao nó n de um grafo GNE N 1 2 n Variáveis xij 01 ativação ou não do arco i j Parâmetros cij custo unitário do fluxo em i j Sj é o conjunto dos nós sucessores de j Pj é o conjunto dos nós predecessores de j Função objetivo min c Departamento de Engenharia de Produção UFPR 67 Professor Volmir Eugênio Wilhelm Restrições n Para resolução do problema de caminho mínimo existem algoritmos alternativos mais simples e mais eficientes do que o método simplex 2 Algoritmo de Dijkstra O algoritmo de Dijkstra é uma solução para o problema do caminho mínimo de origem única Funciona em grafos orientados e não orientados no entanto todas as arestas devem ter custos não negativos Se houver custos negativos usase o algoritmo de BellmanFord Entrada Grafo ponderado GNE e nó origem O N de modo que todos os custos das arestas sejam não negativos Saída Comprimentos de caminhos mais curtos ou os caminhos mais curtos em si de um determinado nó origem O N para todos os outros nós Como funciona O algoritmo de Dijkstra identifica a partir do nó O qual é o custo mínimo entre esse nó e todos os outros do grafo No início o conjunto S contém somente esse nó chamado origem A cada passo selecionamos no conjunto de nós sobrando o que está mais perto da origem Depois atualizamos para cada nó que está sobrando a sua distância em relação à origem Se passando pelo novo nó acrescentado a distância ficar menor é essa nova distância que será memorizada Escolhido um nó como origem da busca este algoritmo calcula então o custo mínimo deste nó para todos os demais nós do grafo O procedimento é iterativo determinando na iteração 1 o nó mais próximo do nó O na segunda iteração o segundo nó mais próximo do nó O e assim sucessivamente até que em alguma iteração todos os n sós sejam atingidos Seja GNE um grafo orientado e s um nó de G Atribua valor zero à estimativa do custo mínimo do nó O a origem da busca e infinito às demais estimativas Departamento de Engenharia de Produção UFPR 68 Professor Volmir Eugênio Wilhelm Atribua um valor qualquer aos precedentes o precedente de um nó t é o nó que precede t no caminho de custo mínimo de s para t Enquanto houver nó aberto seja k um nó ainda aberto cuja estimativa seja a menor dentre todos os nós abertos feche o nó k Para todo nó j ainda aberto que seja sucessor de k faça some a estimativa do nó k com o custo do arco que une k a j caso esta soma seja melhor que a estimativa anterior para o nó j substituaa e anote k como precedente de j Exemplo 1 Departamento de Engenharia de Produção UFPR 69 Professor Volmir Eugênio Wilhelm Exemplo 2 Departamento de Engenharia de Produção UFPR 70 Professor Volmir Eugênio Wilhelm Exemplo 3 Exemplo 4 3 Algoritmo de FloydWarshall httpswwwquoracomWhyistheorderoftheloops inFloydWarshallalgorithmimportanttoitscorrectness O algoritmo de Floyd é um algoritmo que resolve o problema de determinar o caminho mais curto entre todos os pares de nós em um grafo orientado e ponderado Tratase de um algoritmo que utiliza matrizes para determinar os caminhos mínimos entre todos os pares de nós da rede No algoritmo de Floyd são feitas n iterações que corresponde ao número de nós da rede A cada iteração corresponde uma matriz cujos valores são modificados utilizando uma fórmula de recorrência Departamento de Engenharia de Produção UFPR 71 Professor Volmir Eugênio Wilhelm d min d d d Determinase inicialmente a matriz D0 cujos valores correspondem aos comprimentos dos arcos se estes existem senão os valores são Depois se calcula D1 de D0 e D2 de D1 até se obter Dn de Dn1 A matriz Dn é a matriz final que apresenta as distâncias mínimas entre todos os nós da rede A ideia básica deste algoritmo é verificar a cada iteração se a inclusão de um nó k intermediário no caminho de i para j pode reduzir o tamanho de um caminho já determinado Numere os nós do grafo de n Defina a matriz D0 cujos valores d correspondem ao tamanhocomprimento dos arcos i j se existir o arco no grafo caso contrário considere d e faça os elementos da diagonal da matriz d para todo i Para cada k 1n determine sucessivamente os elementos da matriz Dk a partir dos elementos da matriz Dk1 utilizando a expressão acima Este processo é repetido até k n e neste caso o valor do caminho mínimo de todos os pares i j do grafo estão definidos na matriz Dn Entrada Grafo ponderado GNE As arestas do grafo podem ter valores negativos mas o grafo não pode conter nenhum ciclo de valor negativo Saída Matriz n n com os custos dos menores caminhos entre todos os nós de N Um ciclo negativo é aquele em que a soma total do ciclo é negativa Simultaneamente a construção da matriz de distâncias mínimas Dk entre todos os nós podese construir a matriz dos predecessores Pk A matriz Pk pode ser lida da seguinte forma se queremos reconstruir o caminho mais curto entre os nós i e j então observamos o elemento nas coordenadas correspondentes Se seu valor for 0 não haverá caminho entre esses nós caso contrário o valor do elemento denota o predecessor de j no caminho de i a j Repetimos esse procedimento enquanto o nó anterior não é igual a i A matriz Pk é assim construída Departamento de Engenharia de Produção UFPR 72 Professor Volmir Eugênio Wilhelm i ou i caso contr rio Exemplo 1 D3 A B C D P3 A B C D A 4 1 2 A C A A B 4 3 6 B C B A C 1 3 3 C C C A D 2 6 3 D D C A Exemplo 2 httpfacultyycpedudbabcockPastCoursescs360lectureslecture23html Origem Destino Distancia A B 4 A C 1 A D 2 B C 3 B D 6 C D 3 CAD Menor Caminho ACB AC AD BC BCAD Departamento de Engenharia de Produção UFPR 73 Professor Volmir Eugênio Wilhelm Departamento de Engenharia de Produção UFPR 74 Professor Volmir Eugênio Wilhelm Algoritmo de BellmanFord O algoritmo de BellmanFord resolve o problema do caminho mais curto de única origem para o caso mais geral no qual os custos das arestas podem ser negativos Algoritmo de Johnson Enquanto o algoritmo de FloydWarshall é eficiente para grafos densos se o grafo é esparso uma alternativa para todos os pares de estratégia de caminho mais curto conhecida como algoritmo de Johnson pode ser usada Esse algoritmo basicamente usa o BellmanFord para detectar qualquer ciclo de custo negativo e em seguida emprega a técnica de reponderação das arestas para permitir que o algoritmo de Dijkstra encontre os caminhos mais curtos Algoritmo A httptheorystanfordeduamitpGameProgrammingAStarComparisonhtml Derivado do algoritmo de Dijkstra A é a opção mais popular para a busca de caminhos porque é bastante flexível e pode ser usada em uma ampla variedade de contextos Problema de Fluxo Máximo Dado um grafo que representa uma rede de fluxo onde cada aresta tem uma capacidade Também são dados dois vértices fonte s e sumidouro t no grafo GNE O problema consiste em encontrar o fluxo máximo possível de s para t com as seguintes restrições Departamento de Engenharia de Produção UFPR 75 Professor Volmir Eugênio Wilhelm i Cada aresta u E tem uma capacidade não negativa c u ii O fluxo de entrada é igual ao fluxo de saída para todos os nós exceto s e t Se u E então c u A fonte produz o material a uma taxa constante e o sumidouro consome o material a uma taxa constante Por exemplo httpswwwgeeksforgeeksorgdinicsalgorithmmaximumflow Algoritmo Os passos de cada iteração do algoritmo podem ser resumidos do seguinte modo Passo 1 Escolhese um caminho qualquer desde a origem até ao sumidouro via arestas cuja capacidade é positiva 0 Passo 2 Procurar nesse caminho o arco orientado com menor capacidade c Passo 3 Subtrair de c a capacidade de fluxo em cada aresta do caminho no sentido direto e aumentar de c a capacidade das arestas no sentido inverso Passo 4 Regressar ao Passo 1 Se já não existir nenhum caminho em que todas as arestas tenham capacidade positiva então o fluxo máximo já está determinado E se ocorrerem limitações nos arcos e nos nós Em alguns problemas de otimização em redes nos deparamos com limitações de fluxo nos nós juntamente com as limitações nos arcos Neste caso podemos reescrever o problema em outro equivalente no qual as limitações de fluxo estão somente nos arcos Para isso pegue cada nó i com limitações de fluxo no grafo original e substituao por dois nós i1 e i2 No novo grafo o arco ki do grafo original é substituído por um arco ki1 exatamente com os mesmos parâmetros de custos limitações de capacidade etc o arco if do grafo original é substituído por um arco i2f exatamente com os mesmos parâmetros de custo limitações de capacidade etc e adicionamos um arco i1i2 com custo 0 e com as limitações de capacidade do nó i Departamento de Engenharia de Produção UFPR 76 Professor Volmir Eugênio Wilhelm figura abaixo Neste novo grafo o arco i1i2 restringe o fluxo do nó i conforme se deseja ARENALES Algoritmo FordFulkerson Algoritmo BFS Algoritmo de EdmondsKarp Curiosidade algoritmo guloso São tipicamente usados para resolver problemas de otimização Por exemplo o algoritmo para encontrar o caminho mais curto entre duas cidades Um algoritmo guloso escolhe a estrada que parece mais promissora no instante atual e nunca muda essa decisão independentemente do que possa acontecer depois A cada iteração a seleciona um elemento conforme uma função gulosa b marcao para não considerálo novamente nos próximos estágios c atualiza a entrada d examina o elemento selecionado quanto sua viabilidade e decide a sua participação ou não na solução Funcionamento Constrói uma solução elemento a elemento a A cada passo é adicionado um único elemento b O elemento escolhido é o melhor segundo a função ob etivo c O método termina quando todos os elementos foram analisados e inseridos na solução Departamento de Engenharia de Produção UFPR 77 Professor Volmir Eugênio Wilhelm Características dos algoritmos gulosos Para construir a solução ótima existe um conjunto ou lista de candidatos São acumulados um conjunto de candidatos considerados escolhidos e o outro de candidatos considerados rejeitados Existe uma função que verifica se um conjunto particular de candidatos produz uma solução sem considerar otimalidade no momento Outra função verifica se um conjunto de candidatos é viável também sem se preocupar com a otimalidade Uma função de seleção indica a qualquer momento quais dos candidatos restantes é o mais promissor Uma função objetivo fornece o valor da solução encontrada como o comprimento do caminho construído não aparece de forma explícita no algoritmo guloso Quando funciona corretamente a primeira solução encontrada é sempre ótima A função de seleção é geralmente relacionada com a função objetivo Se o objetivo é o Ma imizar pro a elmente escolher o candidato restante que proporcione o maior ganho individual o Minimizar então ser escolhido o candidato restante de menor custo O algoritmo nunca muda de ideia o Uma vez que um candidato é escolhido e adicionado à solução ele lá permanece para sempre o Uma vez que um candidato é excluído do conjunto solução ele nunca mais é reconsiderado Em Algoritmos gulosos a construção de uma solução gulosa consiste em selecionar sequencialmente o elemento de N que minimiza o incremento no custo da solução parcial eventualmente descartando alguns já selecionados de tal forma que ao final se obtenha uma solução viável O incremento no custo da solução parcial é chamado de função gulosa Por escolher a cada passo considerando apenas a próxima decisão chamase também de algoritmo míope pois enxerga somente o que está mais próximo