Débit de pointe et problème d'affectation linéaire

Ongle combinaison maximale matching c'est une combinaison parfaite oui pour chacun nœud n dans G.setOfArcs il y a arc a dans matching où a.fromNode == n or a.toNode == n.

Combinaison bi-partitionnée maximale

Ongle combinaison bi-partitionnée maximale c'est une combinaison maximale en un digrafo G Qu'est que c'est bi-partitionné .

Depuis G il est bi-partitionné , le problème de trouver un combinaison maximale bipartite peut être transformé en un problème de débit de pointe résoluble avec algorithme par Edmonds-Karp et puis le couplage bipartite maximal peut être récupéré de la solution à problème de débit de pointe .

Soit bipartition être un bipartition de G.

Pour cela, j'ai besoin de générer un nouveau digrafo (H) avec de nouveaux nœuds (H.setOfNodes) et certains arcs nouveau (H.setOfArcs). H.setOfNodes contient tout nœuds dans G.setOfNodes et deux nœuds plus, s (une nœud source ) et t (une nœud terminal ).

H.setOfArcs contiendra un arc pour chaque G.setOfArcs. Si un arc a est un G.setOfArcs et a.fromNode est dans bipartition.firstPart et a.toNode est dans bipartition.secondPart puis inclut a dans H (ajout d'un FlowArcDatum(1,0)).

Si a.fromNode est un bipartition.secondPart et a.toNode est un bipartition.firstPart, alors incluez Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) dans H.setOfArcs.

Définition d'un graphique bi-partitionné garantit que non arc connecter tout nœud où les deux nœuds ils sont sur la même partition. H.setOfArcs contient également un arc de nœud s à chaque nœud dans bipartition.firstPart. Enfin, H.setOfArcs contient un arc chaque nœud dans bipartition.secondPart une nœud t. a.datum.capacity = 1 pour tous a dans H.setOfArcs.

Première partition du nœuds dans G.setOfNodes les deux ensembles (part1 et part2) séparé tellement que non arc dans G.setOfArcs passe d'un ensemble au même ensemble (cette partition est possible car G est bi-partitionné ). Puis ajoutez tous les arcs dans G.setOfArcs qui sont dirigés depuis le part1 au part2 vers H.setOfArcs. Ensuite, créez un seul nœud la source s et un seul nœud Terminal t et créez plus arcs

Puis construisez un maxFlowProblemState.

Couverture minimale des nœuds

Une couverture de nœud dans un digraphe G C'est un ensemble de nœuds (cover) à partir de G.setOfNodes tellement que pour tout arc a de G.setOfArcs cela doit être vrai: (a.fromNode en cubierta) o (a.toNode en cubierta).

Une couverture de nœud minimale est le plus petit ensemble de nœuds dans le graphique qui est toujours un couverture de nœud . Le théorème de König indique que sur un graphe bi-partitionné , la taille du correspondance maximale dans ce graphique est égal à la taille du couverture minimale des nœuds , et suggère comment la couverture de nœud peut être récupérée à partir d'un correspondance maximale :

Supposons que nous ayons le bipartition bipartition et la correspondance maximale matching. Définissez un nouveau digrafo H, H.setOfNodes=G.setOfNodes, le arcs dans H.setOfArcs ils sont l'union de deux ensembles.

Le premier ensemble de arcs a dans matching, avec le changement que si a.fromNode in bipartition.firstPart et a.toNode en bipartition.secondPart puis a.fromNode et a.toNode sont échangés dans le acro créé ils donnent un tel arcs un attribut a.datum.inMatching = True pour indiquer qu'ils proviennent de arcs dans une coïncidence .

Le deuxième ensemble est arcs a PAS dans matching, avec le changement que si a.fromNode en bipartition.secondPart et a.toNode en bipartition.firstPart puis a.fromNode et a.toNode sont échangés dans le arc créé (donne un tel arc un attribut a.datum.inMatching = False).

