Supposons qu'un groupe d'amis partage certaines dépenses sur un mois et doive régler les dettes à la fin. Chaque ami a une certaine somme d'argent qu'il doit donner / recevoir (la somme des dettes et des créances est nulle), mais tout doit être réglé par virements directs (pas de pool central, seulement de l'argent d'une personne à une autre), et chaque transfert a un coût.
Par exemple, supposons 3 personnes, A, B et C.
Le coût de chaque transaction peut être décrit par la matrice suivante (la personne de la ligne payant à la personne de la colonne).
Compte tenu de ces coûts, la solution optimale serait
Cela règle toutes les dettes avec un coût de transaction de 2. Comment puis-je généraliser cela?
Tout ce que j'ai trouvé en recherchant était de simplifier les dettes en chaîne (la personne A doit la personne B qui doit la personne C, donc la personne A doit la personne C).
Le plus proche que j'ai trouvé est this , mais il n'y a pas de frais de transaction.
Backstory (si quelqu'un est intéressé):
Nous vivons dans une maison de 8 personnes, et chaque mois, nous payons les factures avec notre propre argent et les annotons dans une feuille de calcul afin qu'à la fin du mois, nous partageons les dépenses équitablement. Cependant, nous avons des comptes sur différentes banques, et certains d'entre eux nécessitent des frais pour transférer de l'argent vers d'autres banques, nous préférons donc conserver les transactions de la même banque.
3 Réponses :
Dans le cas où la banque facture un pourcentage du montant transféré, votre tâche consiste à trouver une min -cost max flow .
Votre graphe doit avoir 5 couches.
(direction)
| Source layer: S
| / | \
| Exchange: A --- B --- C (complete graph)
| \ | /
V Sink : T
La source est connectée aux nœuds A, B, C ... la capacité de S -> A est combien A doit payer, et 0 si A ne possède pas d'argent. Le coût de l'arête est de 0.
Dans la couche d'échange A, B, C ... sont tous connectés les uns aux autres (graphe complet).
La capacité de A -> B est infinie et le coût est le montant que vous devez payer après avoir transféré 1 $ de A à B (même pour toutes les paires).
Les nœuds sont connecté à l'évier. La capacité de A -> Sink est de savoir combien A recevra, et 0 si A ne reçoit pas d'argent. Le coût de l'arête est de 0.
Exécutez un algorithme de flux min-cost max sur le graphe ci-dessus de la source racine au puits racine, comme Edmonds-Karp + cycle-canceling. Vous feriez probablement mieux de trouver une bibliothèque (telle que la bibliothèque de graphes Boost pour C ++), plutôt que d'implémenter les algorithmes vous-même.
Votre structure graphique proposée ne semble pas prendre en charge tous les flux possibles dans le problème réel - par exemple, il n'est pas possible de faire passer de l'argent par deux intermédiaires, tels que Alice -> Bob -> Charlie -> Dave. Bien que vous puissiez utiliser un algorithme de chemin le plus court toutes paires pour remplacer les arêtes inefficaces dans le graphique d'origine par le coût du chemin de remplacement le moins cher, je ne sais pas si cela suffit pour rendre la solution optimale.
Il semble qu'il serait préférable de remplacer la structure de la couche source / mélangeur / récepteur par un graphe orienté complet.
Merci pour votre commentaire! Bien, nous avons besoin d'autant de couches de mixage que de personnes que nous avons et chaque paire de couches suivante doit être entièrement connectée (donc à la fin, les couches de mixage contiendront N ^ 2 nœuds où N est le nombre de personnes). Cela ajoute cependant beaucoup à la complexité. Je vais réfléchir à la façon dont nous pouvons optimiser cela.
Je pense que la version non pondérée est un problème différent.
@j_random_hacker Notez que le poids de 1 est différent de la constante 1. Le transfert de 100 $ coûte 100 $ contre 1 $.
C'est vrai, et c'est pourquoi j'ai écrit dans la première phrase de cette réponse, que cela résout un problème différent mais similaire.
Désolé, j'ai complètement raté ça. Je supprimerai mes commentaires précédents.
J'ai trouvé une autre solution plus simple. On parle toujours de coûts de transfert qui sont proportionnels au montant transféré. Vous pouvez créer un graphique simple avec autant de nœuds que de personnes et exécuter l'algorithme de réseau simplex. Exemple Python:
import networkx as nx
G = nx.DiGraph()
G.add_node('A', demand=-100) # A has to send 100
G.add_node('B', demand=50) # B will receive 50
G.add_node('C', demand=50) # C will receive 50
G.add_edge('A', 'B', weight=1)
G.add_edge('A', 'C', weight=5)
G.add_edge('B', 'A', weight=1)
G.add_edge('B', 'C', weight=1)
G.add_edge('C', 'A', weight=2)
G.add_edge('C', 'B', weight=2)
print nx.network_simplex(G)
renvoie (150, {'A': {'C': 0, 'B': 100}, 'C': {'A': 0 , 'B': 0}, 'B': {'A': 0, 'C': 50}})
Un de mes collègues a mentionné l'algorithme simplex. Il a également mentionné que certains solveurs permettaient de définir des fonctions de coût qui ont coûté 0 si un bord de graphe est 0, ou n (constant) sinon. Lorsque j'ai étudié des algorithmes d'optimisation tels que simplex, il y a eu une brève mention de cela, et je pense que le solveur utiliserait branch and bound pour la résolution. Savez-vous si ce networkx peut faire cela? ou n'importe quel solveur qui peut? Pour l'instant, je suis déjà en train de développer un simple (et très inefficace) branch-and-bound donc, je pense que je vais finir cela en premier, puis essayer de trouver un tel solveur.
Après que @j_random_hacker ait expliqué que ce problème était difficile à résoudre dans les commentaires, j'ai perdu tout espoir de trouver une jolie solution et j'ai décidé d'en faire une qui fonctionne.
Suite à la suggestion de @ user3386109, également dans les commentaires, je me suis basé sur des minpaths pour résoudre le problème. J'ai donc commencé par utiliser [l'algorithme Floyd-Warshall] pour trouver le coût minimum pour faire passer de l'argent d'une personne à une autre pour chaque paire. Cela donne une matrice du coût minimum de transfert d'argent de la personne de la ligne à la personne de la colonne. J'ai également appliqué la modification (elle est disponible dans l'article de Wikipédia dans la section Reconstruction de chemin) pour obtenir une matrice qui donne le nœud suivant (saut suivant, la personne réelle à laquelle vous devez envoyer votre argent si vous souhaitez atteindre la personne de la colonne avec coût minimal) pour la personne de la ligne pour transférer de l'argent à la personne de la colonne.
Exemple des matrices initialisées, et le résultat après exécution de l'algorithme (Les éléments importants qui ont changé ont un point rouge):
J'ai alors décidé de faire une simple récursion Branch-and-Bound. Chaque appel de récursion recevrait une liste de dettes, une matrice pour toutes les transactions jusqu'à présent et le coût pour atteindre cet état. Il doit retourner TODO. Nous gardons un global pour la meilleure solution trouvée, et au début de l'appel de récursivité vérifions si le coût pour atteindre cet état est déjà pire que le meilleur global, si c'est le cas, nous retournons un coût "infini" pour signaler que ce n'est pas une solution que nous devons envisager.
Ensuite, nous sélectionnons quelqu'un qui doit de l'argent dans la liste des dettes et pour chaque personne qui doit recevoir de l'argent, nous créons des copies de la liste des dettes et de la matrice de transaction, et simulons la transaction du montant maximum d'argent entre ces deux personnes (Si A doit payer 100 mais C n'a besoin que de 50, le maximum est de 50). La matrice des transactions est modifiée en augmentant toutes les transactions dans le minpath pour ces deux personnes du montant transféré. Le coût est incrémenté si nous augmentons un élément qui était auparavant nul. Nous appelons alors la récursivité. Si la liste de dettes atteint 0, une solution a été trouvée, le coût minimum global est mis à jour et le coût retourné est de 0.
Dans une version précédente, j'ai engendré une récursion pour chaque paire de personne due / destinataire. Cela a donné des performances horribles et s'est avéré inutile, car l'ordre des transactions n'a pas d'importance, et toutes les dettes qui n'ont pas encore été réglées, nous sommes traitées à des niveaux de récursivité inférieurs.
Cet algorithme semblait correct, mais il y avait toujours un problème!
Dans l'exemple suivant:
L'algorithme tel qu'il est actuellement fait que A, B, C effectuent chacun un transfert vers D. La meilleure façon serait de choisir l'un des A, B ou C pour transférer tout l'argent à D en un seul paiement.
Dans cet exemple, les personnes A, B et C ont toutes le même coût extrêmement élevé de transfert vers D, et le prochain saut pour toutes pour obtenir de l'argent vers D est d'aller directement vers D. Cependant, la solution optimale serait de faire en sorte que chacun transfère tout son argent à une seule personne et le transfère à D en une seule fois. L'algorithme ne parvient pas à reconnaître que puisque quelqu'un a déjà effectué un transfert vers la personne D, le coût de cette transaction est de 0, et nous devrions donc utiliser ce nouveau chemin. Pour résoudre ce problème, j'ai inclus une matrice pour les coûts et une matrice pour les chemins dans la récursivité, au début de la récursivité, nous avons mis tous les coûts des transferts qui ont déjà été effectués dans cette branche de récursivité à 0, et exécutons l'algorithme Floyd-Warshall encore. La récursivité utilise ces matrices au lieu des matrices globales et les transmet. Bien sûr, cela signifie multiplier la complexité par V ^ 3, mais c'est le seul moyen que j'ai trouvé pour résoudre ce problème.
L'algorithme semble fonctionner maintenant, mais je vais probablement continuer à essayer de l'améliorer, en particulier dans la lisibilité du code. Le code complet est disponible sur: Mon projet gitlab, dans le dossier des calculs
Désolé pour la longue réponse et le retard dans sa publication, mais j'ai trouvé important de bien documenter mon travail.
Bien qu'il s'agisse d'un problème algorithmique intéressant, il semble que le problème financier sous-jacent serait mieux résolu par une solution financière. Je ne suis pas un expert en finances, mais vous pouvez essayer de poser la question sur le site de finances personnelles .
Les transferts ont-ils un prix fixe ou un% du montant transféré?
le prix fixe est ce dont nous avons besoin, et je suppose que c'est plus simple. S'il y a des ressources pour% de transfert, je suis sûr que je pourrais aussi y trouver une utilité, ou du moins m'inspirer.
Un point de départ est le problème du chemin le plus court . Pour chaque paire, le chemin le plus court vous indique le moyen le moins cher de transférer de l'argent entre ces deux. Par exemple, le chemin le plus court de A à C est ABC. Avec 8 personnes, il y a 28 chemins les plus courts à trouver.
Même la version non pondérée de ce problème (dans laquelle nous voulons simplement minimiser le nombre de transactions) est en fait NP-difficile - cela revient au problème de Subset Sum déguisé. Voir stackoverflow.com/q/15723165/47984 pour en savoir plus.
@j_random_hacker J'ai du mal à comprendre comment cela se monte au problème de la somme des sous-ensembles, car les transferts ne doivent pas être exactement ce dont une personne a besoin. Mais je continuerai de l'examiner. Mais de toute façon, je vous ai cru sur parole et j'ai renoncé à une bonne solution. J'ai suivi les conseils de l'utilisateur3386109 sur l'utilisation des minpaths et je codifie un algorithme de branchement et de liaison. Jusqu'à présent, ses performances sont absolument ridicules (quelques secondes pour 8 personnes en python, minutes pour 9). Je publierai bientôt une réponse avec cet algorithme au cas où quelqu'un trouverait utile.
Lorsque chaque transaction coûte 1 $, l'objectif est d'utiliser le moins transactions. Habituellement, s'il y a k personnes impliquées, cela nécessite k-1 transactions - mais s'il existe un sous-ensemble approprié de m personnes, m
Pour résoudre une instance de Subset Sum à l'aide d'un algorithme pour résoudre votre problème, créez une personne pour chacun des n nombres dans l'entrée de l'instance SS, et une autre personne avec le solde nécessaire pour rendre la somme de tous les montants nulle. Maintenant, transmettez-le comme entrée à votre algorithme, avec le coût de chaque transaction fixé à 1 $. Si votre algorithme rapporte un coût minimum de n, alors aucun sous-ensemble des n nombres originaux ne fait la somme de 0; s'il rapporte un coût inférieur, alors au moins un de ces sous-ensembles existe.