Discussion :

[geforce]

Bonjour a tous,
Je cherche des éléments qui permette de privilégié l'algorithme de Bellman-Ford sur celui de A* ?

Merci

[dourouc05]

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 .

[geforce]

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.

[geforce]

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(n³)

Si je me base sur le schéma suivant :


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

[dinobogan]

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.

[geforce]

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.

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)?

Quelle sont c'est deux famille d'algorithme ?

Merci