Wegfindung mit A*
Aus Spieleprogrammierer-Wiki
(Unterschied zwischen Versionen)
| [gesichtete Version] | [gesichtete Version] |
K (→Die Schätzfunktion: Grammatikfehler behoben) |
Tris (Diskussion | Beiträge) (→Quellen) |
||
| (Eine dazwischenliegende Version von einem Benutzer wird nicht angezeigt) | |||
| Zeile 47: | Zeile 47: | ||
Die Schätzfunktion wird benötigt, um dem aktuell untersuchten Knoten einen Wert zuzuweisen. Dieser Wert macht eine Aussage darüber, wie weit der Knoten schätzungsweise vom Ziel entfernt ist. Die Schätzfunktion wird im Allgemeinen als <math>h</math> bezeichnet (für ''Heuristik''), und die geschätzten Kosten nennen wir <math>H</math>. Die ''tatsächlichen Kosten'' bezeichnen wir mit <math>c</math>. <math>c(k)</math> gibt die Kosten an, um vom Knoten <math>k</math> zum Ziel zu gelangen, <math>c(k, k')</math> gibt die Kosten an, um vom Knoten <math>k</math> zum Knoten <math>k'</math> zu gelangen. | Die Schätzfunktion wird benötigt, um dem aktuell untersuchten Knoten einen Wert zuzuweisen. Dieser Wert macht eine Aussage darüber, wie weit der Knoten schätzungsweise vom Ziel entfernt ist. Die Schätzfunktion wird im Allgemeinen als <math>h</math> bezeichnet (für ''Heuristik''), und die geschätzten Kosten nennen wir <math>H</math>. Die ''tatsächlichen Kosten'' bezeichnen wir mit <math>c</math>. <math>c(k)</math> gibt die Kosten an, um vom Knoten <math>k</math> zum Ziel zu gelangen, <math>c(k, k')</math> gibt die Kosten an, um vom Knoten <math>k</math> zum Knoten <math>k'</math> zu gelangen. | ||
| − | Es gibt verschiedene Ansätze für die Schätzfunktion. Welche davon eine gute Wahl ist, hängt auch immer davon ab, was im Spiel genau erreicht werden soll. Damit der hier gezeigte A*-Algorithmus korrekt funktioniert, muss die Schätzfunktion eine Voraussetzung erfüllen, sie muss nämlich ''monoton'' sein. Das bedeutet in diesem Zusammenhang: | + | Es gibt verschiedene Ansätze für die Schätzfunktion. Welche davon eine gute Wahl ist, hängt auch immer davon ab, was im Spiel genau erreicht werden soll. Damit der hier gezeigte A*-Algorithmus korrekt funktioniert, muss die Schätzfunktion eine Voraussetzung erfüllen, sie muss nämlich ''[http://de.wikipedia.org/wiki/Monotonie_(Mathematik) monoton]'' sein. Das bedeutet in diesem Zusammenhang: |
# <math>h(k) \leq c(k)</math>: Die geschätzten Kosten dürfen nie größer sein dürfen als die tatsächlichen Kosten. Die Schätzfunktion darf die Kosten also ''nicht überschätzen''. | # <math>h(k) \leq c(k)</math>: Die geschätzten Kosten dürfen nie größer sein dürfen als die tatsächlichen Kosten. Die Schätzfunktion darf die Kosten also ''nicht überschätzen''. | ||
# <math>h(k) \leq c(k, k') + h(k')</math> für benachbarte Knoten <math>k</math> und <math>k'</math>: Die geschätzten Kosten von einem Knoten <math>k</math> zum Ziel dürfen nicht größer sein als die tatsächlichen Kosten zu einem beliebigen Nachbarknoten <math>k'</math> plus die geschätzten Kosten von <math>k'</math> bis zum Ziel. | # <math>h(k) \leq c(k, k') + h(k')</math> für benachbarte Knoten <math>k</math> und <math>k'</math>: Die geschätzten Kosten von einem Knoten <math>k</math> zum Ziel dürfen nicht größer sein als die tatsächlichen Kosten zu einem beliebigen Nachbarknoten <math>k'</math> plus die geschätzten Kosten von <math>k'</math> bis zum Ziel. | ||
| Zeile 1.034: | Zeile 1.034: | ||
== Quellen == | == Quellen == | ||
* http://de.wikipedia.org/wiki/A_Stern | * http://de.wikipedia.org/wiki/A_Stern | ||
| − | |||
Aktuelle Version vom 20. Oktober 2020, 20:29 Uhr
Klicke hier, um diese Version anzusehen.
