Debitul maxim și problema de atribuire liniară

Iată o problemă: afacerea dvs. desemnează contractori să îndeplinească contractele. Vă uitați prin listele dvs. și decideți ce contractori sunt disponibili pentru un angajament de o lună și vă uitați prin contractele disponibile pentru a vedea care dintre ei sunt pentru sarcini de o lună. Având în vedere că știți cât de eficient poate îndeplini fiecare contractor fiecare contract, cum alocați contractori pentru a maximiza eficiența globală pentru luna respectivă?

Acesta este un exemplu de problemă de atribuire, iar problema poate fi rezolvată cu algoritmul clasic maghiar.

Algoritmul maghiar (cunoscut și ca algoritmul Kuhn-Munkres) este un algoritm de timp polinomial care maximizează potrivirea ponderii într-un grafic bipartit ponderat. Aici, antreprenorii și contractele pot fi modelate ca un grafic bipartit, cu eficiența lor ca ponderi ale muchiilor dintre contractant și nodurile contractului.

În acest articol, veți afla despre o implementare a algoritmului maghiar care utilizează algoritmul Edmonds-Karp pentru a rezolva problema de atribuire liniară. Veți afla, de asemenea, cum algoritmul Edmonds-Karp este o ușoară modificare a metodei Ford-Fulkerson și cât de importantă este această modificare.

Problema debitului maxim

Problema debitului maxim în sine poate fi descrisă informal ca problema deplasării unui fluid sau gaz printr-o rețea de conducte de la o singură sursă la un singur terminal. Acest lucru se face presupunând că presiunea din rețea este suficientă pentru a se asigura că fluidul sau gazul nu poate rămâne în nicio lungime de țeavă sau fiting de țeavă (acele locuri în care se întâlnesc lungimi diferite de țeavă).

Făcând anumite modificări în grafic, problema de atribuire poate fi transformată într-o problemă de debit maxim.

Preliminarii

Ideile necesare pentru rezolvarea acestor probleme apar în multe discipline matematice și de inginerie, adesea concepte similare sunt cunoscute sub denumiri diferite și exprimate în moduri diferite (de exemplu, matrice de adiacență și liste de adiacență). Deoarece aceste idei sunt destul de ezoterice, se fac alegeri cu privire la modul în care aceste concepte vor fi definite în general pentru orice cadru dat.

Acest articol nu va presupune nicio cunoștințe anterioare dincolo de o mică teorie introductivă a seturilor.

Implementările din acest post reprezintă problemele ca grafice direcționate (digraf).

DiGraphs

Un digraf are două atribute, setOfNodes și setOfArcs . Ambele aceste atribute sunt seturi (colecții neordonate). În blocurile de cod din această postare, folosesc de fapt setul înghețat al lui Python, dar acest detaliu nu este deosebit de important.

 DiGraph = namedtuple('DiGraph', ['setOfNodes','setOfArcs'])

(Notă: acesta și toate celelalte coduri din acest articol sunt scrise în Python 3.6.)

Noduri

Un nod n este compus din două atribute:

• n.uid : un identificator unic.

  Aceasta înseamnă că pentru oricare două noduri x și y ,

 x.uid != y.uid

• n.datum : Acesta reprezintă orice obiect de date.

 Node = namedtuple('Node', ['uid','datum'])

Arcuri

Un arc a este compus din trei atribute:

• a.fromNode : Acesta este un nod , așa cum este definit mai sus.

• a.toNode : Acesta este un nod , așa cum este definit mai sus.

• a.datum : Acesta reprezintă orice obiect de date.

 Arc = namedtuple('Arc', ['fromNode','toNode','datum'])

Setul de arce din digraf reprezintă o relație binară pe nodurile din digraf . Existența arcului a implică faptul că există o relație între a.fromNode și a.toNode .

Într-un graf direcționat (spre deosebire de un graf nedirecționat), existența unei relații între a.fromNode și a.toNode nu implică că există o relație similară între a.toNode și a.fromNode .

Acest lucru se datorează faptului că într-un grafic nedirecționat, relația care este exprimată nu este neapărat simetrică.

DiGraphs

Nodurile și arcele pot fi folosite pentru a defini un digraf , dar pentru comoditate, în algoritmii de mai jos, un digraf va fi reprezentat folosind ca dicționar.

Iată o metodă care poate converti reprezentarea grafică de mai sus într-o reprezentare de dicționar similară cu aceasta:

 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

Și iată încă unul care îl transformă într-un dicționar de dicționare, o altă operație care va fi utilă:

 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

Când articolul vorbește despre un digraf așa cum este reprezentat de un dicționar, va menționa G_as_dict pentru a se referi la el.

Uneori este util să preluați un nod dintr-un digraf G prin el prin uid (identificatorul unic):

 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()

În definirea graficelor, oamenii folosesc uneori termenii nod și vârf pentru a se referi la același concept; același lucru este valabil și pentru termenii arc și margine.

Două reprezentări grafice populare în Python sunt aceasta care utilizează dicționare și alta care utilizează obiecte pentru a reprezenta grafice. Reprezentarea din această postare se află undeva între aceste două reprezentări utilizate în mod obișnuit.

Aceasta este reprezentarea mea digraf . Sunt multe asemenea, dar acesta este al meu.

Plimbări și poteci

Fie S_Arcs o secvență finită (colecție ordonată) de arce într-un digraf G astfel încât dacă a este orice arc în S_Arcs cu excepția ultimului, și b urmează a în secvență, atunci trebuie să existe un nod n = a.fromNode în G.setOfNodes astfel încât a.toNode = b.fromNode .

Pornind de la primul arc din S_Arcs și continuând până la ultimul arc din S_Arcs , colectați (în ordinea întâlnirii) toate nodurile n așa cum sunt definite mai sus între fiecare două arce consecutive din S_Arcs . Etichetați colecția ordonată de noduri colectate în timpul acestei operațiuni 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

• Dacă vreun nod apare de mai multe ori în secvența S_Nodes , atunci numiți S_Arcs a Walk on digraf G .

• În caz contrar, apelați S_Arcs o cale de la list(S_Nodes)[0] la list(S_Nodes)[-1] pe digraful G .

Nodul sursă

Apelați nodul s un nod sursă în digraful G dacă s este în G.setOfNodes și G.setOfArcs nu conține a arc astfel încât 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

Nodul terminal

