Variações e aplicações do algoritmo de Dijkstra / Variants and applications of Dijkstra s algorithms

AUTOR(ES)
DATA DE PUBLICAÇÃO

2007

RESUMO

O problema de encontrar caminhos mínimos em um grafo com pesos nas arestas é considerado fundamental em otimização combinatória. Diversos problemas do mundo real podem ser modelados dessa forma: percurso mais curto/rápido entre duas cidades, transmissão de dados em uma rede de computadores, reconhecimento de voz, segmentação de imagens entre outros. O algoritmo proposto por Dijkstra em 1959 resolve o problema de caminhos mínimos em grafos sem arestas de peso negativo, o que não chega a ser restritivo na maior parte das aplicações. Desde então, o algoritmo tem sido refinado com o uso de estruturas de dados cada vez mais sofisticadas, reduzindo seu tempo de execução de pior caso (ao menos, do ponto de vista teórico). Recentemente, problemas de caminhos mínimos têm aparecido no contexto de Sistemas de Informação Geográfica (SIG). Neste modelo, o usuário faz consultas ao sistema para encontrar o trajeto mais curto (ou rápido) entre dois pontos especificados (problema ponto-a-ponto ou problema P2P). Além disso, pode haver várias consultas. Instâncias neste tipo de modelo são relativamente grandes: o mapa rodoviário dos Estados Unidos tem mais de 20 milhões de vértices (cada vértice representa intersecções de vias). Mesmo as implementações mais sofisticadas do algoritmo de Dijkstra não apresentam um desempenho prático capaz de atender às demandas que esse tipo de modelo requer. A pesquisa recente tem tentado reduzir este gap entre a teoria e a prática. Várias técnicas de aceleração de algoritmos têm sido propostas e implementadas: busca bidirecional, algoritmo A*, alcance (reach), landmarks e muitos outros. Algumas dessas técnicas têm restrições de domínio e outras podem ser usadas em qualquer contexto. Neste trabalho, estudamos algumas variações da versão original do algoritmo de Dijkstra, caracterizadas pelas diferentes estruturas de dados. Implementamos quatro dessas variações e realizamos testes experimentais utilizando os mapas do mundo real. Nosso objetivo foi analisar o desempenho prático dessas. Dedicamos também uma atenção especial ao problema P2P, apresentando algumas das principais técnicas de aceleração.

ASSUNTO(S)

estruturas de dados (computação) data structures (computer science)

ACESSO AO ARTIGO

Documentos Relacionados