Modèles de décision

[invite8666d089]

Bonjour,

Mon fils fait ses études et a apporté un peu de travail à la maison ce week-end. Je jette un oeil par-dessus son épaule sur ce qu'il est en train de faire et reconnais immédiatement le problème de l'électricien qui veut alimenter un nombre n de prises avec un minimum de fil électrique. Ayant eu à traiter ce problème lorsque j'étais en activité, je lui dis "Kruskal". Il me répond "non : Prim".

Pris d'un gros doute, je fonce sur Wikipédia et vois que l'algorithme de Kruskal date de 1956 et celui de Prim de 1957. Alors, je m'interroge. S'agit-il du même algorithme ou de deux algorithmes dont le second est plus rapide que le premier. J'ai programmé le modèle de Kruskal, mais ne sais rien de celui de Prim. Si quelqu'un a une idée, je suis preneur. Mais ne perdez pas de temps là-dessus, c'est par pure curiosité.

Bon dimanche à tous.
-----

[invite4492c379]

Hello,

a priori il résolvent tous deux le même problème, mais la construction de l'arbre est différente. Avec PRIM on part d'un sommet et on construit l'arbre en l'étendant, avec KRUSKAL on a plutôt une forêt que l'on réduit petit à petit à un arbre.
PRIM a une complexité en O(A*S) (avec une bonne implémentation on peut déscendre à O(A+S*logS)) et KRUSKAL a une complexité en Θ(A*logS) (récupéré sur wikipedia).

A priori je dirai qu'avec peu de sommets on préférera PRIM, avec beaucoup de sommets on préférera KRUSKAL, mais il s'agit là d'une approximation.

[invite8666d089]

Merci photon57 pour le coup de lumière. Je vais donc passer un peu de temps sur PRIM.