Visualisierung der Pathfinder

Auf der rechten Seite sieht man die in der Einführung erwähnten Pathfinder «in action». Der grüne Block repräsentiert jeweils den Endpunkt und der blaue den Startpunkt. Der ausgewählte Pathfinder findet zwischen diesen zwei Pünkten dann den passenden Weg.

Diese Seite soll zur kurzen visuellen Einführung in die Pathfinder dienen. Parameter lassen sich vom Nutzer unter «Steuerung» anpassen.

A*-Pathfinder Beschreibung

Der A*-Algorithmus, gesprochen "A-Star", untersucht mithilfe einer Heuristik immer den wahrscheinlich nächsten Knoten im Raster, der zum Ziel führt. Jedem Nachbarknoten wird zuerst einen Wert d zugeordnet, der angibt, wie lange der Weg geschätzt von diesem Knoten zum Ziel führt. Der Wert d wird mit der Manhattan-Heuristik ausgerechnet. Jeder Graph mit einem d-Wert wird in eine Liste eingetragen. Der A-Star rechnet immer die neuen Nachbarn des Graphen mit dem kleinsten d-Wert aus. Dadurch kann es vorkommen, das nach langer Suche der A-Star plötzlich wieder einige Graphen zurückspringen muss, da die neu berechneten d-Werte grösser als ein früherer gefundener d-Wert ist.

BestFirstFinder Beschreibung

Mit der Benutztung der Mannhattan-Heuristik untersucht der BestFirstFinder nur den vom angeschautem Graph besten Nachbarsgraph, dies ist der Graph mit dem tiefsten Heursitikwert. Jeder beste Graph wird dann in die offene Liste eingetragen und die Suche beim nächsten Graphen wiederholt. Falls nun vom früheren Graph ein kleinerer Heursitikwert berechnet wurde und der jetztige Graph grössere Heuristikwerte in den neuen Nachbarn finden, geht der BestFirstFinder nicht zurück, ausser er landet in einer Sackgasse.

Es wird eine Liste für die offenen Knoten erstellt und der Startknoten eingetragen. Auch hier verweist jeder Knoten auf seinen Vorgänger. Der beste Knoten aus der Liste wird $n$ genannt. Der Algorithmus schaut die Nachbarn von $n$ an und bewertet diese mit der Heuristik, wobei der beste Wert in die Liste eingetragen und der Ablauf wiederholt wird. Kommt ein Knoten, der angeschaut wird nicht weiter, wird der zweitbeste Graph in der Liste angeschaut. Ee kann einer weiteren Liste hinzugefügt werden, der geschlossenen Liste, die den Lösungsweg direkt abspeichert und verhindert, dass dieser Algorithmus nicht in einer Endlosschleife endet.

BreadthFirstFinder Beschreibung

Der BreadthFirstFinder benutzt keine Heuristik, da er seinen Weg über die Breitensuche findet. Er expandiert in jede Richtung gleich schnell und bewegt sich nicht wie die anderen zwei Pathfinder in Richtung Ziel. Wenn alle Knoten mit der gleichen Distanz zum Start angeschaut sind, beginnt er mit der Suche der um eins weiter entfernten Knoten. Dieser Pathfinder besitzt eine Liste in der er die noch zu bearbeitenden Knoten speichert, beginnend mit dem am Start nächsten Knoten.

Der Algorithmus beginnt beim Startpunkt und speichert ihn in die Warteliste. Er schaut am obersten Knoten in der Warteschlange dessen Nachbarn an und prüft, ob einer der ausgewählten Knoten der Zielknoten ist. Ist dies der Fall, wird die Suche abgebrochen, da der Weg gefunden wurde. Falls keiner der Knoten der Zielknoten ist, speichert er die neuen Knoten in der Warteliste an hinterster Stelle und entfernt den ausgewählten Knoten. Jeder Knote, der neu gefunden wird, zeigt auf den ausgewählten Knoten.

Nächster Schritt

Im nächsten Schritt wird's interessant. Wir vergleichen die Pathfinder nebeneinander auf ihre Eigenschaften.

Raster



Messungen

Algorithmus:

Nicht definiert

Start- und Endpunkt:

Berechne...

Berechne...

Zurückgelegter Weg:

Berechne...

Operationen:

Berechne...

Vergangene Zeit:

Berechne...


Steuerung

1 nicht jeder pathfinder verwendet die ausgewählte Heuristik.

2 bei vorgefertigten Rastern wird die Rastergrösse nicht beachtet.