Μέγιστη ροή και πρόβλημα γραμμικής ανάθεσης

ΕΝΑ μέγιστος συνδυασμός matching είναι ένα τέλειος συνδυασμός ναι για καθένα κόμβος n σε G.setOfArcs υπάρχει τόξο a σε matching όπου a.fromNode == n or a.toNode == n.

Μέγιστος συνδυασμός δύο διαμερισμάτων

ΕΝΑ μέγιστος συνδυασμός δύο διαμερισμάτων είναι ένα μέγιστος συνδυασμός σε ένα digrafo G Τι είναι αυτό διμερισμένο .

Από G είναι διμερισμένο , το πρόβλημα εύρεσης α διμερής μέγιστος συνδυασμός μπορεί να μετατραπεί σε α πρόβλημα αιχμής ροής επιλύσιμο με αλγόριθμο από τον Edmonds-Karp και μετά το μέγιστη σύνδεση δύο μερών μπορεί να ανακτηθεί από το διάλυμα στο πρόβλημα αιχμής ροής .

Αφήστε bipartition γίνε α διμερές από G.

Για αυτό, πρέπει να δημιουργήσω ένα νέο digrafo (H) με κάποια νέα κόμβοι (H.setOfNodes) και μερικά τόξα νέο (H.setOfArcs). H.setOfNodes περιέχει όλα κόμβοι σε G.setOfNodes και δύο κόμβοι περισσότερα, s (ένα κόμβος προέλευσης ) και t (ένα τερματικός κόμβος ).

H.setOfArcs θα περιέχει ένα τόξο για κάθε G.setOfArcs. Αν ένα τόξο a είναι ένα G.setOfArcs και a.fromNode είναι σε bipartition.firstPart και a.toNode είναι σε bipartition.secondPart και στη συνέχεια περιλαμβάνει a σε H (προσθήκη a FlowArcDatum(1,0)).

Εάν a.fromNode είναι ένα bipartition.secondPart και a.toNode είναι ένα bipartition.firstPart, τότε συμπεριλάβετε Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) σε H.setOfArcs.

Ορισμός γραφήματος διμερισμένο διασφαλίζει ότι όχι τόξο συνδέστε οποιοδήποτε κόμβος όπου και τα δύο κόμβοι βρίσκονται στο ίδιο διαμέρισμα. H.setOfArcs περιέχει επίσης ένα τόξο από κόμβος s στον καθένα κόμβος σε bipartition.firstPart. Τέλος, H.setOfArcs περιέχει ένα τόξο καθε κόμβος σε bipartition.secondPart ένα κόμβος t. a.datum.capacity = 1 για όλους a σε H.setOfArcs.

Πρώτο διαμέρισμα του κόμβοι σε G.setOfNodes τα δύο σύνολα (part1 και part2) σε διασταση τόσο πολύ που όχι τόξο σε G.setOfArcs πηγαίνει από ένα σετ στο ίδιο σετ (αυτό το διαμέρισμα είναι δυνατό επειδή G είναι διμερισμένο ). Στη συνέχεια, προσθέστε όλα τα τόξα σε G.setOfArcs που κατευθύνονται από το part1 στο part2 προς H.setOfArcs. Στη συνέχεια, δημιουργήστε έναν μόνο κόμβο πηγή s και έναν μόνο κόμβο τερματικό t και δημιουργήστε περισσότερα τόξα

Στη συνέχεια, δημιουργήστε ένα maxFlowProblemState.

Ελάχιστο κάλυμμα κόμβου

Ένα κάλυμμα κόμβου σε ένα δίφθογγος G Είναι ένα σύνολο κόμβοι (cover) από G.setOfNodes τόσο πολύ για οποιοδήποτε τόξο a από G.setOfArcs Αυτό πρέπει να ισχύει: (a.fromNode en cubierta) o (a.toNode en cubierta).

