Problema do caminho mínimo

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.

O caminho mínimo entre D e E não é D-E, mas sim D-F-E, com uma distância de 14.

Formalmente, dado um grafo valorado (ou seja, um conjunto V de vértices, um conjunto A de arestas e uma função de peso $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

\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 $v$ e cada inteiro $i\leq k$ , $dist(v,i)$ como o menor caminho de $s$ até $v$ que usa $i$ arestas. Os valores iniciais de $dist(v,0)$ são $\infty$ para todos os vértices exceto $s$ , para o qual é 0. E a equação geral de atualização é:

$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ó.

Aplicações

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.

Redes rodoviárias

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

Caminho mais curto em redes estocásticas dependentes do tempo

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

Referências

↑ Christian Pretzsch (2007). IT-Case Study: Ontology-Based Answer Selection in Dialog Systems (em inglês). USA: VDM Verlag Dr. Mueller e.K. ISBN 978-3836405102
↑ Baras, John; George Theodorakopoulos (2010). Path Problems in Networks. [S.l.]: Morgan & Claypool Publishers. p. 5. ISBN 9781598299243 |acessodata= requer |url= (ajuda)

Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James; Tarjan, Robert E. (abril de 1990). «Faster algorithms for the shortest path problem». ACM. Journal of the ACM. 37 (2): 213–223. doi:10.1145/77600.77615
Bellman, Richard (1958). «On a routing problem». Quarterly of Applied Mathematics. 16: 87–90. MR 0102435. doi:10.1090/qam/102435
Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996). «Shortest paths algorithms: theory and experimental evaluation». Mathematical Programming. Ser. A. 73 (2): 129–174. MR 1392160. doi:10.1016/0025-5610(95)00021-6
Predefinição:Introduction to Algorithms
Dantzig, G. B. (janeiro de 1960). «On the Shortest Route through a Network». Management Science. 6 (2): 187–190. doi:10.1287/mnsc.6.2.187
Derniame, Jean Claude; Pair, Claude (1971), Problèmes de cheminement dans les graphes (Path Problems in Graphs), Dunod (Paris)
Dijkstra, E. W. (1959). «A note on two problems in connexion with graphs». Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390
Ford, L. R. (1956). «Network Flow Theory». Rand Corporation. P-923
Fredman, Michael Lawrence; Tarjan, Robert E. (1984). Fibonacci heaps and their uses in improved network optimization algorithms. 25th Annual Symposium on Foundations of Computer Science. IEEE. pp. 338–346. ISBN 0-8186-0591-X. doi:10.1109/SFCS.1984.715934
Fredman, Michael Lawrence; Tarjan, Robert E. (1987). «Fibonacci heaps and their uses in improved network optimization algorithms». Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874
Gabow, H. N. (1983). «Scaling algorithms for network problems». Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS 1983) (PDF). pp. 248–258. doi:10.1109/SFCS.1983.68
Gabow, Harold N. (1985). «Scaling algorithms for network problems». Journal of Computer and System Sciences. 31 (2): 148–168. MR 828519. doi:10.1016/0022-0000(85)90039-X
Hagerup, Torben (2000). Montanari, Ugo; Rolim, José D. P.; Welzl, Emo, eds. Improved Shortest Paths on the Word RAM. Proceedings of the 27th International Colloquium on Automata, Languages and Programming. [S.l.: s.n.] pp. 61–72. ISBN 978-3-540-67715-4
Johnson, Donald B. (1977). «Efficient algorithms for shortest paths in sparse networks». Journal of the ACM. 24 (1): 1–13. doi:10.1145/321992.321993
Johnson, Donald B. (dezembro de 1981). «A priority queue in which initialization and queue operations take $O (log log D)$ time». Mathematical Systems Theory. 15 (1): 295–309. MR 683047. doi:10.1007/BF01786986
Karlsson, Rolf G.; Poblete, Patricio V. (1983). «An $O (m log log D)$ algorithm for shortest paths». Discrete Applied Mathematics. 6 (1): 91–93. MR 700028. doi:10.1016/0166-218X(83)90104-X
Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, S. R., Jr.; Petry, R. M.; Seitz, R. N. (1957). Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems. Cleveland, Ohio: Case Institute of Technology
Moore, E. F. (1959). «The shortest path through a maze». Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 April 1957). Cambridge: Harvard University Press. pp. 285–292
Pettie, Seth; Ramachandran, Vijaya (2002). Computing shortest paths with comparisons and additions. Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms. [S.l.: s.n.] pp. 267–276. ISBN 978-0-89871-513-2
Pettie, Seth (26 de janeiro de 2004). «A new approach to all-pairs shortest paths on real-weighted graphs». Theoretical Computer Science. 312 (1): 47–74. doi:10.1016/s0304-3975(03)00402-x
Pollack, Maurice; Wiebenson, Walter (março–abril de 1960). «Solution of the Shortest-Route Problem—A Review». Oper. Res. 8 (2): 224–230. doi:10.1287/opre.8.2.224 Attributes Dijkstra's algorithm to Minty ("private communication") on p. 225.
Schrijver, Alexander (2004). Combinatorial Optimization — Polyhedra and Efficiency. Col: Algorithms and Combinatorics. 24. [S.l.]: Springer. ISBN 978-3-540-20456-5 Here: vol.A, sect.7.5b, p. 103
Shimbel, Alfonso (1953). «Structural parameters of communication networks». Bulletin of Mathematical Biophysics. 15 (4): 501–507. doi:10.1007/BF02476438
Shimbel, A. (1955). Structure in communication nets. Proceedings of the Symposium on Information Networks. New York, NY: Polytechnic Press of the Polytechnic Institute of Brooklyn. pp. 199–203
Thorup, Mikkel (1999). «Undirected single-source shortest paths with positive integer weights in linear time». Journal of the ACM. 46 (3): 362–394. doi:10.1145/316542.316548
Thorup, Mikkel (2004). «Integer priority queues with decrease key in constant time and the single source shortest paths problem». Journal of Computer and System Sciences. 69 (3): 330–353. doi:10.1016/j.jcss.2004.04.003
Whiting, P. D.; Hillier, J. A. March–June 1960. «A Method for Finding the Shortest Route through a Road Network». Operational Research Quarterly. 11 (1/2): 37–40. doi:10.1057/jors.1960.32
Williams, Ryan (2014). «Faster all-pairs shortest paths via circuit complexity». Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC '14). New York: ACM. pp. 664–673. MR 3238994. arXiv:1312.6680 . doi:10.1145/2591796.2591811

[1] Christian Pretzsch (2007). IT-Case Study: Ontology-Based Answer Selection in Dialog Systems (em inglês). USA: VDM Verlag Dr. Mueller e.K. ISBN 978-3836405102

[2] Baras, John; George Theodorakopoulos (2010). Path Problems in Networks. [S.l.]: Morgan & Claypool Publishers. p. 5. ISBN 9781598299243 |acessodata= requer |url= (ajuda)

[1]

[2]