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 :

[Résolu] "math trades" chaînes d'échanges


Sujet :

Algorithmes et structures de données

  1. #1
    Membre à l'essai
    Homme Profil pro
    Chargé d'affaire
    Inscrit en
    juin 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 22
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Chargé d'affaire

    Informations forums :
    Inscription : juin 2019
    Messages : 8
    Points : 12
    Points
    12
    Par défaut [Résolu] "math trades" chaînes d'échanges
    Bonjour,
    Dans certains domaines, des communautés organisent des chaînes d'échanges (livres, jeux...).
    Chacun exprime ses offres et demandes.
    Un logiciel dit de "math trade" permet de réaliser des chaînes d'échanges les plus performantes.
    Les participants s'engagent alors à envoyer ce que le logiciel a calculé.

    Exemple (simple, pour expliquer!)
    A possède 1 et veut 2
    B possède 2 et veut 3
    C possède 3 et veut 4
    D possède 4 et veut 1

    L'algorithme va alors dire
    A envoie 1 à D
    B envoie 2 à A
    C envoie 3 à B
    D envoie 4 à C

    Où peut-on trouver l'algorithme le plus efficace qui permet de réaliser ce calcul?

  2. #2
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 050
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 050
    Points : 9 962
    Points
    9 962
    Par défaut
    Bonjour

    C'est un problème de théorie des graphes.
    Tu dessines un graphe avec les humains comme nœuds, et des flèches pour dire que l'un veut l'objet de l'autre.
    Puis tu cherches un cycle dans le graphe.
    Fin de l'algorithme.

    S'il n'y a pas de cycle, aucun échange n'est possible.
    Si plusieurs cycles sont possibles, tu ne dis pas quelle politique adopter.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  3. #3
    Membre à l'essai
    Homme Profil pro
    Chargé d'affaire
    Inscrit en
    juin 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 22
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Chargé d'affaire

    Informations forums :
    Inscription : juin 2019
    Messages : 8
    Points : 12
    Points
    12
    Par défaut
    En un peu plus compliqué quand même.
    J'avais pris un exemple simple.
    Mais chaque personne peut avoir plusieurs offres et demandes.

    Et il peut y avoir plusieurs solutions. Il faut trouver la meilleure, donc se donner un élément de mesure.

    Il peut aussi y avoir des notions de valeur. Du genre 1 vaut 10, tandis que 2 et 3 valent 5 chacun. Donc il faut 2+3 pour compenser 1. Mais bon, en 1ère approximation, je veux bien me passer de cet aspect.

    Et puis il faut couper des branches parce que ça peut devenir trop gourmand en temps et mémoire.


    D'où ma question, si des éléments d'algorithme sont présents dans la littérature.

  4. #4
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 050
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 050
    Points : 9 962
    Points
    9 962
    Par défaut


    http://perso.ens-lyon.fr/eric.thierr...-panhaleux.pdf

    Il faut trouver la meilleure
    La "meilleure" est toujours par rapport à un critère. Tant que tu ne donneras pas tes critères dans l'ordre d'importance, tu ne trouveras pas.

    En un peu plus compliqué quand même.
    Si tu as plusieurs cycles, tu as un choix. Si tu n'as pas de cycle, tu n'as pas de solution. C'est une condition d'existence.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  5. #5
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    septembre 2009
    Messages
    12 035
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2009
    Messages : 12 035
    Points : 28 476
    Points
    28 476
    Billets dans le blog
    2
    Par défaut
    Salut,

    Chercher TradeMaximizer dans un moteur de recherche...
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

Discussions similaires

  1. [BASH] Insertion de quotes dans une chaîne
    Par Alfred456654 dans le forum Linux
    Réponses: 7
    Dernier message: 21/07/2009, 14h55
  2. Réponses: 12
    Dernier message: 08/08/2008, 12h03
  3. Chaîne tronquée à cause d'une quote
    Par Didier77 dans le forum Langage
    Réponses: 5
    Dernier message: 17/06/2008, 15h43
  4. Chaînes entre double quotes
    Par ybruant dans le forum Langage
    Réponses: 6
    Dernier message: 25/03/2008, 15h46
  5. Réponses: 6
    Dernier message: 08/08/2006, 10h14

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