Ένα ελάχιστο κάλυμμα κόμβου είναι το μικρότερο σύνολο κόμβοι στο γράφημα που είναι ακόμα α κάλυμμα κόμβου . Το θεώρημα του König το δείχνει σε ένα γράφημα διμερισμένο , το μέγεθος του μέγιστο ταίριασμα σε αυτό το γράφημα είναι ίσο με το μέγεθος του ελάχιστο κάλυμμα κόμβου , και προτείνει πώς μπορεί να ανακτηθεί το κάλυμμα κόμβου από ένα μέγιστο ταίριασμα :

Ας υποθέσουμε ότι έχουμε το διμερές bipartition και το μέγιστο ταίριασμα matching. Ορίστε ένα νέο digrafo H, H.setOfNodes=G.setOfNodes, το τόξα σε H.setOfArcs είναι η ένωση δύο σετ.

Το πρώτο σετ των τόξα a σε matching, με την αλλαγή που εάν a.fromNode in bipartition.firstPart και a.toNode en bipartition.secondPart τότε a.fromNode και a.toNode ανταλλάσσονται στο δημιουργήθηκε acro δίνουν τέτοια τόξα ένα χαρακτηριστικό a.datum.inMatching = True για να δείξει ότι προήλθαν από τόξα σε ένα σύμπτωση .

Το δεύτερο σετ είναι τόξα a ΟΧΙ στο matching, με την αλλαγή που εάν a.fromNode en bipartition.secondPart και a.toNode en bipartition.firstPart τότε a.fromNode και a.toNode ανταλλάσσονται στο τόξο δημιουργήθηκε (δίνει τέτοια τόξο ένα χαρακτηριστικό a.datum.inMatching = False).

Στη συνέχεια, εκτελέστε ένα αναζήτηση πρώτου βάθους ( DFS ) από το καθένα κόμβος n σε bipartition.firstPart που δεν είναι n == a.fromNode ούτε n == a.toNodes Για κάθε τόξο a σε matching. Κατά τη διάρκεια του DFS, μερικοί κόμβοι επισκέπτονται και άλλοι δεν είναι (αποθηκεύστε αυτές τις πληροφορίες σε πεδίο n.datum.visited). ο ελάχιστο κάλυμμα κόμβου είναι η ένωση του κόμβοι {a.fromNode para a en H.setOfArcs si ((a.datum.inMatching) y (a.fromNode.datum.visited))} και κόμβοι {a.fromNode para a en H.setOfArcs si (a.datum.inMatching) y (no a.toNode.datum.visited)}.

Αυτό μπορεί να αποδειχθεί ότι οδηγεί από ένα μέγιστο ταίριασμα σε ένα ελάχιστο κάλυμμα κόμβου από ένα απόδειξη με αντίφαση , πάρτε ένα τόξο a η οποία υποτίθεται ότι δεν καλύπτεται και εξετάζει και τις τέσσερις περιπτώσεις σχετικά με το εάν a.fromNode και a.toNode ανήκουν (είτε ως toNode ή fromNode) σε οποιοδήποτε τόξο σε σύμπτωση matching. Κάθε περίπτωση οδηγεί σε αντίφαση λόγω της σειράς με την οποία επισκέπτεται το DFS κόμβοι και το γεγονός ότι matching είναι ένα μέγιστη αντιστοίχιση .

Ας υποθέσουμε ότι έχουμε μια συνάρτηση για την εκτέλεση αυτών των βημάτων και την επιστροφή του συνόλου κόμβοι που περιλαμβάνει το ελάχιστο κάλυμμα κόμβου όταν του δίνεται digrafo G, και το μέγιστο ταίριασμα matching:

Το πρόβλημα γραμμικής ανάθεσης

Το πρόβλημα γραμμικής ανάθεσης συνίσταται στην εύρεση μιας μέγιστης σύμπτωσης βαρών σε ένα σταθμισμένο διμερές γράφημα.

