Comparing the pathfinding algorithms A*, Dijkstra’s, Bellman-Ford, Floyd-Warshall, and best first search for the paparazzi problem
Kein Vorschaubild vorhanden
Autor:in (Körperschaft)
Publikationsdatum
2022
Typ der Arbeit
Studiengang
Typ
04B - Beitrag Konferenzschrift
Herausgeber:innen
Herausgeber:in (Körperschaft)
Betreuer:in
Übergeordnetes Werk
Congress on Intelligent Systems. Proceedings of CIS 2021
Themenheft
DOI der Originalpublikation
Link
Reihe / Serie
Lecture Notes on Data Engineering and Communications Technologies
Reihennummer
111
Jahrgang / Band
2
Ausgabe / Nummer
Seiten / Dauer
561-576
Patentnummer
Verlag / Herausgebende Institution
Springer
Verlagsort / Veranstaltungsort
Singapore
Auflage
Version
Programmiersprache
Abtretungsempfänger:in
Praxispartner:in/Auftraggeber:in
Zusammenfassung
This paper aims to compare A*, Dijkstra, Bellmann-Ford, Floyd-Warshall, and best first search algorithms to solve a particular variant of the pathfinding problem based on the so-called paparazzi problem. This problem consists of a grid with different non-moving obstacles that lead to different traversing costs which are considered as minimization objective in a specific model. The performance of the algorithms that solve the paparazzi problem is compared in terms of computation time, the number of visited nodes, shortest path cost, and accuracy of finding the shortest path. The comparison shows that heuristic algorithms mostly provide the optimal path but with a shorter computation time.
Schlagwörter
Fachgebiet (DDC)
330 - Wirtschaft
Veranstaltung
2nd Congress on Intelligent Systems CIS 2021
Startdatum der Ausstellung
Enddatum der Ausstellung
Startdatum der Konferenz
Enddatum der Konferenz
Datum der letzten Prüfung
ISBN
978-981-16-9112-6
978-981-16-9113-3
978-981-16-9113-3
ISSN
Sprache
Englisch
Während FHNW Zugehörigkeit erstellt
Ja
Zukunftsfelder FHNW
Publikationsstatus
Veröffentlicht
Begutachtung
Peer-Review der ganzen Publikation
Open Access-Status
Closed
Lizenz
Zitation
JOHNER, Robert, Antonino LANAIA, Rolf DORNBERGER und Thomas HANNE, 2022. Comparing the pathfinding algorithms A*, Dijkstra’s, Bellman-Ford, Floyd-Warshall, and best first search for the paparazzi problem. In: Mukesh SARASWAT, Harish SHARMA, K. BALACHANDRAN, Joong Hoon KIM und Jagdish Chand BANSAL (Hrsg.), Congress on Intelligent Systems. Proceedings of CIS 2021. Singapore: Springer. 2022. S. 561–576. Lecture Notes on Data Engineering and Communications Technologies, 111. ISBN 978-981-16-9112-6. Verfügbar unter: https://irf.fhnw.ch/handle/11654/48193