A-Stern - Versionsgeschichte

Thoronador am 1. Mai 2008 um 15:54 Uhr

2008-05-01T15:54:03Z

Flash: /* Algorithmus */

2006-05-04T23:28:37Z

‎Algorithmus

DGLBot: Bot: Korrigiere Wiki-Syntax

2006-02-22T14:44:16Z

Bot: Korrigiere Wiki-Syntax

La Boda: /* Algorithmus */

2005-12-10T11:34:02Z

‎Algorithmus

Flo: Hinweis auf den Wikipedia Artikel

2005-11-25T15:09:09Z

Hinweis auf den Wikipedia Artikel

Akira: /* A-Stern mit Kosten */

2005-11-25T14:34:25Z

‎A-Stern mit Kosten

Lyr: /* Algorithmus */

2005-11-25T02:16:49Z

‎Algorithmus

Lyr am 25. November 2005 um 01:22 Uhr

2005-11-25T01:22:19Z

Neue Seite

Der A-Stern Algorithmus besitzt unter den Pathfinding-begeisterten nahezu den Status des heiligen Grales, und dies nicht zu unrecht. Der A-Stern Algorithmus liefert unter gewissen Voraussetzungen den optimalen Weg und dies noch dazu meistens in einem sehr akzeptablen Zeitraum.

=Vorgehensweise=
Ähnlich zur [[Breitensuche]] wird hier immer der erahnte kürzeste Weg bevorzugt. Zum "erahnen" eines Weges wird eine Heuristik benötigt, also ein Wert welcher Angibt wie weit es ungefähr noch bis zum Ziel sein wird. Die Breitensuche wird nun einfach um diese Heuristik erweitert und dadurch wird der nächste zu überprüfende Knoten bestimmt.

=Algorithmus=
Suche_Weg( Knoten Ziel, Knoten Start )
Kosten_Heap KHeap
KHeap.Add( Min_Kosten( Start, Ziel ) )

