[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?

Bonjour :coucou:

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.

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.

:google2:

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

Citation:

---

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.

Citation:

---

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.

Salut,

Chercher TradeMaximizer dans un moteur de recherche...