Different optimization methods for solving the rush hour puzzle
Lade...
Autor:in (Körperschaft)
Publikationsdatum
2026
Typ der Arbeit
Studiengang
Typ
04B - Beitrag Konferenzschrift
Herausgeber:innen
Herausgeber:in (Körperschaft)
Betreuer:in
Übergeordnetes Werk
2026 8th International Symposium on Computational and Business Intelligence (ISCBI)
Themenheft
DOI der Originalpublikation
Link
Zugehörige Forschungsdaten
Reihe / Serie
Reihennummer
Jahrgang / Band
Ausgabe / Nummer
Seiten / Dauer
333-337
Patentnummer
Verlag / Herausgebende Institution
IEEE
Verlagsort / Veranstaltungsort
Bali
Auflage
Version
Programmiersprache
Abtretungsempfänger:in
Praxispartner:in/Auftraggeber:in
Zusammenfassung
The rush hour puzzle is a widely recognized benchmark problem used to evaluate search algorithms in artificial intelligence. It presents a constrained, grid-based planning task that is known to be PSPACE-complete and serves as a useful model for studying computational complexity, heuristic search, and constraint satisfaction. This paper compares three optimization methods: Breadth-First Search (BFS), A*, and Greedy Best-First Search (GBFS) in their ability to solve rush hour puzzles efficiently. A Python-based prototype was developed to perform 100 benchmark runs on 6 × 6 and 9 × 9 grid configurations at hard difficulty. The analysis focuses on the solver success rate, timeouts, and normalized efficiency metrics, including time per step and nodes per step. The results show that GBFS consistently achieves the fastest performance with the highest solve rate, while $\mathbf{A}^{*}$ offers a balance between solution quality and runtime. BFS, although complete, struggles with scalability. These findings provide practical insights into the trade-offs between completeness, optimality, and computational efficiency in pathfinding under constraints.
Schlagwörter
Fachgebiet (DDC)
Veranstaltung
2026 8th International Symposium on Computational and Business Intelligence (ISCBI)
Startdatum der Ausstellung
Enddatum der Ausstellung
Startdatum der Konferenz
06.02.2026
Enddatum der Konferenz
08.02.2026
Datum der letzten Prüfung
ISBN
979-8-3315-5080-6
979-8-3315-5079-0
979-8-3315-5081-3
979-8-3315-5079-0
979-8-3315-5081-3
ISSN
Sprache
Englisch
Während FHNW Zugehörigkeit erstellt
Ja
Zukunftsfelder FHNW
Publikationsstatus
Veröffentlicht
Begutachtung
peer-reviewed
Open Access-Status
Closed
Zitation
Gafirov, A., Dornberger, R., & Hanne, T. (2026). Different optimization methods for solving the rush hour puzzle. 2026 8th International Symposium on Computational and Business Intelligence (ISCBI), 333–337. https://doi.org/10.1109/iscbi69404.2026.11496271