Algorithmus a*
An
? Woher weiß man, ob eine Möglichkeit vielversprechend ist?
- Durch die Funktion f (x) = g (x) + h (x)
- Das ist eine heuristische Funktion
- g (x) sind die Kosten, um den X -Knoten aus zu erreichen, von Ursprung zu erreichen
- H (x) ist eine heuristische Funktion zur Schätzung der Kosten des nächsten Knotens
- Wir betrachten immer die Möglichkeiten, den Baum zu erweitern, und berechnen den Wert von F (x)
- Wir fügen den Knoten hinzu, der das kleinste f (x) unter denen hat, die wir finden
- OA* ist der effizienteste Algorithmus für minimale Wege in Grafiken
- Es ist jedoch schwerwiegende Einschränkungen
- Es ist notwendig, ein H (x) zu definieren, das zulässig ist: Es wird niemals einen Wert zurückgeben
- Wenn H (x) zulässig ist, aber den tatsächlichen Abstand zu unterschätzt, ist der Algorithmus super ineffizient. Wenn H (x) nicht zulässig ist, findet der Algorithmus möglicherweise nicht den minimalen Weg
? Komplexität
- Die Komplexität hängt direkt von der verwendeten Funktion H (x) ab.
- Im schlimmsten Fall ist die Anzahl der untersuchten Knoten in der Größe des kleinsten Pfades exponentiell, hat jedoch eine polynomiale Komplexität, wenn H ∗ (x) -H (x) ≤ O (logh ∗ (x)).
? Wann ist es gut zu benutzen?
- Diagramme, in denen man den Abstand zwischen zwei Eckpunkten unterschätzen kann, wie in Karten
- Der kürzeste Abstand zwischen zwei Punkten ist eine Linie, aber wahrscheinlich wird die tatsächliche Entfernung größer sein als diese
? Was ist der minimale Weg in diesem Fall?
Das Projekt ausführen
Ergebnis
Autoren
Lizenz
Dieses Projekt befindet sich unter dem MIT. Weitere Informationen finden Sie hier.
