Discussion :

[Nicodemus]

Bonjour,

j'ai un projet d'algo à faire et j'ai quelques questions. Le projet concerne le problème de l'arbre couvrant minimum d'un graphe et en l'occurence je dois implémenter l'algo de prim en C++. L'algo en lui même ne pose pas problème, par contre je dois utiliser différentes structures de données pour définir laquelle est la plus performante (on peut biensur le définir avec une analyse asymptotique mais le but est de programmer aussi , je dois me réferer au temps CPU).

Donc j'ai différentes structures : liste chainée, arbre rouge et noir mais aussi tas binomial. Il faut donc que je fasse pour chaque structure une classe qui possède les méthodes créer, inserer, minimum, extraire-minimum, union, diminuer clé et supprimer.

A votre avis que type de liste je dois utiliser ? chainée simple ? doublement chainée ? Et en ce qui concerne les différentes méthodes à implémenter... ça correspond à quoi dans ce cas l'opération union sur une liste... de même que diminuer clé par exemple ?

Enfin bref, j'essaye de réflechir un peu à tout ça avant de me lancer à fond dans la prog :-) Donc si vous avez un petit conseil ou une indication à me donner je suis prenant.

[Steki-kun]

il me semble avoir appris que Kruskal est plus rapide que Prim pour faire ça mais asymptotiquement cependant (y'a un V logV en moins où V est le nbre de sommets). En ce qui concerne une implémentation réelle je n'en sais rien, es-tu sûr d'obtenir le meilleur résultat avec Prim ?

Sinon, je pense qu'une liste chaînée simple suffit, ensuite c'est à toi de voir si tu privilégies la complexité en temps sur la complexité en espace ou le contraire, ou aucun des deux, mais normalement tu n'as pas besoin de l'avoir doublement chaînée. Il y a toujours un compromis à faire de tte façon pour une liste ou pour autre chose, l'union, c'est l'union ensembliste habituellement (concaténation sans doublons). Traditionnellement en Java, on représente un graphe par un tableau de listes de sommets (dans la case n du tableau, la liste des sommets reliés à n), et ca marche assez bien en C ou en Caml aussi. Pas besoin de grosse machinerie pour tout ça : fondamentalement, Kruskal ne nécessite qu'un tri des sommets et une fonction qui vérifie l'existence ou non de cycle (donc par un parcours de tremaux).

Dans le détail, tu peux toujours faire des benchmarks pour voir le + efficace bon courage

[Nicodemus]

Merci pour la réponse.

En fait, la question de savoir lequel de ces deux algos gloutons Prim ou Kruskal est le plus rapide ne se pose pas. Le sujet du projet est bel et bien l'implémentation de Prim. De plus, le but du projet est surtout de démontrer de manière pratique et non mathématique quelle structure de données est la mieux adapatée pour Prim : ABR, tas binomial ou liste chainée (simple apprarement d'apres ce que tu dis ).

Implémenter Prim avec une liste n'est pas compliqué... mais je maîtrise assez mal les ABR et ne sais même pas encore ce qu'est exactement un tas binomial . Débutant en C++ je vais déjà galérer pour bien programmer, alors si en plus je n'ai pas les notions d'algorithmique requises ...arf.

[Didier69]

Bonjour,

Je te conseille de jeter un coup d'oeil dans ce livre : Introduction à l'algorithmique. Tu devrais sûrement trouver des définitions précises pour tes différents types de données.

Cordialement.

[Nicodemus]

Merci Didier :-)
En fait, le bouquin de Cormen je l'ai sous les yeux. Mais ça fait beaucoup à assimiler d'un coup

[Steki-kun]

trouvé sur google : "les principales apports d'utilisation d'un tas binomial sont pour les recherches d'un minimum et l'union, ils sont donc recommandés dans des applications comme par exemple l'algorithme de Kruskal pour l'arbre couvrant minimum" [j'ai reformulé pour des raisons de place hein ]
donc comme Prim, c'est pas très très différent, y'a des chances que le tas binomial soit plus efficace que l'AB, cependant un peu plus chiant à implémenter peut être ! Voilà, peut être que ca pourra t'orienter.

[Paul Atreide]

Je viens juste de terminer un projet qui consistait à implémenter de manière optimale l'algo de Kruskal. Je te conseille donc d'aborder chacune des structures de données indépendemment. Tu commences par exemple par implémenter les tas binomiaux en t'aidant de documentations : le Cormen est super. Le principe c'est de bien comprendre chacune des structures de données sans te préocuuper du reste du projet. Quand tu auras bien compris toutes les structures alors tu pourras entreprendre l'implémentation de Prim.

Sinon je pense que pour ce que tu as à faire, il faut des listes doublement chaînées : elles permettent de réduire la complexité de la suppression d'un élément (de O(n) à O(1)).

Ah oui, j'allais oublier : toutes les structures que l'on te propose d'implémenter (listes, tas, ...) sont plus ou moins bien adaptées aux opérations que l'on te demande (insérer, suppr_min, ...) Mais je pense que si tu comprends bien toutes ces structures, tu n'auras pas de mal à trouver d'une part comment implémenter ces opérations en fonction des structures et, d'autre part, quelles vonty être les performances.

[Steki-kun]

Sinon je pense que pour ce que tu as à faire, il faut des listes doublement chaînées : elles permettent de réduire la complexité de la suppression d'un élément (de O(n) à O(1)).

C'est vrai en général, mais en pratique, dans Prim ou Kruskal, on ordonne la liste des arêtes avant, et puis on traite toujours le plus petit en premier, donc ca ne change rien ici, c'est O(1) dans les deux cas.

[Nicodemus]

Merci de vos conseils !
Je pense qu'implémenter les structures de données indépendament de l'algo est une bonne chose à faire Kwisatz Haderach (pour ceux qui ne savent pas de quoi je parle... je vous conseille de lire le cycle de Dune de Frank Herbert) .

Une fois que j'aurais implémenter les trois structures et que je m'attaquerais à l'algo en lui même j'aurais surement d'autres questions (donc je ne met pas le sujet résolu pour l'instant).

Merci