Προβλήματα όπως αυτό που εμφανίζεται στην αρχή αυτής της ανάρτησης μπορούν να εκφραστούν ως πρόβλημα γραμμική ανάθεση . Λαμβάνοντας υπόψη ένα σύνολο εργαζομένων, ένα σύνολο εργασιών και μια συνάρτηση που δείχνει την κερδοφορία μιας ανάθεσης ενός εργαζομένου σε μια εργασία, θέλουμε να μεγιστοποιήσουμε το άθροισμα όλων των εργασιών που κάνουμε. αυτό είναι ένα πρόβλημα γραμμικής ανάθεσης .

Ας υποθέσουμε ότι ο αριθμός των εργασιών και των εργαζομένων είναι ίσος, αν και θα δείξω ότι αυτή η υπόθεση είναι εύκολο να αφαιρεθεί. Κατά την εφαρμογή, εκπροσωπώ βάρη τόξου με ένα χαρακτηριστικό a.datum.weight για ένα τόξο a.

Αλγόριθμος Kuhn-Munkres

Ο αλγόριθμος Kuhn-Munkres λύνει το πρόβλημα γραμμικής ανάθεσης . Μια καλή εφαρμογή μπορεί να διαρκέσει χρόνο O(N^{4}), (όπου N είναι ο αριθμός των κόμβοι στο digrafo αντιπροσωπεύει το πρόβλημα). Μια εφαρμογή που είναι πιο εύκολο να εξηγηθεί χρειάζεται O (N ^ {5}) (για μια έκδοση που αναγεννάται διάγραμμα ) και O (N ^ {4}) για (για μια έκδοση που διατηρεί το διάγραμμα ). Αυτό είναι παρόμοιο με τις δύο διαφορετικές υλοποιήσεις του αλγορίθμου Έντμοντς-Καρπ .

Για αυτήν την περιγραφή, δουλεύω μόνο με πλήρη διμερή γραφικά (εκείνα όπου το ήμισυ του κόμβοι βρίσκονται σε ένα μέρος του διμερές και το άλλο μισό στο δεύτερο μέρος). Στον εργαζόμενο, το κίνητρο εργασίας σημαίνει ότι υπάρχουν τόσοι εργαζόμενοι όσο και καθήκοντα.

Αυτό φαίνεται σαν μια σημαντική κατάσταση (τι γίνεται αν αυτά τα σύνολα δεν είναι ίδια;), αλλά είναι εύκολο να διορθώσετε αυτό το πρόβλημα. Μιλώ για το πώς να το κάνω στην τελευταία ενότητα.

Η έκδοση του αλγορίθμου που περιγράφεται εδώ χρησιμοποιεί τη χρήσιμη ιδέα του μηδέν βάρος τόξα . Δυστυχώς, αυτή η έννοια έχει νόημα μόνο όταν λύνουμε ένα σμικροποίηση (Αν αντί να μεγιστοποιήσουμε τα οφέλη των εργασιών εργαζομένων μας, ελαχιστοποιούμε το κόστος αυτών των εργασιών).

η διαπραγματευτική δύναμη των αγοραστών

Ευτυχώς, είναι εύκολο να μετατρέψετε ένα μέγιστο πρόβλημα γραμμικής ανάθεσης σε ένα ελάχιστο πρόβλημα γραμμικής ανάθεσης καθιέρωση καθενός από τα βάρη του τόξο a σε M-a.datum.weight όπου M=max({a.datum.weight for a in G.setOfArcs}). Η λύση στο πρόβλημα μεγιστοποίησης Το πρωτότυπο θα είναι ίδιο με τη λύση ελαχιστοποιώντας το πρόβλημα μετά την αλλαγή των βαρών του Arc . Έτσι, για τα υπόλοιπα, ας υποθέσουμε ότι κάνουμε αυτήν την αλλαγή.

ο Αλγόριθμος Kuhn-Munkres λύσει ελάχιστο βάρος βάρους σε ένα σταθμισμένο διάγραμμα δύο διαμερισμάτων με μια ακολουθία του μέγιστες αντιστοιχίες σε γραφικά χωρίς βάρος διμερής. Αν βρούμε ένα τέλειο ταίρι στο αναπαράσταση του διαγράμματος του προβλήματος γραμμικής ανάθεσης και εάν το βάρος του καθενός τόξο στο σύμπτωση είναι μηδέν, οπότε βρήκαμε το ελάχιστο βάρος βάρους αφού αυτή η σύμπτωση υποδηλώνει ότι όλα κόμβοι στο διάγραμμα υπήρξαν ζευγαρωμένος Για τόξο με το χαμηλότερο δυνατό κόστος (κανένα κόστος δεν μπορεί να είναι μικρότερο από 0, βάσει προηγούμενων ορισμών).

