A*-Algorithmus
A* ist eine Reihe von Schritten (ein Algorithmus), die Computer verwenden können, um herauszufinden, wie man schnell zwischen zwei Orten hin und her kommt. Wenn Sie eine Liste von Orten haben und wissen, wie schwer es ist, von einem Ort direkt zum anderen zu gelangen, können Sie mit A* schnell herausfinden, wie Sie am schnellsten dorthin gelangen. Es ist mit dem Algorithmus von Dijkstra verwandt, macht aber kluge Vermutungen, so dass es nicht so lange dauert, langsame Wege auszuprobieren. Es ist eine gute Schrittfolge, wenn Sie nur den Weg zwischen zwei Orten wollen. Wenn Sie nach vielen Pfaden von derselben Karte aus fragen, dann gibt es schnellere Wege, die alle Antworten auf einmal finden, wie der Floyd-Warshall-Algorithmus. A* wird nicht funktionieren, wenn Sie mehrere Orte auf einer Reise besuchen wollen (das Problem des fahrenden Händlers).
Die Schritte
A* benötigt zunächst eine Liste aller Orte, zu denen Sie gehen können, und dann eine Liste, wie weit die Straße zwischen den einzelnen Orten liegt. Dann wird es Ihnen sagen, wie Sie am schnellsten von Ort A nach Ort Z gelangen.
Als Beispiel nehmen wir an, dass A mit den Orten B und C verbunden ist, und B und C sind beide mit D und E verbunden. D und E sind beide mit Z verbunden. Es gibt 4 mögliche Wege von A nach Z. Man kann A-B-D-Z, A-C-D-Z, A-B-E-Z oder A-C-E-Z gehen. Ein Computer, der A* verwendet, schaut zunächst, wie schwer es ist, von A nach B und von A nach C zu gelangen. Die Kosten eines Platzes bedeuten, wie schwer es ist, von A zu diesem Platz zu gelangen. Nachdem beide Kosten aufgeschrieben wurden, schaut der Computer, wie schwer es ist, von B nach D zu gelangen, und addiert dies zu den Kosten von B. Er schreibt dies als die Kosten von D auf. Dann schaut der Computer, wie schwer es ist, von C nach D zu gelangen, und addiert dies zu den Kosten von C. Dies sind andere Kosten für D, und wenn sie geringer sind als die, die er bereits hat, ersetzt er den alten. Der Computer will nur den besten Weg wissen, also ignoriert er den Weg mit den höheren Kosten. Er merkt sich nur einen der Pfade A-B-D und A-C-D, je nachdem, welcher schneller ist.
Der Computer geht weiter und findet den schnellsten Weg, um zu E zu gelangen. Schließlich geht er von D nach Z und findet einen Preis, und von E nach Z und findet einen Preis. Er bekommt einen Endpreis für Z, und das ist der kleinste Preis, den er bekommen kann. Jetzt weiß der Computer, welcher Weg der schnellste ist, und er hat die Antwort. Der Computer kann eine ähnliche Reihe von Schritten ausführen, aber mit viel mehr Stellen. Jedes Mal schaut er sich den Ort an, der A am nächsten liegt, und addiert die Kosten für die Nachbarn dieses Ortes.
Man nennt die obige Schrittfolge den Dijkstra-Algorithmus. Der Dijkstra-Algorithmus kann langsam sein, weil er viele Orte betrachtet, die von Z aus in die falsche Richtung gehen könnten. Wenn Sie den Computer fragen, wie man von einer Stadt in eine nahegelegene Stadt kommt, könnte der Dijkstra-Algorithmus am Ende in einem anderen Zustand suchen.
A* behebt dieses Problem. Mit A* können Sie dem Computer eine Schätzung mitteilen, wie weit es von jedem Ort bis zum Ende sein wird. Der Computer kann die Schätzung verwenden, um ungefähr zu sagen, wie weit es von einem bestimmten Ort bis zu Z gehen wird. Anstatt einfach den Ort auszuwählen, der A am nächsten liegt, wird er sich denjenigen ansehen, der wahrscheinlich die niedrigste Gesamtsumme haben wird. Sie findet diese Summe, indem sie die Kosten zu der erwarteten verbleibenden Entfernung addiert. Auf diese Weise kann sie nur in die Richtung schauen, in der sich die Dinge wahrscheinlich verbessern werden. Es ist in Ordnung, wenn die Vermutung nicht perfekt ist, aber selbst eine einfache falsche Vermutung kann das Programm viel schneller vorankommen lassen. Wenn Sie versuchen, einen Weg zwischen zwei Orten in der realen Welt zu finden, ist eine gute Schätzung nur die Entfernung zwischen ihnen in einer geraden Linie. Der wirkliche Weg über Straßen wird länger sein, aber das lässt das Programm raten, und es wird nicht in die falsche Richtung gehen.
In der Mathematik- oder Informatikliteratur ist diese Vermutung oft eine Funktion des Ortes und wird als Heuristik bezeichnet. Jeder Ort ist ein Scheitelpunkt, und jeder Weg zwischen zwei Orten ist eine Kante. Dies sind Wörter aus der Graphentheorie.
