A Comparative Study of Maze-Solving Algorithms: Breadth-First Search, A and Binary Tree with Depth-First Search
DOI:
https://doi.org/10.54097/kac3r412Keywords:
BFS, A*, binary tree.Abstract
Maze solving has been an important problem in computer science for a long time, which is used as a model for searching, optimization, and path finding. This study compares three representative algorithms: Breadth-First Search (BFS), A*, and Binary Tree combined with Depth-First Search (DFS). And the study tests the time they cost of different sizes of mazes. Experimental results show that all methods perform similarly in small size mazes with the execution times under 0.1 seconds. However, as maze size increases, BFS and A* are able to maintain efficiency and scalability while the method of Binary Tree + DFS becomes significantly slower and impractical for large size mazes. BFS ensures the shortest solution path but it requires higher memory at the same time. A* achieves a balance between optimality and efficiency through heuristic functions. Binary Tree & DFS provides educational value in demonstrating recursive searching though less scalable, Overall, the study concludes that BFS and A* are more applicable to the real-world path finding problems while Binary Tree & DFS is more suitable for teaching structural search processes than the other 2 methods.
Downloads
References
[1] Cormen T H, Leiserson C E, Rivest R L, Stein C. Introduction to Algorithms. 3rd ed. Cambridge: MIT Press, 2009.
[2] Moore E F. The shortest path through a maze. In: Proceedings of the International Symposium on the Theory of Switching. Cambridge: Harvard University Press, 1959.
[3] Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 1968, 4 (2): 100 – 107.
[4] Cayley A. On the theory of the analytical forms called trees. Philosophical Magazine, 1857, 13 (85): 172 – 176.
[5] Dijkstra E W. A note on two problems in connection with graphs. Numerische Mathematik, 1959, 1: 269 – 271.
[6] Wikipedia. Breadth-first search [EB/OL]. https://en.wikipedia.org/wiki/Breadth-first_search, 2025 - 09 - 12.
[7] GeeksforGeeks. Time and space complexity of DFS and BFS algorithm [EB/OL]. https://www.geeksforgeeks.org/dsa/time-and-space-complexity-of-dfs-and-bfs-algorithm/, 2025 - 09 - 12.
[8] Dinh H Q, Dinh H T. Inconsistency and accuracy of heuristics with A* search. arXiv preprint arXiv: 1307.2200, 2013.
[9] Agostinelli F, McAleer S, Shmakov A, Baldi P. Obtaining approximately admissible heuristic functions. arXiv preprint arXiv:2106.01473, 2021.
[10] Prieditis A E. Machine discovery of effective admissible heuristics. Machine Learning, 1993, 12 (1 – 3): 117 – 141.
[11] Knuth D E. Fundamental Algorithms. The Art of Computer Programming, Vol. 1. 3rd ed. Boston: Addison-Wesley, 1997.
[12] Wikipedia. Depth-first search [EB/OL]. https://en.wikipedia.org/wiki/Depth-first_search, 2025-09 - 12.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Highlights in Science, Engineering and Technology
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
