Lektion
Die Theorie — Pathfinding-Algorithmus-Visualizer
Drei der vier Algorithmen im Dropdown-Menü sind derselbe Algorithmus. Sie alle bewerten die Zellen, die darauf warten, expandiert zu werden, mit einem einzigen Ausdruck: f(n) = g(n) + h(n) — bisherige Kosten plus geschätzte verbleibende Kosten — und sie unterscheiden sich nur darin, welchen der beiden Terme sie beibehalten. Lässt man h weg, erhält man Dijkstra. Ignoriert man g, erhält man Greedy Best-First. Der vierte, die Breitensuche, ist das, wozu Dijkstra zusammenschrumpft, wenn jeder Schritt gleich viel kostet.
Was die einzelnen Symbole bedeuten
g(n)- die Kosten der günstigsten bisher gefundenen Route vom Start zur Zelle n. Ein seitlicher oder vertikaler Schritt kostet
1; eine Diagonale kostet√2, da der Schritt als Länge gemessen und nicht als eine einzelne Bewegung gezählt wird. h(n)- die Schätzung der noch verbleibenden Kosten. Für Dijkstra und die Breitensuche wird sie nicht bloß ungenutzt gelassen — sie ist Null, und genau das macht sie zu demselben Ausdruck mit einem fehlenden Term.
f(n)- der Sortierschlüssel: Die Zelle mit dem kleinsten
fwird als Nächstes expandiert. Er wird oberhalb des Gitters angezeigt, wobei die eigenen Zahlen der aktuellen Zelle eingesetzt sind, sodass die gerade getroffene Wahl des Algorithmus sichtbar ist, anstatt bloß behauptet zu werden. frontier- die bernsteinfarbenen Zellen — entdeckt, aber noch nicht expandiert. Expandierte Knoten zählt, was diese Menge verlassen hat, was es zu einem Maß für die geleistete Arbeit macht und nicht für die Qualität der Antwort.
Woher die Formel kommt
- Lege fest, was „kürzester“ bedeutet, bevor du einen Algorithmus wählst. Die Kosten eines Pfades sind die Summe seiner Schrittlängen:
1für eine seitliche oder vertikale Bewegung,√2für eine Diagonale. Zellen werden nicht gezählt; Entfernungen werden addiert. - Nun die Schleife, die für alle vier identisch ist: Entnimm eine Zelle aus der Front, markiere sie als besucht, und biete jedem passierbaren Nachbarn die Rückkehr in die Front mit einem aktualisierten
gan. Beachte, was diese Schleife nie erwähnt — eine Heuristik, eine Zielrichtung oder welchen Algorithmus du gewählt hast. - Die einzige verbleibende Entscheidung ist also, welche Zelle entnommen werden soll, und sie besteht aus einem einzigen Ausdruck. Sortiere nach
g + h, und du erhältst A*. Setzeh = 0, und die Sortierung erfolgt allein nach den bisherigen Kosten — das ist Dijkstra, der sich in Ringen nach außen ausbreitet, weil er keine Ahnung hat, wo das Ziel liegt. Ignorierst du stattdesseng, erfolgt die Sortierung allein nach der Schätzung — Greedy Best-First, das direkt auf das Ziel zusteuert und jede Route akzeptiert, auf der es angekommen ist. - Die Breitensuche bewertet überhaupt nicht: First in, first out. Ist Diagonalen erlauben deaktiviert, kostet jeder Schritt exakt
1, sodass die Reihenfolge, in der die Zellen eintreffen, die Reihenfolge steigenderg-Werte ist — und die Breitensuche expandiert daher genau das, was Dijkstra expandiert. Du kannst es bestätigen, ohne das Gitter neu zu generieren: Wechsle zwischen den beiden, und Expandierte Knoten bewegt sich kein Stück. Schaltest du Diagonalen ein, bricht das Argument in sich zusammen, da eine Diagonale√2statt1kostet und die Ankunftsreihenfolge die Kosten nicht mehr abbildet.
So liest du, was du siehst
Der Prioritätswert steht oberhalb des Gitters, wobei g und h der aktuellen Zelle eingesetzt sind, sodass du die Bewertung ablesen kannst, die zur letzten Entscheidung geführt hat. Darunter befinden sich zwei Zähler: Expandierte Knoten und Pfadlänge. Bernstein steht für die Front, Indigo für bereits besucht. Das Ändern des Algorithmus generiert kein neues Gitter, und genau das macht den Vergleich überhaupt wertvoll — auf demselben Vier-Wege-Layout ist Dijkstras Expandierte Knoten niemals kleiner als der von A*, und der von Greedy Best-First ist ein kleiner Bruchteil von beiden.
- Setzt voraus
- Schrittkosten, die niemals negativ sind, und ein Gitter, das sich während der Suche nicht ändert. Der Start ist immer die Zelle oben links und das Ziel die unten rechts. Das Schließen einer Zelle ist endgültig — die Schleife zieht eine Zelle nie erneut in Betracht — und das ist nur deshalb sicher, weil keine spätere Route günstiger ankommen kann, wenn jeder Schritt einen nicht-negativen Betrag hinzufügt.
- Versagt, wenn
- Expandierte Knoten ist die Zahl, die sich am dramatischsten verändert, und sie ist kein Maß für Qualität. Wähle Greedy Best-First: Auf demselben Gitter expandiert es einen kleinen Bruchteil dessen, was A* tut, und auf den meisten Layouts liefert es eine längere Pfadlänge zurück. Generiere einige neue Gitter und beobachte, wie sich die beiden Zähler in entgegengesetzte Richtungen bewegen. Weniger Zellen zu untersuchen ist eine Aussage darüber, wie hart der Algorithmus gearbeitet hat, und niemals darüber, wie gut seine Antwort war.
Lernpfad
Arbeit zählen, nicht Sekunden
Quellen (3)
- Where A*, the f = g + h scoring and the admissibility condition were introduced: P. E. Hart, N. J. Nilsson & B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths." IEEE Transactions on Systems Science and Cybernetics 4, 100–107, 1968.
- And the algorithm A* generalises, for comparison in the dropdown: E. W. Dijkstra, "A note on two problems in connexion with graphs." Numerische Mathematik 1, 269–271, 1959.
- The fourth option in the dropdown, and the wavefront it spreads: E. F. Moore, "The shortest path through a maze." Proceedings of an International Symposium on the Theory of Switching, Part II, 285–292. Harvard University Press, 1959.