Comment trouver les cycles qui, ensemble, impliquent le plus grand nombre d'arêtes non partagées dans un graphe orienté?

26

Je ne suis pas un théoricien de l'informatique, mais je pense que ce problème du monde réel appartient ici.

Le problème

Mon entreprise possède plusieurs unités à travers le pays.

Nous avons offert aux employés la possibilité de travailler sur une autre unité. Mais il y a une condition: le nombre total de travailleurs dans une unité ne peut pas changer.

Cela signifie: nous autoriserons un employé à quitter son unité si quelqu'un veut sa place.

Exemple de données de demande (fictives):

Name            Origin    Destination
Maria              1  ->  2
Marcos             2  ->  3
Jones              3  ->  4
Terry              4  ->  5
Joe                5  ->  6
Rodrigo            6  ->  1
Barbara            6  ->  1
Marylin            1  ->  4
Brown              4  ->  6
Benjamin           1  ->  3
Lucas              4  ->  1

Ce qui précède, tracé: Visualisation des données ci-dessus

Voyez comment nous devons choisir entre les options rouge, bleu ou noir?

Le vrai problème est un peu plus complexe, car nous avons 27 unités et 751 demandes. Veuillez jeter un œil à la visualisation

Le but

Après avoir collecté toutes les demandes, comment satisfaire la plupart d'entre elles?

Application de la théorie (?)

Ayant le graphe , soit chaque unité soit un sommet V et une requête un bord dirigé EG(V,E)VE , un échange réussi prendra la forme d'un cyle dirigé.

Chaque cycle ne doit utiliser qu'une seule fois ( un travailleur ne peut pas quitter son unité deux fois ), mais peut visiter V plusieurs fois ( une unité peut avoir de nombreux travailleurs qui souhaitent quitter ).EV

La question

Si ce problème est exprimé comme

"Comment trouver les cycles qui, ensemble, impliquent le plus grand nombre d'arêtes non partagées dans un graphe orienté"?

Allons-nous satisfaire la plupart des demandeurs?

Cela étant vrai, il existe un algorithme pour trouver cet ensemble optimal de cycles?

Cette approche greddy résoudra-t-elle le problème?

  1. Trouvez le plus grand cycle dirigé sur ;G
  2. Retirez ses bords de ;G
  3. Répétez 1 jusqu'à ce qu'il n'y ait pas de cycle dirigé sur ;G

Pouvez-vous m'aider?

Connaissez-vous une autre façon de décrire le problème d'origine (rendre la plupart des demandeurs heureux)?

Edit : changé de département en unité, pour mieux décrire le problème.

motobói
la source
3
Êtes-vous sûr de vouloir éviter d'utiliser le même bord plus d'une fois? D'après votre description de l'application, il me semble que vous devriez éviter d'utiliser le même sommet plus d'une fois, ce qui est une condition plus forte.
Tsuyoshi Ito
3
@TsuyoshiIto: Si je comprends bien de la description, la condition est qu'à chaque sommet, l'indegree doit être égal à l'outdegree. Donc, la séparation des sommets n'est pas nécessaire.
Yoshio Okamoto
7
Soit dit en passant, si ma compréhension est correcte, le problème devrait être résolu en temps polynomial au moyen d'un flux de réseau. A savoir, si nous donnons une unité de profit pour une unité de flux le long d'un bord, et nous donnons une capacité unitaire sur chaque bord, le problème est de trouver une circulation de profit maximum.
Yoshio Okamoto
3
Cet article traite d'une généralisation de votre problème okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html (pensez à chaque personne comme ayant un article à échanger, à savoir son placement).
Radu GRIGore
4
Une question géniale, nous donne l'impression que ce que nous faisons peut vraiment être utilisé dans la vraie vie :).
Gopi

Réponses:

9

OK, j'ai lu le code de TradeMaximizer et je crois qu'il résout le problème plus général suivant.

PROBLÈME: Étant donné est un graphe orienté dont les arcs ont des coûts. Trouvez un ensemble de cycles sommet-disjoint qui maximise le nombre de sommets couverts en premier et minimise le coût total en second.

Pour résoudre la question posée ici, faites des sommets des employés et tracez un arc de coût unitaire lorsque x aimerait le travail de y . Notez que les employés sont désormais des sommets plutôt que des arêtes. Ce qui est bien, c'est qu'un employé peut dire "Je veux vraiment le travail de y , mais celui de z le ferait aussi".xyxyyz

Solution:

  1. Construisez un graphique bipartite comme suit: Pour chaque sommet dans le graphique d'origine, introduisez un sommet gauche x L , un sommet droit x R et un arc x Lx R dont le coût est énorme (supérieur à la somme des coûts dans l'original graphique). Pour chaque arc x y dans le graphe d'origine, introduisez un arc x Ly R dans le graphe biparti.xxLxRxLxRxyxLyR

  2. Trouvez une correspondance parfaite de coût minimum dans le graphique bipartite.

Il existe également un prétraitement du graphique d'origine: supprimez les arcs entre les SCC, puis traitez tous les SCC de taille comme indiqué ci-dessus.>1

(En fait, TradeMaximizer itère sur toutes les solutions optimales, selon les deux critères ci-dessus, afin d'optimiser heuristiquement d'autres choses, telles que la longueur du plus grand cycle. Les gros cycles augmentent les chances qu'un «deal» ne passe pas par personne change d'avis.)

PS: L'auteur, Chris Okasaki, a confirmé que c'est ce que fait le code, de retour sur le blog .

