Análise e Comparação dos Algoritmos de Dijkstra e A-Estrela na Descoberta de Caminhos Mínimos em Mapas de Grade
Resumo
Este trabalho apresenta uma comparação entre dois algoritmos de descoberta de caminhos mínimos em mapas de grade. O primeiro deles é o Dijkstra, um algoritmo guloso muito conhecido por encontrar o caminho mais curto entre vértices em um dado grafo. O segundo é o A* (A-Estrela), um algoritmo que utiliza heurística para prever seu comportamento, também percorrendo um grafo e encontrando o menor caminho entre vértices. Para cada algoritmo foi adicionada uma condição de parada, demonstrando os respectivos pseudocódigos, analisando a complexidade dos mesmos e apresentando resultados promissores do A-Estrela em comparação ao Dijkstra.
Referências
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition.
Djojo, M. and Karyono, K. (2013). Computational load analysis of dijkstra, a*, and floyd-warshall algorithms in mesh network. In Robotics, Biomimetics, and Intelligent Computational Systems (ROBIONETICS), 2013 IEEE International Conference on, pages 104–108.
Eraghi, N., Lopez-Colino, F., de Castro, A., and Garrido, J. (2014). Path length comparison in grid maps of planning algorithms: Hctnav, a*; and dijkstra. In Design of Circuits and Integrated Circuits (DCIS), 2014 Conference on, pages 1–6.
Russell, S. J. and Norvig, P. (2013). Artificial Intelligence: A Modern Approach. Pearson Education, 2 edition.
Djojo, M. and Karyono, K. (2013). Computational load analysis of dijkstra, a*, and floyd-warshall algorithms in mesh network. In Robotics, Biomimetics, and Intelligent Computational Systems (ROBIONETICS), 2013 IEEE International Conference on, pages 104–108.
Eraghi, N., Lopez-Colino, F., de Castro, A., and Garrido, J. (2014). Path length comparison in grid maps of planning algorithms: Hctnav, a*; and dijkstra. In Design of Circuits and Integrated Circuits (DCIS), 2014 Conference on, pages 1–6.
Russell, S. J. and Norvig, P. (2013). Artificial Intelligence: A Modern Approach. Pearson Education, 2 edition.
Publicado
04/07/2016
Como Citar
RIOS, Marcel L.; S. NETO, Francisco S.; NETTO, José F. Magalhães.
Análise e Comparação dos Algoritmos de Dijkstra e A-Estrela na Descoberta de Caminhos Mínimos em Mapas de Grade. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 1. , 2016, Porto Alegre.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 887-890.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2016.9852.
