Algorithme a *
Sur
? Comment savoir si une possibilité est prometteuse?
- À travers la fonction f (x) = g (x) + h (x)
- Qui est une fonction heuristique
- g (x) est le coût, d'origine, d'atteindre le nœud x
- h (x) est une fonction heuristique pour estimer le coût du nœud suivant
- Nous regardons toujours les possibilités d'élargir l'arbre et de calculer la valeur de f (x)
- Nous ajoutons le nœud qui a le plus petit F (x) parmi ceux que nous trouvons
- OA * est l'algorithme le plus efficace pour les façons minimales dans les graphiques
- Cependant, il est grave
- Il est nécessaire de définir un h (x) qui est admissible: il ne renverra jamais une valeur supérieure à la distance réelle de x à y
- Si H (x) est admissible, mais a trop sous-estimé la distance réelle, l'algorithme est super inefficace. Si H (x) n'est pas admissible, l'algorithme peut ne pas trouver le moyen minimum
? Complexité
- La complexité dépend directement de la fonction h (x) utilisée.
- Dans le pire des cas, la quantité de nœuds explorée est exponentielle dans la taille du plus petit chemin, mais a une complexité polynomiale si h ∗ (x) −h (x) ≤o (Logh ∗ (x)).
? Quand est-il bon à utiliser?
- Graphiques où l'on peut sous-estimer la distance entre deux sommets, comme dans les cartes
- La distance la plus courte entre deux points est une ligne, mais la distance réelle sera probablement supérieure à celle
? Quelle est la manière minimale dans ce cas?
Exécuter le projet
Résultat
Auteurs
Licence
Ce projet est sous le MIT. Voir ici pour plus d'informations.
