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

**bouquetin** · 10/09/2019, 11h35

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?

**Flodelarab** · 10/09/2019, 11h47

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.

**bouquetin** · 10/09/2019, 12h00

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.