Καμία άλλη τόξα μπορεί να προστεθεί στο σύμπτωση (Από όλα κόμβοι έχουν ήδη αντιστοιχιστεί) και όχι τόξα πρέπει να αφαιρεθεί από το συμπίπτων γιατί οποιαδήποτε πιθανή αντικατάσταση τόξο θα έχει τουλάχιστον τόσο μεγάλη αξία βάρους.

Αν βρούμε ένα μέγιστο ταίριασμα απο subgrafo από G περιέχει μόνο μηδέν βάρος τόξα , και δεν είναι τέλειο ταίρι , δεν έχουμε πλήρη λύση (από τότε ο συνδυασμός Δεν είναι τέλειος ). Ωστόσο, μπορούμε να παράγουμε ένα νέο digrafo H αλλάζοντας τα βάρη του τόξα σε G.setOfArcs έτσι ώστε να εμφανιστεί νέο 0-βάρος τόξα και η βέλτιστη λύση του 'Η' είναι η ίδια με τη βέλτιστη λύση του 'G'. Δεδομένου ότι εγγυόμαστε ότι τουλάχιστον ένα μηδενικό βάρος τόξο συμβαίνει σε κάθε επανάληψη, εγγυόμαστε ότι θα φτάσουμε σε ένα τέλειο ταίρι σε όχι περισσότερο από | G.setOfNodes | 2 = N 2 σε τέτοιες επαναλήψεις.

Ας υποθέσουμε ότι στο διμερές bipartition, bipartition.firstPart περιέχει κόμβοι που εκπροσωπούν τους εργαζομένους και bipartition.secondPart Αντιπροσωπεύει κόμβοι που ταυτόχρονα αντιπροσωπεύει αποδεικτικά στοιχεία.

Ο αλγόριθμος ξεκινά δημιουργώντας ένα νέο digrafo H. H.setOfNodes = G.setOfNodes. Μερικοί τόξα σε H Αυτοί είναι κόμβοι n δημιουργήθηκε σε bipartition.firstPart. Καθε κόμβος n παράγει ένα τόξο b σε H.setOfArcs Για κάθε τόξο a σε bipartition.G.setOfArcs όπου a.fromNode = n ή a.toNode = n, b=Arc(a.fromNode, a.toNode, a.datum.weight - z) όπου z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )).

Συν τόξα σε H δημιουργούνται από κόμβοι n σε bipartition.secondPart. Κάθε ένα από αυτά κόμβοι n παράγει ένα τόξο b σε H.setOfArcs Για κάθε τόξο a σε bipartition.G.setOfArcs όπου a.fromNode = n ή a.toNode = n, b=Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) όπου z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )).

KMA: Στη συνέχεια, σχηματίστε ένα νέο digrafo K αποτελείται μόνο από το μηδέν βάρος τόξα του H, και του κόμβοι περιστατικό σε αυτούς τόξα . Έντυπο a bipartition στο κόμβοι στο K, στη συνέχεια χρησιμοποιήστε solve_mbm( bipartition ) Για να πάρετε ένα μέγιστος συνδυασμός (matching) σε K. Εάν matching είναι ένα τέλειος συνδυασμός σε H (ο τόξα σε matching Αυτοί είναι περιστατικό σε όλα τα κόμβοι σε H.setOfNodes) μετά matching είναι η βέλτιστη λύση για πρόβλημα γραμμικής ανάθεσης .

Διαφορετικά, εάν matching Δεν είναι τέλειος , δημιουργεί το ελάχιστο κάλυμμα κόμβου από K χρησιμοποιώντας node_cover = get_min_node_cover(matching, bipartition(K)). Στη συνέχεια ορίστε z=min({a.datum.weight for a in H.setOfArcs if a not in node_cover}). Ορίστε 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)}. Το != σύμβολο στην παραπάνω έκφραση ενεργεί ως χειριστής XOR . Τότε arcs = arcs1.union(arcs2.union(arcs3)). Τότε H=DiGraph(nodes,arcs). Επιστροφή στην επωνυμία ΚΜΑ . Ο αλγόριθμος συνεχίζεται έως το a τέλειος συνδυασμός . Είναι συνδυασμός είναι επίσης η λύση για πρόβλημα γραμμικής ανάθεσης .

Αυτή η εφαρμογή είναι O(N^{5}) γιατί δημιουργεί ένα νέο μέγιστος συνδυασμός matching σε κάθε επανάληψη · παρόμοια με τις προηγούμενες δύο υλοποιήσεις του Έντμοντς-Καρπ Αυτός ο αλγόριθμος μπορεί να τροποποιηθεί για να παρακολουθεί τον αγώνα και να τον προσαρμόζει έξυπνα σε κάθε επανάληψη. Όταν γίνει αυτό, η πολυπλοκότητα γίνεται O(N^{4}). Μια πιο προηγμένη και νεότερη έκδοση αυτού του αλγορίθμου (που απαιτεί κάποιες πιο προηγμένες δομές δεδομένων) μπορεί να εκτελεστεί στο O (N ^ {3}). Λεπτομέρειες σχετικά με την απλούστερη εφαρμογή παραπάνω και την πιο προηγμένη εφαρμογή μπορείτε να βρείτε στη διεύθυνση αυτήν την ανάρτηση που παρακίνησε αυτό το ιστολόγιο.

Καμία από τις εργασίες στα βάρη του τόξο τροποποιεί την τελική ανάθεση που επιστρέφεται από τον αλγόριθμο. Επομένως: Δεδομένου ότι τα γραφήματα εισόδου μας είναι πάντα πλήρη γραφικά δύο διαμερισμάτων , μια λύση πρέπει να αντιστοιχεί σε κάθε κόμβος σε ένα διαμέρισμα στο άλλο κόμβος στο δεύτερο διαμέρισμα, μέσω του τόξο μεταξύ αυτών των δύο κόμβοι . Σημειώστε ότι οι εργασίες που εκτελούνται στα βάρη του τόξο Ποτέ μην αλλάζετε τη σειρά (κατά παραγγελία κατά βάρος) του τόξα συμβάντα χωρίς κόμβο ιδιαιτερος .

Επομένως, όταν ο αλγόριθμος τελειώνει σε ένα τέλειο και πλήρες ταίριασμα bi-partition , καθε κόμβος έχει ανατεθεί ένα μηδενικό τόξο , δεδομένου ότι η σχετική σειρά του τόξα από τι κόμβος δεν έχει αλλάξει κατά τη διάρκεια του αλγορίθμου και από το α μηδενικό βάρος τόξο είναι το τόξο φθηνότερη δυνατή και το τέλειο πλήρες διμερές συμπλήρωμα εγγυάται ότι υπάρχει τόξο για κάθε κόμβος . Αυτό σημαίνει ότι η παραγόμενη λύση είναι στην πραγματικότητα η ίδια με την προβληματική λύση αρχική γραμμική χαρτογράφηση χωρίς καμία τροποποίηση των βαρών του τόξο .

Μη ισορροπημένες κατανομές

Φαίνεται ότι ο αλγόριθμος είναι αρκετά περιορισμένος, καθώς όπως περιγράφεται, λειτουργεί μόνο σε πλήρη διμερή γραφικά (εκείνοι όπου το ήμισυ του κόμβοι βρίσκονται σε ένα μέρος του διμερές και το άλλο μισό στο δεύτερο μέρος). Στον εργαζόμενο, το κίνητρο της εργασίας σημαίνει ότι υπάρχουν τόσοι εργαζόμενοι όσο και καθήκοντα (φαίνεται αρκετά περιοριστικό).