Apelați nodul t un nod terminal în digraful G dacă t este în G.setOfNodes și G.setOfArcs nu conține niciun arc a astfel încât 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

Taieturi si taieturi st

O cut a unui digraf conectat G este un subset de arce din G.setOfArcs care partiţionează setul de noduri G.setOfNodes în G . G este conectat dacă fiecare nod n din G.setOfNodes și are cel puțin un arc a în G.setOfArcs astfel încât fie n = a.fromNode sau n = a.toNode , dar a.fromNode != a.toNode .

 Cut = namedtuple('Cut', ['setOfCutArcs'])

Definiția de mai sus se referă la un subset de arce , dar poate defini și o partiție a nodurilor G.setOfNodes .

Pentru funcțiile predecessors_of și successors_of , n este un nod din mulțimea G.setOfNodes al digrafului G , iar cut este o tăietură a lui 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

Fie cut o tăietură a digrafului 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 este o tăietură a digrafului G dacă: (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 se numește xy cut dacă (x in get_first_part(cut, G)) and (y in get_second_part(cut, G) ) and (x != y) . Când nodul x dintr-o cut xy este un nod sursă și nodul y din tăietura xy este un nod terminal , atunci această tăietură se numește o tăietură st .

 STCut = namedtuple('STCut', ['s','t','cut'])

Rețele de flux

Puteți folosi un digraf G pentru a reprezenta o rețea de flux.

Atribuiți fiecărui nod n , unde n este în G.setOfNodes un n.datum care este un FlowNodeDatum :

 FlowNodeDatum = namedtuple('FlowNodeDatum', ['flowIn','flowOut'])

Atribuiți fiecărui arc a , unde a este în G.setOfArcs și a.datum care este un FlowArcDatum .

 FlowArcDatum = namedtuple('FlowArcDatum', ['capacity','flow'])

flowNodeDatum.flowIn și flowNodeDatum.flowOut sunt numere reale pozitive.

flowArcDatum.capacity și flowArcDatum.flow sunt, de asemenea, numere reale pozitive.

Pentru fiecare nod nod n din 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})

Digraful G reprezintă acum o rețea de flux .

Curgerea lui G se referă la a.flow pentru toate arcele a din G .

Fluxuri fezabile

Fie digraful G o rețea de curgere .

Rețeaua de curgere reprezentată de G are fluxuri fezabile dacă:

1. Pentru fiecare nod n din G.setOfNodes cu excepția nodurilor sursă și a nodurilor terminale : n.datum.flowIn = n.datum.flowOut .

2. Pentru fiecare arc a din G.setOfNodes : a.datum.capacity <= a.datum.flow .

Condiția 1 se numește constrângere de conservare.

Condiția 2 se numește constrângere de capacitate.

Capacitate de tăiere

Capacitatea de tăiere a unui st cut stCut cu nodul sursă s și nodul terminal t al unei rețele de curgere reprezentată printr-un digraf G este:

 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

Tăierea capacității minime

Fie stCut = stCut(s,t,cut) să fie o primă tăietură a unei rețele de curgere reprezentată printr-un digraf G .

stCut este capacitatea minimă de tăiere a rețelei de curgere reprezentată de G dacă nu există alt st cut stCutCompetitor în această rețea de flux astfel încât:

 cut_capacity(stCut, G) < cut_capacity(stCutCompetitor, G)

Îndepărtarea fluxurilor

Aș dori să mă refer la digraful care ar fi rezultatul luării unui digraf G și îndepărtarea tuturor datelor de flux de la toate nodurile din G.setOfNodes și, de asemenea, toate arcele din 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)

Problemă de debit maxim

O rețea de flux reprezentată ca un digraf G , un nod sursă s în G.setOfNodes și un nod terminal t în G.setOfNodes , G poate reprezenta o problemă de debit maxim dacă:

 (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)

Etichetați această reprezentare:

 MaxFlowProblemState = namedtuple('MaxFlowProblemState', ['G','sourceNodeUid','terminalNodeUid','maxFlowProblemStateUid'])

Unde sourceNodeUid = s.uid , terminalNodeUid = t.uid și maxFlowProblemStateUid este un identificator pentru instanța problemei.

Soluție cu debit maxim

Fie maxFlowProblem să reprezinte o problemă de debit maxim . Soluția pentru maxFlowProblem poate fi reprezentată printr-o rețea de flux reprezentată ca un digraf H .

Digraful H este o soluție fezabilă la problema debitului maxim pe intrarea python maxFlowProblem dacă:

1. strip_flows(maxFlowProblem.G) == strip_flows(H) .

2. H este o rețea de curgere și are debite fezabile .

Dacă în plus față de 1 și 2:

1. Nu poate exista o altă rețea de flux reprezentată de digraful K astfel încât strip_flows(G) == strip_flows(K) și find_node_by_uid(t.uid,G).flowIn < find_node_by_uid(t.uid,K).flowIn .

Atunci H este, de asemenea, o soluție optimă pentru maxFlowProblem .

Cu alte cuvinte, o soluție fezabilă de debit maxim poate fi reprezentată printr-un digraf , care:

1. Este identic cu digraful G al problemei de curgere maximă corespunzătoare, cu excepția faptului că n.datum.flowIn , n.datum.flowOut și a.datum.flow ale oricăruia dintre noduri și arcuri pot fi diferite.

2. Reprezintă o rețea de flux care are fluxuri fezabile .

Și, poate reprezenta o soluție optimă de debit maxim dacă în plus:

1. flowIn pentru nodul corespunzător nodului terminal din problema debitului maxim este cât mai mare posibil (când condițiile 1 și 2 sunt încă îndeplinite).

Dacă digraful H reprezintă o soluție fezabilă de curgere maximă : find_node_by_uid(s.uid,H).flowOut = find_node_by_uid(t.uid,H).flowIn Aceasta rezultă din teorema debitului maxim, minut (discutată mai jos). În mod informal, deoarece se presupune că H are fluxuri fezabile, aceasta înseamnă că fluxul nu poate fi nici „creat” (cu excepția nodului sursă s ) și nici „distrus” (cu excepția nodului terminal t ) în timp ce traversează orice (alt) nod ( constrângeri de conservare ).

Deoarece o problemă de debit maxim conține doar un singur nod sursă s și un singur nod terminal t , tot fluxul „creat” la s trebuie „distrus” la t sau rețeaua de curgere nu are fluxuri fezabile ( constrângerea de conservare ar fi fost încălcată ).

Fie digraful H o soluție de debit maxim fezabil ; valoarea de mai sus se numește prima valoare a debitului lui H .

Lăsa:

 mfps=MaxFlowProblemState(H, maxFlowProblem.sourceNodeUid, maxFlowProblem.terminalNodeUid, maxFlowProblem.maxFlowProblemStateUid)

Aceasta înseamnă că mfps este o stare succesoare a maxFlowProblem , ceea ce înseamnă doar că mfps este exact ca maxFlowProblem , cu excepția faptului că valorile a.flow pentru arcele a din maxFlowProblem.setOfArcs pot fi diferite de a.flow pentru arcurile a în 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 st flow') return flow_to_t

Iată o vizualizare a unui mfps împreună cu maxFlowProb asociat. Fiecare arc a din imagine are o etichetă, aceste etichete sunt a.datum.flowFrom / a.datum.flowTo , fiecare nod n din imagine are o etichetă, iar aceste etichete sunt n.uid {n.datum.flowIn / a.datum.flowOut} .

St Cut Flow

Fie mfps să reprezinte un MaxFlowProblemState și stCut să reprezinte o tăietură de mfps.G . Fluxul de tăiere al stCut este definit:

 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

St cut flow este suma fluxurilor de la partiția care conține nodul sursă la partiția care conține nodul terminal minus suma fluxurilor de la partiția care conține nodul terminal la partiția care conține nodul sursă .

Debit maxim, tăiere minimă

Fie maxFlowProblem să reprezinte o problemă de debit maxim și soluția pentru maxFlowProblem să fie reprezentată de o rețea de flux reprezentată ca digraf H .

Fie minStCut reducerea capacității minime a rețelei de curgere reprezentată de maxFlowProblem.G .

Deoarece, în problema debitului maxim, fluxul provine dintr-un singur nod sursă și se termină la un singur nod terminal și, din cauza constrângerilor de capacitate și a constrângerilor de conservare , știm că tot fluxul care intră în maxFlowProblem.terminalNodeUid trebuie să traverseze orice tăietură . , în special trebuie să traverseze minStCut . Acest lucru înseamnă:

 get_flow_value(H, maxFlowProblem) <= cut_capacity(minStCut, maxFlowProblem.G)

Rezolvarea problemei debitului maxim

Ideea de bază pentru rezolvarea unei probleme de debit maxim maxFlowProblem este de a începe cu o soluție de debit maxim reprezentată de digraful H . Un astfel de punct de plecare poate fi H = strip_flows(maxFlowProblem.G) . Sarcina este apoi de a folosi H și printr-o modificare lacomă a valorilor a.datum.flow ale unor arce a în H.setOfArcs pentru a produce o altă soluție de debit maxim reprezentată de digraful K , astfel încât K să nu reprezinte încă o rețea de curgere cu debite fezabile. și get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) . Atâta timp cât acest proces continuă, calitatea ( get_flow_value(K, maxFlowProblem) ) a celei mai recente soluții de debit maxim întâlnit ( K ) este mai bună decât orice altă soluție de debit maxim care a fost găsită. Dacă procesul ajunge într-un punct în care știe că nicio altă îmbunătățire nu este posibilă, procesul se poate termina și va returna soluția optimă de debit maxim .

Descrierea de mai sus este generală și omite multe dovezi, cum ar fi dacă un astfel de proces este posibil sau cât timp poate dura, voi da mai multe detalii și algoritmul.

Debitul maxim, teorema tăieturii minime

Din cartea Fluxuri în rețele de Ford și Fulkerson, enunțul debitului maxim, teorema tăieturii minime (Teorema 5.1) este:

Pentru orice rețea, valoarea debitului maxim de la s la t este egală cu capacitatea minimă de tăiere a tuturor tăierilor care separă s și t .

Folosind definițiile din această postare, asta se traduce prin:

Soluția unui maxFlowProblem reprezentat de o rețea de flux reprezentată ca digraf H este optimă dacă:

 get_flow_value(H, maxFlowProblem) == cut_capacity(minStCut, maxFlowProblem.G)

Îmi place această dovadă a teoremei, iar Wikipedia are alta.

Teorema debitului maxim, tăiere minimă este utilizată pentru a demonstra corectitudinea și completitudinea metodei Ford-Fulkerson .

De asemenea, voi da o demonstrație a teoremei în secțiunea după creșterea căilor .

Metoda Ford-Fulkerson și algoritmul Edmonds-Karp

CLRS definește metoda Ford-Fulkerson astfel (secțiunea 26.2):

 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

Graficul rezidual

Graficul rezidual al unei rețele de flux reprezentat ca digraf G poate fi reprezentat ca un digraf 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) returnează suma a.datum.capacity pentru toate arcurile din submulțimea G.setOfArcs unde arcul a este în submulțime dacă a.fromNode = n și a.toNode = u .

• agg_n_to_u_cap(n,u,G_as_dict) returnează suma a.datum.flow pentru toate arcele din submulțimea G.setOfArcs unde arcul a este în submulțime dacă a.fromNode = n și a.toNode = u .

Pe scurt, graficul rezidual G_f reprezintă anumite acțiuni care pot fi efectuate pe digraful G .

Fiecare pereche de noduri n,u din G.setOfNodes a rețelei de curgere reprezentată de digraful G poate genera 0, 1 sau 2 arce în graficul rezidual G_f al lui G .

1. Perechea n,u nu generează niciun arc în G_f dacă nu există un arc a în G.setOfArcs astfel încât a.fromNode = n și a.toNode = u .

2. Perechea n,u generează arcul a în G_f.setOfArcs unde a reprezintă un arc etichetat ca un arc de flux de împingere de la n la u a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) dacă n_to_u_cap_sum > n_to_u_flow_sum .

3. Perechea n,u generează arcul a în G_f.setOfArcs unde a reprezintă un arc etichetat ca arc de curgere de tragere de la n la u a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) dacă n_to_u_flow_sum > 0.0 .

• Fiecare arc de flux de împingere în G_f.setOfArcs reprezintă acțiunea de a adăuga un total de x <= n_to_u_cap_sum - n_to_u_flow_sum flux la arce din submulțimea G.setOfArcs unde arcul a este în submult dacă a.fromNode = n și a.toNode = u .

• Fiecare arc de flux de tragere din G_f.setOfArcs reprezintă acțiunea de a scădea un total de x <= n_to_u_flow_sum flux la arce din submulțimea G.setOfArcs unde arcul a este în submulțime dacă a.fromNode = n și a.toNode = u .

Efectuarea unei acțiuni individuale de împingere sau tragere din G_f pe arcurile aplicabile din G ar putea genera o rețea de curgere fără fluxuri fezabile, deoarece constrângerile de capacitate sau constrângerile de conservare ar putea fi încălcate în rețeaua de curgere generată.

Iată o vizualizare a graficului rezidual din exemplul anterior de vizualizare a unei soluții de curgere maximă , în vizualizare fiecare arc a reprezintă a.residualCapacity .

Calea de creștere

Fie maxFlowProblem o problemă de debit maxim și G_f = get_residual_graph_of(G) graficul rezidual al maxFlowProblem.G .

O cale de augmentingPath pentru maxFlowProblem este orice cale de la find_node_by_uid(maxFlowProblem.sourceNode,G_f) la find_node_by_uid(maxFlowProblem.terminalNode,G_f) .

Se dovedește că o cale de augmentingPath poate fi aplicată unei soluții de debit maxim reprezentată de digraful H generând o altă soluție de debit maxim reprezentată de digraful K unde get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) dacă H nu este optim .

Iată cum:

 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

În cele de mai sus, TOL este o anumită valoare de toleranță pentru rotunjirea valorilor debitului în rețea. Acest lucru este pentru a evita imprecizia în cascadă a calculelor în virgulă mobilă. Deci, de exemplu, am folosit TOL = 10 pentru a însemna rotunjirea la 10 cifre semnificative.

Fie K = augment(augmentingPath, H) , apoi K reprezintă o soluție fezabilă de flux maxim pentru maxFlowProblem . Pentru ca afirmația să fie adevărată, rețeaua de curgere reprezentată de K trebuie să aibă debite fezabile (să nu încalce constrângerea de capacitate sau constrângerea de conservare .

Iată de ce: în metoda de mai sus, fiecare nod adăugat la noua rețea de flux reprezentată de digraful K este fie o copie exactă a unui nod din digraful H , fie un nod n care a avut același număr adăugat la n.datum.flowIn ca sale n.datum.flowOut . Aceasta înseamnă că constrângerea de conservare este satisfăcută în K atâta timp cât a fost satisfăcută în H . Constrângerea de conservare este satisfăcută deoarece verificăm în mod explicit că orice arc nou a din rețea are a.datum.flow <= a.datum.capacity ; astfel, atâta timp cât arcele din mulțimea H.setOfArcs care au fost copiate nemodificate în K.setOfArcs nu încalcă constrângerea de capacitate , atunci K nu încalcă constrângerea de capacitate .

De asemenea, este adevărat că get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) dacă H nu este optim .

Iată de ce: Pentru ca o cale de augmentingPath să existe în reprezentarea digraf a graficului rezidual G_f al unei probleme de flux maxim maxFlowProblem , atunci ultimul arc a pe augmentingPath trebuie să fie un arc „push” și trebuie să aibă a.toNode == maxFlowProblem.terminalNode . O cale de creștere este definită ca una care se termină la nodul terminal al problemei fluxului maxim pentru care este o cale de creștere . Din definiția graficului rezidual , este clar că ultimul arc dintr-o cale de creștere pe acel grafic rezidual trebuie să fie un arc de „împingere” deoarece orice arc de „tragere” b din calea de creștere va avea b.toNode == maxFlowProblem.terminalNode și b.fromNode != maxFlowProblem.terminalNode din definiția căii . În plus, din definiția căii , este clar că nodul terminal este modificat o singură dată prin metoda de augment . Astfel, augment modifică maxFlowProblem.terminalNode.flowIn exact o dată și crește valoarea lui maxFlowProblem.terminalNode.flowIn deoarece ultimul arc din augmentingPath trebuie să fie arcul care provoacă modificarea în maxFlowProblem.terminalNode.flowIn în timpul augment . Din definiția de creștere, așa cum se aplică arcurilor „împingere”, augment poate maxFlowProblem.terminalNode.flowIn doar mărită, nu redusă.

Câteva dovezi de la Sedgewick și Wayne

Cartea Algoritmi, ediția a patra de Robert Sedgewich și Kevin Wayne are câteva dovezi minunate și scurte (paginile 892-894) care vor fi utile. Le voi recrea aici, deși voi folosi limbajul care se potrivește cu definițiile anterioare. Etichetele mele pentru dovezi sunt aceleași ca în cartea Sedgewick.

Propunerea E: Pentru orice digraf H care reprezintă o soluție fezabilă de debit maxim la o problemă de debit maxim maxFlowProblem , pentru orice stCut get_stcut_flow(stCut,H,maxFlowProblem) = get_flow_value(H, maxFlowProblem) .

Dovada: Let stCut=stCut(maxFlowProblem.sourceNode,maxFlowProblem.terminalNode,set([a for a in H.setOfArcs if a.toNode == maxFlowProblem.terminalNode])) . Propoziţia E este valabilă pentru stCut direct din definiţia valorii st de curgere . Să presupunem că acolo dorim să mutăm un nod n din partiția s ( get_first_part(stCut.cut, G) ) și în partiția t (get_second_part(stCut.cut, G)) , pentru a face acest lucru trebuie să schimbăm stCut.cut , care ar putea schimba stcut_flow = get_stcut_flow(stCut,H,maxFlowProblem) și ar putea invalida propoziția E . Cu toate acestea, să vedem cum se va schimba valoarea stcut_flow pe măsură ce facem această modificare. nodul n este la echilibru, ceea ce înseamnă că suma debitului în nodul n este egală cu suma debitului din el (acest lucru este necesar pentru ca H să reprezinte o soluție fezabilă ). Observați că tot fluxul care face parte din stcut_flow care intră în nodul n intră în el din partiția s (fluxul care intră în nodul n din partiția t, fie direct, fie indirect, nu ar fi fost numărat în valoarea stcut_flow deoarece se îndreaptă într-o direcție greșită pe baza definiţiei). În plus, tot fluxul care iese din n va curge în cele din urmă (direct sau indirect) în nodul terminal (demonstrat mai devreme). Când mutam nodul n în partiția t, tot fluxul care intră în n din partiția s trebuie adăugat la noua valoare stcut_flow ; totuși, tot fluxul care iese din n trebuie să fie scăzut din noua valoare stcut_flow ; partea de flux direct în partiția t este scăzută deoarece acest flux este acum intern noii partiții t și nu este numărat ca stcut_flow . Partea fluxului de la n îndreptarea către nodurile din partiția s trebuie, de asemenea, scăzută din stcut_flow : După ce n este mutat în partiția t, aceste fluxuri vor fi direcționate din partiția t și în partiția s și așadar nu trebuie luate în considerare în stcut_flow , deoarece aceste fluxuri sunt eliminate fluxul de intrare în partiția s și trebuie reduse cu suma acestor fluxuri și fluxul de ieșire din partiția s în partiția t (unde toate fluxurile din st trebuie să ajungă) trebuie redus cu aceeași cantitate. Deoarece nodul n era la echilibru înainte de proces, actualizarea va fi adăugat aceeași valoare la noua valoare stcut_flow așa cum a scăzut, lăsând astfel propoziția E adevărată după actualizare. Validitatea propoziției E decurge apoi din inducerea dimensiunii partiției t.

