Laufzeitverhalten von Wegfindungsalgorithmen
-
Hat Jemand Links, Tipps, Tutorials zu Laufzeitverhalten von Wegfindungsalgorithmen? (in 2d)
-
Hallo,
das Laufzeitverhalten von Wegfindungsalgorithmen wird bei den komplexeren Algorithmen maßgeblich von der Qualität einer/mehrerer heuristischen Funktion(en) beeinflusst. Es lässt sich deshalb nicht einfach in Abhängigkeit von der Anzahl an Knoten angeben.
-
Hallo,
gibt es nicht einmal bei den berühmten wie A* so durchschnittliche Erfahrungswerte?
Soll nix 100% wissenschaftliches sein.
Ich habe mir einen eigenen gebastelt und wollte wissen, wie weit ich vom derzeit Besten entfernt bin, was die Efizienz angeht.
-
Nein, der Aufwand hängt zum allergrößten Teil von der heuristischen Funktion ab. Wenn die heuristische Funktion gleich mal weiß "aha, da vorne ist ein Gebirge, da kann niemand durch" und die Entfernung zur anderen Seite deshalb gleich viel höher schätzt, kannst du dir damit vielleicht den größten Teil der Berechnungen einsparen.
Außerdem ist beim A* eine evtl. Angabe des Laufzeitverhaltens irrelevant. Es lässt sich zeigen, dass A* optimal effizient ist, wenn die heuristische Funktion die Entfernungen immer richtig schätzt.
Und so lange sie nicht völlig falsch liegt, dürfte der A* wohl besser sein, als die meisten anderen Algorithmen.
-
Im Worst Case verhällt er sich wie der Dijkstra-Algorithmus, im bessten Fall läuft er nur genau den richtigen Weg ab.
Jetzt müsstest du aussagen über den Dijkstra-Algorithmus treffen. Naja, im schlimmsten Fall durchläuft er alle Knoten.