A* Wegfindung Optimalität
-
Wikipedia schrieb:
Wie bereits erwähnt ist eine gute Heuristik eine der wichtigsten Voraussetzungen damit der A*-Algorithmus effizient arbeiten kann. Setzt man weiterhin voraus, dass die verwendete Heuristik monoton ist – also sowohl die Kosten bis zum Ziel, als auch die Kosten zwischen zwei beliebigen Knoten nie überschätzt – und dass der Graph keine negativen Kantengewichte besitzt, so kann man beweisen dass der A*-Algorithmus immer einen kürzesten Pfad vom Start zum Ziel findet.
Warum ist das "als auch die Kosten zwischen zwei beliebigen Knoten" wichtig? In dem Algorithmus wird doch nie mit Hilfe der Schätzfunktion die Entfernung zwischen zwei Knoten, sondern immer nur die von einem Knoten zum Ziel abgeschätzt.
-
snOOfy schrieb:
Warum ist das "als auch die Kosten zwischen zwei beliebigen Knoten" wichtig? In dem Algorithmus wird doch nie mit Hilfe der Schätzfunktion die Entfernung zwischen zwei Knoten, sondern immer nur die von einem Knoten zum Ziel abgeschätzt.
Spontan würde ich sagen: Weil sie sonst nicht monoton ist und Teilstrecken falsch schätzen würde.
BTW, kennst Du schon http://theory.stanford.edu/~amitp/GameProgramming/index.html ?
-
Dieser Thread wurde von Moderator/in HumeSikkins aus dem Forum C++ in das Forum Rund um die Programmierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
snOOfy schrieb:
Wikipedia schrieb:
Wie bereits erwähnt ist eine gute Heuristik eine der wichtigsten Voraussetzungen damit der A*-Algorithmus effizient arbeiten kann. Setzt man weiterhin voraus, dass die verwendete Heuristik monoton ist – also sowohl die Kosten bis zum Ziel, als auch die Kosten zwischen zwei beliebigen Knoten nie überschätzt – und dass der Graph keine negativen Kantengewichte besitzt, so kann man beweisen dass der A*-Algorithmus immer einen kürzesten Pfad vom Start zum Ziel findet.
Warum ist das "als auch die Kosten zwischen zwei beliebigen Knoten" wichtig? In dem Algorithmus wird doch nie mit Hilfe der Schätzfunktion die Entfernung zwischen zwei Knoten, sondern immer nur die von einem Knoten zum Ziel abgeschätzt.
Das ist irgendwie zweimal das selbe. Es kann ja jeder beliebige Knoten das Ziel sein und die Heuristik darf von keinem Knoten zum Ziel überschätzen.
BENUTZT wird die Heuristik "nur", um die Entfernung eines beliebigen Knotens zum Ziel zu schätzen, aber wie gesagt in aller Regel kann ich jeden Knoten als Ziel nehmen ohne dabei die Heuristische Funktion auszutauschen.
-
OK, danke. Ich hab das in der Beschreibung einfach mal ein bisschen gröber gehalten, wird bestimmt niemandem auffallen^^