Problema do caminho mínimo

Esta página cita fontes, mas que não cobrem todo o conteúdo. Ajude a inserir referências (Encontre fontes: ABW  • CAPES  • Google (N • L • A)). (Maio de 2024)

Na teoria de grafos, o problema do caminho mínimo consiste na minimização do custo de travessia de um grafo entre dois nós (ou vértices); custo este dado pela soma dos pesos de cada aresta percorrida.

Formalmente, dado um grafo valorado (ou seja, um conjunto V de vértices, um conjunto A de arestas e uma função de peso ${\displaystyle f:A\to \mathbb {R} }$) e, dado qualquer elemento v de V, encontrar um caminho P de v para cada v' de V tal que

${\displaystyle \sum _{p\in P}f(p)}$

é mínimo entre todos os caminhos conectando n a n'.

Em programação dinâmica, podemos escolher um subproblema de modo que toda a informação vital seja recordada e levada adiante. Assim, vamos definir que para cada vértice ${\displaystyle v}$ e cada inteiro ${\displaystyle i\leq k}$ , ${\displaystyle dist(v,i)}$ como o menor caminho de ${\displaystyle s}$ até ${\displaystyle v}$ que usa ${\displaystyle i}$ arestas. Os valores iniciais de ${\displaystyle dist(v,0)}$ são ${\displaystyle \infty }$ para todos os vértices exceto ${\displaystyle s}$, para o qual é 0. E a equação geral de atualização é:

${\displaystyle dist(v,i)=\min _{(u,v)\in E}\{dist(u,i-1)+l(u,v)\}}$

Existem várias variantes para problemas de caminho mínimo, cada uma adequada a um conjunto de problemas diferente:

• Problema de único destino: consiste em determinar o menor caminho entre cada um dos nós do grafo e um nó de destino dado.
• Problema de único origem: determinar o menor caminho entre um nó dado e todos os demais nós do grafo.
• Problema de origem-destino: determinar o menor caminho entre nós dados.
• Problemas de todos os pares: determinar o menor caminho entre cada par de nós presentes no grafo.

Os algoritmos especializados em solucionar o problema do caminho mínimo são eventualmente chamados de algoritmos de busca de caminhos. Entre os algoritmos dessa classe, os mais conhecidos são:

• Algoritmo de Dijkstra  — Resolve o problema com um vértice-fonte em grafos cujas arestas tenham peso maior ou igual a zero. Sem reduzir o desempenho, este algoritmo é capaz de determinar o caminho mínimo, partindo de um vértice de início v para todos os outros vértices do grafo.^[1]
• Algoritmo de Bellman-Ford  — Resolve o problema para grafos com um vértice-fonte e arestas que podem ter pesos negativos.
• Algoritmo A*  — um algoritmo heurístico que calcula o caminho mínimo com um vértice-fonte.
• Algoritmo de Floyd-Warshall  — Determina a distância entre todos os pares de vértices de um grafo.^[2]
• Algoritmo de Johnson  — Determina a distância entre todos os pares de vértices de um grafo, pode ser mais veloz que o algoritmo de Floyd-Warshall em grafos esparsos.
• Algoritmo Viterbi — Resolve o menor problema de caminho estocástico com um peso probabilístico adicional em cada nó.

O problema de caminho mínimo é um dos problemas genéricos intensamente estudados e utilizados em diversas áreas como Engenharia de Transportes, Pesquisa Operacional, Ciência da Computação e Inteligência Artificial. Isso decorre do seu potencial de aplicação a inúmeros problemas práticos que ocorrem em transportes, logística, redes de computadores e de telecomunicações, entre outros.

Podem ser aplicados para encontrar automaticamente direções entre locais físicos, como instruções de direção em sites de mapeamento da web como o MapQuest ou o Google Maps. Para esta aplicação, algoritmos especializados rápidos estão disponíveis.

Outras possibilidades de aplicação incluem quaisquer problemas envolvendo redes ou grafos em que se tenha grandezas (distâncias, tempo, perdas, ganhos, despesas) que se acumulem linearmente ao longo do percurso da rede. Se alguém representa uma máquina abstrata não determinística como um gráfico em que os vértices descrevem estados e arestas descrevem possíveis transições, algoritmos de caminho mínimo podem ser usados ​​para encontrar uma sequência ótima de opções para atingir um determinado estado objetivo ou para estabelecer limites mais baixos no tempo necessário para atingir um determinado estado. Por exemplo, se os vértices representam os estados de um quebra-cabeça como o Cubo de Rubik e cada borda direcionada corresponde a um único movimento ou turno, os algoritmos de caminho mínimo podem ser usados ​​para encontrar uma solução que use o número mínimo possível de movimentos. Um problema relacionado é o Problema do Caixeiro-viajante, que consiste em determinar o caminho mais curto que passa exatamente uma vez por cada vértice e retorna ao vértice de partida. Este é um problema NP-Completo, para os quais não há uma solução eficiente.

