BDBComp
Parceria:
SBC
Busca Heurística de Melhor Caminho entre Dois Pontos quando Múltiplas Origens e Múltiplos Destinos São Possíveis

Caio PonteCarlos CaminhaVasco Furtado

Algoritmos de busca do caminho mais curto, embora possuam complexidade de tempo exponencial, são satisfatoriamente aplicados quando o fator de ramificação e o caminho mais curto não são muito extensos. No entanto, quando o objetivo é encontrar um bom caminho entre duas regiões do grafo que envolve múltiplas origens e múltiplos destinos, esses algoritmos não conseguem resolver isso de uma maneira eficiente, pois precisam realizar reiteradas buscas entre as origens e os destinos. Neste artigo, propomos um algoritmo de busca em grafo que colapsa os círculos que definem as respectivas áreas de origem e de destino formando dois super nós. Estes super nós mantém, no entanto, as mesmas conexões que existiam antes do colapso. Seguindo esse enfoque algoritmos de melhor caminho como A* ou Busca em Largura podem ser aplicados com melhora significativa de tempo, o que o faz uma alternativa para uso em situações específicas em que as exigências de performance se impõem à otimalidade. Mostramos, num cenário de mobilidade em transporte coletivo, onde isso se aplica.

http://www.lbd.dcc.ufmg.br/colecoes/eniac/2016/024.pdf

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato: bdbcomp@lbd.dcc.ufmg.br
     Mantida por:
LBD