Bonjour a tous,
Je cherche des éléments qui permette de privilégié l'algorithme de Bellman-Ford sur celui de A* ?
Merci
Version imprimable
Bonjour a tous,
Je cherche des éléments qui permette de privilégié l'algorithme de Bellman-Ford sur celui de A* ?
Merci
:salut:
De manière générale, pour comparer deux algorithmes, tu peux regarder la complexité en temps et en mémoire (ou bien des implémentations en faisant tourner le code et en récupérant des statistiques). A* utilisant une heuristique, il se peut qu'il donne une solution de moins bonne qualité qu'un autre (particulièrement si elle ne respecte pas les hypothèses de l'algorithme). Plus particulièrement, dans les algorithmes de recherche dans un graphe, certains partent d'un point et calculent le meilleur chemin jusqu'à un seul autre point, d'autres vers tous les autres points. Voici pour quelques pistes de recherche ;).
Ok merci dourouc05
J'ai une relative bonne idée des deux algorithmes.
1- A* est une extension de Dijkstra (que j'ai déjà utilisé) mais je ne connais pas bien l’amélioration apportée.
2- Bellman-Ford aussi je l'utilise.
- je ne connais pas bien leur complexité au pire cas ? (peu tu m'aider a déterminé quel est le meilleur des deux pour ce critère)
Je vu que Bellman-Ford est un algo : qui calcule le chemin vers tous les autres points.
et que A* calcule le meilleur chemin jusqu'à un seul noeud a la fois.
Selon me petite lecture sur wikipedia (je n'ai pas tout compris a 100%)
je déduit que :
Complexité de A* = O(log n)
Complexité de Bellman-Ford = O(n3)
Si je me base sur le schéma suivant :
Pièce jointe 178078
La complexité de en temps de A* est bien plus stable donc plus performante. dit moi si je me trompe quand je dis A* > Bellman-Ford ??
Merci
L'algorithme de Bellman-Ford est systématique : il évalue l'intégralité des branches dans l'arbre des possibilités de parcours du graphe.
L'algorithme A* élimine au plus tôt les branches les moins probables dans l'arbre des possibilités.
Ces deux algorithmes n'appartiennent pas à la même famille.
Personne ne peut te dire lequel des deux est le meilleur : tout dépend du problème à traiter. Il y a des cas ou Bellman-Ford est plus rapide et des cas ou il est moins rapide.
De plus, la charge de calcul et l'usage de la mémoire n'ont rien à voir entre ces deux algorithmes.
C'est possible de me répondre avec plus de précision dans le cas : trouves le plus cours chemin dans un Graphe (Automate fini)?Citation:
Envoyé par dinobogan
Quelle sont c'est deux famille d'algorithme ?
Merci
Je l'ai déjà dit : impossible de donner une réponse, tout dépend de la forme du graphe à analyser. Mais je vais être plus précis : si le graphe est quasiment complet, alors A*. Si le graphe contient énormément de cul-de-sac ou si les quelques cul-de-sac existants sont très profond, alors Bellman-Ford. Mais là encore c'est une généralité qui peut être remise en cause par les cas particuliers à analyser.Citation:
Envoyé par geforce
Déjà dit aussi : Bellman-Ford est systématique et A* est heuristique.Citation:
Quelle sont c'est deux famille d'algorithme ?
OK, je commence tout juste à comprendre,
Mais dit moi y a une autre caractéristique qui les différencié (me semble très importante) c'est la détection des 'circuits absorbants' Bellman-Ford peu le faire, mais A* ne peu le faire.
Mais c'est quoi la conséquence d'entrer dans un circuit absorbant dans le cas de A* ?
Pour Bellman-Ford je crois que s'il détecte un seul circuit absorbant dans un graphe, alors le graphe en totalité n'est pas explorable donc il est dans l'impossibilité de trouver les chemins optimaux?
Merci de donner plus de détail dans ce cas-là.
A* ne peut pas passer deux fois par un même noeud puisqu'il marque tous les noeuds traités.
ci-joint mon document merci de me dire si votre avis?Citation:
Envoyé par dinobogan
Pièce jointe 178671
des critiques constructive si possible Merci.