Radu GRIGore
la source
J'ai réussi à trouver une solution au problème d'origine en utilisant TradeMaximizer. Je posterai detais demain.
motobói
@ motobói, mais tout ce que vous avez à faire est ce que j'ai écrit dans le deuxième paragraphe ...
Radu GRIGore
J'ai trouvé cette explication sur l'algorithme: boardgamegeek.com/wiki/page/TradeMaximizer
motobói
Pourriez-vous expliquer ou pointer une explication sur la raison pour laquelle il est nécessaire de supprimer les arcs entre les composants fortement connectés?
motobói
@ motobói, c'est une optimisation (pour le cas moyen). Les étapes (1) et (2) devraient être suffisantes.
Radu GRIGore
22

Il s'agit d'un problème de circulation à coût minimum standard. Donnez à chaque bord dirigé la capacité et le coût - 111 . Une circulation réalisable est alors une somme (c.-à-d., Union) de cycles dirigés disjoints, et le coût de la circulation est la négation du nombre de bords.

Parce que tous les coûts et capacités sont limités par des constantes, un simple algorithme d'annulation de cycle trouvera la circulation requise en temps polynomial. C'est presque la même chose que l'algorithme gourmand évident:

while G has any negative-cost directed cycles
    γ = arbitrary negative-cost directed cycle
    reverse every edge in γ
    negate the cost of every edge in γ
return the subgraph of reversed edges

O(VE)0EEO(VE2)

Ce n'est pas l'algorithme le plus rapide connu.

Jeffε
la source
pense que cela fonctionne tant qu'une personne ne veut pas travailler dans plus d'une "unité", non? en utilisant la formulation de la question d'origine. mais si les gens veulent travailler dans plus d'une unité, soupçonnez que cette abstraction tombe en panne. OP a déclaré un problème en termes d'une seule unité, mais cela me semble plutôt artificiellement contraignant. [quel humain n'a qu'une préférence ...?]
vzn
1
Qu'est-ce qu'une "personne" et une "unité"? C'est une question sur les graphiques.
Jeffε
Je suis perplexe: mon exemple n'est-il pas un contre-exemple pour cet algorithme? Après avoir choisi C, les cycles C_1 et C_2 ne sont plus des cycles (car chaque cycle a un bord inversé); Le C ne sera plus utilisé car il a un coût positif après avoir inversé ses bords et aucun nouveau cycle n'a été introduit. Parlons-nous du même problème? J'adorerais avoir une formulation mathématique du problème.
FiB
3
CCC1C2CCC1C2C=C1+C2C
apparemment, une "unité" est quelque chose comme un "département" et les utilisateurs enregistrent les demandes de transferts entre départements [pas exactement des postes spécifiques dans les départements]? Le diagramme des FIB semble avoir des unités comme sommets et des arêtes comme demandes d'empl entre les unités. FiB-- "aimerait avoir une formulation mathématique du problème" .. c'est vraiment à vous de fournir une formulation précise .. vous semblez être à mi-chemin ..
vzn
4

Cette approche gourmande ne donnera pas toujours la meilleure solution.

Cn{(v1,v2),,(vn,v1)}C1C2n1C .

CnC1C2 perdent chacun un bord et ne sont plus des cycles.

C1C22(n1)=2n2

n2

Mensonge
la source
-3

il y a probablement une méthode / formulation de théorie des graphes pour résoudre ce problème, mais ce problème ressemble plus à un problème de permutation pour moi où certaines de toutes les permutations sont rejetées et d'autres sont valides. les permutations sont des employés et les postes sont des "postes" dans l'entreprise. une permutation est rejetée si elle ne correspond pas aux exigences de "la personne [x] veut la position [y]". la distinction des limites unités / départements / organisation est apparemment quelque peu superflue dans ce cas.

ce type de problème de permutation avec contraintes peut être facilement converti en une instance de problème SAT (satisfiabilité). les affectations de variables booléennes représentent les employés et les clauses de contrainte représentent les contraintes "personne [x] veut position [y]". il y a des exemples classiques à proximité de cela, l'un généralement appelé le problème de la "table de dîner" où vous avez des places assises et des invités et tous les invités ne veulent pas s'asseoir côte à côte (ou de manière très similaire certains invités veulent s'asseoir à côté d'autres invités).

et bien sûr, il existe des solveurs SAT sophistiqués pour des instances assez importantes impliquant jusqu'à des centaines de variables et de clauses, sur PC, et si le problème n'est pas "difficile", par milliers.

voir par exemple [1] pour une référence professionnelle et [2] pour un exercice en classe. il y a aussi une certaine similitude structurelle avec ce que l'on appelle des "problèmes de pigeonniers" qui sont bien étudiés dans les cercles SAT où les pigeons sont affectés à des pigeonniers et où vous avez plus ou moins de trous que les pigeons. dans ce cas, cependant, les pigeons sont généralement considérés comme interchangeables. en d'autres termes, le problème de la table du dîner est comme le problème des pigeonniers avec des contraintes plus fortes et les invités / pigeons ont des préférences requises.

notez bien sûr / gardez à l'esprit que pour ces types de problèmes, en fonction des contraintes, la réponse peut être "aucune solution contrainte de ce type n'existe".

[1] l'algorithme de table de dîner, par crato

[2] CS402 princeton HW SAT

[3] Problème de satisfaction, wikipedia

vzn
la source
J'ai essayé la permutation en utilisant trademaximizer. Définir un employé comme un utilisateur qui veut échanger son unité X pour l' unité Y . Mais le logiciel ne permettra pas à plus d'un utilisateur d'échanger le même article (son unité). Chaque article doit être unique. Pour s'adapter à cela, j'aurais dû avoir, disons, [(Jones) veut échanger Unit-C-James contre Unit-D-Laura ou Unit-D-Sergio ou Unit-D-Mary]
motobói