EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC 4.0

Scaling Analysis of Maze-Solving Algorithms: From BFS And Dijkstra to Heuristic A*

Kewen Zhu

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →