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 :

Reduction maximum d'ensemble.


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre habitué
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    11
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 11
    Par défaut Reduction maximum d'ensemble.
    Bonjour a tous,

    je vous soumets un problème pour lequel je n'arrive pas a trouver l'algorithme.

    Je le présente par l'exemple :

    Soit un puzzle (Z) de 10 pièces numérotées de 0 a 9.
    Il y a 10 personnes qui savent positionner 1 ou plusieurs pièces suivant ces règles :
    - p1 : z0,z1,z2,z6 (personne 1 sait positionner pièces 0,1,2 et 6)
    - p2 : z0,z1,z3,z7
    - p3 : z0,z2,z3,z9
    - p4 : z1,z2,z3,z5
    - p5 : z4,z5
    - p6 : z3,z4,z5
    - p7 : z0,z6,z7,z9
    - p8 : z1,z6,z7,z9
    - p9 : z7,z8
    - p10 : z2,z6,z9

    évidemment si je prends les 10 personnes j'aurais mon puzzle.
    Cependant elles coutent cher, donc je voudrais en prendre le minimum.

    Il semblerait que 3 personnes suffisent : P2,P4 et P7.

    Voila, entre autre, j'aimerais trouver l'algorithme qui sait réduire au max un tel ensemble suivant des règles de ce style.

    Merci beaucoup.

  2. #2
    Membre confirmé
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    118
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 118
    Par défaut
    Il y la méthode brutale qui consiste à explorer toutes les solutions possibles. Mais bon, c'est en O(2^n), donc irréalisable au delà de quelques pièces/personnes.

    Sinon, je trouve que ce problème a une sale tête de problème NP complet, donc il n'existe peut-être pas d'algorithme polynomial pour le résoudre...

    Est ce que tu veux absolument LA meilleure solution, ou une solution pas trop mauvaise te suffirait ?

  3. #3
    Membre habitué
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    11
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 11
    Par défaut
    Je cherche effectivement la meilleure solution.

    Le programme tournera sur des ensembles pouvant aller sur 10000 pieces - 10000 personnes

    J'apprecierais cependant de toujours avoir LA meilleure solution. ^_^

  4. #4
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    mmmm ça ressemble fortement au problème traité dans ce fil :

    http://www.developpez.net/forums/sho...d.php?t=292604

    ici-même... (je ne connaissais pas le terme, mais "problème de la célébrité"..)

  5. #5
    Membre confirmé
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    118
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 118
    Par défaut
    La représentation des données y ressemble un peu, mais il me semble que la complexité algorithmique de ce problème est bien supérieure !

    Et vu la quantité de données, j'aurais presque envie de dire que c'est peine perdue. Le seul algo que je vois est l'algo brutal, qui demanderait un nb de calculs de l'ordre de 2^10000, soit environ 10^3000 opérations...

    Et si quelqu'un confirme que c'est bien un pb NP complet, faudra s'orienter vers une résolution approchée.

    Pour voir si c'est un problème NP, on peut modéliser ce problème comme un graphe bipartie entre les personnes et les pièces, les arcs montrant quelles personnes peuvent monter quelles pièces. Résoudre ce problème reviendrait donc à trouver (dsl, je ne me souviens plus des termes exacts) le plus petit ensemble de sommets-personnes tels que tous les sommets-pièces soient atteints par au moins un arc.

    Sinon, ça a de fortes similitudes avec ce pb NP :
    http://fr.wikipedia.org/wiki/Probl%C...verture_exacte

    Je ne connais pas tous les problèmes listés ici, mais ça peut ptet dire quelque chose à quelqu'un :
    http://fr.wikipedia.org/wiki/21_prob...mplets_de_Karp

    Bon, bref... perso, la solution exacte me semble mal barrée, quelle que soit la puissance de calcul dont tu disposes...

    Mais j'espère pour toi que je me trompe !

    En attendant l'arrivée des ordinateurs quantique, faudra ptet se contenter d'une solution approchée.

  6. #6
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par fumidu
    Pour voir si c'est un problème NP, on peut modéliser ce problème comme un graphe bipartie entre les personnes et les pièces, les arcs montrant quelles personnes peuvent monter quelles pièces. Résoudre ce problème reviendrait donc à trouver (dsl, je ne me souviens plus des termes exacts) le plus petit ensemble de sommets-personnes tels que tous les sommets-pièces soient atteints par au moins un arc.
    On peut aussi le voir comme le probleme du voyageur de commerce avec une contrainte sur les tournées possibles.

    enfin bon, si tu preferes les graphes biparties...
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  7. #7
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Par défaut
    Salut
    Je te propose une méthode qui vaut ce qu'elle vaut, je l'ai testée, sur ton exemple, elle me donne une solution minimale mais il faudrait voir sur plus de pieces et de bonhommes.

    J'effectue une boucle.
    A chaque tour de boucle
    1. je selectionne la pièce qui est posée par le moins de personne
    2. Je selectionne dans la liste des personnes de la pièce selectionnée celle qui pose le plus de pièces
    3. j'enlève cette personne et je mets à jour les pièces posées par les autres personnes en leur enlevant celles qui sont déjà posées
    La boucle s'arrête évidemment quand il n'y a plus de pièce à sélectionner.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  8. #8
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par lannel
    Soit un puzzle (Z) de 10 pièces numérotées de 0 a 9.
    Il y a 10 personnes qui savent positionner 1 ou plusieurs pièces suivant ces règles : ...
    C'est marrant comme ca ressemble a la problematique du download des chunk sur un réseau P2P...

    @Trap D: J'en ai un autre

    1. Je choisis la personne qui a le plus de pieces
    2. Je pose ces pieces sur la table
    3. Je supprime ces pieces chez toutes les personnes
    4. je boucle au 1, tant qu'il reste des personnes avec des pieces
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. Le minimum et le maximum d'un ensemble de noeud
    Par Erwy dans le forum Télécharger
    Réponses: 0
    Dernier message: 10/01/2012, 16h06
  2. Reduction maximum d'ensemble
    Par lannel dans le forum Langage
    Réponses: 9
    Dernier message: 03/05/2007, 14h54
  3. Récupérer les maximums pour chaque ensemble ?
    Par vynce dans le forum Langage SQL
    Réponses: 2
    Dernier message: 15/12/2005, 09h52
  4. [Kylix] ensemble
    Par chico dans le forum EDI
    Réponses: 3
    Dernier message: 17/07/2002, 12h22
  5. Réponses: 3
    Dernier message: 12/06/2002, 19h03

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