Solange Ziel nicht gefunden
K = Knoten mit minimalen Kosten aus KHeap
Für K' = alle (nicht besuchten) Nachbarknoten von K
KHeap.Add( Kosten( Start, K' ) + Min_Kosten( K', Ziel ), K' )
Durch die minimalen Kosten von K zum Ziel setzen wir voraus, das wir eine derartige Funktion besitzen. Und es lässt sich recht einfach durch Worte beweisen, dass dieser Algorithmus wirklich den optimalen Weg findet:

Dieser Algorithmus erweitert den Knoten mit den minimalen bisherigen Kosten + den minimal zu erwartenden Kosten.
Wenn die minimal zu erwartenden Kosten kleiner (oder gleich) den tatsächlichen Kosten ab dem Punkt wo er
sich befindet sind, so können die tatsächlichen Kosten für den ersten gefundenen Weg niemals höher sein als
die Kosten für einen bereits durchsuchten Weg + dessen minimaler Kosten und somit auch niemals höher als die
Kosten für einen bereits durchsuchten Weg + dessen tatsächliche Kosten zum Ziel.

Der Algorithmus besitzt jedoch immer noch eine maximale Laufzeit von [[O-Notation|O]](n) jedoch kann man dies wiederum umformen in [[O-Notation|O]](t^v) wobei t die Tiefe des Zieles ist und v der (durchschnittliche) Verzweigungsgrad des Baumes, bzw. des Graphen ohne wiederholte Knoten ist. Jedoch für die durchschnittliche Laufzeit kann man hier v auch als Verzweigungsgrad des Baumes in die "ungefähre" Richtung des Zieles sehen, und dieser ist meistens um einiges geringer als der tatsächliche Verzweigungsgrad. Der maximale Speicherbedarf ist jedoch (leider) wiederum [[O-Notation|O]](t^v).

Wenn jedoch der Wert der durch Min_Kosten berechnet wird die minimalen Kosten überschreiten kann, so liefert dieser Algorithmus nicht mehr zwingendermaßen den minimalen Weg, denn dann wird obiger (textuelle) Beweis nichtig. Aufzupassen ist somit auf schnellere Fortbewegungsmöglichkeiten wie beispielsweise:
* Die Heuristik von A-Stern wird mit den Daten "zu Fuß gehen" gefüttert, es gibt jedoch auch eine Zugverbindung
* Es gibt einen Teleporter welcher ohne Zeitverlust eine Passage von A nach B öffnet.
Die minimalen Kosten müssen somit mit dem schnellsten Transportmittel über Luftlinie berechnet werden.

Die Qualität des A-Stern-Algorithmus beruht somit auf der Qualität der Heuristik. Sowohl darauf, dass die Heuristik für die minimalen Kosten niemals höher wird als die tatsächlichen Kosten, als auch darauf, dass die tatsächlichen Kosten niemals allzu viel höher werden als die minimalen Kosten. Wenn man für diese Heuristik immer den Wert 0 verwendet, so entspricht A-Stern einer [[Breitensuche]].

=A-Stern mit Kosten=
Wie am Ende des vorigen Absatzes bereits klar geworden sein sollte, benötigt A-Stern Kosten (vor allem minimale Kosten), ansonnsten degeneriert er zu einer [[Breitensuche]].

← Nächstältere Version		Version vom 22. Februar 2006, 14:44 Uhr
Zeile 39:		Zeile 39:

	=Siehe auch=		=Siehe auch=
−	[[http://de.wikipedia.org/wiki/A%2A-Algorithmus\|Wikipedia Artikel zum A-Algorithmus]]	+	[http://de.wikipedia.org/wiki/A%2A-Algorithmus Wikipedia Artikel zum A-Algorithmus]

← Nächstältere Version		Version vom 25. November 2005, 15:09 Uhr
Zeile 36:		Zeile 36:
	=A-Stern mit Kosten=		=A-Stern mit Kosten=
	Wie am Ende des vorigen Absatzes bereits klar geworden sein sollte, benötigt A-Stern Kosten (vor allem minimale Kosten), ansonsten degeneriert er zu einer [[Breitensuche]].		Wie am Ende des vorigen Absatzes bereits klar geworden sein sollte, benötigt A-Stern Kosten (vor allem minimale Kosten), ansonsten degeneriert er zu einer [[Breitensuche]].
		+
		+	=Siehe auch=
		+	[[http://de.wikipedia.org/wiki/A%2A-Algorithmus\|Wikipedia Artikel zum A-Algorithmus]]

← Nächstältere Version		Version vom 25. November 2005, 14:34 Uhr
Zeile 35:		Zeile 35:

	=A-Stern mit Kosten=		=A-Stern mit Kosten=
−	Wie am Ende des vorigen Absatzes bereits klar geworden sein sollte, benötigt A-Stern Kosten (vor allem minimale Kosten), ~~ansonnsten~~ degeneriert er zu einer [[Breitensuche]].	+	Wie am Ende des vorigen Absatzes bereits klar geworden sein sollte, benötigt A-Stern Kosten (vor allem minimale Kosten), ansonsten degeneriert er zu einer [[Breitensuche]].

@@ Zeile 1: / Zeile 1: @@
-Der A-Stern Algorithmus besitzt unter den Pathfinding-begeisterten nahezu den Status des heiligen Grales, und dies nicht zu unrecht. Der A-Stern Algorithmus liefert unter gewissen Voraussetzungen den optimalen Weg und dies noch dazu meistens in einem sehr akzeptablen Zeitraum.
+Der '''A-Stern-Algorithmus''' besitzt unter den Pathfindingbegeisterten nahezu den Status des heiligen Grales, und dies nicht zu unrecht. Der A-Stern-Algorithmus liefert unter gewissen Voraussetzungen den optimalen Weg und dies noch dazu meistens in einem sehr akzeptablen Zeitraum.
 =Vorgehensweise=
-Ähnlich zur [[Breitensuche]] wird hier immer der erahnte kürzeste Weg bevorzugt. Zum "erahnen" eines Weges wird eine Heuristik benötigt, also ein Wert welcher Angibt wie weit es ungefähr noch bis zum Ziel sein wird. Die Breitensuche wird nun einfach um diese Heuristik erweitert und dadurch wird der nächste zu überprüfende Knoten bestimmt.
+Ähnlich zur [[Breitensuche]] wird hier immer der erahnte kürzeste Weg bevorzugt. Zum "Erahnen" eines Weges wird eine Heuristik benötigt, also ein Wert, welcher angibt, wie weit es ungefähr noch bis zum Ziel sein wird. Die Breitensuche wird nun einfach um diese Heuristik erweitert und dadurch wird der nächste zu überprüfende Knoten bestimmt.
 =Algorithmus=
@@ Zeile 21: / Zeile 21: @@
   Dieser Algorithmus erweitert den Knoten mit den minimalen bisherigen Kosten + den minimal
   zu erwartenden Kosten. Wenn die minimal zu erwartenden Kosten kleiner (oder gleich) den
-  tatsächlichen Kosten ab dem Punkt wo er sich befindet sind, so können die tatsächlichen
+  tatsächlichen Kosten ab dem Punkt, wo er sich befindet sind, so können die tatsächlichen
   Kosten für den ersten gefundenen Weg niemals höher sein als die Kosten für einen bereits
   durchsuchten Weg + dessen minimaler Kosten und somit auch niemals höher als die
   Kosten für einen bereits durchsuchten Weg + dessen tatsächliche Kosten zum Ziel.
-Der Algorithmus besitzt jedoch immer noch eine maximale Laufzeit von [[O-Notation|O]](n) jedoch kann man dies wiederum umformen in [[O-Notation|O]](t^v) wobei t die Tiefe des Zieles ist und v der (durchschnittliche) Verzweigungsgrad des Baumes, bzw. des Graphen ohne wiederholte Knoten ist. Jedoch für die durchschnittliche Laufzeit kann man hier v auch als Verzweigungsgrad des Baumes in die "ungefähre" Richtung des Zieles sehen, und dieser ist meistens um einiges geringer als der tatsächliche Verzweigungsgrad. Der maximale Speicherbedarf ist jedoch (leider) wiederum [[O-Notation|O]](t^v).
+Der Algorithmus besitzt jedoch immer noch eine maximale Laufzeit von [[O-Notation|O]](n), jedoch kann man dies wiederum umformen in [[O-Notation|O]](t^v) wobei t die Tiefe des Zieles ist und v der (durchschnittliche) Verzweigungsgrad des Baumes, bzw. des Graphen ohne wiederholte Knoten ist. Jedoch für die durchschnittliche Laufzeit kann man hier v auch als Verzweigungsgrad des Baumes in die "ungefähre" Richtung des Zieles sehen, und dieser ist meistens um einiges geringer als der tatsächliche Verzweigungsgrad. Der maximale Speicherbedarf ist jedoch (leider) wiederum [[O-Notation|O]](t^v).
-Wenn jedoch der Wert der durch Min_Kosten berechnet wird die minimalen Kosten überschreiten kann, so liefert dieser Algorithmus nicht mehr zwingendermaßen den minimalen Weg, denn dann wird obiger (textuelle) Beweis nichtig. Aufzupassen ist somit auf schnellere Fortbewegungsmöglichkeiten wie beispielsweise:
+Wenn jedoch der Wert, der durch Min_Kosten berechnet wird, die minimalen Kosten überschreiten kann, so liefert dieser Algorithmus nicht mehr zwingendermaßen den minimalen Weg, denn dann wird obiger (textueller) Beweis nichtig. Aufzupassen ist somit auf schnellere Fortbewegungsmöglichkeiten wie beispielsweise:
-* Die Heuristik von A-Stern wird mit den Daten "zu Fuß gehen" gefüttert, es gibt jedoch auch eine Zugverbindung
+* Die Heuristik von A-Stern wird mit den Daten "zu Fuß gehen" gefüttert, es gibt jedoch auch eine Zugverbindung.
-* Es gibt einen Teleporter welcher ohne Zeitverlust eine Passage von A nach B öffnet.
+* Es gibt einen Teleporter, welcher ohne Zeitverlust eine Passage von A nach B öffnet.
 Die minimalen Kosten müssen somit mit dem schnellsten Transportmittel über Luftlinie berechnet werden.
@@ Zeile 40: / Zeile 40: @@
 =Siehe auch=
 *[http://de.wikipedia.org/wiki/A%2A-Algorithmus Wikipedia Artikel zum A*-Algorithmus]

@@ Zeile 17: / Zeile 17: @@
       Für K' = alle (nicht besuchten) Nachbarknoten von K
         KHeap.Add( Kosten( Start, K' ) + Min_Kosten( K', Ziel ), K' )
-Durch die minimalen Kosten von K zum Ziel setzen wir voraus, das wir eine derartige Funktion besitzen. Und es lässt sich recht einfach durch Worte beweisen, dass dieser Algorithmus wirklich den optimalen Weg findet:
+Durch die minimalen Kosten von K zum Ziel setzen wir voraus, das wir eine derartige Funktion besitzen. (Eine solche Funktion könnte z.B. der euklidische Abstand zum Ziel sein, da dieser immer minimal ist.) Und es lässt sich recht einfach durch Worte beweisen, dass dieser Algorithmus wirklich den optimalen Weg findet:
   Dieser Algorithmus erweitert den Knoten mit den minimalen bisherigen Kosten + den minimal

@@ Zeile 11: / Zeile 11: @@
     Solange Ziel nicht gefunden
       K = Knoten mit minimalen Kosten aus KHeap
       Für K' = alle (nicht besuchten) Nachbarknoten von K
         KHeap.Add( Kosten( Start, K' ) + Min_Kosten( K', Ziel ), K' )