Análise do desempenho de técnicas de otimização aplicadas ao algortimo A* híbrido para busca de rotas de veículos
Visualizar/ Abrir
Data
2019-12-11Autor
Santos, Adrian Kaminski dos
Metadata
Mostrar registro completoResumo
Este trabalho de graduação propõe o desenvolvimento de técnicas de otimização,
aplicadas ao algoritmo A* Híbrido para busca de caminhos para veículos, baseado na
implementação utilizada na navegação local de viaturas no sistema de simulação
SIS-ASTROS. Durante o trabalho foi implementado, utilizando a linguagem C#, uma
adaptação do algoritmo. Foram desenvolvidas duas técnicas: para otimização de cálculos de
intersecção com polígonos (obstáculos para os veículos) foi implementada uma hash de
aproximação de polígono, com tempo de avaliação de complexidade O(1), e para otimização
da heurística do algoritmo foi utilizada o algoritmo de Dijkstra sobre um grafo de visibilidade.
Ambas técnicas foram avaliadas em diferentes cenários de teste, e apresentaram desempenho
superior aos algoritmos utilizados como comparação neste trabalho no que tange o tempo de
execução de uma busca de caminhos.
Coleções
Os arquivos de licença a seguir estão associados a este item: