Publicité
+ Répondre à la discussion Actualité déjà publiée
Page 3 sur 3 PremièrePremière 123
Affichage des résultats 41 à 45 sur 45
  1. #41
    Membre à l'essai
    Inscrit en
    décembre 2008
    Messages
    24
    Détails du profil
    Informations forums :
    Inscription : décembre 2008
    Messages : 24
    Points : 21
    Points
    21

    Par défaut

    Citation Envoyé par millie Voir le message
    En fait, dès que le graphe est faiblement connexe, il y a une méthode vachement plus simple que de passer par des flots.
    Laisse moi deviner: à partir du graphe réduit on cherche à compléter les arcs existants pour trouver un cycle hamiltonien ?

  2. #42
    Membre Expert
    Homme Profil pro
    Inscrit en
    mars 2007
    Messages
    895
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : mars 2007
    Messages : 895
    Points : 1 196
    Points
    1 196

    Par défaut

    Bon, il y a quelques temps j'avais implémenté l'algo suivant, mais je n'avais pas posté car je ne sais pas prouver qu'il est bon. Mais bon voilà.
    C'est sur l'idée de Jean-Marc Bourguet à la seconde page de cette discussion.

    1) réduire la graphe à ses composants fortement connexes
    2) si ce graphe ne contient qu'un seul noeud, on a fini
    3) trouver un couple (puits, source) tel que la source ne domine pas le puits (c'est à dire tel qu'il n'existe pas de chemin de la source au puits)
    - s'il un tel couple existe, ajouter cette arc et continuer en 3)
    - sinon relier n'importe quel puits à n'importe quelle source et continuer en 1)

    [edit: J'avais oublié le code]
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    smallestForSC g = applyReduce edgesToAdd g
        where edgesToAdd g' | null (drop 1 $ vertices g') = []
                            | null undominated = let newEdge = (head roots, head sinks) in 
                                                     newEdge : (smallestForSC $ buildG (bounds g') (newEdge:edges g')) 
                            | otherwise = let newEdge = head undominated in
                                              newEdge : (edgesToAdd $ buildG (bounds g') (newEdge:edges g'))
                            where
                   roots = [ix | (ix, deg) <- assocs (indegree g'), deg == 0]
                   sinks = [ix | (ix, deg) <- assocs (outdegree g'), deg == 0]
                   undominated = [(s,r) | [s,r] <- sequence [sinks, roots], not $ path g' r s]
    Pour les fonctions annexes, voir premier post de Jedai dans cette discussion.
    [/edit]

  3. #43
    Membre du Club
    Inscrit en
    décembre 2004
    Messages
    147
    Détails du profil
    Informations forums :
    Inscription : décembre 2004
    Messages : 147
    Points : 63
    Points
    63

    Par défaut Suite ?

    Je vois qu'il n'y a toujours pas eu de réponse à ce fil depuis un moment.
    Le défi est-il terminé ? Quelle serait la (ou les) solution ?

  4. #44
    Rédacteur/Modérateur

    Avatar de millie
    Profil pro
    Inscrit en
    juin 2006
    Messages
    6 939
    Détails du profil
    Informations personnelles :
    Localisation : Luxembourg

    Informations forums :
    Inscription : juin 2006
    Messages : 6 939
    Points : 8 758
    Points
    8 758

    Par défaut

    Citation Envoyé par dest Voir le message
    Je vois qu'il n'y a toujours pas eu de réponse à ce fil depuis un moment.
    Le défi est-il terminé ? Quelle serait la (ou les) solution ?
    Les défis ne se ferment jamais

    Pour l'instant, il n'y a pas eu de solution complète sans erreurs (sauf la brute-force) (EDIT : ah si, celle de dividee doit être bonne )

    Et il y a encore moins eu de réponses avec preuve.
    Je ne répondrai à aucune question technique en privé

  5. #45
    Alp
    Alp est déconnecté
    Expert Confirmé Sénior
    Avatar de Alp
    Homme Profil pro
    Inscrit en
    juin 2005
    Messages
    8 586
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 25
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations forums :
    Inscription : juin 2005
    Messages : 8 586
    Points : 10 409
    Points
    10 409

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
  •