Puis lancez un première recherche en profondeur ( DFS ) de chaque nœud n dans bipartition.firstPart qui n'est pas n == a.fromNode ni n == a.toNodes pour n'importe qui arc a dans matching. Pendant DFS, certains nœuds sont visités et d'autres non (stockez ces informations dans un champ n.datum.visited). La couverture minimale des nœuds est l'union de nœuds {a.fromNode para a en H.setOfArcs si ((a.datum.inMatching) y (a.fromNode.datum.visited))} et nœuds {a.fromNode para a en H.setOfArcs si (a.datum.inMatching) y (no a.toNode.datum.visited)}.

Cela peut être montré pour conduire à partir d'un correspondance maximale à une couverture minimale des nœuds par un preuve par contradiction , prendre un arc a qui n'était pas censé être couvert et examinez les quatre cas pour savoir si a.fromNode et a.toNode appartiennent (soit comme toNode ou fromNode) à tout arc dans coïncidence matching. Chaque cas conduit à une contradiction en raison de l'ordre dans lequel DFS visite nœuds et le fait que matching c'est un correspondance maximale .

Supposons que nous ayons une fonction pour exécuter ces étapes et renvoyer l'ensemble de nœuds qui comprend le couverture minimale des nœuds quand il reçoit le digrafo G, et le correspondance maximale matching:

Le problème d'affectation linéaire

Le problème d'affectation linéaire consiste à trouver une coïncidence maximale des poids dans un graphe biparti pondéré.

Des problèmes comme celui qui apparaît au début de cet article peuvent être exprimés comme un problème affectation linéaire . Étant donné un ensemble de travailleurs, un ensemble de tâches et une fonction qui indique la rentabilité d'une affectation d'un travailleur à une tâche, nous voulons maximiser la somme de toutes les affectations que nous effectuons; c'est un problème d'affectation linéaire .

Supposons que le nombre de tâches et de travailleurs soit égal, même si je montrerai que cette hypothèse est facile à supprimer. Dans la mise en œuvre, je représente poids d'arc avec un attribut a.datum.weight pour arc a.

Algorithme de Kuhn-Munkres

L'algorithme de Kuhn-Munkres résout le problème d'affectation linéaire . Une bonne implémentation peut prendre du temps O(N^{4}), (où N est le nombre de nœuds dans le digrafo représentant le problème). Une implémentation plus simple à expliquer prend O (N ^ {5}) (pour une version qui régénère digraphos ) et O (N ^ {4}) for (pour une version qui garde le digraphos ). Ceci est similaire aux deux implémentations différentes de l'algorithme Edmonds-Karp .

