Wie ist die Komplexität vom A*-Algorithmus?

Wissenschaft Informatik
#1

Künstliche Intelligenz:

Wie sieht es mit der Komplexität vom A*-Algorithmus aus?

Dabei rede ich von einem gerichteten Baum mit:

  • Tiefe T
  • Verzweigungsrate V (jeder Knoten hat V Nachfolger)

Platzbedarf des Verfahrens (Gesamtspeicherbedarf):
worst-case: ???
average-case: ???

Zeitbedarf des Verfahrens:
worst-case: O(V^2) oder O(V*logV)
average-case: ???

Anscheinend ist das Ganze von der tatsächlichen Implementierung des Algorithmus abhängig, aber ich habe nicht einmal EIN Bsp. im Internet gefunden. Wikipedia sagt auch nur teilweise etwas zum Zeitbedarf.

#2

Eine Implementierung…
Moin,

zur Komplexität und Zeitbedarf kann ich nicht viel sagen…

Implementierung des Algorithmus abhängig, aber ich habe nicht
einmal EIN Bsp. im Internet gefunden. Wikipedia sagt auch nur

… aber ein Beispiel einer Implementierung kann ich Dir geben: http://www.openttd.org (link zu nightly oben links, dort gibt’s auch sources)
Der Pathfinder für Züge ist eine Implementierung des A*-Algorithmus; Dich interessieren somit die Dateien in ./src/yapf

Gruß,
Ingo

#3

Hallo Ingo,

danke für die Antwort!

Implementationen habe ich bereits im Netz gefunden, ich benötige aber unbedingt die Info zur Komplexität (sowohl Zeit- als auch Speicherbedarf).

Viele Grüße
Jessi

#4

Hallo Ingo,

danke für die Antwort!

Implementationen habe ich bereits im Netz gefunden, ich
benötige aber unbedingt die Info zur Komplexität (sowohl Zeit-
als auch Speicherbedarf).

Vielleicht hilft das (ist aber auch sehr theoretisch):
Journal of the ACM (JACM), Volume 32 , Issue 3 (July 1985)
Pages: 505 - 536
Rina Dechter and Judea Pearl
Publisher: ACM New York, NY, USA
http://doi.acm.org/10.1145/3828.3830

Gruß,
Ingo