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 :

Décomposition d'un nombre à partir d'éléments d'un 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 éclairé
    Homme Profil pro
    Fondateur
    Inscrit en
    Octobre 2002
    Messages
    445
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Fondateur
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Octobre 2002
    Messages : 445
    Par défaut Décomposition d'un nombre à partir d'éléments d'un ensemble
    Bonjour,

    Voici mon problème :

    Imaginons qu'on ait un nombre x et un ensemble y de nombres.
    Je cherche à obtenir toutes les décompositions possibles du nombre x enn additionnant les éléments de y.

    Ma première idée a été d'utiliser un algo de type brute force sur l'ensemble y en calculant toutes les sommes possibles avec ses éléments et de sélectionner les calculs permettant d'obtenir x.

    Cela fonctionne mais n'est pas forcément la meilleure solution.

    J'aimerais donc avoir vos idées sur une meilleure approche afin de décomposer mon nombre x.

    Merci d'avance de votre aide.

  2. #2
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Par défaut
    Bonjour,

    si tu veux TOUTES les décompositions possibles, j'ai peur qu'un arbre de recherche s'impose.
    En revanche si tu veux une décomposition, la meilleure selon certains critères, tu peux utiliser une heuristique : tabou, recuit simulé, ...
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  3. #3
    Expert confirmé

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Par défaut
    Le probleme est NP-complet, donc il n'y a rien de mieux de connu que la force brute a un facteur constant (qui peut cependant etre important!).

  4. #4
    Inactif  
    Inscrit en
    Mars 2006
    Messages
    352
    Détails du profil
    Informations forums :
    Inscription : Mars 2006
    Messages : 352
    Par défaut
    Bonjour,

    Je pense qu'il existe tout un défi pour ce problème, c'est Génération des ensembles de nombre dont la somme est identique.

    Cordialement,
    Sidahmed

  5. #5
    Expert confirmé
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Par défaut
    La question posée est un peu plus complexe que celle traitée dans le défi, mais qu'à cela ne tienne, elle a également déjà été traitée sur le forum.

    --
    Jedaï

  6. #6
    Membre chevronné
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Par défaut
    Il serait sans doute efficace de mélanger un arbre d'exploration (pour avoir toutes les solutions) et la classique programmation dynamique du problème du sac à dos (pour savoir si dans une branche donnée au moins une solution existe).

    Cela marche comme une branch-and-bound. Un noeud correspond à un sous-problème où on a décidé que certains éléments de y doivent être dans la somme et certains ne doivent pas l'être (les autres peuvent l'être ou ne pas l'être).
    A chaque noeud, tu exécutes la programmation dynamique.
    • Si tu ne trouves pas de solution ce n'est pas la peine d'explorer plus en profondeur le sous-problème.
    • Si tu trouves une solution, tu choisis un nombre z dans y (parmi les nombres qui peuvent être ou pas dans la somme) et tu crées deux sous-problèmes: celui où z est dans la somme et celui où z n'est pas dans la somme.

Discussions similaires

  1. Réponses: 14
    Dernier message: 02/10/2009, 10h28
  2. Réponses: 6
    Dernier message: 20/07/2006, 11h25
  3. nombre impairs d'éléments dans un hash
    Par G-rhum dans le forum Langage
    Réponses: 2
    Dernier message: 14/01/2006, 14h47
  4. Incrémenter un nombre à partir de 5000.
    Par kmayoyota dans le forum Débuter
    Réponses: 3
    Dernier message: 03/10/2005, 17h59
  5. Réponses: 18
    Dernier message: 08/02/2004, 22h38

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