Pour cette description, je travaille uniquement avec des graphiques bipartites complets (ceux où la moitié des nœuds font partie de la bipartition et l'autre moitié dans la seconde partie). Chez le travailleur, la motivation des tâches signifie qu'il y a autant de travailleurs que de tâches.

Cela semble être une condition importante (et si ces ensembles ne sont pas égaux?), Mais ce problème est facile à résoudre; Je parle de la façon de le faire dans la dernière section.

La version de l'algorithme décrite ici utilise le concept utile de arcs de poids zéro . Malheureusement, ce concept n'a de sens que lorsque nous résolvons un minimisation (Si, au lieu de maximiser les avantages de nos affectations de tâches, nous minimisons plutôt le coût de ces affectations).

qu'est-ce qu'un architecte de solutions certifié aws

Heureusement, il est facile de convertir un problème d'affectation linéaire maximum en un problème d'affectation linéaire minimal établissant chacun des poids de arc a dans M-a.datum.weight où M=max({a.datum.weight for a in G.setOfArcs}). La solution au problème de maximisation l'original sera identique à la solution minimiser le problème après le changement des poids d'Arc . Donc pour le reste, supposons que nous fassions ce changement.

La Algorithme de Kuhn-Munkres résoudre poids minimum dans un graphique bi-partitionné pondéré par une séquence de matchs maximum dans les graphiques non pondéré bipartite. Si on en trouve un match parfait dans la représentation du digraphe du problème d'affectation linéaire et si le poids de chacun arc dans la coïncidence est zéro, nous avons donc trouvé le poids minimum poids puisque cette coïncidence suggère que tout nœuds dans le digraphos ils ont été joint pour un arc avec le coût le plus bas possible (aucun coût ne peut être inférieur à 0, selon les définitions précédentes).

Aucun autre arcs peut être ajouté au coïncidence (Puisque toutes nœuds sont déjà jumelés) et non arcs doit être retiré du coïncident car tout remplacement possible arc aura au moins une valeur pondérale aussi élevée.

Si nous trouvons un correspondance maximale du subgrafo de G contenant seulement arcs de poids zéro , et ce n'est pas un match parfait , nous n'avons pas de solution complète (puisque la combinaison ce n'est pas parfaite ). Cependant, nous pouvons produire un nouveau digrafo H changer les poids de arcs dans G.setOfArcs pour que le nouveau poids 0 apparaisse arcs et la solution optimale de 'H' est la même que la solution optimale de 'G'. Puisque nous garantissons qu'au moins un arc poids zéro se produit à chaque itération, nous garantissons que nous atteindrons un match parfait en pas plus de | G.setOfNodes | 2 = N 2 dans de telles itérations.

Supposons que dans le bipartition bipartition, bipartition.firstPart contient nœuds représentant les travailleurs, et bipartition.secondPart Cela représente nœuds qui en même temps représente une preuve.

L'algorithme commence par générer un nouveau digrafo H. H.setOfNodes = G.setOfNodes. Certains arcs dans H ils sont nœuds n généré dans bipartition.firstPart. Chaque nœud n génère un arc b dans H.setOfArcs pour chaque arc a dans bipartition.G.setOfArcs où a.fromNode = n ou a.toNode = n, b=Arc(a.fromNode, a.toNode, a.datum.weight - z) où z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )).

Plus arcs dans H sont générés par nœuds n dans bipartition.secondPart. Chacun de ces nœuds n génère un arc b dans H.setOfArcs pour chaque arc a dans bipartition.G.setOfArcs où a.fromNode = n ou a.toNode = n, b=Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) où z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )).

KMA: Puis formez un nouveau digrafo K composé uniquement du arcs de poids zéro de H, et le nœuds incident dans ces arcs . Formez un bipartition dans les nœuds dans K, puis utilisez solve_mbm( bipartition ) Pour en avoir un combinaison maximale (matching) dans K. Si matching c'est une combinaison parfaite dans H (Les arcs dans matching ils sont incident dans tous les nœuds dans H.setOfNodes) puis matching est une solution optimale pour problème d'affectation linéaire .

Sinon, si matching ce n'est pas parfait , génère le couverture minimale des nœuds de K en utilisant node_cover = get_min_node_cover(matching, bipartition(K)). Définissez ensuite z=min({a.datum.weight for a in H.setOfArcs if a not in node_cover}). Définissez nodes = H.setOfNodes, arcs1 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh-z)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) and (a.toNode not in node_cover)}, arcs2 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) != (a.toNode not in node_cover)}, arcs3 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh+z)) for a in H.setOfArcs if ( (a.fromNode in node_cover) and (a.toNode in node_cover)}. Le != le symbole dans l'expression ci-dessus agit comme un opérateur XOR . Puis arcs = arcs1.union(arcs2.union(arcs3)). Puis H=DiGraph(nodes,arcs). Revenir à la marque KMA . L'algorithme continue jusqu'à ce qu'un combinaison parfaite . Est combinaison est aussi la solution pour problème d'affectation linéaire .

Cette implémentation est O(N^{5}) car il génère un nouveau combinaison maximale matching à chaque itération; similaire aux deux implémentations précédentes de Edmonds-Karp Cet algorithme peut être modifié pour suivre le match et l'adapter intelligemment à chaque itération. Lorsque cela est fait, la complexité devient O(N^{4}). Une version plus avancée et plus récente de cet algorithme (nécessitant des structures de données plus avancées) peut être exécutée sur O (N ^ {3}). Les détails de l'implémentation plus simple ci-dessus et de l'implémentation plus avancée peuvent être trouvés sur ce post qui a motivé ce blog.

