IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algo P.E.R.T ?


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éprouvé
    Avatar de TicTacToe
    Inscrit en
    Septembre 2005
    Messages
    1 940
    Détails du profil
    Informations personnelles :
    Âge : 52

    Informations forums :
    Inscription : Septembre 2005
    Messages : 1 940
    Par défaut Algo P.E.R.T ?
    Bonjour

    Mon but: démarrer des taches dans l'ordre, avec comme seule contrainte, des couples (A implique B).

    Entrée: Liste de couples ( A-> B)
    Sortie: Liste des taches dans l'ordre selon les contraintes de précédence.
    Eventuellement, prévenir en cas de bouclage (liste de couples non valide)

    Exemple:
    Entrée = (A->B), (A->C), (C->B)
    Sortie = (A,C,B)

    Je sais qu'il y a la méthode PERT pour effectuer cela (bien que je n'ai aucune contrainte de durée de tache).

    1. J'ai fais ca il y a bien trop longtemps pour m'en rappeler, qq'un connait un site ou l'algo est clairement décris ?

    2. Si ca se trouve ca ne s'appelle plus PERT comme il n'y a pas de contrainte de durée ? si c'est un autre nom, ca m'aiderait de le savoir pour rechercher l'algo...

    Merci !
    Section Delphi
    La mine d'or: La FAQ, les Sources

    Un développement compliqué paraitra simple pour l'utilisateur, frustrant non ?
    Notre revanche ? l'inverse est aussi vrai ;-)

  2. #2
    Expert confirmé

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Par défaut
    J'appelle ca un tri topologique.

  3. #3
    Membre éprouvé
    Avatar de TicTacToe
    Inscrit en
    Septembre 2005
    Messages
    1 940
    Détails du profil
    Informations personnelles :
    Âge : 52

    Informations forums :
    Inscription : Septembre 2005
    Messages : 1 940
    Par défaut
    Merci !

    j'ai trouvé mon bonheur grace à ce nom de méthode (pffiouu, c'est loin les études )
    Section Delphi
    La mine d'or: La FAQ, les Sources

    Un développement compliqué paraitra simple pour l'utilisateur, frustrant non ?
    Notre revanche ? l'inverse est aussi vrai ;-)

  4. #4
    Membre confirmé Avatar de Jimmy_S
    Inscrit en
    Octobre 2005
    Messages
    214
    Détails du profil
    Informations forums :
    Inscription : Octobre 2005
    Messages : 214
    Par défaut
    A l'occasion tu pourras me montrer à quoi ressemble ton algo ? Ca m'interesse pas mal

  5. #5
    Membre éprouvé
    Avatar de TicTacToe
    Inscrit en
    Septembre 2005
    Messages
    1 940
    Détails du profil
    Informations personnelles :
    Âge : 52

    Informations forums :
    Inscription : Septembre 2005
    Messages : 1 940
    Par défaut
    Désolé Jimmy, j'avais pas vu ton Post...

    J'ai traduit l'algo que j'ai trouvé en Delphi pour mes besoins.
    (Je n'ai plus le lien ou j'avais l'algo brut)
    Je vois que tu es plutot PHP, donc pas de problème si tu as des questions sur la syntaxe.

    Voici le Code:

    Une Fonction pour construire la liste d'elt.
    LElts : La liste des elements en cours (non triées)
    SDe et SVers: La contrainte SDe doit être fait AVANT SVers

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    procedure TriTopoAjouter( LElts: TStringList; SDe, SVers: string );
    var
       IIndex : Integer;
    begin
         if not LElts.Sorted
           then LElts.Sorted := True;
         // Ajout du predecesseur dans la liste
         if SDe = '' then Exit;
         if not LElts.Find( SDe, IIndex )
           then LElts.AddObject( SDe, TStringList.Create );
         // ajout de elt dans la liste
         if SVers = '' then Exit;
         if not LElts.Find( SVers, IIndex )
           then IIndex := LElts.AddObject( SVers, TStringList.Create );
         // ajout de l'arc
         if TStringList( LElts.Objects[ IIndex ] ).IndexOf( SDe ) = -1
           then TStringList( LElts.Objects[ IIndex ] ).Add( SDe );
    end;
    Une fonction pour détruire ma la liste initiale
    LElts: Liste des élements non triées (la même qu'au dessus)
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    procedure TriTopoToutSupprimer( LElts: TStringList );
    var
       i : Integer;
    begin
         // Suppression des objets de la liste... et de la liste
         for i := 0 to LElts.Count - 1 do
           if Assigned( LElts.Objects[ i ] )
             then TStringList( LElts.Objects[ i ] ).Free;
         LElts.Clear;
    end;
    Et enfin, la fonction principale de tri, une fois la liste LElts alimentée
    LElts: Listes des élements non triées (les contraintes sont inclus dans la liste sous forme d'objets)
    LResultat: La liste des élements dans l'ordre topologique
    Retour fonction: TRUE si pas de cycle, FALSE sinon

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    function TriTopologique( LElts: TStringList; LResultat: TStringList ): Boolean;
    var
       i : Integer;
       LNoPreds: TStringList;
       SNoPred : string;
       IIndex : Integer;
    begin
         // Inits
         Result := True;
         LResultat.Clear;
         if LElts.Count = 0 then Exit;
         LNoPreds := TStringList.Create;
         try
         // Listes initiales des elts sans prédecesseur
         for i := 0 to LElts.Count - 1 do
           if TStringList( LElts.Objects[ i ] ).Count = 0
             then LNoPreds.Add( LElts[ i ] );
         // boucle principale
         while LElts.Count > 0 do
           begin
           if LNoPreds.Count > 0 then
             try
             SNoPred := LNoPreds[ 0 ];
             if LElts.Find( SNoPred, IIndex ) // sup. de SNoPred de la liste
               then LElts.Delete( IIndex );
             for i := 0 to LElts.Count - 1 do // sup. des éleves de SNoPred
               begin
               IIndex := TStringList( LElts.Objects[ i ] ).IndexOf( SNoPred );
               if IIndex <> -1 then
                 begin
                 TStringList( LElts.Objects[ i ] ).Delete( IIndex ); // sup. de l'arc do'rigine SNoPred
                 if TStringList( LElts.Objects[ i ] ).Count = 0
                   then LNoPreds.Add( LElts[ i ] );
                 end;
               end;
             LResultat.Add( SNoPred );
             finally LNoPreds.Delete( 0 ); end
           else
             Break;
           end;
         Result := LElts.Count = 0;
         finally LNoPreds.Free; TriTopoToutSupprimer( LElts ); end;
    end;
    Bon courage !
    Section Delphi
    La mine d'or: La FAQ, les Sources

    Un développement compliqué paraitra simple pour l'utilisateur, frustrant non ?
    Notre revanche ? l'inverse est aussi vrai ;-)

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. cherche algos Delphi pour : Huffman, R.S.A, D.E.S.
    Par X-Delphi dans le forum Débuter
    Réponses: 3
    Dernier message: 24/08/2002, 18h51
  2. Cherche l'algo crc 16 bits
    Par icepower dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 21/08/2002, 13h27
  3. Algo de calcul de FFT
    Par djlex03 dans le forum Traitement du signal
    Réponses: 15
    Dernier message: 02/08/2002, 17h45
  4. Algo de Hough et ou de Radon
    Par victorracine dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 29/07/2002, 11h09
  5. Recherche algo tree
    Par Anonymous dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 24/05/2002, 13h44

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo