Ακολουθεί ένα πρόβλημα: Η επιχείρησή σας αναθέτει στους εργολάβους να εκπληρώσουν συμβάσεις. Κοιτάζετε μέσα από τα ρόστερ σας και αποφασίζετε ποιοι εργολάβοι είναι διαθέσιμοι για δέσμευση ενός μηνός και κοιτάζετε τις διαθέσιμες συμβάσεις σας για να δείτε ποιοι από αυτούς είναι για εργασίες ενός μήνα. Δεδομένου ότι γνωρίζετε πόσο αποτελεσματικά μπορεί κάθε εργολήπτης να εκπληρώσει κάθε σύμβαση, πώς αναθέτετε στους εργολάβους να μεγιστοποιήσετε τη συνολική αποτελεσματικότητα για αυτόν τον μήνα;
Αυτό είναι ένα παράδειγμα του προβλήματος ανάθεσης και το πρόβλημα μπορεί να λυθεί με το κλασικό Ουγγρικός αλγόριθμος .
Ο ουγγρικός αλγόριθμος (επίσης γνωστός ως αλγόριθμος Kuhn-Munkres) είναι ένας πολυώνυμος αλγόριθμος χρόνου που μεγιστοποιεί την αντιστοίχιση βάρους σε ένα σταθμισμένο διμερές γράφημα. Εδώ, οι εργολάβοι και τα συμβόλαια μπορούν να μοντελοποιηθούν ως ένα διμερές γράφημα, με την αποτελεσματικότητά τους ως βάρη των άκρων μεταξύ του εργολάβου και των κόμβων των συμβάσεων.
Σε αυτό το άρθρο, θα μάθετε για την εφαρμογή του ουγγρικού αλγορίθμου που χρησιμοποιεί το Αλγόριθμος Edmonds-Karp για να λύσει το πρόβλημα γραμμικής ανάθεσης. Θα μάθετε επίσης πώς ο αλγόριθμος Edmonds-Karp είναι μια μικρή τροποποίηση του Ford-Φούλκερσον μέθοδος και πώς αυτή η τροποποίηση είναι σημαντική.
Το πρόβλημα της μέγιστης ροής
Το ίδιο το πρόβλημα της μέγιστης ροής μπορεί να περιγραφεί ανεπίσημα ως το πρόβλημα της μεταφοράς κάποιου ρευστού ή αερίου μέσω ενός δικτύου σωλήνων από μία μόνο πηγή σε ένα μόνο τερματικό. Αυτό γίνεται με την παραδοχή ότι η πίεση στο δίκτυο είναι επαρκής για να διασφαλιστεί ότι το υγρό ή το αέριο δεν μπορούν να παραμείνουν σε οποιοδήποτε μήκος σωληνώσεων ή σωληνώσεων (εκείνα τα μέρη όπου συναντώνται διαφορετικά μήκη σωλήνων).
Κάνοντας ορισμένες αλλαγές στο γράφημα, το πρόβλημα ανάθεσης μπορεί να μετατραπεί σε πρόβλημα μέγιστης ροής.
Προκριματικά
Οι ιδέες που απαιτούνται για την επίλυση αυτών των προβλημάτων προκύπτουν σε πολλούς μαθηματικούς και μηχανολογικούς κλάδους, συχνά παρόμοιες έννοιες είναι γνωστές με διαφορετικά ονόματα και εκφράζονται με διαφορετικούς τρόπους (π.χ. πίνακες παρακέντησης και λίστες γειτνίασης). Δεδομένου ότι αυτές οι ιδέες είναι αρκετά εσωτερικές, γίνονται επιλογές σχετικά με το πώς γενικά αυτές οι έννοιες θα καθοριστούν για οποιοδήποτε δεδομένο περιβάλλον.
Αυτό το άρθρο δεν θα έχει καμία προηγούμενη γνώση πέρα από μια μικρή εισαγωγική θεωρία.
Οι υλοποιήσεις σε αυτήν την ανάρτηση αντιπροσωπεύουν τα προβλήματα ως κατευθυνόμενα γραφήματα (διάγραμμα).
DiGraphs
ΠΡΟΣ ΤΟ δίφθογγος έχει δύο γνωρίσματα , setOfNodes και setOfArcs . Και τα δύο αυτά χαρακτηριστικά είναι σκηνικά (μη ταξινομημένες συλλογές). Στα μπλοκ κώδικα σε αυτήν την ανάρτηση, χρησιμοποιώ πραγματικά το Python's frozenset , αλλά αυτή η λεπτομέρεια δεν είναι ιδιαίτερα σημαντική.
DiGraph = namedtuple('DiGraph', ['setOfNodes','setOfArcs']) (Σημείωση: Αυτός, και όλοι οι άλλοι κωδικοί σε αυτό το άρθρο, είναι γραμμένοι στο Python 3.6.)
Κόμβοι
ΠΡΟΣ ΤΟ κόμβος n αποτελείται από δύο χαρακτηριστικά:
-
n.uid: Α μοναδική ταυτότητα .
Αυτό σημαίνει ότι για δύο κόμβους
xκαιy,
x.uid != y.uid n.datum: Αυτό αντιπροσωπεύει οποιοδήποτε αντικείμενο δεδομένων.
Node = namedtuple('Node', ['uid','datum']) Τόξα
Ενα τόξο a αποτελείται από τρία χαρακτηριστικά:
-
a.fromNode: Αυτό είναι ένα κόμβος , όπως ορίζεται παραπάνω. -
a.toNode: Αυτό είναι ένα κόμβος , όπως ορίζεται παραπάνω. -
a.datum: Αυτό αντιπροσωπεύει οποιοδήποτε αντικείμενο δεδομένων.
Arc = namedtuple('Arc', ['fromNode','toNode','datum']) Το σύνολο των τόξα στο δίφθογγος αντιπροσωπεύει μια δυαδική σχέση στο κόμβοι στο δίφθογγος . Η ύπαρξη του τόξο a υπονοεί ότι υπάρχει σχέση μεταξύ a.fromNode και a.toNode.
Σε ένα κατευθυνόμενο γράφημα (σε αντίθεση με ένα μη κατευθυνόμενο γράφημα), η ύπαρξη σχέσης μεταξύ a.fromNode και a.toNode κάνει δεν υπονοεί ότι μια παρόμοια σχέση μεταξύ a.toNode και a.fromNode υπάρχει.
Αυτό συμβαίνει επειδή σε ένα μη κατευθυνόμενο γράφημα, η σχέση που εκφράζεται δεν είναι απαραίτητα συμμετρική.
DiGraphs
Κόμβοι και τόξα μπορεί να χρησιμοποιηθεί για να ορίσει a δίφθογγος , αλλά για ευκολία, στους παρακάτω αλγόριθμους, a δίφθογγος θα αναπαρασταθεί χρησιμοποιώντας ως λεξικό .
Ακολουθεί μια μέθοδος που μπορεί να μετατρέψει την αναπαράσταση γραφήματος παραπάνω σε αναπαράσταση λεξικού παρόμοια με αυτήν αυτό :
def digraph_to_dict(G): G_as_dict = dict([]) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) pdg(G) raise KeyError(err_msg) if(a.toNode not in G.setOfNodes): err_msg = 'There is no Node {a.toNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) pdg(G) raise KeyError(err_msg) G_as_dict[a.fromNode] = (G_as_dict[a.fromNode].union(frozenset([a]))) if (a.fromNode in G_as_dict) else frozenset([a]) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if a.toNode not in G_as_dict: G_as_dict[a.toNode] = frozenset([]) return G_as_dict Και εδώ είναι ένα άλλο που το μετατρέπει σε λεξικό λεξικών, μια άλλη λειτουργία που θα είναι χρήσιμη:
def digraph_to_double_dict(G): G_as_dict = dict([]) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if(a.toNode not in G.setOfNodes): err_msg = 'There is no Node {a.toNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if(a.fromNode not in G_as_dict): G_as_dict[a.fromNode] = dict({a.toNode : frozenset([a])}) else: if(a.toNode not in G_as_dict[a.fromNode]): G_as_dict[a.fromNode][a.toNode] = frozenset([a]) else: G_as_dict[a.fromNode][a.toNode] = G_as_dict[a.fromNode][a.toNode].union(frozenset([a])) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if a.toNode not in G_as_dict: G_as_dict[a.toNode] = dict({}) return G_as_dict Όταν το άρθρο μιλά για ένα δίφθογγος όπως αντιπροσωπεύεται από ένα λεξικό, θα αναφέρει G_as_dict να το αναφερθώ.
Μερικές φορές είναι χρήσιμο να φέρετε ένα κόμβος από ένα δίφθογγος G από αυτό μέσω του uid (μοναδικό αναγνωριστικό):
def find_node_by_uid(find_uid, G): nodes = {n for n in G.setOfNodes if n.uid == find_uid} if(len(nodes) != 1): err_msg = 'Node with uid {find_uid!s} is not unique.'.format(**locals()) raise KeyError(err_msg) return nodes.pop() Κατά τον καθορισμό γραφημάτων, οι άνθρωποι μερικές φορές χρησιμοποιούν τους όρους κόμβος και κορυφή για να αναφέρεται στην ίδια έννοια? το ίδιο ισχύει και για τους όρους τόξο και άκρη.
Δύο δημοφιλείς αναπαραστάσεις γραφημάτων στο Python είναι αυτό που χρησιμοποιεί λεξικά και αλλο που χρησιμοποιεί αντικείμενα για την αναπαράσταση γραφημάτων. Η αναπαράσταση σε αυτήν την ανάρτηση βρίσκεται κάπου ανάμεσα σε αυτές τις δύο κοινές παραστάσεις.
Αυτό είναι δικό μου δίφθογγος αναπαράσταση. Υπάρχουν πολλά όπως αυτό, αλλά αυτό είναι δικό μου.
Περίπατοι και μονοπάτια
Αφήστε S_Arcs να είσαι πεπερασμένος αλληλουχία (παραγγελία παραγγελίας) από τόξα σε ένα δίφθογγος G έτσι ώστε εάν a είναι οποιοδήποτε τόξο σε S_Arcs εκτός από το τελευταίο και b ακολουθεί a στη σειρά, τότε πρέπει να υπάρχει ένα κόμβος n = a.fromNode σε G.setOfNodes έτσι ώστε a.toNode = b.fromNode.
Ξεκινώντας από το πρώτο τόξο σε S_Arcs και συνεχίζεται μέχρι το τελευταίο τόξο σε S_Arcs, συλλέξτε (με τη σειρά που παρουσιάστηκε) όλα κόμβοι n όπως ορίζεται παραπάνω μεταξύ κάθε δύο διαδοχικών τόξα σε S_Arcs. Επισημάνετε την παραγγελθείσα συλλογή του κόμβοι συλλέχθηκε κατά τη διάρκεια αυτής της λειτουργίας S_{Nodes}.
def path_arcs_to_nodes(s_arcs): s_nodes = list([]) arc_it = iter(s_arcs) step_count = 0 last = None try: at_end = False last = a1 = next(arc_it) while (not at_end): s_nodes += [a1.fromNode] last = a2 = next(arc_it) step_count += 1 if(a1.toNode != a2.fromNode): err_msg = 'Error at index {step_count!s} of Arc sequence.'.format(**locals()) raise ValueError(err_msg) a1 = a2 except StopIteration as e: at_end = True if(last is not None): s_nodes += [last.toNode] return s_nodes -
Εάν υπάρχει κόμβος εμφανίζεται περισσότερες από μία φορές στην ακολουθία
S_Nodesστη συνέχεια καλέστεS_Arcsένα Περπατήστε επί δίφθογγοςG. -
Διαφορετικά, καλέστε
S_Arcsένα μονοπάτι απόlist(S_Nodes)[0]έωςlist(S_Nodes)[-1]επί δίφθογγοςG.
Κόμβος πηγής
Κλήση κόμβος s προς το κόμβος προέλευσης σε δίφθογγος G αν s είναι σε G.setOfNodes και G.setOfArcs περιέχει αριθ τόξο a έτσι ώστε a.toNode = s.
def source_nodes(G): to_nodes = frozenset({a.toNode for a in G.setOfArcs}) sources = G.setOfNodes.difference(to_nodes) return sources Τερματικός κόμβος
Κλήση κόμβος t προς το τερματικός κόμβος σε δίφθογγος G αν t είναι σε G.setOfNodes και G.setOfArcs περιέχει αριθ τόξο a έτσι ώστε a.fromNode = t.
def terminal_nodes(G): from_nodes = frozenset({a.fromNode for a in G.setOfArcs}) terminals = G.setOfNodes.difference(from_nodes) return terminals Περικοπές και s-t Περικοπές
ΠΡΟΣ ΤΟ Τομή cut του α συνδεδεμένος δίφθογγος G είναι ένα υποσύνολο του τόξα από G.setOfArcs οι οποίες χωρίσματα το σετ των κόμβοι G.setOfNodes σε G. G είναι συνδεδεμένο αν κάθε κόμβος n σε G.setOfNodes και έχει τουλάχιστον ένα τόξο a σε G.setOfArcs έτσι ώστε είτε n = a.fromNode ή n = a.toNode, αλλά a.fromNode != a.toNode.
Cut = namedtuple('Cut', ['setOfCutArcs']) Ο παραπάνω ορισμός αναφέρεται σε ένα υποσύνολο του τόξα , αλλά μπορεί επίσης να ορίσει ένα διαμέρισμα του κόμβοι από G.setOfNodes.
Για τις συναρτήσεις predecessors_of και successors_of, n είναι ένα κόμβος στο σετ G.setOfNodes του δίφθογγος G, και cut είναι ένα Τομή από G:
def cut_predecessors_of(n, cut, G): allowed_arcs = G.setOfArcs.difference(frozenset(cut.setOfCutArcs)) predecessors = frozenset({}) previous_count = len(predecessors) reach_fringe = frozenset({n}) keep_going = True while( keep_going ): reachable_from = frozenset({a.fromNode for a in allowed_arcs if (a.toNode in reach_fringe)}) reach_fringe = reachable_from predecessors = predecessors.union(reach_fringe) current_count = len(predecessors) keep_going = current_count - previous_count > 0 previous_count = current_count return predecessors def cut_successors_of(n, cut, G): allowed_arcs = G.setOfArcs.difference(frozenset(cut.setOfCutArcs)) successors = frozenset({}) previous_count = len(successors) reach_fringe = frozenset({n}) keep_going = True while( keep_going ): reachable_from = frozenset({a.toNode for a in allowed_arcs if (a.fromNode in reach_fringe)}) reach_fringe = reachable_from successors = successors.union(reach_fringe) current_count = len(successors) keep_going = current_count - previous_count > 0 previous_count = current_count return successors Αφήστε cut γίνε α Τομή του δίφθογγος G.
def get_first_part(cut, G): firstPartFringe = frozenset({a.fromNode for a in cut.setOfCutArcs}) firstPart = firstPartFringe for n in firstPart: preds = cut_predecessors_of(n,cut,G) firstPart = firstPart.union(preds) return firstPart def get_second_part(cut, G): secondPartFringe = frozenset({a.toNode for a in cut.setOfCutArcs}) secondPart = secondPartFringe for n in secondPart: succs= cut_successors_of(n,cut,G) secondPart = secondPart.union(succs) return secondPart cut είναι ένα Τομή του δίφθογγος G αν: (get_first_part(cut, G).union(get_second_part(cut, G)) == G.setOfNodes) and (len(get_first_part(cut, G).intersect(get_second_part(cut, G))) == 0) cut ονομάζεται x-y περικοπή αν (x in get_first_part(cut, G)) and (y in get_second_part(cut, G) ) and (x != y). Οταν ο κόμβος x σε ένα x-y περικοπή cut είναι ένα κόμβος προέλευσης και κόμβος y στο x-y περικοπή είναι ένα τερματικός κόμβος , τότε αυτό Τομή ονομάζεται a κοπή s-t .
STCut = namedtuple('STCut', ['s','t','cut']) Δίκτυα ροής
Μπορείτε να χρησιμοποιήσετε ένα δίφθογγος G να αντιπροσωπεύει ένα δίκτυο ροής.
Εκχωρήστε το καθένα κόμβος n, όπου n είναι σε G.setOfNodes ένα n.datum δηλαδή είναι FlowNodeDatum:
FlowNodeDatum = namedtuple('FlowNodeDatum', ['flowIn','flowOut']) Εκχωρήστε το καθένα τόξο a, όπου a είναι σε G.setOfArcs και a.datum δηλαδή είναι FlowArcDatum.
FlowArcDatum = namedtuple('FlowArcDatum', ['capacity','flow']) flowNodeDatum.flowIn και flowNodeDatum.flowOut είναι θετικός πραγματικοί αριθμοί .
flowArcDatum.capacity και flowArcDatum.flow είναι επίσης θετικοί πραγματικοί αριθμοί.
Για κάθε κόμβο κόμβος n σε G.setOfNodes:
n.datum.flowIn = sum({a.datum.flow for a in G.Arcs if a.toNode == n}) n.datum.flowOut = sum({a.datum.flow for a in G.Arcs if a.fromNode == n}) Δίφθογγος G τώρα αντιπροσωπεύει ένα δίκτυο ροής .
ο ροή από G αναφέρεται στο a.flow για όλα τόξα a σε G.
Εφικτές ροές
Αφήνω δίφθογγος G αντιπροσωπεύουν ένα δίκτυο ροής .
ο δίκτυο ροής εκπροσωπείται από G έχει εφικτές ροές αν:
-
Για κάθε κόμβος
nσεG.setOfNodesεκτός από κόμβοι προέλευσης και τερματικοί κόμβοι :n.datum.flowIn = n.datum.flowOut. -
Για κάθε τόξο
aσεG.setOfNodes:a.datum.capacity <= a.datum.flow.
Η συνθήκη 1 ονομάζεται a περιορισμός διατήρησης .
Η συνθήκη 2 ονομάζεται a περιορισμός χωρητικότητας .
Κόψτε την ικανότητα
ο ικανότητα αποκοπής ενός κοπή s-t stCut με κόμβος προέλευσης s και τερματικός κόμβος t του α δίκτυο ροής αντιπροσωπεύεται από ένα δίφθογγος G είναι:
def cut_capacity(stCut, G): part_1 = get_first_part(stCut.cut,G) part_2 = get_second_part(stCut.cut,G) s_part = part_1 if stCut.s in part_1 else part_2 t_part = part_1 if stCut.t in part_1 else part_2 cut_capacity = sum({a.datum.capacity for a in stCut.cut.setOfCutArcs if ( (a.fromNode in s_part) and (a.toNode in t_part) )}) return cut_capacity Ελάχιστη μείωση χωρητικότητας
Αφήστε stCut = stCut(s,t,cut) γίνε ένα κοπή s-t του α δίκτυο ροής αντιπροσωπεύεται από ένα δίφθογγος G.
stCut είναι το ελάχιστη μείωση χωρητικότητας απο δίκτυο ροής εκπροσωπείται από G αν δεν υπάρχει άλλο κοπή s-t stCutCompetitor σε αυτό δίκτυο ροής έτσι ώστε:
cut_capacity(stCut, G) Αφαιρώντας τις ροές μακριά
Θα ήθελα να αναφερθώ στο δίφθογγος αυτό θα ήταν το αποτέλεσμα της λήψης ενός δίφθογγος G και αφαιρώντας όλα τα δεδομένα ροής από όλα κόμβοι σε G.setOfNodes και επίσης όλα τα τόξα σε G.setOfArcs.
def strip_flows(G): new_nodes= frozenset( (Node(n.uid, FlowNodeDatum(0.0,0.0)) for n in G.setOfNodes) ) new_arcs = frozenset([]) for a in G.setOfArcs: new_fromNode = Node(a.fromNode.uid, FlowNodeDatum(0.0,0.0)) new_toNode = Node(a.toNode.uid, FlowNodeDatum(0.0,0.0)) new_arc = Arc(new_fromNode, new_toNode, FlowArcDatum(a.datum.capacity, 0.0)) new_arcs = new_arcs.union(frozenset([new_arc])) return DiGraph(new_nodes, new_arcs) Πρόβλημα μέγιστης ροής
ΠΡΟΣ ΤΟ δίκτυο ροής εκπροσωπείται ως δίφθογγος G, α κόμβος προέλευσης s σε G.setOfNodes και ένα τερματικός κόμβος t σε G.setOfNodes, G μπορεί να αντιπροσωπεύει ένα πρόβλημα μέγιστης ροής αν:
(len(list(source_nodes(G))) == 1) and (next(iter(source_nodes(G))) == s) and (len(list(terminal_nodes(G))) == 1) and (next(iter(terminal_nodes(G))) == t) Επισήμανση αυτής της παράστασης:
MaxFlowProblemState = namedtuple('MaxFlowProblemState', ['G','sourceNodeUid','terminalNodeUid','maxFlowProblemStateUid']) Όπου sourceNodeUid = s.uid, terminalNodeUid = t.uid, και maxFlowProblemStateUid είναι ένα αναγνωριστικό για την παρουσία προβλήματος.
Μέγιστη λύση ροής
Αφήστε maxFlowProblem αντιπροσωπεύουν ένα πρόβλημα μέγιστης ροής . Η λύση στο maxFlowProblem μπορεί να αντιπροσωπεύεται από ένα δίκτυο ροής εκπροσωπείται ως δίφθογγος H.
Δίφθογγος H είναι ένα εφικτός λύση στο πρόβλημα μέγιστης ροής κατά την είσοδο python maxFlowProblem αν:
-
strip_flows(maxFlowProblem.G) == strip_flows(H).
-
H είναι ένα δίκτυο ροής και έχει εφικτές ροές .
Εάν επιπλέον των 1 και 2:
- Δεν μπορεί να υπάρχει άλλο δίκτυο ροής αντιπροσωπεύεται από δίφθογγος
K έτσι ώστε strip_flows(G) == strip_flows(K) και find_node_by_uid(t.uid,G).flowIn .
Τότε H είναι επίσης ένα άριστος solution to |_+_|.
Με άλλα λόγια α εφικτή λύση μέγιστης ροής μπορεί να αντιπροσωπεύεται από ένα δίφθογγος , οι οποίες:
-
Είναι πανομοιότυπο με δίφθογγος maxFlowProblem του αντίστοιχου πρόβλημα μέγιστης ροής με την εξαίρεση ότι το G, n.datum.flowIn και το n.datum.flowOut οποιουδήποτε από τα κόμβοι και τόξα μπορεί να είναι διαφορετική.
-
Αντιπροσωπεύει ένα δίκτυο ροής που έχει εφικτές ροές .
Και, μπορεί να αντιπροσωπεύει ένα βέλτιστη λύση μέγιστης ροής εάν επιπλέον:
- Το
a.datum.flow για το κόμβος αντιστοιχεί στο τερματικός κόμβος στο πρόβλημα μέγιστης ροής είναι όσο το δυνατόν μεγαλύτερο (όταν εξακολουθούν να πληρούνται οι προϋποθέσεις 1 και 2).
Αν δίφθογγος flowIn αντιπροσωπεύει ένα εφικτή λύση μέγιστης ροής : H Αυτό προκύπτει από το μέγιστη ροή, ελάχιστο θεώρημα (συζητείται παρακάτω). Άτυπα, αφού find_node_by_uid(s.uid,H).flowOut = find_node_by_uid(t.uid,H).flowIn θεωρείται ότι έχει εφικτές ροές αυτό σημαίνει ότι ροή δεν μπορεί ούτε να «δημιουργηθεί» (εκτός από το κόμβος προέλευσης H) ούτε «καταστράφηκε» (εκτός από στις τερματικός κόμβος s) κατά τη διέλευση οποιουδήποτε (άλλου) κόμβος ( περιορισμοί διατήρησης ).
σύστημα σημείων πώλησης android
Από το α πρόβλημα μέγιστης ροής περιέχει μόνο ένα κόμβος προέλευσης t και ένα τερματικός κόμβος s, όλη η ροή «δημιουργήθηκε» στο t πρέπει να «καταστραφεί» σε s ή το δίκτυο ροής κάνει δεν έχω εφικτές ροές (ο περιορισμός διατήρησης θα είχε παραβιαστεί).
Αφήνω δίφθογγος t αντιπροσωπεύουν ένα εφικτή λύση μέγιστης ροής ; η παραπάνω τιμή ονομάζεται το Τιμή ροής s-t από H.
Αφήνω:
HΑυτό σημαίνει ότι mfps=MaxFlowProblemState(H, maxFlowProblem.sourceNodeUid, maxFlowProblem.terminalNodeUid, maxFlowProblem.maxFlowProblemStateUid) είναι ένα διάδοχο κράτος από mfps, που σημαίνει απλώς ότι maxFlowProblem είναι ακριβώς όπως mfps με την εξαίρεση ότι οι τιμές maxFlowProblem για τόξα a.flow σε a μπορεί να είναι διαφορετικό από το maxFlowProblem.setOfArcs για τόξα a.flow σε a.
mfps.setOfArcsΑκολουθεί μια οπτικοποίηση ενός def get_mfps_flow(mfps): flow_from_s = find_node_by_uid(mfps.sourceNodeUid,mfps.G).datum.flowOut flow_to_t = find_node_by_uid(mfps.terminalNodeUid,mfps.G).datum.flowIn if( (flow_to_t - flow_from_s) > 0): raise Exception('Infeasible s-t flow') return flow_to_t μαζί με το σχετικό mfps. Καθε τόξο maxFlowProb στην εικόνα έχει μια ετικέτα, αυτές οι ετικέτες είναι a, η καθεμία κόμβος a.datum.flowFrom / a.datum.flowTo στην εικόνα έχει μια ετικέτα και αυτές οι ετικέτες είναι n.
s-t Αποκοπή ροής
Αφήστε n.uid {n.datum.flowIn / a.datum.flowOut} αντιπροσωπεύουν ένα mfps και αφήστε MaxFlowProblemState αντιπροσωπεύουν ένα Τομή από stCut. ο περικοπή ροής από mfps.G ορίζεται:
stCut s-t περικοπή ροής είναι το άθροισμα των ροών από το διαμέρισμα που περιέχει το κόμβος προέλευσης στο διαμέρισμα που περιέχει το τερματικός κόμβος μείον το άθροισμα των ροών από το διαμέρισμα που περιέχει το τερματικός κόμβος στο διαμέρισμα που περιέχει το κόμβος προέλευσης .
Μέγιστη ροή, ελάχιστη περικοπή
Αφήστε def get_stcut_flow(stCut,mfps): s = find_node_by_uid(mfps.sourceNodeUid, mfps.G) t = find_node_by_uid(mfps.terminalNodeUid, mfps.G) part_1 = get_first_part(stCut.cut,mfps.G) part_2 = get_second_part(stCut.cut,mfps.G) s_part = part_1 if s in part_1 else part_2 t_part = part_1 if t in part_1 else part_2 s_t_sum = sum(a.datum.flow for a in mfps.G.setOfArcs if (a in stCut.cut.setOfCutArcs) and (a.fromNode in s_part) ) t_s_sum = sum(a.datum.flow for a in mfps.G.setOfArcs if (a in stCut.cut.setOfCutArcs) and (a.fromNode in t_part) ) cut_flow = s_t_sum - t_s_sum return cut_flow αντιπροσωπεύουν ένα πρόβλημα μέγιστης ροής και αφήστε τη λύση στο maxFlowProblem να εκπροσωπείται από ένα δίκτυο ροής εκπροσωπήθηκε ως δίφθογγος maxFlowProblem.
Αφήστε H γίνε το ελάχιστη μείωση χωρητικότητας απο δίκτυο ροής εκπροσωπείται από minStCut.
Επειδή στο πρόβλημα μέγιστης ροής η ροή προέρχεται μόνο σε ένα κόμβος προέλευσης και τερματίζει σε ένα μόνο τερματικός κόμβος και, λόγω του περιορισμοί χωρητικότητας και το περιορισμοί διατήρησης , γνωρίζουμε ότι όλη η ροή εισέρχεται maxFlowProblem.G πρέπει να διασχίσει οποιοδήποτε κοπή s-t , συγκεκριμένα πρέπει να διασχίσει maxFlowProblem.terminalNodeUid. Αυτό σημαίνει:
minStCutΕπίλυση του προβλήματος μέγιστης ροής
Η βασική ιδέα για την επίλυση α πρόβλημα μέγιστης ροής get_flow_value(H, maxFlowProblem) <= cut_capacity(minStCut, maxFlowProblem.G) είναι να ξεκινήσετε με ένα διάλυμα μέγιστης ροής αντιπροσωπεύεται από δίφθογγος maxFlowProblem. Ένα τέτοιο σημείο εκκίνησης μπορεί να είναι H. Η εργασία είναι τότε να χρησιμοποιήσετε H = strip_flows(maxFlowProblem.G) και από μερικούς άπληστος τροποποίηση του H τιμές μερικών τόξα a.datum.flow σε a για να παράγει ένα άλλο διάλυμα μέγιστης ροής αντιπροσωπεύεται από δίφθογγος H.setOfArcs έτσι ώστε K δεν μπορεί ακόμα να αντιπροσωπεύει ένα δίκτυο ροής με εφικτές ροές και K. Όσο συνεχίζεται αυτή η διαδικασία, η ποιότητα (get_flow_value(H, maxFlowProblem) ) της πιο πρόσφατης αντιμετώπισης διάλυμα μέγιστης ροής (get_flow_value(K, maxFlowProblem)) είναι καλύτερο από οποιοδήποτε άλλο διάλυμα μέγιστης ροής που έχει βρεθεί. Εάν η διαδικασία φτάσει σε σημείο που γνωρίζει ότι δεν είναι δυνατή καμία άλλη βελτίωση, η διαδικασία μπορεί να τερματιστεί και θα επιστρέψει το άριστος διάλυμα μέγιστης ροής .
Η παραπάνω περιγραφή είναι γενική και παραλείπει πολλές αποδείξεις όπως εάν είναι δυνατή μια τέτοια διαδικασία ή πόσο καιρό μπορεί να διαρκέσει, θα δώσω μερικές ακόμη λεπτομέρειες και τον αλγόριθμο.
The Max Flow, Min Cut Θεώρημα
Από το βιβλίο Ροές στα δίκτυα των Ford και Fulkerson , η δήλωση του μέγιστη ροή, ελάχιστο θεώρημα (Το θεώρημα 5.1) είναι:
Για οποιοδήποτε δίκτυο, η μέγιστη τιμή ροής από K έως s ισούται με την ελάχιστη χωρητικότητα κοπής όλων των τεμαχίων που χωρίζουν t και s.
Χρησιμοποιώντας τους ορισμούς σε αυτήν την ανάρτηση, που μεταφράζεται σε:
Η λύση σε ένα t αντιπροσωπεύεται από ένα δίκτυο ροής εκπροσωπήθηκε ως δίφθογγος maxFlowProblem είναι άριστος αν:
Hμου αρέσει αυτή την απόδειξη του θεωρήματος και της Wikipedia άλλο ένα .
ο μέγιστη ροή, ελάχιστο θεώρημα χρησιμοποιείται για να αποδείξει την ορθότητα και την πληρότητα του Μέθοδος Ford-Fulkerson .
Θα δώσω επίσης μια απόδειξη του θεωρήματος στην ενότητα μετά αύξηση διαδρομών .
Η μέθοδος Ford-Fulkerson και ο αλγόριθμος Edmonds-Karp
CLRS ορίζει τη μέθοδο Ford-Fulkerson έτσι (ενότητα 26.2):
get_flow_value(H, maxFlowProblem) == cut_capacity(minStCut, maxFlowProblem.G) Υπόλοιπο γράφημα
ο Υπόλοιπο γράφημα του α δίκτυο ροής εκπροσωπείται ως δίφθογγος FORD-FULKERSON-METHOD(G, s, t): initialize flow f to 0 while there exists an augmenting path p in the residual graph G_f augment flow f along μπορεί να αναπαρασταθεί ως δίφθογγος G:
G_f -
ResidualDatum = namedtuple('ResidualDatum', ['residualCapacity','action']) def agg_n_to_u_cap(n,u,G_as_dict): arcs_out = G_as_dict[n] return sum([a.datum.capacity for a in arcs_out if( (a.fromNode == n) and (a.toNode == u) ) ]) def agg_n_to_u_flow(n,u,G_as_dict): arcs_out = G_as_dict[n] return sum([a.datum.flow for a in arcs_out if( (a.fromNode == n) and (a.toNode == u) ) ]) def get_residual_graph_of(G): G_as_dict = digraph_to_dict(G) residual_nodes = G.setOfNodes residual_arcs = frozenset([]) for n in G_as_dict: arcs_from = G_as_dict[n] nodes_to = frozenset([find_node_by_uid(a.toNode.uid,G) for a in arcs_from]) for u in nodes_to: n_to_u_cap_sum = agg_n_to_u_cap(n,u,G_as_dict) n_to_u_flow_sum = agg_n_to_u_flow(n,u,G_as_dict) if(n_to_u_cap_sum > n_to_u_flow_sum): flow = round(n_to_u_cap_sum - n_to_u_flow_sum, TOL) residual_arcs = residual_arcs.union( frozenset([Arc(n,u,datum=ResidualDatum(flow, 'push'))]) ) if(n_to_u_flow_sum > 0.0): flow = round(n_to_u_flow_sum, TOL) residual_arcs = residual_arcs.union( frozenset([Arc(u,n,datum=ResidualDatum(flow, 'pull'))]) ) return DiGraph(residual_nodes, residual_arcs) επιστρέφει το άθροισμα agg_n_to_u_cap(n,u,G_as_dict) για όλα τόξα στο υποσύνολο του a.datum.capacity που τόξο G.setOfArcs βρίσκεται στο υποσύνολο εάν a και a.fromNode = n.
-
a.toNode = u επιστρέφει το άθροισμα agg_n_to_u_cap(n,u,G_as_dict) για όλα τόξα στο υποσύνολο του a.datum.flow που τόξο G.setOfArcs βρίσκεται στο υποσύνολο εάν a και a.fromNode = n.
Εν συντομία, το υπόλοιπο γράφημα a.toNode = u αντιπροσωπεύει ορισμένες ενέργειες που μπορούν να εκτελεστούν στο δίφθογγος G_f.
Κάθε ζευγάρι κόμβοι G σε n,u απο δίκτυο ροής αντιπροσωπεύεται από δίφθογγος G.setOfNodes μπορεί να δημιουργήσει 0, 1 ή 2 τόξα στο υπόλοιπο γράφημα G από G_f.
-
Το ζεύγος G δεν δημιουργεί κανένα τόξα σε n,u αν δεν υπάρχει τόξο G_f σε a έτσι ώστε G.setOfArcs και a.fromNode = n.
-
Το ζεύγος a.toNode = u παράγει το τόξο n,u σε a όπου G_f.setOfArcs αντιπροσωπεύει ένα τόξο με την ένδειξη α τόξο ροής ώθησης από a έως n u αν a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)).
-
Το ζεύγος n_to_u_cap_sum > n_to_u_flow_sum παράγει το τόξο n,u σε a όπου G_f.setOfArcs αντιπροσωπεύει ένα τόξο με την ένδειξη α τόξο ροής έλξης από a έως n u αν a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)).
-
Καθε τόξο ροής ώθησης σε n_to_u_flow_sum > 0.0 αντιπροσωπεύει την ενέργεια της προσθήκης ενός συνόλου G_f.setOfArcs ροή προς τόξα στο υποσύνολο του x <= n_to_u_cap_sum - n_to_u_flow_sum που τόξο G.setOfArcs βρίσκεται στο υποσύνολο εάν a και a.fromNode = n.
-
Καθε τόξο ροής έλξης σε a.toNode = u αντιπροσωπεύει τη δράση αφαίρεσης ενός συνόλου G_f.setOfArcs ροή προς τόξα στο υποσύνολο του x <= n_to_u_flow_sum που τόξο G.setOfArcs βρίσκεται στο υποσύνολο εάν a και a.fromNode = n.
Εκτέλεση ενός ατόμου Σπρώξτε ή Τραβήξτε δράση από a.toNode = u σχετικά με την ισχύουσα τόξα σε G_f μπορεί να δημιουργήσει ένα δίκτυο ροής χωρίς εφικτές ροές επειδή η περιορισμοί χωρητικότητας ή το περιορισμοί διατήρησης μπορεί να παραβιαστεί στη δημιουργία δίκτυο ροής .
Ακολουθεί μια οπτικοποίηση του υπόλοιπο γράφημα του προηγούμενου παραδείγματος οπτικοποίηση ενός διάλυμα μέγιστης ροής , στην απεικόνιση κάθε τόξο G αντιπροσωπεύει a.
Διαδρομή επαύξησης
Αφήστε a.residualCapacity γίνε α πρόβλημα μέγιστης ροής και αφήστε maxFlowProblem γίνε το υπόλοιπο γράφημα από G_f = get_residual_graph_of(G).
Ενα αύξηση της διαδρομής maxFlowProblem.G για augmentingPath είναι οποιοδήποτε μονοπάτι από maxFlowProblem έως find_node_by_uid(maxFlowProblem.sourceNode,G_f).
Αποδεικνύεται ότι αυξάνει μονοπάτι find_node_by_uid(maxFlowProblem.terminalNode,G_f) μπορεί να εφαρμοστεί σε ένα μέγιστη λύση ροής αντιπροσωπεύεται από δίφθογγος augmentingPath δημιουργώντας ένα άλλο μέγιστη λύση ροής αντιπροσωπεύεται από δίφθογγος H όπου K αν get_flow_value(H, maxFlowProblem) δεν είναι άριστος .
Δείτε πώς:
HΣτα παραπάνω, def augment(augmentingPath, H): augmentingPath = list(augmentingPath) H_as_dict = digraph_to_dict(H) new_nodes = frozenset({}) new_arcs = frozenset({}) visited_nodes = frozenset({}) visited_arcs = frozenset({}) bottleneck_residualCapacity = min( augmentingPath, key=lambda a: a.datum.residualCapacity ).datum.residualCapacity for x in augmentingPath: from_node_uid = x.fromNode.uid if x.datum.action == 'push' else x.toNode.uid to_node_uid = x.toNode.uid if x.datum.action == 'push' else x.fromNode.uid from_node = find_node_by_uid( from_node_uid, H ) to_node = find_node_by_uid( to_node_uid, H ) load = bottleneck_residualCapacity if x.datum.action == 'push' else -bottleneck_residualCapacity for a in H_as_dict[from_node]: if(a.toNode == to_node): test_sum = a.datum.flow + load new_flow = a.datum.flow new_from_node_flow_out = a.fromNode.datum.flowOut new_to_node_flow_in = a.toNode.datum.flowIn new_from_look = {n for n in new_nodes if (n.uid == a.fromNode.uid)} new_to_look = {n for n in new_nodes if (n.uid == a.toNode.uid) } prev_from_node = new_from_look.pop() if (len(new_from_look)>0) else a.fromNode prev_to_node = new_to_look.pop() if (len(new_to_look)>0) else a.toNode new_nodes = new_nodes.difference(frozenset({prev_from_node})) new_nodes = new_nodes.difference(frozenset({prev_to_node})) if(test_sum > a.datum.capacity): new_flow = a.datum.capacity new_from_node_flow_out = prev_from_node.datum.flowOut - a.datum.flow + a.datum.capacity new_to_node_flow_in = prev_to_node.datum.flowIn - a.datum.flow + a.datum.capacity load = test_sum - a.datum.capacity elif(test_sum <0.0): new_flow = 0.0 new_from_node_flow_out = prev_from_node.datum.flowOut - a.datum.flow new_to_node_flow_in = prev_to_node.datum.flowIn - a.datum.flow load = test_sum else: new_flow = test_sum new_from_node_flow_out = prev_from_node.datum.flowOut - a.datum.flow + new_flow new_to_node_flow_in = prev_to_node.datum.flowIn - a.datum.flow + new_flow load = 0.0 new_from_node_flow_out = round(new_from_node_flow_out, TOL) new_to_node_flow_in = round(new_to_node_flow_in, TOL) new_flow = round(new_flow, TOL) new_from_node = Node(prev_from_node.uid, FlowNodeDatum(prev_from_node.datum.flowIn, new_from_node_flow_out)) new_to_node = Node(prev_to_node.uid, FlowNodeDatum(new_to_node_flow_in, prev_to_node.datum.flowOut)) new_arc = Arc(new_from_node, new_to_node, FlowArcDatum(a.datum.capacity, new_flow)) visited_nodes = visited_nodes.union(frozenset({a.fromNode,a.toNode})) visited_arcs = visited_arcs.union(frozenset({a})) new_nodes = new_nodes.union(frozenset({new_from_node, new_to_node})) new_arcs = new_arcs.union(frozenset({new_arc})) not_visited_nodes = H.setOfNodes.difference(visited_nodes) not_visited_arcs = H.setOfArcs.difference(visited_arcs) full_new_nodes = new_nodes.union(not_visited_nodes) full_new_arcs = new_arcs.union(not_visited_arcs) G = DiGraph(full_new_nodes, full_new_arcs) full_new_arcs_update = frozenset([]) for a in full_new_arcs: new_from_node = a.fromNode new_to_node = a.toNode new_from_node = find_node_by_uid( a.fromNode.uid, G ) new_to_node = find_node_by_uid( a.toNode.uid, G ) full_new_arcs_update = full_new_arcs_update.union( {Arc(new_from_node, new_to_node, FlowArcDatum(a.datum.capacity, a.datum.flow))} ) G = DiGraph(full_new_nodes, full_new_arcs_update) return G είναι κάποια αξία ανοχής για στρογγύλεμα τις τιμές ροής στο δίκτυο. Αυτό γίνεται για να αποφευχθεί η κατάρρευση ανακρίβεια υπολογισμών κυμαινόμενου σημείου . Έτσι, για παράδειγμα, χρησιμοποίησα TOL να σημαίνει γύρο έως 10 σημαντικά ψηφία .
Αφήστε TOL = 10, μετά K = augment(augmentingPath, H) αντιπροσωπεύει ένα εφικτή λύση μέγιστης ροής για K. Για να είναι αληθινή η δήλωση, το δίκτυο ροής εκπροσωπείται από maxFlowProblem πρέπει να έχω εφικτές ροές (δεν παραβιάζει το περιορισμός χωρητικότητας ή το περιορισμός διατήρησης .
πότε να χρησιμοποιήσετε το web api
Να γιατί: Στην παραπάνω μέθοδο, το καθένα κόμβος προστέθηκε στο νέο δίκτυο ροής αντιπροσωπεύεται από δίφθογγος K είναι είτε ένα ακριβές αντίγραφο του κόμβος από δίφθογγος K ή α κόμβος H που είχε προσθέσει τον ίδιο αριθμό στο n ως του n.datum.flowIn. Αυτό σημαίνει ότι το περιορισμός διατήρησης ικανοποιείται σε n.datum.flowOut αρκεί να ήταν ικανοποιημένη σε K. ο περιορισμός διατήρησης είναι ικανοποιημένος επειδή ελέγξουμε ρητά ότι υπάρχει νέο τόξο H στο δίκτυο έχει a; έτσι, όσο το τόξα από το σετ a.datum.flow <= a.datum.capacity που αντιγράφηκαν χωρίς τροποποίηση σε H.setOfArcs μην παραβιάζετε το περιορισμός χωρητικότητας , τότε K.setOfArcs δεν παραβιάζει το περιορισμός χωρητικότητας .
Είναι επίσης αλήθεια ότι K αν get_flow_value(H, maxFlowProblem) δεν είναι άριστος .
Να γιατί: Για ένα αύξηση της διαδρομής H να υπάρχει στο δίφθογγος εκπροσώπηση του υπόλοιπο γράφημα augmentingPath του α πρόβλημα μέγιστης ροής G_f μετά το τελευταίο τόξο maxFlowProblem στις a πρέπει να είναι «ώθηση» τόξο και πρέπει να έχει augmentingPath. Ενα αύξηση της διαδρομής ορίζεται ως αυτό που τελειώνει στο τερματικός κόμβος απο πρόβλημα μέγιστης ροής για το οποίο είναι αύξηση της διαδρομής . Από τον ορισμό του υπόλοιπο γράφημα , είναι σαφές ότι το τελευταίο τόξο σε ένα αύξηση της διαδρομής σε αυτό υπόλοιπο γράφημα πρέπει να είναι «ώθηση» τόξο γιατί οποιαδήποτε «έλξη» τόξο a.toNode == maxFlowProblem.terminalNode στο αύξηση της διαδρομής θα έχει b και b.toNode == maxFlowProblem.terminalNode από τον ορισμό του μονοπάτι . Επιπλέον, από τον ορισμό του μονοπάτι , είναι σαφές ότι το τερματικός κόμβος τροποποιείται μόνο μία φορά από το b.fromNode != maxFlowProblem.terminalNode μέθοδος. Έτσι augment τροποποιεί augment ακριβώς μία φορά και αυξάνει την τιμή maxFlowProblem.terminalNode.flowIn γιατί το τελευταίο τόξο στο maxFlowProblem.terminalNode.flowIn πρέπει να είναι το τόξο που προκαλεί την τροποποίηση στο augmentingPath κατά τη διάρκεια maxFlowProblem.terminalNode.flowIn. Από τον ορισμό του augment όπως ισχύει για το 'push' τόξα , το augment μπορεί να αυξηθεί μόνο, όχι να μειωθεί.
Μερικές αποδείξεις από τους Sedgewick και Wayne
Το βιβλίο Αλγόριθμοι, τέταρτη έκδοση των Robert Sedgewich και Kevin Wayne έχει μερικές υπέροχες και σύντομες αποδείξεις (σελίδες 892-894) που θα είναι χρήσιμες. Θα τα αναδημιουργήσω εδώ, αν και θα χρησιμοποιήσω τη γλώσσα που ταιριάζει με τους προηγούμενους ορισμούς. Οι ετικέτες μου για τις αποδείξεις είναι ίδιες με αυτές του βιβλίου Sedgewick.
Πρόταση Ε: Για κάθε δίφθογγος maxFlowProblem.terminalNode.flowIn αντιπροσωπεύοντας ένα εφικτή λύση μέγιστης ροής σε ένα πρόβλημα μέγιστης ροής H, για οποιαδήποτε maxFlowProblem stCut.
Απόδειξη: Αφήστε get_stcut_flow(stCut,H,maxFlowProblem) = get_flow_value(H, maxFlowProblem). Πρόταση Ε ισχύει για stCut=stCut(maxFlowProblem.sourceNode,maxFlowProblem.terminalNode,set([a for a in H.setOfArcs if a.toNode == maxFlowProblem.terminalNode])) απευθείας από τον ορισμό του τιμή ροής s-t . Ας υποθέσουμε ότι εκεί θέλουμε να μετακινήσουμε μερικά κόμβος stCut από το s-partition (n) και στο t-partition get_first_part(stCut.cut, G), πρέπει να αλλάξουμε (get_second_part(stCut.cut, G)), το οποίο θα μπορούσε να αλλάξει stCut.cut και ακυρώνει πρόταση Ε . Ωστόσο, ας δούμε πώς η τιμή του stcut_flow = get_stcut_flow(stCut,H,maxFlowProblem) θα αλλάξει καθώς κάνουμε αυτήν την αλλαγή. κόμβος stcut_flow είναι σε ισορροπία που σημαίνει ότι το άθροισμα της ροής προς κόμβος n είναι ίσο με το άθροισμα της ροής από αυτό (αυτό είναι απαραίτητο για την n να αντιπροσωπεύει a εφικτή λύση ). Παρατηρήστε ότι όλη η ροή που είναι μέρος του H μπαίνω κόμβος stcut_flow το εισάγει από το s-partition (εισερχόμενη ροή κόμβος n από το διαμέρισμα t είτε άμεσα είτε έμμεσα δεν θα είχε υπολογιστεί στο n τιμή επειδή οδηγεί σε λάθος κατεύθυνση με βάση τον ορισμό). Επιπλέον, όλες οι ροές εξέρχονται stcut_flow θα ρέει τελικά (άμεσα ή έμμεσα) στο τερματικός κόμβος (αποδείχθηκε νωρίτερα). Όταν κινούμαστε κόμβος n στο διαμέρισμα t, όλη η ροή εισέρχεται n από το s-partition πρέπει να προστεθεί στο νέο n αξία; Ωστόσο, όλες οι ροές εξέρχονται stcut_flow πρέπει να αφαιρεθεί από το νέο n αξία; το τμήμα της ροής που κατευθύνεται κατευθείαν στο t-partition αφαιρείται επειδή αυτή η ροή είναι τώρα εσωτερική στο νέο t-partition και δεν μετράται ως stcut_flow. Το μέρος της ροής από stcut_flow κατευθυνόμενοι προς κόμβοι στο s-partition πρέπει επίσης να αφαιρεθεί από n: Μετά stcut_flow μετακινηθεί στο t-partition, αυτές οι ροές θα κατευθυνθούν από το t-partition και στο s-partition και έτσι δεν πρέπει να ληφθούν υπόψη στο n, καθώς αυτές οι ροές αφαιρούνται η εισροή στο s- διαμέρισμα και πρέπει να μειωθεί με το άθροισμα αυτών των ροών και η εκροή από το s-partition στο t-partition (όπου όλες οι ροές από το st πρέπει να καταλήξουν) πρέπει να μειωθεί κατά το ίδιο ποσό. Οπως και κόμβος stcut_flow ήταν σε ισορροπία πριν από τη διαδικασία, η ενημέρωση θα είχε προσθέσει την ίδια τιμή στο νέο n αξία καθώς αφαιρέθηκε αφήνοντας έτσι πρόταση Ε αλήθεια μετά την ενημέρωση. Η ισχύς του πρόταση Ε Στη συνέχεια, ακολουθείται από επαγωγή στο μέγεθος του διαμερίσματος t.
Εδώ είναι μερικά παραδείγματα δίκτυα ροής για να βοηθήσουμε στην απεικόνιση των λιγότερο προφανών περιπτώσεων όπου πρόταση Ε κατέχει? Στην εικόνα, οι κόκκινες περιοχές δείχνουν το s-partition, οι μπλε περιοχές αντιπροσωπεύουν το t-partition και το πράσινο τόξα υποδείξτε ένα κοπή s-t . Στη δεύτερη εικόνα, ροή μεταξύ κόμβος Α και κόμβος Το Β αυξάνεται ενώ η ροή προς τερματικός κόμβος δεν αλλάζει .:
Συνέπεια: Οχι s-t περικοπή ροής η τιμή μπορεί να υπερβεί την ικανότητα οποιουδήποτε κοπή s-t .
Πρόταση ΣΤ (μέγιστη ροή, ελάχιστο θεώρημα): Αφήστε stcut_flow γίνε ένα ροή s-t . Οι ακόλουθες 3 συνθήκες είναι ισοδύναμες:
-
Υπάρχει ένα κοπή s-t του οποίου η χωρητικότητα ισούται με την τιμή της ροής f.
-
f είναι ένα μέγιστη ροή .
-
Δεν υπάρχει αύξηση της διαδρομής σε σχέση με f.
Η συνθήκη 1 υποδηλώνει την κατάσταση 2 από το αποτέλεσμα. Η συνθήκη 2 υποδηλώνει την κατάσταση 3 επειδή η ύπαρξη μιας διαδρομής αύξησης συνεπάγεται την ύπαρξη ροής με μεγαλύτερες τιμές, που έρχονται σε αντίθεση με το μέγιστο του f. Η συνθήκη 3 υποδηλώνει την κατάσταση 1: Αφήστε f να είναι το σύνολο όλων κόμβοι που μπορεί να επιτευχθεί από C_s με ένα αύξηση της διαδρομής στο υπόλοιπο γράφημα . Αφήστε s είναι το υπόλοιπο τόξα , τότε C_t πρέπει να είναι σε t (από την υπόθεσή μας). ο τόξα διέλευση από C_t έως C_s τότε σχηματίστε ένα κοπή s-t που περιέχει μόνο τόξα C_t όπου είτε a ή a.datum.capacity = a.datum.flow. Εάν αυτό ήταν διαφορετικό τότε το κόμβοι συνδέεται με ένα τόξο με εναπομένουσα εναπομένουσα χωρητικότητα σε a.datum.flow = 0.0 θα ήταν στο σετ C_s αφού θα υπήρχε τότε αύξηση της διαδρομής από C_s σε ένα τέτοιο κόμβος . Η ροή κατά μήκος του κοπή s-t είναι ίσο με το s-t cut's χωρητικότητα (από τότε τόξα από s έως C_s έχουν ροή ίση με χωρητικότητα) και επίσης με την τιμή του ροή s-t (με πρόταση Ε ).
Αυτή η δήλωση του μέγιστη ροή, ελάχιστο θεώρημα υπονοεί την προηγούμενη δήλωση από Ροές στα δίκτυα .
Συντελεστής (ιδιοκτησία ακεραιότητας): Όταν οι χωρητικότητες είναι ακέραιοι, υπάρχει μια μέγιστη ροή ακέραιας αξίας και ο αλγόριθμος Ford-Fulkerson το βρίσκει.
Απόδειξη: Κάθε αύξηση της διαδρομής αυξάνει τη ροή με θετικό ακέραιο, το ελάχιστο των αχρησιμοποίητων δυνατοτήτων στο 'push' τόξα και οι ροές στο «τράβηγμα» τόξα , τα οποία είναι πάντα θετικοί ακέραιοι.
Αυτό δικαιολογεί το Μέθοδος Ford-Fulkerson περιγραφή από CLRS . Η μέθοδος είναι να συνεχίσετε να βρίσκετε αύξηση διαδρομών και εφαρμογή C_t έως το αργότερο augment να βρούμε καλύτερες λύσεις, έως ότου πια αύξηση της διαδρομής που σημαίνει ότι το πιο πρόσφατο διάλυμα μέγιστης ροής είναι άριστος .
Από τη Ford-Fulkerson στο Edmonds-Karp
Οι υπόλοιπες ερωτήσεις σχετικά με την επίλυση προβλήματα μέγιστης ροής είναι:
-
Πώς θα έπρεπε αύξηση διαδρομών να κατασκευαστεί;
-
Θα τερματιστεί η μέθοδος εάν χρησιμοποιούμε πραγματικούς αριθμούς και όχι ακέραιους αριθμούς;
-
Πόσος χρόνος θα χρειαστεί για να τερματιστεί (εάν ισχύει);
ο Αλγόριθμος Edmonds-Karp καθορίζει ότι το καθένα αύξηση της διαδρομής κατασκευάζεται από ένα Πρώτη αναζήτηση εύρους ( BFS ) απο υπόλοιπο γράφημα ; Αποδεικνύεται ότι αυτή η απόφαση του σημείου 1 παραπάνω θα αναγκάσει επίσης τον τερματισμό του αλγορίθμου (σημείο 2) και επιτρέπει το ασυμπτωτική πολυπλοκότητα χρόνου και χώρου να καθοριστεί.
Πρώτον, εδώ είναι BFS εκτέλεση:
maxFlowSolutionΧρησιμοποίησα ένα deque από την ενότητα συλλογών python .
Για να απαντήσω στην ερώτηση 2 παραπάνω, θα παραφράσω μια άλλη απόδειξη Sedgewick και Wayne : Πρόταση Ζ. Ο αριθμός των αύξηση διαδρομών απαιτείται στο Έντμοντς-Καρπ αλγόριθμος με def bfs(sourceNode, terminalNode, G_f): G_f_as_dict = digraph_to_dict(G_f) parent_arcs = dict([]) visited = frozenset([]) deq = deque([sourceNode]) while len(deq) > 0: curr = deq.popleft() if curr == terminalNode: break for a in G_f_as_dict.get(curr): if (a.toNode not in visited): visited = visited.union(frozenset([a.toNode])) parent_arcs[a.toNode] = a deq.extend([a.toNode]) path = list([]) curr = terminalNode while(curr != sourceNode): if (curr not in parent_arcs): err_msg = 'No augmenting path from {} to {}.'.format(sourceNode.uid, terminalNode.uid) raise StopIteration(err_msg) path.extend([parent_arcs[curr]]) curr = parent_arcs[curr].fromNode path.reverse() test = deque([path[0].fromNode]) for a in path: if(test[-1] != a.fromNode): err_msg = 'Bad path: {}'.format(path) raise ValueError(err_msg) test.extend([a.toNode]) return path κόμβοι και N τόξα είναι το πολύ A. Απόδειξη: Όλα αύξηση της διαδρομής έχει ένα λαιμός φιάλης τόξο - ένα τόξο που διαγράφεται από το υπόλοιπο γράφημα γιατί αντιστοιχεί είτε σε «ώθηση» τόξο που γεμίζει σε χωρητικότητα ή ένα «τράβηγμα» τόξο μέσω της οποίας η ροή γίνεται 0. Κάθε φορά ένα τόξο γίνεται εμπόδιο τόξο , το μήκος οποιουδήποτε αύξηση της διαδρομής μέσα από αυτό πρέπει να αυξηθεί κατά 2. Αυτό συμβαίνει επειδή το καθένα κόμβος σε ένα μονοπάτι μπορεί να εμφανίζεται μόνο μία φορά ή καθόλου (από τον ορισμό του μονοπάτι από το μονοπάτια διερευνώνται από το συντομότερο μονοπάτι στο μακρύτερο, αυτό σημαίνει ότι τουλάχιστον ένα ακόμη κόμβος πρέπει να επισκεφθείτε το επόμενο μονοπάτι που περνά από το συγκεκριμένο σημείο συμφόρησης κόμβος αυτό σημαίνει ένα επιπλέον 2 τόξα στο μονοπάτι πριν φτάσουμε στο κόμβος . Από το αύξηση της διαδρομής έχει μέγιστο μήκος NA/2 καθε τόξο μπορεί να είναι το πολύ N αύξηση διαδρομών , και ο συνολικός αριθμός αύξηση διαδρομών είναι το πολύ N/2.
ο Αλγόριθμος Edmonds-Karp εκτελείται σε NA/2. Εάν το πολύ O(NA^2) μονοπάτια θα διερευνηθεί κατά τη διάρκεια του αλγορίθμου και θα εξερευνηθεί το καθένα μονοπάτι με BFS είναι NA/2 τότε ο πιο σημαντικός όρος του προϊόντος και συνεπώς η ασυμπτωτική πολυπλοκότητα είναι N+A.
Αφήστε O(NA^2) να είναι mfp.
maxFlowProblemStateΗ παραπάνω έκδοση είναι αναποτελεσματική και έχει χειρότερη πολυπλοκότητα από την def edmonds_karp(mfp): sid, tid = mfp.sourceNodeUid, mfp.terminalNodeUid no_more_paths = False loop_count = 0 while(not no_more_paths): residual_digraph = get_residual_graph_of(mfp.G) try: asource = find_node_by_uid(mfp.sourceNodeUid, residual_digraph) aterm = find_node_by_uid(mfp.terminalNodeUid, residual_digraph) apath = bfs(asource, aterm, residual_digraph) paint_mfp_path(mfp, loop_count, apath) G = augment(apath, mfp.G) s = find_node_by_uid(sid, G) t = find_node_by_uid(tid, G) mfp = MaxFlowProblemState(G, s.uid, t.uid, mfp.maxFlowProblemStateUid) loop_count += 1 except StopIteration as e: no_more_paths = True return mfp αφού κατασκευάζει ένα νέο διάλυμα μέγιστης ροής και νέο α υπόλοιπο γράφημα κάθε φορά (αντί να τροποποιείτε υπάρχοντα διαγράμματα καθώς ο αλγόριθμος προχωρά). Για να φτάσετε σε πραγματικό O(NA^2) λύση ο αλγόριθμος πρέπει να διατηρεί και τα δύο δίφθογγος που αντιπροσωπεύει το κατάσταση προβλήματος μέγιστης ροής και τα σχετικά υπόλοιπο γράφημα . Έτσι, ο αλγόριθμος πρέπει να αποφύγει την επανάληψη τόξα και κόμβοι άσκοπα και ενημερώστε τις τιμές τους και τις σχετικές τιμές στο υπόλοιπο γράφημα μόνο όπως είναι απαραίτητο.
Για να γράψετε πιο γρήγορα Έντμοντς Καρπ αλγόριθμος, ξαναγράφω πολλά κομμάτια κώδικα από τα παραπάνω. Ελπίζω να περάσω από τον κώδικα που δημιούργησε ένα νέο δίφθογγος ήταν χρήσιμη για την κατανόηση του τι συμβαίνει. Στον γρήγορο αλγόριθμο, χρησιμοποιώ μερικά νέα κόλπα και δομές δεδομένων Python που δεν θέλω να αναλύσω λεπτομερώς. Θα πω ότι O(NA^2) και a.fromNode αντιμετωπίζονται τώρα ως χορδές και υγρά κόμβοι . Για αυτόν τον κωδικό, αφήστε a.toNode να είναι mfps
maxFlowProblemStateΑκολουθεί μια οπτικοποίηση του τρόπου με τον οποίο αυτός ο αλγόριθμος λύνει το παράδειγμα δίκτυο ροής από πάνω. Η οπτικοποίηση δείχνει τα βήματα καθώς αντικατοπτρίζονται στο δίφθογγος import uuid def fast_get_mfps_flow(mfps): flow_from_s = {n for n in mfps.G.setOfNodes if n.uid == mfps.sourceNodeUid}.pop().datum.flowOut flow_to_t = {n for n in mfps.G.setOfNodes if n.uid == mfps.terminalNodeUid}.pop().datum.flowIn if( (flow_to_t - flow_from_s) > 0.00): raise Exception('Infeasible s-t flow') return flow_to_t def fast_e_k_preprocess(G): G = strip_flows(G) get = dict({}) get['nodes'] = dict({}) get['node_to_node_capacity'] = dict({}) get['node_to_node_flow'] = dict({}) get['arcs'] = dict({}) get['residual_arcs'] = dict({}) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if(a.toNode not in G.setOfNodes): err_msg = 'There is no Node {a.toNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) get['nodes'][a.fromNode.uid] = a.fromNode get['nodes'][a.toNode.uid] = a.toNode lark = Arc(a.fromNode.uid, a.toNode.uid, FlowArcDatumWithUid(a.datum.capacity, a.datum.flow, uuid.uuid4())) if(a.fromNode.uid not in get['arcs']): get['arcs'][a.fromNode.uid] = dict({a.toNode.uid : dict({lark.datum.uid : lark})}) else: if(a.toNode.uid not in get['arcs'][a.fromNode.uid]): get['arcs'][a.fromNode.uid][a.toNode.uid] = dict({lark.datum.uid : lark}) else: get['arcs'][a.fromNode.uid][a.toNode.uid][lark.datum.uid] = lark for a in G.setOfArcs: if a.toNode.uid not in get['arcs']: get['arcs'][a.toNode.uid] = dict({}) for n in get['nodes']: get['residual_arcs'][n] = dict() get['node_to_node_capacity'][n] = dict() get['node_to_node_flow'][n] = dict() for u in get['nodes']: n_to_u_cap_sum = sum(a.datum.capacity for a in G.setOfArcs if (a.fromNode.uid == n) and (a.toNode.uid == u) ) n_to_u_flow_sum = sum(a.datum.flow for a in G.setOfArcs if (a.fromNode.uid == n) and (a.toNode.uid == u) ) if(n_to_u_cap_sum > n_to_u_flow_sum): flow = round(n_to_u_cap_sum - n_to_u_flow_sum, TOL) get['residual_arcs'][n][u] = Arc(n,u,ResidualDatum(flow, 'push')) if(n_to_u_flow_sum > 0.0): flow = round(n_to_u_flow_sum, TOL) get['residual_arcs'][u][n] = Arc(u,n,ResidualDatum(flow, 'pull')) get['node_to_node_capacity'][n][u] = n_to_u_cap_sum get['node_to_node_flow'][n][u] = n_to_u_flow_sum return get def fast_bfs(sid, tid, get): parent_of = dict([]) visited = frozenset([]) deq = coll.deque([sid]) while len(deq) > 0: n = deq.popleft() if n == tid: break for u in get['residual_arcs'][n]: if (u not in visited): visited = visited.union(frozenset({u})) parent_of[u] = get['residual_arcs'][n][u] deq.extend([u]) path = list([]) curr = tid while(curr != sid): if (curr not in parent_of): err_msg = 'No augmenting path from {} to {}.'.format(sid, curr) raise StopIteration(err_msg) path.extend([parent_of[curr]]) curr = parent_of[curr].fromNode path.reverse() return path def fast_edmonds_karp(mfps): sid, tid = mfps.sourceNodeUid, mfps.terminalNodeUid get = fast_e_k_preprocess(mfps.G) no_more_paths, loop_count = False, 0 while(not no_more_paths): try: apath = fast_bfs(sid, tid, get) get = fast_augment(apath, get) loop_count += 1 except StopIteration as e: no_more_paths = True nodes = frozenset(get['nodes'].values()) arcs = frozenset({}) for from_node in get['arcs']: for to_node in get['arcs'][from_node]: for arc in get['arcs'][from_node][to_node]: arcs |= frozenset({get['arcs'][from_node][to_node][arc]}) G = DiGraph(nodes, arcs) mfps = MaxFlowProblemState(G, sourceNodeUid=sid, terminalNodeUid=tid, maxFlowProblemStateUid=mfps.maxFlowProblemStateUid) return mfps αντιπροσωπεύοντας τις πιο ενημερωμένες δίκτυο ροής και καθώς αντικατοπτρίζονται στο υπόλοιπο γράφημα αυτού του δικτύου ροής. Διαδρομές επαύξησης στο υπόλοιπο γράφημα εμφανίζονται ως κόκκινες διαδρομές και το δίφθογγος που αντιπροσωπεύει το πρόβλημα το σύνολο των κόμβοι και τόξα επηρεάζεται από ένα δεδομένο αύξηση της διαδρομής επισημαίνεται με πράσινο χρώμα. Σε κάθε περίπτωση, θα επισημάνω τα μέρη του γραφήματος που θα αλλάξουν (σε κόκκινο ή πράσινο) και στη συνέχεια θα δείξω το γράφημα μετά τις αλλαγές (μόνο σε μαύρο).
Ακολουθεί μια άλλη οπτικοποίηση του τρόπου με τον οποίο αυτός ο αλγόριθμος επιλύει ένα διαφορετικό παράδειγμα δίκτυο ροής . Παρατηρήστε ότι αυτός χρησιμοποιεί πραγματικούς αριθμούς και περιέχει πολλαπλούς τόξα με το ίδιο G και fromNode αξίες.
** Σημειώστε επίσης ότι επειδή τα τόξα με ένα 'pull' ResidualDatum ενδέχεται να αποτελούν μέρος της διαδρομής επαύξησης, οι κόμβοι που επηρεάζονται στο DiGraph του Flown Network _ ενδέχεται να μην βρίσκονται σε διαδρομή στο toNode.
Διμερή γραφήματα
Ας υποθέσουμε ότι έχουμε ένα δίφθογγος G!, G είναι διμερής εάν είναι δυνατόν να διαχωριστεί το κόμβοι σε G σε δύο σύνολα (G.setOfNodes και part_1) έτσι ώστε για οποιοδήποτε τόξο part_2 σε a το δεν μπορεί να είναι αλήθεια ότι G.setOfArcs σε a.fromNode και part_1 σε a.toNode. Το επίσης δεν μπορεί να είναι αλήθεια ότι part_1 σε a.fromNode και part_2 σε a.toNode.
Με άλλα λόγια part_2 είναι διμερής εάν μπορεί να χωριστεί σε δύο σύνολα κόμβοι έτσι ώστε κάθε τόξο πρέπει να συνδέσετε ένα κόμβος σε ένα σετ σε ένα κόμβος στο άλλο σετ.
Δοκιμή διμερούς
Ας υποθέσουμε ότι έχουμε ένα δίφθογγος G, θέλουμε να δοκιμάσουμε εάν είναι διμερής . Μπορούμε να το κάνουμε αυτό στο G με άπληστο χρωματισμό του γραφήματος σε δύο χρώματα.
Πρώτον, πρέπει να δημιουργήσουμε ένα νέο δίφθογγος O(|G.setOfNodes|+|G.setOfArcs|). Αυτό το γράφημα θα έχει το ίδιο σύνολο κόμβοι ως H, αλλά θα έχει περισσότερα τόξα από G. Κάθε τόξο G σε a θα δημιουργήσει 2 τόξα σε G; ο πρώτος τόξο θα είναι ίδιο με το H και το δεύτερο τόξο αντιστρέφει τον διευθυντή του a (a).
b = Arc(a.toNode,a.fromNode,a.datum)Αντιστοιχίες και Μέγιστοι Αντιστοιχίες
Ας υποθέσουμε ότι έχουμε ένα δίφθογγος Bipartition = coll.namedtuple('Bipartition',['firstPart', 'secondPart', 'G']) def bipartition(G): nodes = frozenset(G.setOfNodes arcs = frozenset(G.setOfArcs) arcs = arcs.union( frozenset( {Arc(a.toNode,a.fromNode,a.datum) for a in G.setOfArcs} ) ) H = DiGraph(nodes, arcs) H_as_dict = digraph_to_dict(H) color = dict([]) some_node = next(iter(H.setOfNodes)) deq = coll.deque([some_node]) color[some_node] = -1 while len(deq) > 0: curr = deq.popleft() for a in H_as_dict.get(curr): if (a.toNode not in color): color[a.toNode] = -1*color[curr] deq.extend([a.toNode]) elif(color[curr] == color[a.toNode]): print(curr,a.toNode) raise Exception('Not Bipartite.') firstPart = frozenset( {n for n in color if color[n] == -1 } ) secondPart = frozenset( {n for n in color if color[n] == 1 } ) if( firstPart.union(secondPart) != G.setOfNodes ): raise Exception('Not Bipartite.') return Bipartition(firstPart, secondPart, G) και G είναι ένα υποσύνολο του τόξα από matching. G.setOfArcs είναι ένα ταιριάζει αν για δύο τόξα matching και a σε b: matching. Με άλλα λόγια, όχι δύο τόξα σε ένα ταιριάζει μοιραστείτε ένα κόμβος .
Ταιριάζει len(frozenset( {a.fromNode} ).union( {a.toNode} ).union( {b.fromNode} ).union( {b.toNode} )) == 4, είναι η μέγιστη αντιστοίχιση εάν δεν υπάρχει άλλη ταιριάζει matching σε alt_matching έτσι ώστε G. Με άλλα λόγια, len(matching) είναι ένα μέγιστη αντιστοίχιση εάν είναι το μεγαλύτερο σετ τόξα από matching που εξακολουθεί να ικανοποιεί τον ορισμό του ταιριάζει (η προσθήκη οποιουδήποτε τόξο δεν είναι ήδη στο ταίριασμα θα σπάσει το ταιριάζει ορισμός).
ΠΡΟΣ ΤΟ μέγιστη αντιστοίχιση G.setOfArcs είναι ένα τέλειο ταίριασμα αν κάθε για κόμβος matching σε n υπάρχει ένα τόξο G.setOfArcs σε a όπου matching.
Μέγιστη διμερής αντιστοίχιση
ΠΡΟΣ ΤΟ μέγιστη διμερή αντιστοίχιση είναι ένα μέγιστη αντιστοίχιση δέκα α δίφθογγος a.fromNode == n or a.toNode == n το οποίο είναι διμερής .
Δεδομένου ότι G είναι διμερής , το πρόβλημα εύρεσης α μέγιστη διμερή αντιστοίχιση μπορεί να μετατραπεί σε α πρόβλημα μέγιστης ροής επιλύσιμο με το Έντμοντς-Καρπ αλγόριθμος και μετά το μέγιστη διμερή αντιστοίχιση μπορεί να ανακτηθεί από το διάλυμα στο πρόβλημα μέγιστης ροής .
Αφήστε G γίνε α διμερές από bipartition.
Για να το κάνω αυτό, πρέπει να δημιουργήσω ένα νέο δίφθογγος (G) με κάποια νέα κόμβοι (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 (προσθήκη a H).
Εάν FlowArcDatum(1,0) είναι σε a.fromNode και bipartition.secondPart είναι στο a.toNode, και μετά συμπεριλάβετε bipartition.firstPart σε Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)).
Ο ορισμός του a διμερής γράφημα διασφαλίζει ότι όχι τόξο συνδέει οποιοδήποτε κόμβοι όπου και τα δύο κόμβοι βρίσκονται στο ίδιο διαμέρισμα. 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Ελάχιστο κάλυμμα κόμβου
Ένα κάλυμμα κόμβου σε ένα δίφθογγος def solve_mbm( bipartition ): s = Node(uuid.uuid4(), FlowNodeDatum(0,0)) t = Node(uuid.uuid4(), FlowNodeDatum(0,0)) translate = {} arcs = frozenset([]) for a in bipartition.G.setOfArcs: if ( (a.fromNode in bipartition.firstPart) and (a.toNode in bipartition.secondPart) ): fark = Arc(a.fromNode,a.toNode,FlowArcDatum(1,0)) arcs = arcs.union({fark}) translate[frozenset({a.fromNode.uid,a.toNode.uid})] = a elif ( (a.toNode in bipartition.firstPart) and (a.fromNode in bipartition.secondPart) ): bark = Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) arcs = arcs.union({bark}) translate[frozenset({a.fromNode.uid,a.toNode.uid})] = a arcs1 = frozenset( {Arc(s,n,FlowArcDatum(1,0)) for n in bipartition.firstPart } ) arcs2 = frozenset( {Arc(n,t,FlowArcDatum(1,0)) for n in bipartition.secondPart } ) arcs = arcs.union(arcs1.union(arcs2)) nodes = frozenset( {Node(n.uid,FlowNodeDatum(0,0)) for n in bipartition.G.setOfNodes} ).union({s}).union({t}) G = DiGraph(nodes, arcs) mfp = MaxFlowProblemState(G, s.uid, t.uid, 'bipartite') result = edmonds_karp(mfp) lookup_set = {a for a in result.G.setOfArcs if (a.datum.flow > 0) and (a.fromNode.uid != s.uid) and (a.toNode.uid != t.uid)} matching = {translate[frozenset({a.fromNode.uid,a.toNode.uid})] for a in lookup_set} return matching είναι ένα σύνολο κόμβοι (G) από cover έτσι ώστε για οποιοδήποτε τόξο G.setOfNodes από a Αυτό πρέπει να ισχύει: G.setOfArcs.
Ένα ελάχιστο κάλυμμα κόμβου είναι το μικρότερο δυνατό σύνολο κόμβοι στο γράφημα που είναι ακόμα α κάλυμμα κόμβου . Το θεώρημα του König δηλώνει ότι στο a διμερής γράφημα, το μέγεθος του μέγιστη αντιστοίχιση σε αυτό το γράφημα είναι ίσο με το μέγεθος του ελάχιστο κάλυμμα κόμβου , και προτείνει πώς το κάλυμμα κόμβου μπορεί να ανακτηθεί από ένα μέγιστη αντιστοίχιση :
Ας υποθέσουμε ότι έχουμε το διμερές (a.fromNode in cover) or (a.toNode in cover) και το μέγιστη αντιστοίχιση bipartition. Ορίστε ένα νέο δίφθογγος matching, H, το τόξα σε H.setOfNodes=G.setOfNodes είναι η ένωση δύο συνόλων.
Το πρώτο σετ είναι τόξα H.setOfArcs σε a, με την αλλαγή που εάν matching και a.fromNode in bipartition.firstPart τότε a.toNode in bipartition.secondPart και a.fromNode ανταλλάσσονται στη δημιουργία τόξο δώστε τέτοια τόξα α a.toNode χαρακτηριστικό για να δείξει ότι προήλθαν από τόξα σε ένα ταιριάζει .
Το δεύτερο σετ είναι τόξα a.datum.inMatching=True ΟΧΙ στο a, με την αλλαγή που εάν matching και a.fromNode in bipartition.secondPart τότε a.toNode in bipartition.firstPart και a.fromNode ανταλλάσσονται στη δημιουργία τόξο (δώστε τέτοια τόξα α a.toNode Χαρακτηριστικό).
Στη συνέχεια, εκτελέστε ένα πρώτη αναζήτηση βάθους ( DFS ) ξεκινώντας από το καθένα κόμβος a.datum.inMatching=False σε n που δεν είναι ούτε bipartition.firstPart ούτε n == a.fromNode για κάθε τόξο n == a.toNodes σε a. Κατά τη διάρκεια του DFS, μερικοί κόμβοι επισκέπτονται και μερικά δεν είναι (αποθηκεύστε αυτές τις πληροφορίες σε ένα πεδίο matching). ο ελάχιστο κάλυμμα κόμβου είναι η ένωση του κόμβοι n.datum.visited και το κόμβοι {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (a.fromNode.datum.visited) ) }.
Αυτό μπορεί να αποδειχθεί ότι οδηγεί από ένα μέγιστη αντιστοίχιση σε ένα ελάχιστο κάλυμμα κόμβου από ένα απόδειξη με αντίφαση , Πάρε μερικά τόξο {a.fromNode for a in H.setOfArcs if (a.datum.inMatching) and (not a.toNode.datum.visited)} που υποτίθεται ότι δεν καλύπτεται και εξετάζει και τις τέσσερις περιπτώσεις σχετικά με το αν a και a.fromNode ανήκουν (είτε ως a.toNode ή toNode) σε οποιοδήποτε τόξο σε ταιριάζει fromNode. Κάθε περίπτωση οδηγεί σε αντίφαση λόγω της σειράς που επισκέπτεται το DFS κόμβοι και το γεγονός ότι matching είναι ένα μέγιστη αντιστοίχιση .
Ας υποθέσουμε ότι έχουμε μια συνάρτηση για την εκτέλεση αυτών των βημάτων και την επιστροφή του συνόλου κόμβοι που περιλαμβάνει το ελάχιστο κάλυμμα κόμβου όταν δοθεί το δίφθογγος matching, και το μέγιστη αντιστοίχιση G:
matchingΤο πρόβλημα γραμμικής ανάθεσης
Το πρόβλημα γραμμικής εκχώρησης συνίσταται στην εύρεση ενός μέγιστου βάρους αντιστοίχισης σε ένα σταθμισμένο διμερές γράφημα.
Προβλήματα όπως αυτό στην αρχή αυτής της ανάρτησης μπορούν να εκφραστούν ως πρόβλημα γραμμικής ανάθεσης . Λαμβάνοντας υπόψη ένα σύνολο εργαζομένων, ένα σύνολο εργασιών και μια συνάρτηση που δείχνει την κερδοφορία μιας ανάθεσης ενός εργαζομένου σε μία εργασία, θέλουμε να μεγιστοποιήσουμε το άθροισμα όλων των εργασιών που κάνουμε. αυτό είναι ένα πρόβλημα γραμμικής ανάθεσης .
Ας υποθέσουμε ότι ο αριθμός των εργασιών και των εργαζομένων είναι ίσος, αν και θα δείξω ότι αυτή η υπόθεση είναι εύκολο να αφαιρεθεί. Στην εφαρμογή, εκπροσωπώ βάρη τόξου με ένα χαρακτηριστικό ArcMatchingDatum = coll.namedtuple('ArcMatchingDatum', ['inMatching' ]) NodeMatchingDatum = coll.namedtuple('NodeMatchingDatum', ['visited']) def dfs_helper(snodes, G): sniter, do_stop = iter(snodes), False visited, visited_uids = set(), set() while(not do_stop): try: stack = [ next(sniter) ] while len(stack) > 0: curr = stack.pop() if curr.uid not in visited_uids: visited = visited.union( frozenset( {Node(curr.uid, NodeMatchingDatum(False))} ) ) visited_uids = visited.union(frozenset({curr.uid})) succ = frozenset({a.toNode for a in G.setOfArcs if a.fromNode == curr}) stack.extend( succ.difference( frozenset(visited) ) ) except StopIteration as e: stack, do_stop = [], True return visited def get_min_node_cover(matching, bipartition): nodes = frozenset( { Node(n.uid, NodeMatchingDatum(False)) for n in bipartition.G.setOfNodes} ) G = DiGraph(nodes, None) charcs = frozenset( {a for a in matching if ( (a.fromNode in bipartition.firstPart) and (a.toNode in bipartition.secondPart) )} ) arcs0 = frozenset( { Arc(find_node_by_uid(a.toNode.uid,G), find_node_by_uid(a.fromNode.uid,G), ArcMatchingDatum(True) ) for a in charcs } ) arcs1 = frozenset( { Arc(find_node_by_uid(a.fromNode.uid,G), find_node_by_uid(a.toNode.uid,G), ArcMatchingDatum(True) ) for a in matching.difference(charcs) } ) not_matching = bipartition.G.setOfArcs.difference( matching ) charcs = frozenset( {a for a in not_matching if ( (a.fromNode in bipartition.secondPart) and (a.toNode in bipartition.firstPart) )} ) arcs2 = frozenset( { Arc(find_node_by_uid(a.toNode.uid,G), find_node_by_uid(a.fromNode.uid,G), ArcMatchingDatum(False) ) for a in charcs } ) arcs3 = frozenset( { Arc(find_node_by_uid(a.fromNode.uid,G), find_node_by_uid(a.toNode.uid,G), ArcMatchingDatum(False) ) for a in not_matching.difference(charcs) } ) arcs = arcs0.union(arcs1.union(arcs2.union(arcs3))) G = DiGraph(nodes, arcs) bip = Bipartition({find_node_by_uid(n.uid,G) for n in bipartition.firstPart},{find_node_by_uid(n.uid,G) for n in bipartition.secondPart},G) match_from_nodes = frozenset({find_node_by_uid(a.fromNode.uid,G) for a in matching}) match_to_nodes = frozenset({find_node_by_uid(a.toNode.uid,G) for a in matching}) snodes = bip.firstPart.difference(match_from_nodes).difference(match_to_nodes) visited_nodes = dfs_helper(snodes, bip.G) not_visited_nodes = bip.G.setOfNodes.difference(visited_nodes) H = DiGraph(visited_nodes.union(not_visited_nodes), arcs) cover1 = frozenset( {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (a.fromNode.datum.visited) ) } ) cover2 = frozenset( {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (not a.toNode.datum.visited) ) } ) min_cover_nodes = cover1.union(cover2) true_min_cover_nodes = frozenset({find_node_by_uid(n.uid, bipartition.G) for n in min_cover_nodes}) return min_cover_nodes για ένα τόξο a.datum.weight.
aΑλγόριθμος Kuhn-Munkres
Ο αλγόριθμος Kuhn-Munkres λύνει το πρόβλημα γραμμικής ανάθεσης . Μια καλή εφαρμογή μπορεί να διαρκέσει WeightArcDatum = namedtuple('WeightArcDatum', [weight]) ώρα, (όπου O(N^{4}) είναι ο αριθμός των κόμβοι στο δίφθογγος αντιπροσωπεύει το πρόβλημα). Μια εφαρμογή που είναι πιο εύκολο να εξηγηθεί χρειάζεται N (για μια έκδοση που αναγεννάται DiGraphs ) και O(N^{5}) για (για μια έκδοση που διατηρεί DiGraphs ). Αυτό είναι παρόμοιο με τις δύο διαφορετικές υλοποιήσεις του Έντμοντς-Καρπ αλγόριθμος.
Για αυτήν την περιγραφή, δουλεύω μόνο με πλήρη διμερή γραφήματα (εκείνα όπου τα μισά κόμβοι βρίσκονται σε ένα μέρος του διμερές και το άλλο μισό στο δεύτερο μέρος). Στον εργαζόμενο, το κίνητρο εργασίας σημαίνει ότι υπάρχουν τόσοι εργαζόμενοι όσο και καθήκοντα.
Αυτό φαίνεται σαν μια σημαντική συνθήκη (τι γίνεται αν αυτά τα σύνολα δεν είναι ίδια!) Αλλά είναι εύκολο να διορθώσετε αυτό το ζήτημα. Μιλώ για το πώς να το κάνω αυτό στην τελευταία ενότητα.
Η έκδοση του αλγορίθμου που περιγράφεται εδώ χρησιμοποιεί τη χρήσιμη ιδέα του τόξα μηδενικού βάρους . Δυστυχώς, αυτή η έννοια έχει νόημα μόνο όταν λύνουμε ένα σμικροποίηση (εάν αντί να μεγιστοποιήσουμε τα κέρδη από τις αναθέσεις εργαζομένων-εργασιών μας, αντί να ελαχιστοποιούμε το κόστος αυτών των εργασιών).
Ευτυχώς, είναι εύκολο να μετατρέψετε ένα μέγιστο πρόβλημα γραμμικής ανάθεσης μέσα σε ελάχιστο πρόβλημα γραμμικής ανάθεσης ορίζοντας κάθε ένα τόξο O(N^{4}) βάρη έως a όπου M-a.datum.weight. Η λύση στο πρωτότυπο μεγιστοποιώντας το πρόβλημα θα είναι ίδια με τη λύση ελαχιστοποιώντας το πρόβλημα μετά το τόξο τα βάρη αλλάζουν. Επομένως, για τα υπόλοιπα, υποθέστε ότι κάνουμε αυτήν την αλλαγή.
ο Αλγόριθμος Kuhn-Munkres λύνει ελάχιστο ταίριασμα βάρους σε ένα σταθμισμένο διμερές γράφημα με μια ακολουθία του μέγιστες αντιστοιχίσεις σε μη ζυγισμένο διμερής γραφικές παραστάσεις. Εάν ένα, βρίσκουμε ένα τέλειο ταίριασμα στο δίφθογγος εκπροσώπηση του πρόβλημα γραμμικής ανάθεσης , και αν το βάρος κάθε τόξο στο ταιριάζει είναι μηδέν, τότε βρήκαμε το ελάχιστο ταίριασμα βάρους δεδομένου ότι αυτό το ταίριασμα δείχνει ότι όλα κόμβοι στο δίφθογγος υπήρξαν ταιριάζει από ένα τόξο με το χαμηλότερο δυνατό κόστος (κανένα κόστος δεν μπορεί να είναι χαμηλότερο από 0, βάσει προηγούμενων ορισμών).
Καμία άλλη τόξα μπορεί να προστεθεί στο ταιριάζει (γιατί όλα κόμβοι έχουν ήδη αντιστοιχιστεί) και όχι τόξα πρέπει να αφαιρεθεί από το ταιριάζει γιατί οποιαδήποτε πιθανή αντικατάσταση τόξο θα έχει τουλάχιστον τόσο μεγάλη αξία βάρους.
Εάν βρούμε ένα μέγιστη αντιστοίχιση απο υπογράφος από M=max({a.datum.weight for a in G.setOfArcs}) που περιέχει μόνο τόξα μηδενικού βάρους , και δεν είναι τέλειο ταίριασμα , δεν έχουμε μια πλήρη λύση (από τότε ταιριάζει δεν είναι τέλειος ). Ωστόσο, μπορούμε να παράγουμε ένα νέο δίφθογγος G αλλάζοντας τα βάρη του τόξα σε H με τρόπο που το νέο 0-βάρος τόξα εμφανίζεται και η βέλτιστη λύση του G.setOfArcs είναι το ίδιο με τη βέλτιστη λύση του H. Δεδομένου ότι εγγυόμαστε ότι τουλάχιστον ένα τόξο μηδενικού βάρους παράγεται σε κάθε επανάληψη, εγγυόμαστε ότι θα φτάσουμε σε ένα τέλειο ταίριασμα σε όχι περισσότερο από | G.setOfNodes | 2 = N 2 τέτοιες επαναλήψεις.
Ας υποθέσουμε ότι στο διμερές G, bipartition περιέχει κόμβοι που εκπροσωπούν τους εργαζομένους και bipartition.firstPart αντιπροσωπεύει κόμβοι που αντιπροσωπεύουν καθήκοντα.
Ο αλγόριθμος ξεκινά δημιουργώντας ένα νέο δίφθογγος bipartition.secondPart. 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)).
KMA: Στη συνέχεια, σχηματίστε ένα νέο δίφθογγος z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) αποτελείται μόνο από το τόξα μηδενικού βάρους από K, και το κόμβοι περιστατικό σε αυτά τόξα . Έντυπο a H στο κόμβοι στο 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)). Επιστρέψτε στην ετικέτα ΚΜΑ . Ο αλγόριθμος συνεχίζεται έως το a τέλειο ταίριασμα παράγεται. Αυτό ταιριάζει είναι επίσης η λύση στο πρόβλημα γραμμικής ανάθεσης .
H=DiGraph(nodes,arcs)Αυτή η εφαρμογή είναι def kuhn_munkres( bipartition ): nodes = bipartition.G.setOfNodes arcs = frozenset({}) for n in bipartition.firstPart: z = min( {x.datum.weight for x in bipartition.G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )} ) arcs = arcs.union( frozenset({Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) }) ) for n in bipartition.secondPart: z = min( {x.datum.weight for x in bipartition.G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )} ) arcs = arcs.union( frozenset({Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) }) ) H = DiGraph(nodes, arcs) assignment, value = dict({}), 0 not_done = True while( not_done ): zwarcs = frozenset( {a for a in H.setOfArcs if a.datum.weight == 0} ) znodes = frozenset( {n.fromNode for n in zwarcs} ).union( frozenset( {n.toNode for n in zwarcs} ) ) K = DiGraph(znodes, zwarcs) k_bipartition = bipartition(K) matching = solve_mbm( k_bipartition ) mnodes = frozenset({a.fromNode for a in matching}).union(frozenset({a.toNode for a in matching})) if( len(mnodes) == len(H.setOfNodes) ): for a in matching: assignment[ a.fromNode.uid ] = a.toNode.uid value = sum({a.datum.weight for a in matching}) not_done = False else: node_cover = get_min_node_cover(matching, bipartition(K)) z = min( frozenset( {a.datum.weight for a in H.setOfArcs if a not in node_cover} ) ) nodes = H.setOfNodes arcs1 = frozenset( {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 = frozenset( {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 = frozenset( {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)} ) arcs = arcs1.union(arcs2.union(arcs3)) H = DiGraph(nodes,arcs) return value, assignment γιατί δημιουργεί ένα νέο μέγιστη αντιστοίχιση O(N^{5}) σε κάθε επανάληψη · παρόμοια με τις προηγούμενες δύο υλοποιήσεις του Έντμοντς-Καρπ Αυτός ο αλγόριθμος μπορεί να τροποποιηθεί έτσι ώστε να παρακολουθεί την αντιστοίχιση και να τον προσαρμόζει έξυπνα σε κάθε επανάληψη. Όταν γίνει αυτό, η πολυπλοκότητα γίνεται matching. Μια πιο προηγμένη και πιο πρόσφατη έκδοση αυτού του αλγορίθμου (που απαιτεί κάποιες πιο προηγμένες δομές δεδομένων) μπορεί να εκτελεστεί σε O(N^{4}). Λεπτομέρειες τόσο για την απλούστερη εφαρμογή παραπάνω όσο και για την πιο προηγμένη εφαρμογή μπορείτε να βρείτε στη διεύθυνση αυτήν την ανάρτηση που κίνησε αυτήν την ανάρτηση ιστολογίου.
Καμία από τις εργασίες στις τόξο τα βάρη τροποποιούν την τελική εκχώρηση που επιστρέφεται από τον αλγόριθμο. Να γιατί: Δεδομένου ότι τα γραφήματα εισόδου μας είναι πάντα πλήρη διμερή γραφήματα μια λύση πρέπει να χαρτογραφεί η καθεμία κόμβος σε ένα διαμέρισμα στο άλλο κόμβος στο δεύτερο διαμέρισμα, μέσω του τόξο μεταξύ αυτών των δύο κόμβοι . Παρατηρήστε ότι οι λειτουργίες που πραγματοποιήθηκαν στο τόξο τα βάρη δεν αλλάζουν ποτέ τη σειρά (ταξινομημένη κατά βάρος) του τόξα περιστατικό σε οποιοδήποτε συγκεκριμένο κόμβος .
Έτσι, όταν ο αλγόριθμος τερματίζεται στο a τέλεια πλήρης διμερής αντιστοίχιση καθε κόμβος έχει ανατεθεί ένα τόξο μηδενικού βάρους , δεδομένου ότι η σχετική σειρά του τόξα από αυτό κόμβος δεν έχει αλλάξει κατά τη διάρκεια του αλγορίθμου και από το α τόξο μηδενικού βάρους είναι το φθηνότερο δυνατό τόξο και το τέλεια πλήρης διμερής αντιστοίχιση εγγυάται ότι ένα τέτοιο τόξο υπάρχει για καθένα κόμβος . Αυτό σημαίνει ότι η λύση που δημιουργείται είναι πράγματι η ίδια με τη λύση από το πρωτότυπο πρόβλημα γραμμικής ανάθεσης χωρίς καμία τροποποίηση του τόξο βάρη.
Μη ισορροπημένες εργασίες
Φαίνεται ότι ο αλγόριθμος είναι αρκετά περιορισμένος αφού όπως περιγράφεται λειτουργεί μόνο σε πλήρη διμερή γραφήματα (εκείνοι όπου το μισό κόμβοι βρίσκονται σε ένα μέρος του διμερές και το άλλο μισό στο δεύτερο μέρος). Στον εργαζόμενο, το κίνητρο εργασίας σημαίνει ότι υπάρχουν τόσοι εργαζόμενοι όσο οι εργασίες (φαίνεται αρκετά περιοριστικές).
Ωστόσο, υπάρχει ένας εύκολος μετασχηματισμός που καταργεί αυτόν τον περιορισμό. Ας υποθέσουμε ότι υπάρχουν λιγότεροι εργαζόμενοι από τα καθήκοντα, προσθέτουμε μερικούς πλαστά εργαζομένους (αρκετά για να δημιουργήσουμε το γράφημα που προκύπτει πλήρες διμερές γράφημα ). Κάθε πλαστά εργαζόμενος έχει τόξο κατευθύνεται από τον εργαζόμενο σε καθεμία από τις εργασίες. Κάθε τέτοια τόξο έχει βάρος 0 (η τοποθέτησή του σε αντιστοίχιση δεν δίνει επιπλέον κέρδος). Μετά από αυτήν την αλλαγή, το γράφημα είναι ένα πλήρες διμερές γράφημα για το οποίο μπορούμε να λύσουμε. Δεν έχει ξεκινήσει οποιαδήποτε εργασία που έχει ανατεθεί σε έναν πλαστό εργαζόμενο.
Ας υποθέσουμε ότι υπάρχουν περισσότερες εργασίες από τους εργαζόμενους. Προσθέτουμε μερικές πλαστές εργασίες (αρκετά για να δημιουργήσουμε το γράφημα που προκύπτει α πλήρες διμερές γράφημα ). Κάθε πλαστή εργασία έχει ένα τόξο κατευθύνεται από κάθε εργαζόμενο στην πλαστή εργασία. Κάθε τέτοια τόξο έχει βάρος 0 (η τοποθέτηση σε αντιστοίχιση δεν δίνει πρόσθετο κέρδος). Μετά από αυτήν την αλλαγή, το γράφημα είναι ένα πλήρες διμερές γράφημα για το οποίο μπορούμε να λύσουμε. Κάθε εργαζόμενος που έχει ανατεθεί σε πλαστή εργασία δεν απασχολείται κατά τη διάρκεια της περιόδου.
Ένα παράδειγμα γραμμικής ανάθεσης
Τέλος, ας κάνουμε ένα παράδειγμα με τον κωδικό που χρησιμοποιώ. Θα τροποποιήσω το παράδειγμα του προβλήματος από εδώ . Έχουμε 3 εργασίες: πρέπει καθάρισε την τουαλέτα , σκουπίζω το πάτωμα , και καθάρισε τα παράθυρα .
Οι εργαζόμενοι που είναι διαθέσιμοι για χρήση είναι Αλίκη , Βαρίδι , Κάρολος , και Ντιάν . Κάθε ένας από τους εργαζόμενους μας δίνει το μισθό που απαιτείται ανά εργασία. Εδώ είναι οι μισθοί ανά εργαζόμενο:
Καθάρισε την τουαλέτα Σκουπίζω το πάτωμα Καθάρισε τα παράθυρα Αλίκη 2 $ 3 $ 3 $ Βαρίδι 3 $ 2 $ 3 $ Κάρολος 3 $ 3 $ 2 $ Ντιάν 9 $ 9 $ 1 $
Εάν θέλουμε να πληρώσουμε το ελάχιστο χρηματικό ποσό, αλλά ακόμα να ολοκληρώσουμε όλες τις εργασίες, ποιος πρέπει να κάνει τι έργο; Ξεκινήστε εισάγοντας μια πλαστή εργασία για να κάνετε το διάγραμμα που αντιπροσωπεύει το πρόβλημα διμερές.
Καθάρισε την τουαλέτα Σκουπίζω το πάτωμα Καθάρισε τα παράθυρα Μην κάνεις τίποτα Αλίκη 2 $ 3 $ 3 $ 0 $ Βαρίδι 3 $ 2 $ 3 $ 0 $ Κάρολος 3 $ 3 $ 2 $ 0 $ Ντιάν 9 $ 9 $ 1 $ 0 $
Ας υποθέσουμε ότι το πρόβλημα έχει κωδικοποιηθεί σε ένα δίφθογγος , τότε O(N^{3}) θα λύσει το πρόβλημα και θα επιστρέψει την ανάθεση. Είναι εύκολο να επαληθεύσετε ότι το βέλτιστο (χαμηλότερο κόστος) ανάθεση θα κοστίζει 5 $.
Ακολουθεί μια οπτικοποίηση της λύσης που δημιουργεί ο παραπάνω κώδικας:
Αυτό είναι. Τώρα γνωρίζετε όλα όσα πρέπει να γνωρίζετε για το πρόβλημα γραμμικής ανάθεσης.
Μπορείτε να βρείτε όλο τον κώδικα από αυτό το άρθρο GitHub .