Aucune des opérations sur les poids du arc modifie l'affectation finale renvoyée par l'algorithme. Par conséquent: puisque nos graphiques d'entrée sont toujours graphiques bi-partitionnés complets , une solution doit attribuer à chaque nœud d'une partition à l'autre nœud dans la deuxième partition, à travers le arc entre ces deux nœuds . Notez que les opérations effectuées sur les poids de arc ne changez jamais l'ordre (trié par poids) des arcs incidents à aucun nœud particulier .

Par conséquent, lorsque l'algorithme se termine par un bi-partition parfaite et complète , chaque nœud se voit attribuer un poids d'arc nul , puisque l'ordre relatif des arcs de quoi nœud n'a pas changé pendant l'algorithme et depuis un arc poids zéro c'est l'arc le moins cher possible et le complément bipartite complet parfait garantit qu'il y a un arc pour chaque nœud . Cela signifie que la solution générée est en fait la même que la solution du problème cartographie linéaire d'origine sans aucune modification des poids de arc .

Allocations déséquilibrées

Il semble que l'algorithme soit assez limité, car comme décrit, il n'opère que sur graphiques bipartites complets (ceux où la moitié des nœuds font partie de la bipartition et l'autre moitié dans la seconde partie). Chez l'ouvrier, la motivation des tâches signifie qu'il y a autant d'ouvriers qu'il y a de tâches (cela semble assez limitant).

Cependant, il existe une transformation simple qui supprime cette restriction. Supposons qu'il y ait moins de travailleurs que de tâches, nous ajoutons des travailleurs fictifs (assez pour faire du graphique résultant un graphique bipartite complet ). Chaque travailleur fictif a un arc dirigé par le travailleur vers chacune des tâches. Chacun de ces arc a un poids 0 (le placer dans un match ne donne aucun avantage supplémentaire). Après ce changement, le graphique est un graphique bipartite complet que nous pouvons résoudre. Aucune tâche assignée à un travailleur fictif n'est démarrée.

Supposons qu'il y ait plus de tâches que de travailleurs. Nous avons ajouté quelques tâches factices (assez pour faire du graphique résultant un graphe bi-partitionné complet ). Chaque tâche fictive a un arc dirigé de chaque travailleur vers la tâche fictive. Chacun de ces arc il a un poids de 0 (le placer dans un match ne donne aucun avantage supplémentaire). Après ce changement, le graphique est un graphe bi-partitionné complet que nous pouvons résoudre. Tout travailleur affecté à la tâche fictive n'est pas employé pendant la période.

Exemple d'affectation linéaire

Enfin, nous allons faire un exemple avec le code que j'ai utilisé. Je vais modifier l'exemple de problème de ici . Nous avons 3 tâches: nous avons besoin nettoyer la salle de bain , balayer le sol , Y nettoyer les vitres .

Les travailleurs disponibles sont Alice , Bob , Charlie Oui Diane . Chacun des travailleurs nous donne le salaire dont il a besoin par tâche. Voici les salaires par travailleur:

Si nous voulons payer le moins d'argent possible tout en réalisant toutes les tâches, qui devrait faire quelle tâche? Commencez par entrer une tâche factice pour le digraphe qui représente le problème bipartite.

En supposant que le problème est codé dans un digrafo , alors kuhn_munkres( bipartition(G) ) résoudra le problème et retournera la mission. Il est facile de vérifier que l'allocation optimale (coût le plus bas) coûtera 5 $.

Voici une visualisation de la solution que le code ci-dessus génère:

C'est tout . Vous savez maintenant tout ce que vous devez savoir sur le problème d'affectation linéaire.

Vous pouvez trouver tout le code de cet article sur GitHub .