Iată câteva exemple de rețele de flux pentru a ajuta la vizualizarea cazurilor mai puțin evidente în care propoziția E este valabilă; în imagine, zonele roșii indică partiția s, zonele albastre reprezintă partiția t, iar arcele verzi indică o tăietură st . În a doua imagine, fluxul dintre nodul A și nodul B crește, în timp ce fluxul în nodul terminal t nu se modifică.:

Corolar: nicio valoare a debitului st cut nu poate depăși capacitatea oricărei st cut .

Propoziţia F. (debit maxim, teorema de tăiere min): Fie f un debit st . Următoarele 3 condiții sunt echivalente:

1. Există o tăietură st a cărei capacitate este egală cu valoarea debitului f .

2. f este un debit maxim .

3. Nu există o cale de creștere în raport cu f .

Condiția 1 implică condiția 2 prin corolar. Condiția 2 implică condiția 3 deoarece existența unui drum de creștere implică existența unui flux cu valori mai mari, contrazicând maximalitatea lui f . Condiția 3 implică condiția 1: Fie C_s mulțimea tuturor nodurilor la care se poate ajunge din s cu o cale de creștere în graficul rezidual . Fie C_t arcele rămase, atunci t trebuie să fie în C_t (prin presupunerea noastră). Arcele care se încrucișează de la C_s la C_t formează apoi o tăietură st care conține doar arce a unde fie a.datum.capacity = a.datum.flow sau a.datum.flow = 0.0 . Dacă ar fi altfel, atunci nodurile conectate printr-un arc cu capacitatea reziduală rămasă la C_s ar fi în setul C_s , deoarece ar exista atunci o cale de creștere de la s la un astfel de nod . Debitul prin prima tăietură este egal cu capacitatea primei tăieturi (deoarece arcurile de la C_s la C_t au debit egal cu capacitatea) și, de asemenea, cu valoarea primului flux (prin propoziția E ).

Această afirmație a debitului maxim, teorema tăieturii minime implică declarația anterioară din Fluxuri în rețele.

Corolar (proprietatea de integralitate): Când capacitățile sunt numere întregi, există un flux maxim cu valori întregi, iar algoritmul Ford-Fulkerson îl găsește.

Dovada: Fiecare cale de creștere crește fluxul cu un număr întreg pozitiv, minimul capacităților neutilizate din arcele de „împingere” și fluxurile din arcele de „tragere”, toate fiind întotdeauna numere întregi pozitive.

Acest lucru justifică descrierea metodei Ford-Fulkerson de la CLRS . Metoda este de a continua să găsești căi de creștere și să aplici augment la cea mai recentă maxFlowSolution vine cu soluții mai bune, până când nu mai există cale de creștere, ceea ce înseamnă că cea mai recentă soluție de debit maxim este optimă .

De la Ford-Fulkerson la Edmonds-Karp

Restul întrebărilor referitoare la rezolvarea problemelor de debit maxim sunt:

1. Cum ar trebui să fie construite căile de creștere ?

2. Se va termina metoda dacă folosim numere reale și nu numere întregi?

3. Cât timp va dura să se rezilieze (dacă se întâmplă)?

Algoritmul Edmonds-Karp specifică că fiecare cale de creștere este construită printr-o primă căutare în lățime (BFS) a graficului rezidual ; rezultă că această decizie de la punctul 1 de mai sus va forța și algoritmul să se termine (punctul 2) și permite determinarea complexității asimptotice de timp și spațiu.

Mai întâi, iată o implementare BFS :

 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

Am folosit un deque din modulul de colecții Python.

Pentru a răspunde la întrebarea 2 de mai sus, voi parafraza o altă dovadă de la Sedgewick și Wayne: Propunerea G. Numărul de căi de creștere necesare în algoritmul Edmonds-Karp cu N noduri și A arce este de cel mult NA/2 . Dovada: Fiecare cale de creștere are un arc de blocaj - un arc care este șters din graficul rezidual deoarece corespunde fie unui arc de „împingere” care devine umplut la capacitate, fie unui arc de „tragere” prin care fluxul devine 0. De fiecare dată când un arcul devine un arc de blocaj , lungimea oricărei căi de creștere prin acesta trebuie să crească cu un factor de 2. Acest lucru se datorează faptului că fiecare nod dintr-o cale poate apărea o singură dată sau deloc (din definiția căii ) deoarece căile sunt explorat de la cea mai scurtă cale la cea mai lungă, ceea ce înseamnă că cel puțin încă un nod trebuie vizitat de următoarea cale care trece prin nodul de blocaj specific, ceea ce înseamnă încă 2 arce pe cale înainte de a ajunge la nod . Deoarece calea de creștere este de cel mult N lungime, fiecare arc poate fi pe cel mult N/2 căi de creștere , iar numărul total de căi de creștere este de cel mult NA/2 .

Algoritmul Edmonds-Karp se execută în O(NA^2) . Dacă cel mult NA/2 căi vor fi explorate în timpul algoritmului și explorarea fiecărei căi cu BFS este N+A , atunci termenul cel mai semnificativ al produsului și, prin urmare, complexitatea asimptotică este O(NA^2) .

Fie mfp un 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

