Komparasi Kinerja Algoritma BFS, Dijkstra, Greedy BFS, dan A* dalam Melakukan Pathfinding
DOI:
https://doi.org/10.14421/jiska.2020.53-07Abstract
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
Additional Files
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms as stated in http://creativecommons.org/licenses/by-nc/4.0
a. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
b. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
c. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.