Pathfinding

Was ist Pathfinding?

Unter Pathfinding versteht man in der Informatik Algorithmen, mit welchen der optimale Weg zwischen zwei oder mehreren Punkten gefunden werden soll. Dabei kann der optimale Weg anhand von unterschiedlichen Parametern definiert werden.

Der optimale Weg ist immer vom jeweiligen Anwendungsfall abhängig. Neben dem kürzesten Weg kann beispielsweise auch der kostengünstigste Weg als Optimum definiert werden. Beispielsweise können auch andere Nebenbedingungen wie das Vermeiden von gewissen Wegpunkten oder Streckenabschnitten die Bestimmung des optimalen Weges beeinflussen.

Dieses Verhalten ist im Allgemeinen bei Routenplanern bekannt, wenn Autobahnen oder Mautstraßen vermieden werden sollen.

Algorithmen

Je nach Anforderung der Zielsetzung lassen sich im Rahmen des Pathfinding verschiedene Algorithmen anwenden.

Beim A*-Algorithmus handelt es sich um einen sogenannten informierten Suchalgorithmus, welcher den kürzesten Graphen zwischen zwei Punkten mithilfe einer Schätzfunktion/Heuristik ermittelt. Bei der Suche wird (vom Startpunkt aus gesehen) jener Folgeknoten untersucht, welcher wahrscheinlich schnell zum Ziel führt bzw. die Entfernung zum Zielknoten verringert. Ist eine Untersuchung eines Knotens nicht zielführend, wird dieser als solcher markiert und die Suche wird mit einem anderen Knoten fortgesetzt. Gemäß diesem Algorithmus wird der kürzeste Weg zum Zielknoten untersucht.

Ein weiterer Algorithmus zur Ermittlung des kürzesten Pfades ist der Algorithmus von Dijkstra. Dieser basiert nicht auf Heuristik, sondern auf Basis der Vorgehensweise, dass vom Startknoten ausgehend alle Knoten mit den kürzesten Teilstrecken zueinander zur Optimallösung führen, indem die Summe der kürzesten Teilstrecken zum insgesamt kürzesten Gesamtpfad führt. Somit funktioniert die Vorgehensweise in Form der aussichtsreichsten Teillösung.

Im Gegensatz zu den bisher beschriebenen Vorgehensweisen erlaubt der Bellman-Ford-Algorithmus (bzw. Moore-Bellman-Ford-Algorithmus) auch die Betrachtung von Graphen mit negativen Kantengewichten zur Ermittlung der kürzesten Pfade. Dies bedeutet, dass die Kosten (z. B. Zeit) zwischen zwei Knoten auch negativ sein können. Es muss jedoch sichergestellt sein, dass Zyklen durch negative Gewichte ausgeschlossen werden, da sich ansonsten der Pfad durch wiederholtes Durchlaufen der negativen Kantengewichte verringert. Alle bisher betrachteten Vorgehensweisen optimieren den Pfad von einem bestimmten Knoten aus gesehen.

Der Min-Plus-Matrixmultiplikations-Algorithmus sucht hingegen das Optimum sämtlicher Knotenpaare zueinander.

Gleiches gilt für den Floyd-Warshall-Algorithmus. Das Verfahren macht sich dabei die Vorgehensweise der dynamischen Programmierung zunutze. Zur Findung des Optimums wird das Gesamtproblem in gleichartige Teilprobleme geteilt und anschließend durch die Lösung und Speicherung dieser zu einer Optimierung des Gesamtproblems übergeführt. Die Funktionsweise ist zweigeteilt, wobei der Teil von Floyd dafür sorgt, dass die kürzesten Distanzen zwischen den Knoten berechnet werden, während der Teil von Warshall für die Konstruktion der kürzesten Pfade zuständig ist. Auch die Betrachtung von negativen Kantengewichten ist bei diesem Algorithmus möglich.

Während manche Verfahren die Optimierung zwischen zwei Knotenpunkten als Zielsetzung haben, optimieren andere sämtliche Knotenpunkte zueinander. Dies führt natürlich zu einer Erhöhung der Rechenleistung. Deshalb ist neben der Betrachtung der Zielsetzung bei der Wahl des Algorithmus mitunter auch die Beanspruchung der Ressourcen ein ausschlaggebender Faktor. Neben der Rechenleistung können auch der benötigte Speicherplatz und die Laufzeit relevante Größen bei der Wahl des Verfahrens darstellen.

Für manche der beschriebenen Verfahren bestehen vorgefertigte Algorithmen, welche in eigene Lösungen implementiert werden können. So kann unter anderem die Bibliothek NetworkX in Python implementiert und als Framework für die Pathfinding-Probleme genutzt werden.

Beispiele für die Anwendung von Pathfinding in der Praxis

Die Anwendungsmöglichkeiten von Pathfinding sind vielfältig. Sie reichen von einfachen sowie komplexen Steuerungen und Routenplanungen im Computerspiel-Sektor bis hin zur Lösung von Transportlogistikproblemen und der Optimierung von Routing-Problemen im Netzwerk-Sektor. Zur Unterstützung der Optimierungslösungen können auch Teilbereiche der Künstlichen Intelligenz implementiert werden.

Wie eingangs erwähnt, kann das zu erreichende Optimum individuell definiert sein. Die Begrenzung der Kostengröße kann durch Minimierung des Faktors Zeit, Geld, Zwischenstopps und vielen anderen Parametern dargestellt werden.

Data Navigator Newsletter