Komparasi Kinerja Algoritma BFS, Dijkstra, Greedy BFS, dan A* dalam Melakukan Pathfinding

Authors

  • Nadila Sugianti
  • Ainatul Mardhiyah
  • Nurma Romihim Fadilah

DOI:

https://doi.org/10.14421/jiska.2020.53-07

Abstract

Pathfinding is a computational process in finding the best route between two points or nodes to find the shortest path. This method has many algorithms that can be applied in various fields. In carrying out the pathfinding, speed and distance are considered as important. Through the test diagram, this paper illustrates the execution steps related to the pathfinding algorithm which includes BFS, Dijkstra, Greedy BFS, and A * for comparison. From several studies, the authors identified that execution time and mileage can be used optimally in the comparison process. Input variables as well as media used are 2-dimensional grids and heuristic function calculations. The analogy is carried out on a unity platform with the C# programming language, producing A * as a more flexible pathfinding algorithm to be implemented in various domains.

References

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press.

Gonçalves, S. M. M., Da Rosa, L. S., & Marques, F. S. (2019). An improved heuristic function for A*-based path search in detailed routing. Proceedings - IEEE International Symposium on Circuits and Systems, 2019-May. https://doi.org/10.1109/ISCAS.2019.8702460

Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics. https://doi.org/10.1109/TSSC.1968.300136

Lawrence, R., & Bulitko, V. (2012). Database-Driven Real-Time Heuristic Search in Video-Game Pathfinding. IEEE Transactions on Computational Intelligence and AI in Games, 5(3), 227–241. https://doi.org/10.1109/TCIAIG.2012.2230632

Mahmud, M. S., Sarker, U., Islam, M. M., & Sarwar, H. (2012). A Greedy Approach in Path Selection for DFS Based Maze-map Discovery Algorithm for an autonomous robot. Proceeding of the 15th International Conference on Computer and Information Technology, ICCIT 2012. https://doi.org/10.1109/ICCITechn.2012.6509798

Ortega-Arranz, H., Llanos, D. R., & Gonzalez-Escribano, A. (2014). The Shortest-Path Problem: Analysis and Comparison of Methods. Synthesis Lectures on Theoretical Computer Science, 1(1), 1–87. https://doi.org/10.2200/s00618ed1v01y201412tcs001

Risald, Mirino, A. E., & Suyoto. (2017). Best routes selection using Dijkstra and Floyd-Warshall algorithm. Proceedings of the 11th International Conference on Information and Communication Technology and System, ICTS 2017, 155–158. https://doi.org/10.1109/ICTS.2017.8265662

Wang, C., Liu, J., Deng, L., Yunyun, X., Lin, S., Xu, H., Zheng, R., & Cao, X. (2015). Research on the optimization of the DC converter station recovery path based on BFS. 10th International Conference on Advances in Power System Control, Operation & Management (APSCOM 2015), 2015(8). https://doi.org/10.1049/ic.2015.0282

Yiu, Y. F., Du, J., & Mahapatra, R. (2018). Evolutionary Heuristic A∗ Search: Heuristic Function Optimization via Genetic Algorithm. Proceedings - 2018 1st IEEE International Conference on Artificial Intelligence and Knowledge Engineering, AIKE 2018, 25–32. https://doi.org/10.1109/AIKE.2018.00012

Zhao, L., & Zhao, J. (2017). Comparison study of three shortest path algorithm. Proceedings - 2017 International Conference on Computer Technology, Electronics and Communication, ICCTEC 2017, 748–751. https://doi.org/10.1109/ICCTEC.2017.00165

Downloads

Published

2020-11-10

How to Cite

Sugianti, N., Mardhiyah, A., & Fadilah, N. R. (2020). Komparasi Kinerja Algoritma BFS, Dijkstra, Greedy BFS, dan A* dalam Melakukan Pathfinding. JISKA (Jurnal Informatika Sunan Kalijaga), 5(3), 194–204. https://doi.org/10.14421/jiska.2020.53-07