 |
|  |  | A-Stern-Algorithmus - Definition und Bedeutung |
|  | | Sie haben im Ilexikon erfolgreich nach der Definition, der Bedeutung oder Informationen zum Begriff 'A-Stern-Algorithmus' gesucht. Hier finden Sie eine Beschreibung, Erklärung, Definition, die Bedeutung sowie viele aktuelle Infos zum Begriff 'A-Stern-Algorithmus' und damit verwandten Themen.
Der Algorithmus verwendet dazu eine Schätzfunktion, die für jeden Knoten v eine untere Schranke für den obendrein zu erwartenden Abstand (im Sinne der Pfadlänge) von v nach e liefert. Durch die Verwendung dieser Funktion ergibt sich eine zielgerichtete Suche in Richtung auf den Endknoten. Zu beachten ist, dass es sich dabei um eine Heuristik handelt: Es werden wohl die "vielversprechendsten" Pfade zuerst untersucht, aber keine Lösungsmöglichkeit grundsätzlich ausgeschlossen.
Von entscheidender Bedeutung ist, dass die Schätzfunktion eine möglichst hohe, untere Schranke für die obendrein zu erwartende Pfadlänge liefern muss. Für die Suche in einer Landkarte (z.B. bei Routenplanern) erfüllt die Luftlinie diese Bedingung. Der Algorithmus sucht dann so, wie man es als Mensch ebenso tun würde: Wird z.B. eine Route von München nach Hamburg gesucht, macht es wenig Sinn, zuerst in Richtung Salzburg zu suchen, sondern man wird zuerst eine Strecke prüfen, die in Richtung Norden führt.
| · | Der A*-Algorithmus ist vollständig, d.h. wenn ein Pfad zum Zielknoten existiert, so wird dieser ebenso gefunden.
|
| · | Außerdem ist er optimal, d.h. es gibt keinen kürzeren Pfad als den gefundenen.
|
| · | Zudem ist A* optimal effizient, d.h. jeder andere optimale und vollständige Algorithmus, der dieselbe Heuristik verwendet, muss mindestens so viele Knoten betrachten wie A*, um eine Lösung zu finden.
|
Es wird eine Liste A von "aktuellen Knoten" verwaltet. Zu jedem Knoten wird sein Abstand von s auf dem kürzesten bisher gefundenen Pfad gespeichert. Soll außer der Länge des kürzesten Pfades ebenso der Pfad selbst gefunden werden, wird bei jedem Knoten in Schritt 4. ebenso sein Vorgänger gespeichert. Das Ergebnis kann dann in umgekehrter Reihenfolge (von e nach s) ermittelt werden.
| · | Nimm den Startknoten s in A auf
|
| · | Für jeden Knoten aus A: Berechne die Summe aus seinem Abstand von s und seiner Schätzfunktion und ermittle den Knoten vmin mit der kleinsten Summe
|
| · | Wenn vmin = e dann wurde der kürzeste Weg gefunden
|
| · | Ansonsten nimm die Nachfolger von vmin in A auf (vmin wird "aufgelöst") und gehe zu 2. Ist einer der Nachfolger schon in A enthalten, nehme die Variante mit dem kleineren Abstand von s.
|
Zu beachten ist, dass die Suche nicht schon endet, wenn der Zielknoten e gefunden wird, sondern erst, wenn dieser als Kandidat für die "Auflösung" identifiziert wird.
| Infos zu Ilexikon.comWir hoffen dass Sie alle gewünschten Informationen zum Begriff 'A-Stern-Algorithmus' gefunden haben. Alle Informationen zur Definition des Begriffs A-Stern-Algorithmus und zur Bedeutung des Wortes A-Stern-Algorithmus werden Ihnen kostenlos bereitgestellt. Unser Traffic und unsere Programmierarbeit finanziert sich ausschließlich durch Werbeeinnahmen. Wir danken für Ihren Besuch und hoffen dass Sie unser Portal zusätzlichempfehlen. |
Weiteres zu dem Artikel
Sie möchten die Besucher Ihrer Internet-Seite auf weiterführende Definitionen und Informationen zum
Thema "A-Stern-Algorithmus" aufmerksam machen? Dann platzieren Sie doch einfach folgenden Link auf Ihre Homepage:
<a href="http://www.ilexikon.com/A-Stern-Algorithmus.html" title="Definition und Informationen zu dem Thema A-Stern-Algorithmus">A-Stern-Algorithmus</a> | |  | |  |
|  |
