Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 7 sur 7
  1. #1
    Invité régulier
    Inscrit en
    septembre 2008
    Messages
    17
    Détails du profil
    Informations forums :
    Inscription : septembre 2008
    Messages : 17
    Points : 5
    Points
    5

    Par défaut plus grand ensemble (propriété non transitive)

    Bonjour,

    J'ai un problème à résoudre mais je n'arrive pas à le faire en un temps raisonnable lorsque le nombre d'élément est grand alors j'espère pouvoir obtenir de l'aide.

    J'ai un ensemble d'éléments mathématiques. entre ces éléments il existe une relation binaire qui permet de dire si deux éléments sont liés. Il est important de préciser que cette propriété n'est pas transitive. On note ~ l'opération de relation. Si a~b et b~c sont vrais alors on ne peut rien dire sur le résultat de a~c.

    Mon but est de trouver le cardinal du plus grand ensemble noté (E) tel que
    pour tout (x,y) € E² x~y.

    Pour le moment l'algorithme le plus rapide que j'ai trouvé était de tester toutes les combinaisons d’éléments (j'évite les doublons en associant à chaque objet un identifiant unique entier et en ne considérant que les ensemble d'identifiants décroissants). Cependant à partir de 45 éléments le temps de calcul est déjà trop conséquent.

    Je suis débutant en algorithmique, peut être existe-til un algorithme standard pour faire ça mais je n'ai pas trouvé sur internet.

    Merci beaucoup de votre aide.

  2. #2
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 756
    Points
    15 756

    Par défaut

    D'après ce que je comprend de ton problème, il s'agit de trouver la plus grande clique dans un graphe.

    "maximum clique problem"
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Invité régulier
    Inscrit en
    septembre 2008
    Messages
    17
    Détails du profil
    Informations forums :
    Inscription : septembre 2008
    Messages : 17
    Points : 5
    Points
    5

    Par défaut

    Merci beaucoup,

    je vais lire ça et je retourne vous dire si c'est ce que je cherchais.

  4. #4
    Invité régulier
    Inscrit en
    septembre 2008
    Messages
    17
    Détails du profil
    Informations forums :
    Inscription : septembre 2008
    Messages : 17
    Points : 5
    Points
    5

    Par défaut

    C'est exactement cela. Merci beaucoup. Mon problème peut se ramener à un graphe à n où il y a entre 0 et n-1 liens par sommets. Il semble que dans çe cas les algorithme sont difficilement implémentables

  5. #5
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 756
    Points
    15 756

    Par défaut

    Citation Envoyé par destroyer-duck Voir le message
    C'est exactement cela. Merci beaucoup. Mon problème peut se ramener à un graphe à n où il y a entre 0 et n-1 liens par sommets. Il semble que dans çe cas les algorithme sont difficilement implémentables
    C'est un problème NP-Hard pour lequel les algos de résolution existant sont exponentiels en temps.

    Pour autant, ces algos sont peut-être suffisants pour satisfaire tes contraintes: nmb d'élements, nmb de liaisons, ressources CPU/Mem disponibles, délai maximum, ...
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  6. #6
    Invité régulier
    Inscrit en
    septembre 2008
    Messages
    17
    Détails du profil
    Informations forums :
    Inscription : septembre 2008
    Messages : 17
    Points : 5
    Points
    5

    Par défaut

    il y a 500 sommets dans mon graphe.
    Entre 0 et 499 liaisons par sommet.
    et le tout doit être exécuté en T<0.1s

    J'ai essayé de regarder les publications mais je pense que si j'essaie de comprendre ça : lien. Je pense que je ferais mieux d'abstraire différemment le problème.

  7. #7
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 756
    Points
    15 756

    Par défaut

    Citation Envoyé par destroyer-duck Voir le message
    il y a 500 sommets dans mon graphe.
    Entre 0 et 499 liaisons par sommet.
    et le tout doit être exécuté en T<0.1s
    Whoo. Ca parait difficilement atteignable. Par exemple, dans le papier "An improved bit parallel exact maximum clique algorithm", ce genre de temps n'est atteignable que pour 100/150 sommets.

    Je pense que je ferais mieux d'abstraire différemment le problème.
    Effectivement. Tu peux toujours nous décrire le problème de départ si tu y es autorisé.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •