Modèles de décision
Répondre à la discussion
Affichage des résultats 1 à 3 sur 3

Modèles de décision



  1. #1
    Dormeur74

    Modèles de décision


    ------

    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.

    -----
    Dernière modification par Dormeur74 ; 06/11/2011 à 11h25.

  2. #2
    invite4492c379

    Re : Modèles de décision

    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.

  3. #3
    Dormeur74

    Re : Modèles de décision

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

Discussions similaires

  1. Outil d'aide à la décision
    Par inviteb7760f40 dans le forum Logiciel - Software - Open Source
    Réponses: 8
    Dernier message: 27/10/2011, 11h47
  2. Statistique : Critère de décision
    Par invite4d02ada1 dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 09/05/2011, 15h20
  3. Notation : décision
    Par prgasp77 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 26/03/2009, 16h02
  4. [Biologie Moléculaire] Décision de replication de l'ADN
    Par invite81f40b96 dans le forum Biologie
    Réponses: 14
    Dernier message: 17/04/2008, 23h02
  5. Prendre une décision
    Par invite0993b796 dans le forum [ARCHIVE] Psychologie / Sociologie
    Réponses: 6
    Dernier message: 29/05/2004, 00h11