Versiunea de mai sus este ineficientă și are o complexitate mai slabă decât O(NA^2) , deoarece construiește o nouă soluție de debit maxim și un nou grafic rezidual de fiecare dată (în loc să modifice digrafele existente pe măsură ce algoritmul avansează). Pentru a ajunge la o soluție adevărată O(NA^2) , algoritmul trebuie să mențină atât digraful care reprezintă starea problemei debitului maxim, cât și graficul rezidual asociat. Deci algoritmul trebuie să evite iterarea peste arce și noduri în mod inutil și să își actualizeze valorile și valorile asociate în graficul rezidual doar dacă este necesar.

Pentru a scrie un algoritm Edmonds Karp mai rapid, am rescris mai multe bucăți de cod din cele de mai sus. Sper că parcurgerea codului care a generat un nou digraf a fost utilă pentru a înțelege ce se întâmplă. În algoritmul rapid, folosesc câteva trucuri noi și structuri de date Python pe care nu vreau să le trec în detaliu. Voi spune că a.fromNode și a.toNode sunt acum tratate ca șiruri și uid-uri către noduri . Pentru acest cod, să fie mfps un 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 st 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

Iată o vizualizare a modului în care acest algoritm rezolvă exemplul de rețea de flux de sus. Vizualizarea arată pașii așa cum sunt reflectați în digraful G reprezentând cea mai recentă rețea de flux și așa cum sunt reflectați în graficul rezidual al acelei rețele de flux. Căile de creștere în graficul rezidual sunt afișate ca căi roșii, iar digraful care reprezintă problema setul de noduri și arce afectate de o anumită cale de creștere este evidențiat în verde. În fiecare caz, voi evidenția părțile din grafic care vor fi modificate (în roșu sau verde) și apoi voi afișa graficul după modificări (doar în negru).

Iată o altă vizualizare a modului în care acest algoritm rezolvă un exemplu de rețea de flux diferit. Observați că acesta folosește numere reale și conține mai multe arce cu aceleași valori fromNode și toNode .

**De asemenea, observați că, deoarece arcurile cu un ResidualDatum „pull” pot face parte din Augmenting Path, nodurile afectate în DiGraph-ul rețelei Flown _s-ar putea să nu fie pe o cale în G! .

Grafice bipartite

Să presupunem că avem un digraf G , G este bipartit dacă este posibil să partiționăm nodurile din G.setOfNodes în două seturi ( part_1 și part_2 ) astfel încât pentru orice arc a din G.setOfArcs nu poate fi adevărat că a.fromNode din part_1 și a.toNode în part_1 . De asemenea, nu poate fi adevărat că a.fromNode în part_2 și a.toNode în part_2 .

Cu alte cuvinte, G este bipartit dacă poate fi împărțit în două seturi de noduri , astfel încât fiecare arc trebuie să conecteze un nod dintr-un set la un nod din celălalt set.

Testarea Bipartită

Să presupunem că avem un digraf G , vrem să testăm dacă este bipartit . Putem face acest lucru în O(|G.setOfNodes|+|G.setOfArcs|) colorând lacom graficul în două culori.

În primul rând, trebuie să generăm un nou digraf H . Acest grafic va avea același set de noduri ca G , dar va avea mai multe arce decât G Fiecare arc a din G va crea 2 arce în H ; primul arc va fi identic cu a , iar al doilea arc inversează directorul lui 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)

Potriviri și potriviri maxime

Să presupunem că avem un digraf G și matching este un subset de arce din G.setOfArcs . matching este o potrivire dacă pentru oricare două arce a și b din matching : len(frozenset( {a.fromNode} ).union( {a.toNode} ).union( {b.fromNode} ).union( {b.toNode} )) == 4 . Cu alte cuvinte, nici două arcuri dintr-o potrivire nu au un nod .

Potrivirea matching , este o potrivire maximă dacă nu există altă potrivire alt_matching în G , astfel încât len(matching) < len(alt_matching) . Cu alte cuvinte, matching este o potrivire maximă dacă este cel mai mare set de arce din G.setOfArcs care încă satisface definiția potrivirii (adăugarea oricărui arc care nu este deja în potrivire va rupe definiția de potrivire ).

O matching maximă este o potrivire perfectă dacă fiecare pentru nodul n din G.setOfArcs există un arc a în matching unde a.fromNode == n or a.toNode == n .

Potrivire bipartită maximă

O potrivire bipartită maximă este o potrivire maximă pe un digraf G care este bipartit .

Având în vedere că G este bipartit , problema găsirii unei potriviri bipartite maxime poate fi transformată într-o problemă de debit maxim rezolvabilă cu algoritmul Edmonds-Karp și apoi potrivirea bipartită maximă poate fi recuperată din soluția la problema debitului maxim .

Fie bipartition o bipartiție a lui G

Pentru a face acest lucru, trebuie să generez un nou digraf ( H ​​) cu câteva noduri noi ( H.setOfNodes ) și niște arce noi ( H.setOfArcs ). H.setOfNodes conține toate nodurile din G.setOfNodes și încă două noduri , s (un nod sursă ) și t (un nod terminal ).

H.setOfArcs va conține câte un arc pentru fiecare G.setOfArcs . Dacă un arc a este în G.setOfArcs și a.fromNode este în bipartition.firstPart și a.toNode este în bipartition.secondPart , atunci includeți a în H (adăugând un FlowArcDatum(1,0) ).

Dacă a.fromNode este în bipartition.secondPart și a.toNode este în bipartition.firstPart , atunci includeți Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) în H.setOfArcs .

Definiția unui graf bipartit asigură că niciun arc nu conectează niciun nod în care ambele noduri sunt în aceeași partiție. H.setOfArcs conține, de asemenea, un arc de la nodurile s la fiecare nod din bipartition.firstPart . În cele din urmă, H.setOfArcs conține un arc pentru fiecare nod din bipartition.secondPart la nodul t . a.datum.capacity = 1 pentru toate a din H.setOfArcs .

Mai întâi partiționați nodurile din G.setOfNodes cele două seturi disjunse ( part1 și part2 ) astfel încât niciun arc din G.setOfArcs să nu fie direcționat de la un set la același set (această partiție este posibilă deoarece G este bipartit ). Apoi, adăugați toate arcurile din G.setOfArcs care sunt direcționate de la partea 1 la part2 H.setOfArcs part1 Apoi creați un singur nod sursă s și un singur nod terminal t și creați mai multe arce

Apoi, construiți un 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