Uma aplicação mais alegre são os jogos de "seis graus de separação" que tentam encontrar o caminho mais curto em gráficos como estrelas de cinema que aparecem no mesmo filme.

Outras aplicações, frequentemente estudadas em pesquisa operacional, incluem layout de instalações e instalações, robótica, transporte e design de VLSI.

Uma rede rodoviária pode ser considerada como um gráfico com pesos positivos. Os nós representam cruzamentos e cada aresta do gráfico é associado a um segmento de estrada entre dois cruzamentos. O peso de uma aresta pode corresponder ao comprimento do segmento de estrada associado, ao tempo necessário para atravessar o segmento ou ao custo de atravessar o segmento. Usando arestas direcionadas, também é possível modelar ruas de mão única. Esses gráficos são especiais no sentido de que algumas arestas são mais importantes que outras para viagens de longa distância (por exemplo, rodovias). Esta propriedade foi formalizada usando a noção de dimensão da estrada. Há um grande número de algoritmos que exploram essa propriedade e, portanto, são capazes de calcular o caminho mais curto muito mais rapidamente do que seria possível em gráficos gerais.

Todos esses algoritmos funcionam em duas fases. Na primeira fase, o gráfico é pré-processado sem conhecer o nó de origem ou destino. A segunda fase é a fase de consulta. Nesta fase, o nó de origem e o destino são conhecidos. A ideia é que a rede rodoviária seja estática; portanto, a fase de pré-processamento pode ser realizada uma vez e usada para um grande número de consultas na mesma rede rodoviária.

O algoritmo com o tempo de consulta mais rápido conhecido é chamado de rotulagem de hub e é capaz de calcular o caminho mais curto nas redes rodoviárias da Europa ou dos EUA em uma fração de microssegundo. Outras técnicas que foram usadas são:

• ALT (pesquisa A *, pontos de referência e desigualdade de triângulo)
• Bandeiras de arco
• Hierarquias de contração
• Roteamento do nó de trânsito
• Poda baseada em alcance
• Marcação
• Etiquetas do hub

Em situações da vida real, a rede de transporte geralmente é estocástica e depende do tempo. De fato, um viajante que atravessa um link diariamente pode experimentar diferentes tempos de viagem nesse link, devido não apenas às flutuações na demanda de viagens (matriz de origem-destino), mas também devido a incidentes como zonas de trabalho, más condições climáticas, acidentes e avarias de veículos. Como resultado, uma rede estocástica dependente do tempo (DST) é uma representação mais realista de uma rede rodoviária real em comparação com a rede determinística.

Apesar dos progressos consideráveis ​​ao longo da década passada, continua sendo uma questão controversa como um caminho ideal deve ser definido e identificado nas redes rodoviárias estocásticas. Em outras palavras, não existe uma definição única de um caminho ideal sob incerteza. Uma resposta possível e comum a essa pergunta é encontrar um caminho com o tempo mínimo de viagem esperado. A principal vantagem do uso dessa abordagem é que algoritmos eficientes de caminho mínimo introduzidos para as redes determinísticas podem ser facilmente empregados para identificar o caminho com o tempo de viagem mínimo esperado em uma rede estocástica. No entanto, o caminho ideal resultante identificado por essa abordagem pode não ser confiável, porque essa abordagem falha em lidar com a variabilidade do tempo de viagem. Para resolver esse problema, alguns pesquisadores usam a distribuição do tempo de viagem em vez do valor esperado para encontrar a distribuição de probabilidade do tempo total de viagem usando diferentes métodos de otimização, como programação dinâmica e algoritmo de Dijkstra. Esses métodos usam otimização estocástica, especificamente estocástica programação dinâmica para encontrar o caminho mais curto em redes com comprimento de arco probabilístico. O conceito de confiabilidade do tempo de viagem é usado de forma intercambiável com a variabilidade do tempo de viagem na literatura de pesquisa em transporte, de modo que, em geral, pode-se dizer que quanto maior a variabilidade no tempo de viagem, menor a confiabilidade e vice-versa.

Para explicar a confiabilidade do tempo de viagem com mais precisão, foram sugeridas duas definições alternativas comuns para um caminho ideal sob incerteza. Alguns introduziram o conceito do caminho mais confiável, com o objetivo de maximizar a probabilidade de chegar a tempo ou antes de um determinado orçamento de tempo de viagem. Outros, em alternativa, propuseram o conceito de um caminho α confiável com base no qual pretendiam minimizar o orçamento de tempo de viagem necessário para garantir uma probabilidade de chegada pontual pré-especificada.

• Andrew V. Goldberg (2009). The Shortest Path Problem (Dimacs Series in Discrete Mathematics and Theoretical Computer Science). USA: American Mathematical Society. ISBN 978-0821843833 

• Portal da matemática