Ich suche nach einer Erklärung, warum der AStar / A * -Algorithmus AStar heißt. Alle ähnlichen Algorithmen (Kürzestpfadproblem) werden oft wie ihre Entwickler benannt. Wofür steht AStar also?
Es gab Algorithmen namens A1 und A2. Später wurde bewiesen, dass A2 optimal und in der Tat auch der bestmögliche Algorithmus war, daher gab er ihm den Namen A *, der symbolisch alle möglichen Versionsnummern enthält.
Quelle:
1964 erfand Nils Nilsson einen heuristischen Ansatz, um die Geschwindigkeit des Dijkstra-Algorithmus zu erhöhen. Dieser Algorithmus wurde A1 genannt. 1967 verbesserte Bertram Raphael diesen Algorithmus drastisch, konnte jedoch keine Optimalität zeigen. Er nannte diesen Algorithmus A2. Dann führte Peter E. Hart 1968 ein Argument ein, das zeigte, dass A2 optimal war, wenn eine konsistente Heuristik mit nur geringfügigen Änderungen verwendet wurde. Sein Beweis des Algorithmus beinhaltete auch einen Abschnitt, der zeigte, dass der neue A2-Algorithmus der beste Algorithmus war, der unter den gegebenen Bedingungen möglich war. Er benannte daher den neuen Algorithmus in der Kleene-Star-Syntax als den Algorithmus, der mit A beginnt und alle möglichen Versionsnummern oder A *
enthält
Nosrati, Masoud, Ronak Karimi und Hojat Allah Hasanvand. "Untersuchung der (Stern) Suchalgorithmen: Merkmale, Methoden und Ansätze." World Applied Programming 2.4 (2012): 251-256. *
Tags und Links algorithm graph-algorithm a-star shortest-path dijkstra