Scaling Analysis of Maze-Solving Algorithms: From BFS And Dijkstra to Heuristic A*
Mathematical Modeling and Algorithm Application · 15.03.2026 · 9 (1) · 189-195
DOI: 10.54097/arvg8s77 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Modeling and Algorithm Application, online erschienen am 15.03.2026. Verfasst von Kewen Zhu. Die Arbeit wurde bisher 1-mal zitiert (Crossref). Der Volltext ist frei zugänglich (Open Access, CC BY-NC 4.0).
Abstract (Originalsprache)
The maze solving has long been regarded as a fundamental problem in computer science and artificial intelligence. By modeling a maze as a weighted graph through the skeletonization, the problem can be approached as a path-finding task. This paper presents an empirical study that evaluates the classical search algorithms including BFS, DFS, Dijkstra alongside heuristic search methods (standard A* with Manhattan distance and a turn-penalized A* variant). Using mazes of varying and averaging results across multiple random seeds, the experiments measure performance in terms of expanded nodes, and runtime. Furthermore, log–log regression is applied to characterize the empirical scaling behavior of each algorithm. The results show that all algorithms exhibit near-linear growth in both node expansions and runtime, but differ significantly in constant factors. The turn-penalized A* demonstrates the influence of the heuristic design on search cost and path smoothness, highlighting trade-offs between the human-inspired intuition and the algorithmic optimality.
Zitieren
APA
Zhu, K. (2026). Scaling Analysis of Maze-Solving Algorithms: From BFS And Dijkstra to Heuristic A*. Mathematical Modeling and Algorithm Application, 9(1), 189-195. https://doi.org/10.54097/arvg8s77
Vancouver
Zhu K. Scaling Analysis of Maze-Solving Algorithms: From BFS And Dijkstra to Heuristic A*. Mathematical Modeling and Algorithm Application. 2026;9(1):189-195. doi:10.54097/arvg8s77
BibTeX
@article{Zhu2026,
author = {Zhu, Kewen},
title = {Scaling Analysis of Maze-Solving Algorithms: From BFS And Dijkstra to Heuristic A*},
journal = {Mathematical Modeling and Algorithm Application},
year = {2026},
volume = {9},
number = {1},
pages = {189--195},
doi = {10.54097/arvg8s77}
}
EUVIMED