Ωστόσο, υπάρχει ένας εύκολος μετασχηματισμός που καταργεί αυτόν τον περιορισμό. Ας υποθέσουμε ότι υπάρχουν λιγότεροι εργαζόμενοι από τα καθήκοντα, προσθέτουμε μερικούς πλαστά εργαζομένους (αρκετά για να δημιουργήσουμε το γράφημα που προκύπτει α πλήρες διμερές γραφικό ). Κάθε πλασματικός εργαζόμενος έχει τόξο κατευθύνεται από τον εργαζόμενο σε κάθε ένα από τα καθήκοντα. Κάθε ένα από αυτά τόξο έχει βάρος 0 (η τοποθέτηση σε αγώνα δεν δίνει κανένα πρόσθετο όφελος). Μετά από αυτήν την αλλαγή, το γράφημα είναι ένα πλήρες διμερές γραφικό που μπορούμε να λύσουμε. Δεν ξεκινά καμία εργασία που έχει ανατεθεί σε έναν πλασματικό εργαζόμενο.

Ας υποθέσουμε ότι υπάρχουν περισσότερες εργασίες από τους εργαζόμενους. Προσθέσαμε μερικές πλαστές εργασίες (αρκετά για να δημιουργήσουμε το γράφημα που προκύπτει α πλήρες γράφημα δύο διαμερισμάτων ). Κάθε φανταστική εργασία έχει ένα τόξο κατευθύνεται από κάθε εργαζόμενο στο φανταστικό έργο. Κάθε ένα από αυτά τόξο έχει βάρος 0 (η τοποθέτηση σε αγώνα δεν δίνει κανένα πρόσθετο όφελος). Μετά από αυτήν την αλλαγή, το γράφημα είναι ένα πλήρες γράφημα δύο διαμερισμάτων που μπορούμε να λύσουμε. Κάθε εργαζόμενος που έχει ανατεθεί στην πλασματική εργασία δεν απασχολείται κατά τη διάρκεια της περιόδου.

Παράδειγμα γραμμικής ανάθεσης

Τέλος, θα κάνουμε ένα παράδειγμα με τον κωδικό που έχω χρησιμοποιήσει. Θα τροποποιήσω το παράδειγμα του προβλήματος από εδώ . Έχουμε 3 εργασίες: χρειαζόμαστε για να καθαρίσετε το μπάνιο , σκουπίζω το πάτωμα Γ καθάρισε τα παράθυρα .

Οι διαθέσιμοι εργαζόμενοι είναι Αλίκη , Βαρίδι , Κάρολος Υ Ντιάν . Κάθε ένας από τους εργαζόμενους μας δίνει τον μισθό που απαιτείται ανά εργασία. Εδώ είναι οι μισθοί ανά εργαζόμενο:

Εάν θέλουμε να πληρώσουμε το ελάχιστο χρηματικό ποσό, αλλά ακόμα να ολοκληρώσουμε όλες τις εργασίες, ποιος πρέπει να κάνει τι έργο; Ξεκινήστε εισάγοντας μια πλαστή εργασία για το διάγραμμα που αντιπροσωπεύει το διμερές πρόβλημα.

Υποθέτοντας ότι το πρόβλημα κωδικοποιείται σε ένα digrafo , τότε kuhn_munkres( bipartition(G) ) θα λύσει το πρόβλημα και θα επιστρέψει την ανάθεση. Είναι εύκολο να επαληθευτεί ότι η βέλτιστη κατανομή (χαμηλότερο κόστος) θα κοστίσει 5 $.

Ακολουθεί μια οπτικοποίηση της λύσης που δημιουργεί ο παραπάνω κώδικας:

Αυτό είναι όλο . Τώρα γνωρίζετε όλα όσα πρέπει να γνωρίζετε για το πρόβλημα γραμμικής ανάθεσης.

Μπορείτε να βρείτε όλο τον κωδικό για αυτό το άρθρο στη διεύθυνση GitHub .