EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Left-Hand Rule versus BFS: A Trade-Off Study in Maze Solving

Weijing Huang

ITM Web of Conferences · 2026 · 93 · 02011

DOI: 10.1051/itmconf/20269302011 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ITM Web of Conferences, online erschienen am 13.11.2026. Verfasst von Weijing Huang. Die Arbeit nennt 10 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The maze-solving process is a fundamental benchmark for evaluating path search algorithms and is closely related to robot navigation, circuit routing, and network routing. This paper conducts an experimental comparison of two fundamentally different methods: the left-hand along the wall rule (a purely reactive, memory-efficient approach) and breadth-first search (BFS, a globally optimal graph traversal algorithm). Both algorithms are implemented in OCaml and tested in three large multi-loop grid mazes encoded by bitmask wall strings. The left-hand rule successfully reached the goal in each instance, but the generated path lengths were 2.8 to 10 times the optimal solution, with step counts being 1161, 188, and 623 respectively, while BFS corresponded to 117, 68, and 69. BFS always outputs the shortest path, but it requires O(W×H) memory to store the access matrix and parent node matrix, while the left-hand rule only consumes a very small amount of incremental memory. The results empirically confirm the fundamental trade-off between optimality and resource efficiency. This paper also describes the elimination of recursion and the adoption of array queues and other engineering adaptations, which ensure that the code can run stably in both local and Try OCaml environments.

Zitieren

APA

Huang, W. (2026). Left-Hand Rule versus BFS: A Trade-Off Study in Maze Solving. ITM Web of Conferences, 93, 02011. https://doi.org/10.1051/itmconf/20269302011

Vancouver

Huang W. Left-Hand Rule versus BFS: A Trade-Off Study in Maze Solving. ITM Web of Conferences. 2026;93:02011. doi:10.1051/itmconf/20269302011

BibTeX
@article{Huang2026,
  author = {Huang, Weijing},
  title = {Left-Hand Rule versus BFS: A Trade-Off Study in Maze Solving},
  journal = {ITM Web of Conferences},
  year = {2026},
  volume = {93},
  pages = {02011},
  doi = {10.1051/itmconf/20269302011}
}
Kostenlos starten →