Acoperire minimă a nodului

O acoperire de nod într-un digraf G este un set de noduri ( cover ) din G.setOfNodes , astfel încât pentru orice arc a din G.setOfArcs acest lucru trebuie să fie adevărat: (a.fromNode in cover) or (a.toNode in cover) .

O acoperire minimă de noduri este cel mai mic set posibil de noduri din grafic care este încă o acoperire de noduri . Teorema lui Konig afirmă că într-un grafic bipartit , dimensiunea potrivirii maxime pe acel grafic este egală cu dimensiunea acoperirii minime a nodului și sugerează cum poate fi recuperată acoperirea nodului dintr-o potrivire maximă :

Să presupunem că avem bipartiția bipartition și matching maximă . Definiți un nou digraf H , H.setOfNodes=G.setOfNodes , arcele din H.setOfArcs sunt unirea a două mulțimi.

Primul set este arcurile a în matching , cu schimbarea că, dacă a.fromNode in bipartition.firstPart și a.toNode in bipartition.secondPart , atunci a.fromNode și a.toNode sunt schimbate în arcul creat, dă astfel de arcuri un a.datum.inMatching=True pentru a indica faptul că au fost derivate din arce dintr-o potrivire .

Cel de-al doilea set este arce a NOT în matching , cu modificarea că, dacă a.fromNode in bipartition.secondPart și a.toNode in bipartition.firstPart , atunci a.fromNode și a.toNode sunt schimbate în arcul creat (dați astfel de arcuri a a.datum.inMatching=False . a.datum.inMatching=False ).

Apoi, rulați o căutare depth first (DFS) pornind de la fiecare nod n din bipartition.firstPart care nu este nici n == a.fromNode , nici n == a.toNodes pentru orice arc a în matching . În timpul DFS, unele noduri sunt vizitate, iar altele nu (stochează aceste informații într-un câmp n.datum.visited ). Acoperirea minimă a nodurilor este unirea nodurilor {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (a.fromNode.datum.visited) ) } și a nodurilor {a.fromNode for a in H.setOfArcs if (a.datum.inMatching) and (not a.toNode.datum.visited)} .

Se poate demonstra că aceasta duce de la o potrivire maximă la o acoperire minimă a nodului printr-o demonstrație prin contradicție, luați un arc a care se presupune că nu a fost acoperit și luați în considerare toate cele patru cazuri privind dacă aparțin a.fromNode și a.toNode (fie ca toNode sau fromNode ) la orice arc în potrivire matching Fiecare caz duce la o contradicție din cauza ordinii în care DFS vizitează nodurile și a faptului că matching este o potrivire maximă .

Să presupunem că avem o funcție pentru a executa acești pași și a returna setul de noduri care cuprinde acoperirea minimă a nodurilor atunci când este dat digraful G și matching maximă :

 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

Problema atribuirii liniare

Problema de atribuire liniară constă în găsirea unei potriviri maxime a greutății într-un grafic bipartit ponderat.

Probleme precum cea de la începutul acestei postări pot fi exprimate ca o problemă de atribuire liniară . Având în vedere un set de muncitori, un set de sarcini și o funcție care indică profitabilitatea unei atribuiri a unui lucrător la o sarcină, dorim să maximizăm suma tuturor sarcinilor pe care le facem; aceasta este o problemă de atribuire liniară .

Să presupunem că numărul de sarcini și lucrători sunt egale, deși voi arăta că această ipoteză este ușor de eliminat. În implementare, reprezint greutățile arcului cu un atribut a.datum.weight pentru un arc a .

 WeightArcDatum = namedtuple('WeightArcDatum', [weight])

Algoritmul Kuhn-Munkres

Algoritmul Kuhn-Munkres rezolvă problema de atribuire liniară . O implementare bună poate dura O(N^{4}) timp, (unde N este numărul de noduri din digraful care reprezintă problema). O implementare care este mai ușor de explicat necesită O(N^{5}) (pentru o versiune care regenerează DiGraphs ) și O(N^{4}) pentru (pentru o versiune care menține DiGraphs ). Acest lucru este similar cu cele două implementări diferite ale algoritmului Edmonds-Karp .

Pentru această descriere, lucrez doar cu grafice bipartite complete (cele în care jumătate din nodurile sunt într-o parte a bipartiției și cealaltă jumătate în a doua parte). La muncitor, motivarea sarcinii înseamnă că există tot atâtea lucrători câte sarcini.

Aceasta pare o condiție semnificativă (ce ar fi dacă aceste seturi nu sunt egale!), dar este ușor să remediați această problemă; Vorbesc despre cum se face asta în ultima secțiune.

Versiunea algoritmului descrisă aici folosește conceptul util de arc de greutate zero . Din păcate, acest concept are sens doar atunci când rezolvăm o minimizare (dacă, în loc să maximizăm profiturile sarcinilor noastre de muncitor, am minimiza costurile unor astfel de sarcini).

Din fericire, este ușor să transformați o problemă de alocare liniară maximă într-o problemă de alocare liniară minimă, setând fiecare pondere a arcului la Ma.datum.weight unde M=max({a.datum.weight for a in G.setOfArcs}) . Soluția la problema de maximizare inițială va fi identică cu problema de minimizare a soluției după modificarea greutăților arcului . Deci, pentru restul, să presupunem că facem această schimbare.

Algoritmul Kuhn-Munkres rezolvă potrivirea ponderii minime într-un grafic bipartit ponderat printr-o secvență de potriviri maxime în grafice bipartite neponderate. Dacă a găsim o potrivire perfectă pe reprezentarea digraf a problemei de atribuire liniară și dacă greutatea fiecărui arc din potrivire este zero, atunci am găsit potrivirea minimă a greutății, deoarece această potrivire sugerează că toate nodurile din digraf au fost potrivită de un arc cu cel mai mic cost posibil (niciun cost nu poate fi mai mic de 0, pe baza definițiilor anterioare).

Niciun alt arc nu poate fi adăugat la potrivire (deoarece toate nodurile sunt deja potrivite) și nici un arc nu trebuie eliminat din potrivire , deoarece orice arc de înlocuire posibil va avea o valoare cel puțin la fel de mare.

