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

[dinobogan]

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

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.

Quelle sont c'est deux famille d'algorithme ?

Déjà dit aussi : Bellman-Ford est systématique et A* est heuristique.

[geforce]

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à.

[dinobogan]

A* ne peut pas passer deux fois par un même noeud puisqu'il marque tous les noeuds traités.

[geforce]

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?

Particularité de algo.2.docx

[geforce]

des critiques constructive si possible Merci.