Dacă găsim o potrivire maximă a subgrafului lui G care conține doar arce cu greutate zero și nu este o potrivire perfectă , nu avem o soluție completă (deoarece potrivirea nu este perfectă ). Cu toate acestea, putem produce un nou digraf H prin modificarea greutăților arcelor din G.setOfArcs astfel încât să apară noi arce cu greutate 0 și soluția optimă a lui H este aceeași cu soluția optimă a lui G . Deoarece garantăm că se produce cel puțin un arc cu greutate zero la fiecare iterație, garantăm că vom ajunge la o potrivire perfectă în nu mai mult de |G.setOfNodes|^{2}=N^{2} astfel de iterații.

Să presupunem că în bipartition bipartition , bipartition.firstPart conține noduri care reprezintă lucrători, iar bipartition.secondPart reprezintă noduri care reprezintă sarcini.

Algoritmul începe prin generarea unui nou digraf H . H.setOfNodes = G.setOfNodes . Unele arce din H sunt generate din nodurile n din bipartition.firstPart . Fiecare astfel de nod n generează un arc b în H.setOfArcs pentru fiecare arc a din bipartition.G.setOfArcs unde a.fromNode = n sau a.toNode = n , b=Arc(a.fromNode, a.toNode, a.datum.weight - z) unde z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) .

Mai multe arce în H sunt generate din nodurile n în bipartition.secondPart . Fiecare astfel de nod n generează un arc b în H.setOfArcs pentru fiecare arc a din bipartition.G.setOfArcs unde a.fromNode = n sau a.toNode = n , b=Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) unde z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) .

KMA: Apoi, formați un nou digraf K compus doar din arcele cu greutate zero din H și nodurile incidente pe acele arce . Formați o bipartition pe nodurile din K , apoi utilizați solve_mbm( bipartition ) pentru a obține o potrivire maximă ( matching ) pe K Dacă matching este o potrivire perfectă în H ( arcurile din matching sunt incidente pe toate nodurile din H.setOfNodes ), atunci matching este o soluție optimă pentru problema de atribuire liniară .

În caz contrar, dacă matching nu este perfectă , generați acoperirea minimă a nodului K folosind node_cover = get_min_node_cover(matching, bipartition(K)) . Apoi, definiți z=min({a.datum.weight for a in H.setOfArcs if a not in node_cover}) . Definiți 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)} . Simbolul != din expresia anterioară acționează ca un operator XOR. Apoi arcs = arcs1.union(arcs2.union(arcs3)) . În continuare, H=DiGraph(nodes,arcs) . Înapoi la eticheta KMA .Algoritmul continuă până când se produce o potrivire perfectă.Această potrivire este și soluția problemei de atribuire liniară .

 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

Această implementare este O(N^{5}) deoarece generează o nouă matching maximă la fiecare iterație; similar cu cele două implementări anterioare ale lui Edmonds-Karp, acest algoritm poate fi modificat astfel încât să țină evidența potrivirii și să o adapteze inteligent la fiecare iterație. Când se face acest lucru, complexitatea devine O(N^{4}) . O versiune mai avansată și mai recentă a acestui algoritm (care necesită niște structuri de date mai avansate) poate rula în O(N^{3}) . Detalii atât despre implementarea mai simplă de mai sus, cât și despre implementarea mai avansată pot fi găsite la această postare care a motivat această postare pe blog.

Niciuna dintre operațiile asupra greutăților arcului nu modifică atribuirea finală returnată de algoritm. Iată de ce: Deoarece graficele noastre de intrare sunt întotdeauna grafice bipartite complete , o soluție trebuie să mapați fiecare nod dintr-o partiție cu un alt nod din a doua partiție, prin arcul dintre aceste două noduri . Observați că operațiile efectuate asupra greutăților arcului nu schimbă niciodată ordinea (ordonată în funcție de greutate) a arcurilor incidente pe un anumit nod .

Astfel, atunci când algoritmul se termină la o potrivire bipartită completă perfectă, fiecărui nod i se atribuie un arc cu greutate zero , deoarece ordinea relativă a arcelor din acel nod nu s-a schimbat în timpul algoritmului și deoarece un arc cu greutate zero este cel mai ieftin arc posibil și potrivirea bipartită completă perfectă garantează că există un astfel de arc pentru fiecare nod . Aceasta înseamnă că soluția generată este într-adevăr aceeași cu soluția din problema de atribuire liniară inițială fără nicio modificare a greutăților arcului .

Misiuni dezechilibrate

Se pare că algoritmul este destul de limitat, deoarece așa cum este descris, funcționează numai pe grafuri bipartite complete (cele în care jumătate din noduri sunt într-o parte a bipartiției și cealaltă jumătate în a doua parte). La muncitor, motivația sarcinii înseamnă că există tot atâtea lucrători câte sarcini (pare destul de limitativ).

Cu toate acestea, există o transformare ușoară care înlătură această restricție. Să presupunem că există mai puțini lucrători decât sarcini, adăugăm câțiva lucrători inactiv (suficient pentru a face din graficul rezultat un grafic bipartit complet ). Each dummy worker has an arc directed from the worker to each of the tasks. Each such arc has weight 0 (placing it in a matching gives no added profit). After this change the graph is a complete bipartite graph which we can solve for. Any task assigned a dummy worker is not initiated.

Suppose that there are more tasks than workers. We add some dummy tasks (enough to make the resulting graph a complete bipartite graph ). Each dummy task has an arc directed from each worker to the dummy task. Each such arc has a weight of 0 (placing it in a matching gives no added profit). After this change the graph is a complete bipartite graph which we can solve for. Any worker assigned to dummy task is not employed during the period.

A Linear Assignment Example

Finally, let's do an example with the code I've been using. I'm going to modify the example problem from here. We have 3 tasks: we need to clean the bathroom , sweep the floor , and wash the windows .

The workers available to use are Alice , Bob , Charlie , and Diane . Each of the workers gives us the wage they require per task. Here are the wages per worker:

If we want to pay the least amount of money, but still get all the tasks done, who should do what task? Start by introducing a dummy task to make the digraph representing the problem bipartite.

Supposing that the problem is encoded in a digraph , then kuhn_munkres( bipartition(G) ) will solve the problem and return the assignment. It's easy to verify that the optimal (lowest cost) assignment will cost $5.

Here's a visualization of the solution the code above generates:

That is it. You now know everything you need to know about the linear assignment problem.

You can find all of the code from this article on GitHub.

Citiți suplimentare pe blogul Toptal Engineering:

• Graph Data Science cu Python/NetworkX