Andmeteadus Ja Andmebaasid

Tippvool ja lineaarse määramise probleem

Siin on probleem: teie ettevõte määrab töövõtjad lepingute täitmiseks. Vaatate oma nimekirju ja otsustate, millised töövõtjad on kuu pikkuse lepingu jaoks saadaval, ja vaatate oma olemasolevad lepingud üle, et näha, millised on kuu pikkuste ülesannete jaoks. Arvestades, et teate, kui tõhusalt saavad kõik töövõtjad iga lepingut täita, kuidas määrata töövõtjad selle kuu üldise efektiivsuse maksimeerimiseks?

See on näide määramisprobleemist ja probleemi saab lahendada klassikaga Ungari algoritm .

Kahepoolne kokkulangevus

Ungari algoritm (tuntud ka kui Kuhn-Munkresi algoritm) on polünoomiaja algoritm, mis maksimeerib kaalu kaalu kahepoolsel graafil. Siin saab töövõtjaid ja lepinguid modelleerida kahepoolse graafikuna, kusjuures nende tõhusus on töövõtja ja lepingu sõlmede vaheliste servade kaal.

Selles artiklis leiate teavet Ungari algoritmi rakenduse kohta, mis kasutab Edmonds-Karpi algoritm lineaarse määramise ülesande lahendamiseks. Samuti saate teada, kuidas Edmonds-Karpi algoritm on modifikatsiooni väike modifikatsioon Ford-Fulkerson ja selle muudatuse olulisus.

Tippvoolu probleem

Tippvooluprobleemi iseenesest võib mitteametlikult kirjeldada kui osa vedeliku või gaasi liikumist torustike võrgu kaudu ühest allikast ühte klemmi. Seda tehakse eeldusel, et rõhk võrgus on piisav, et tagada vedeliku või gaasi püsimine toru või toruliitmiku mis tahes pikkuses (kohtades, kus toru erinevad pikkused kokku puutuvad).

Graafikus teatud muudatusi tehes võib eraldamisprobleemist saada voolu tippprobleem.

Eeltööd

Nende probleemide lahendamiseks vajalikud ideed tekivad paljudel matemaatika- ja inseneridistsipliinidel, sageli on sarnased mõisted tuntud erinevate nimedega ja väljendatud erineval viisil (näiteks külgnemismaatriksid ja külgnevusloendid). Kuna need ideed on üsna esoteerilised, tehakse valikuid selle kohta, kuidas neid mõisteid üldjuhul mis tahes seadetes määratletakse.

See artikkel ei eelda eelteadmisi peale lühikese sissejuhatava hulga teooria.

Selles postituses olevad teostused kujutavad probleeme suunatud graafidena (diggraaf).

Digrafo

A digrafo on kaks atribuudid , setOfNodes Y setOfArcs . Mõlemad atribuudid on komplektid (räpased kogud). Selle postituse koodiplokkides kasutan Pythoni frozenset , kuid see detail pole eriti oluline.

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

(Märkus. See ja kõik muud selle artikli koodid on kirjutatud Python 3.6-s.)

Sõlmed

A sõlm n See koosneb kahest atribuudist:

n.uid: A Unikaalne identifikaator .

See tähendab, et mis tahes kahe sõlme puhul x ja y,

x.uid != y.uid

n.datum: See tähistab mis tahes andmeobjekti.

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

Kaar

A kaar a See koosneb kolmest atribuudist:

a.fromNode: See on a sõlm , nagu eespool määratletud.
a.toNode: See on a sõlm , nagu eespool määratletud.
a.datum: See tähistab mis tahes andmeobjekti.

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

Komplekt vibud kell joonistus tähistab binaarsuhet sõlmed kell joonistus . - olemasolu kaar a tähendab, et a.fromNode vahel on seos ja a.toNode.

Suunatud graafis (erinevalt suunamata graafist) seose olemasolu a.fromNode vahel ja a.toNode ei vihjata sellele, et sarnane suhe a.toNode vahel ja a.fromNode olemas.

ember js õpetus algajatele

Seda seetõttu, et suunamata graafil ei ole väljendatud seos tingimata sümmeetriline.

Numbrid

Sõlmed Y vibud saab kasutada a määratlemiseks joonistus , kuid mugavuse huvides järgmistes algoritmides a joonistus kasutades a sõnastik .

Siin on meetod, mille abil saab ülaltoodud graafilise kujutise teisendada sarnaseks sõnastiku esituseks on :

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

Ja siin on veel üks, mis muudab selle sõnastike sõnaraamatuks, mis on veel üks kasulik toiming:

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

Kui artiklis räägitakse a joonistus kuna sõnastik esindab seda, mainib ta G_as_dict viitamiseks.

Mõnikord aitab see a sõlm aasta joonistus G kuni teie uid (Kordumatu identifikaator):

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

Graafika tuvastamisel kasutavad inimesed mõnikord termineid sõlm ja tipp viitavad samale mõistele; sama öeldakse ka terminite kohta kaar ja serv.

Pythonis on kaks graafilist esitust, on mis kasutab sõnastikke ja muud mis kasutab objekte graafika esitamiseks. Esindus selles postituses jääb nende kahe ühise esituse vahele.

See on minu esindus a joonistus . Selliseid on palju, kuid see on minu oma.

Teed ja rajad

Olgu S_Arcs olema a järjestus lõplik (tellitud kogu) vibud sees joonistus G nii palju, et kui a on ükskõik milline kaar aastal S_Arcs välja arvatud viimane ja b järgneb a jadas, siis peab olema a sõlm n = a.fromNode aastal G.setOfNodes kui a.toNode = b.fromNode.

Alustades esimesest kaar aastal S_Arcs ja jätkub viimaseni kaar aastal S_Arcs, kogub (leitud järjekorras) kõik sõlmed n nagu me neid kahe eespool defineerime vibud järjestikune S_Arcs Märkige tellitud kollektsioon sõlmed selle toimingu käigus kogutud 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

Kui mõni sõlm ilmub järjestuses S_Nodes rohkem kui üks kord siis helistage S_Arcs a Tee kõrval joonistus G.
Muul juhul helistage S_Arcs a kaudu kohta list(S_Nodes)[0] a list(S_Nodes)[-1] kell joonistus G.

Allikasõlm

Helistama sõlm s a allikasõlm aastal joonistus G kui s asub G.setOfNodes ja G.setOfArcs tal pole kaar a kui 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

Terminalisõlm

Helistama sõlm t a terminali sõlm kell joonistus G kui t asub G.setOfNodes ja G.setOfArcs tal pole kaar a kui 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

Cortes y Cortes s-t

A lõigatud cut aasta joonistus G ühendatud on alamhulk alates vibud alates G.setOfArcs mis osa komplekt sõlmed G.setOfNodes aastal G G on ühendatud, kui kumbki sõlm n aastal G.setOfNodes on vähemalt üks kaar a aastal G.setOfArcs kui n = a.fromNode või n = a.toNode, kuid mitte a.fromNode != a.toNode.

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

Eespool toodud määratlus viitab jaotise vibud , kuid saate määratleda ka partitsiooni sõlmed kohta G.setOfNodes

Funktsioonide jaoks predecessors_of ja successors_of, n on sõlm komplektis G.setOfNodes alates joonistus G ja cut on lõigatud 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

Olgu cut Ole a lõigatud selle joonistus 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 on lõigatud selle joonistus G kui: (get_first_part(cut, G).union(get_second_part(cut, G)) == G.setOfNodes) y (len(get_first_part(cut, G).intersect(get_second_part(cut, G))) == 0) cut nimetatakse a x-y lõigatud kui (x in get_first_part(cut, G)) y (y in get_second_part(cut, G) ) y (x != y). Kui sõlm x sees x-y lõigatud cut on allikasõlm ja sõlm y kell x-y lõigatud on terminali sõlm , siis see lõigatud nimetatakse a s-t lõigatud .

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

Vooluvõrgud

Võite kasutada a joonistus G vooluvõrgu esindamiseks.

Määrake kumbki sõlm n, kus n asub G.setOfNodes a n.datum mis on FlowNodeDatum

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

Määrake kumbki kaar a, kus a on a G.setOfArcs ja a.datum mis on FlowArcDatum.

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

flowNodeDatum.flowIn ja flowNodeDatum.flowOut Nemad on reaalarvud positiivne .

flowArcDatum.capacity ja flowArcDatum.flow need on ka positiivsed reaalarvud.

kuidas lihtsat mängu kodeerida

Iga sõlme jaoks sõlm n sisse 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})

The Silmapilt G esindab nüüd vooluvõrk .

The voolama kohta G viitab voolule a.flow kõigi jaoks vibud a aastal G

Teostatavad voogud

Las ta laseb joonistus G esindama a vooluvõrk .

The vooluvõrk mida esindab G omama teostatavad voogud jah:

Igaühele sõlm n aastal G.setOfNodes väljaarvatud allikasõlmed Y terminali sõlmed : n.datum.flowIn = n.datum.flowOut.
Igaühele kaar a aastal G.setOfNodes: a.datum.capacity <= a.datum.flow.

Tingimust 1 nimetatakse kaitse piiramine .

Tingimust 2 nimetatakse võimsuse piiramine .

Lõikevõime

The lõikevõime aasta s-t lõigatud stCut koos allikasõlm s ja a terminali sõlm t aasta vooluvõrk mida esindab a joonistus G see on:

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

Minimaalne võimsuse vähendamine

Olgu stCut = stCut(s,t,cut) Ole a s-t lõigatud aasta vooluvõrk mida esindab a joonistus G.

stCut kas ta on minimaalne lõikevõime selle vooluvõrk mida esindab G kui muud pole s-t lõigatud stCutCompetitor selles vooluvõrk kui:

 cut_capacity(stCut, G) Voogude eemaldamine
 Tahaksin viidata joonistus mis oleks a võtmise tulemus joonistus G ja kustutage kõik vooandmed kõigilt sõlmed aastal G.setOfNodes ja ka kõik vibud aastal 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) Tippvoolu probleem
 A vooluvõrk esindatud kui joonistus G, a allikasõlm s aastal G.setOfNodes ja a terminali sõlm t aastal G.setOfNodes, G võib esindada a tippvoolu probleem jah:
(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) Märgi see esitus:
MaxFlowProblemState = namedtuple('MaxFlowProblemState', ['G','sourceNodeUid','terminalNodeUid','maxFlowProblemStateUid']) Kus sourceNodeUid = s.uid, terminalNodeUid = t.uid ja maxFlowProblemStateUid on probleemeksemplari identifikaator.
 Peak Flow lahendus
 Olgu maxFlowProblem esindama a tippvoolu probleem . Probleemi lahendus maxFlowProblem saab tähistada a vooluvõrk esindatud kui joonistus H.
 The Silmapilt H on lahendus teostatav tema jaoks tippvoolu probleem sisendis python maxFlowProblem jah:
   strip_flows(maxFlowProblem.G) == strip_flows(H).
 
  H on vooluvõrk ja on teostatavad voogud .
 
 
 Kui lisaks punktidele 1 ja 2:
  Muud ei saa olla vooluvõrk mida esindab joonistus K kui strip_flows(G) == strip_flows(K) ja find_node_by_uid(t.uid,G).flowIn .
 
 Siis H see on ka lahendus optimaalne jaoks maxFlowProblem
 Teisisõnu, a teostatav tippvoolulahus saab esitada a-ga joonistus , et:
   See on identne joonistus G vastavatest tippvoolu probleem välja arvatud voog n.datum.flowIn, n.datum.flowOut ja voog a.datum.flow mis tahes sõlmed Y vibud need võivad olla erinevad.
 
  Esindab a vooluvõrk mis sellel viga on teostatavad voogud .
 
 
 Ja see võib tähendada a optimaalne tippvoolulahus kui lisaks:
  flowIn tema jaoks sõlm mis vastab terminali sõlm kell tippvoolu probleem on võimalikult suur (kui tingimused 1 ja 2 on endiselt täidetud).
 
 Jah joonistus H tähistab a tippvoolulahus : find_node_by_uid(s.uid,H).flowOut = find_node_by_uid(t.uid,H).flowIn see tuleneb maksimaalne vooluhulk, minimaalse nihke teoreem (arutatakse allpool). Mitteametlikult, kuna H omama elujõulised voolud see tähendab, et voolama ei saa 'luua' (välja arvatud allikasõlm s) ega 'hävitatud' (välja arvatud terminali sõlm t) ületades ühtegi (muud) sõlm ( kaitse piirangud ).
 Kuna a tippvoolu probleem   sisaldab ainult ühte allikasõlme s ja ühe terminali sõlm t, iga voog, mis on 'loodud' s -s tuleb hävitada t Laine vooluvõrk   ei omama teostatavad voogud ( kaitse kitsendamine oli vägistatud).
 Las ta laseb joonistus H esindama a teostatav tippvoolulahus ; ülaltoodud väärtust nimetatakse Voolu väärtus s-t kohta H
 See lubab:
mfps=MaxFlowProblemState(H, maxFlowProblem.sourceNodeUid, maxFlowProblem.terminalNodeUid, maxFlowProblem.maxFlowProblemStateUid) See tähendab, et mfps on õigusjärglane , mis tähendab, et  maxFlowProblem on täpselt nagu mfps välja arvatud see, et maxFlowProblem väärtused kaaride jaoks a.flow aastal a võib erineda maxFlowProblem.setOfArcs -st kaaride jaoks a.flow aastal a
mfps.setOfArcsSee on 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  kuva koos selle mfps seotud. Iga kaar maxFlowProb pildil on silt, need sildid on a, igaüks sõlm a.datum.flowFrom/a.datum.flowTo pildil on silt ja need sildid on n.
  
 Nihke vool
 Olgu n.uid {n.datum.flowIn / a.datum.flowOut} kujutavad probleemseisundit mfps ja laseme MaxFlowProblemState esindama a lõigatud kohta stCut The nihkevool mfps.G on määratletud järgmiselt:
stCut s-t vooluhulk on partitsiooni sisaldava sektsiooni voogude summa allikasõlm partitsiooni sisaldava partitsiooni jaoks terminali sõlm miinus partitsiooni sisaldava sektsiooni voogude summa terminali sõlm partitsiooni sisaldava partitsiooni jaoks allikasõlm .
 Maksimaalne vooluhulk, minimaalne nihkejõud
 Mis 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  esindama a tippvoolu probleem ja et lahendus maxFlowProblem on tähistatud a vooluvõrk esindatud kui joonistus maxFlowProblem.
 Olgu H minimaalne lõikevõime selle vooluvõrk mida esindab minStCut.
 Sest voolus tippvool voog pärineb ühest allikasõlm ja lõpeb ühes sõlmes terminal ja tänu võimsuse piirangud ja kaitse piirangud , me teame, et kogu voog siseneb maxFlowProblem.G peab ületama ükskõik millise s-t lõigatud , eriti peab see ületama maxFlowProblem.terminalNodeUid. See tähendab:
minStCutMaksimaalse voolu probleemi lahendus
 Põhiidee lahendada a tippvoolu probleem get_flow_value(H, maxFlowProblem) <= cut_capacity(minStCut, maxFlowProblem.G)  on alustada a tippvoolulahus mida esindab joonistus maxFlowProblem. Selline lähtepunkt võib olla H.
 Seejärel on ülesandeks kasutada H = strip_flows(maxFlowProblem.G) ja mõne poolt ahne väärtuste muutmine H mõnest vibud a.datum.flow aastal a teise tootmiseks tippvoolulahus mida esindab joonistus H.setOfArcs nii et K ei saa veel esindada a vooluvõrk koos elujõulised voolud ja K. Niikaua kui see protsess jätkub, on toote kvaliteet (get_flow_value(H, maxFlowProblem) ) tippvoolulahus (get_flow_value(K, maxFlowProblem)) leidis hiljuti paremini kui ükski teine tippvoolulahus see on leitud. Kui protsess jõuab punkti, kus ta teab, et edasine parendamine pole võimalik, võib protsess lõpetada ja tagastab selle tippvoolulahus   optimaalne .
 Ülaltoodud kirjeldus on üldine ja jätab välja paljud testid, näiteks kui selline protsess on võimalik või kui kaua see võib aega võtta, annan veel mõned üksikasjad ja algoritmi.
 Maksimaalse voolu teoreem, minimaalne nihkumine
 Raamatust Vood võrkudes de Ford y Fulkerson , deklaratsioon Maksimaalse voolu teoreem, minimaalne nihkumine (Lause 5.1) on:
   Mis tahes võrgu puhul maksimaalne voo väärtus K a s on võrdne kõigi t eraldavate lõikude minimaalse lõikevõimega ja s.
 
 Selle postituse määratlusi kasutades tähendab see järgmist:
 Lahendus a t mida esindab a vooluvõrk esindatud kui joonistus maxFlowProblem see on optimaalne jah:
H Mulle meeldib see test teoreemi ja Vikipeedias on muud .
 The maksimaalse voolu, minimaalse nihke teoreem kasutatakse dokumendi õigsuse ja täielikkuse demonstreerimiseks Ford-Fulkersoni meetod .
 Annan teoreemi kohta tõendi ka järgnevas osas suurendamise viisid .
 Ford-Fulkersoni meetod ja Edmonds-Karpi algoritm
  CLRS määratlege Ford-Fulkersoni meetod (punkt 26.2) järgmiselt:
get_flow_value(H, maxFlowProblem) == cut_capacity(minStCut, maxFlowProblem.G) Jääkgraafik
 The Jääkgraafik aasta vooluvõrk esindatud kui joonistus 'G' saab esitada a-na joonistus 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_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)  naase agg_n_to_u_cap(n,u,G_as_dict) summa juurde jaoks vibud a.datum.capacity alamhulgas kus ta kaar G.setOfArcs on alamhulgas, kui a ja a.fromNode = n.
 
  a.toNode = u tagastab agg_n_to_u_cap(n,u,G_as_dict) summa kõigi jaoks vibud a.datum.flow alamhulgas kus ta kaar G.setOfArcs on alamhulgas, kui a ja a.fromNode = n.
 
 
 Lühidalt öeldes jääkgraafik a.toNode = u tähistab teatud toiminguid, mida saab joonistus 'G'.
 Iga paar sõlmed G_f aastal n, u selle vooluvõrk mida esindab joonistus G.setOfNodes võib genereerida 0,1 või 2 vibud kell jääkgraafik G 'G'.
   Paar G_f ei genereeri vibud aastal n, u kui seda pole kaar G_f aastal a nagu G.setOfArcs ja a.fromNode = n.
 
  Paar a.toNode = u genereerib kaar n, u aastal a kus G_f.setOfArcs tähistab a kaar märgistatud kui impulssvoog alates a a n u kui a = Arco (n, u, datum = ResidualNode (n_to_u_cap_sum - n_to_u_flow_sum)).
 
  Paar n_to_u_cap_sum> n_to_u_flow_sum genereerib kaar n, u aastal a kus G_f.setOfArcs tähistab a kaar märgistatud kui tõmba voolukaar kohta a a n u kui a = Arco (n, u, datum = ResidualNode (n_to_u_cap_sum - n_to_u_flow_sum)).
 
 
   Iga tõukevoolukaar aastal n_to_u_flow_sum> 0.0 tähistab voo kogusumma G_f.setOfArcs lisamise toimingut kuni vibud x <= n_to_u_cap_sum - n_to_u_flow_sum alamhulgas kus ta kaar G.setOfArcs on alamhulgas, kui a ja a.fromNode = n.
 
  Iga veojõu voolukaar aastal a.toNode = u tähistab kogu voo lahutamise toimingut G_f.setOfArcs kuni vibud x <= n_to_u_flow_sum alamhulgas kus kaar G.setOfArcs on alamhulgas, kui a ja a.fromNode = n.
 
 
 Sooritage individuaalne toiming nagu Lükake või ikka alates a.toNode = u aastal vibud kohaldatav G_f võiks genereerida a vooluvõrk ilma teostatavad voogud sest võimsuse piirangud või kaitse piirangud saaks vägistada loodud voogude võrk .
 Siin on jääkgraafik eelmisest a kuvamise näitest tippvoolulahus , kuvatakse igaüks kaar G tähistab a.
  
 Suurenev rada
 Olgu a.residualCapacity Ole a tippvoolu probleem ja laske maxFlowProblem olema jääkgraafik kohta G_f = get_residual_graph_of (G)
 A tee üles maxFlowProblem.G jaoks augmentingPath on ükskõik milline kaudu alates maxFlowProblem a find_node_by_uid(maxFlowProblem.sourceNode,G_f).
 Selgub, et a suurendamise tee find_node_by_uid(maxFlowProblem.terminalNode,G_f) saab rakendada a tippvoolulahus mida esindab joonistus augmentingPath teise genereerimine tippvoolulahus mida esindab joonistus H kus K kui get_flow_value (H, maxFlowProblem)  See ei ole optimaalne .
 Siin näete, kuidas:
HEespool nimetatutega 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  on hälbe tolerants ümardada voolu väärtused võrgus. Seda selleks, et vältida kaskaadi ujukomaarvutuste ebatäpsus . Nii näiteks kasutasin kümneni ümardamiseks sõna 'TOL = 10' olulised numbrid .
 Lahkuge TOL, seejärel K = augment (augmentingPath, H) tähistab a teostatav tippvoolulahus jaoks K Et väide oleks tõene, peab vooluvõrk mida esindab maxFlowProblem oleks pidanud teostatavad voogud (mitte rikkuda võimsuse piiramine Laine kaitse piiramine . Selle põhjus on järgmine: ülaltoodud meetodil igaüks sõlm lisati uuele vooluvõrk mida esindab joonistus K  on a täpne koopia sõlm alates joonistus K või a sõlm H mille teie n -le on lisatud sama number nagu teie n.datum.flowIn. See tähendab, et kaitse piiramine see on täidetud tähes „K” seni, kuni see on täidetud tähes „H”. The kaitse piiramine on rahul, kuna kontrollime sõnaselgelt, kas mõni neist on olemas kaar uus n.datum.flowOut võrgus olete a; seega seni, kuni vibud komplekti a.datum.flow <= a.datum.capacity mis kopeeriti muutmata kujul H.setOfArcs ei riku võimsuse piiramine , siis K.setOfArcs ei riku võimsuse piiramine .
 Samuti on tõsi, et K kui get_flow_value (H, maxFlowProblem)  See ei ole optimaalne .
 Sellepärast: a marsruudi suurenemine H on olemas joonistus esindus jääkgraafik augmentingPath aasta tippvoolu probleem G_f siis viimane kaar maxFlowProblem aastal a peab olema a kaar 'Push' ja sellel peab olema augmentingPath. A suurendamise tee on määratletud kui üks lõpp terminali sõlm selle tippvoolu probleem mille jaoks on a suurendamise tee . Definitsioonist jääkgraafik , on selge, et viimane kaar sees suurendamise viis selles jääkgraafik peab olema a kaar 'Push', sest ükskõik kaar 'Tõmba' a.toNode == maxFlowProblem.terminalNode aastal suurendamise viis on b ja b.toNode == maxFlowProblem.terminalNode määratlusest kaudu . Lisaks määratlusest kaudu , on selge, et terminali sõlm Seda muudetakse meetodi b.fromNode! = maxFlowProblem.terminalNode abil ainult üks kord. Niisiis augment muuda augment täpselt üks kord ja suurendab  maxFlowProblem.terminalNode.flowIn väärtust sest viimane kaar aastal maxFlowProblem.terminalNode.flowIn see peab olema Tema kaar mis põhjustab modifikatsiooni augmentingPath ajal maxFlowProblem.terminalNode.flowIn. augment Definitsioonist, kuna see kehtib vibud 'Push', augment seda saab ainult suurendada, mitte vähendada.
 Mõned Sedgewicki ja Wayne'i tõendid
 Raamat Algoritmid, Robert Sedgewichi ja Kevin Wayne'i neljas väljaanne on mõned suurepärased lühikesed testid (lk 892–894), mis on kasulikud. Loon need siin uuesti, ehkki kasutan ülaltoodud määratlustele vastavat keelt. Minu sildid testide jaoks on samad, mis Sedgewicki raamatus.
  Ettepanek E: Iga joonistus maxFlowProblem.terminalNode.flowIn mis tähistab a teostatav tippvoolulahus veel tippvoolu probleem H mis tahes maxFlowProblem stCut.
  Test: Lahku get_stcut_flow(stCut,H,maxFlowProblem) = get_flow_value(H, maxFlowProblem). Ettepanek E on stCut=stCut(maxFlowProblem.sourceNode,maxFlowProblem.terminalNode,set([a for a in H.setOfArcs if a.toNode == maxFlowProblem.terminalNode])) otse määratlusest vooluhulk s-t . Oletame, et tahame liikuda a sõlm stCut partitsioonist s (n) ja partitsioonil get_first_part(stCut.cut, G), selleks peame muutma (get_second_part(stCut.cut, G)), mis võib muutuda stCut.cut ja kehtetuks tunnistama ettepanek E . Vaatame siiski, kuidas stcut_flow = get_stcut_flow(stCut,H,maxFlowProblem) väärtus see muutub, kui me selle muudatuse teeme. The sõlm stcut_flow on tasakaalus, mis tähendab, et voo summa in sõlm n on võrdne selle voo summaga (see on vajalik selleks, et n tähistaks a teostatav lahendus ).
 Pange tähele, et kogu voog, mis on osa H sisse tulemas sõlm stcut_flow sisestab selle sektsioonist s (sisenev voog sõlm n kuna partitsioon t teeb seda otseselt või kaudselt, siis ei oleks seda arvestatud väärtusesse n kuna see läheb definitsiooni põhjal vales suunas). Pange tähele, et kogu voog, mis on osa stcut_flow mis siseneb sõlm stcut_flow sisestab selle sektsioonist s (vool, mis siseneb sõlm n otseselt või kaudselt partitsioonist t ei ole väärtuses n arvesse võetud kuna liigute definitsiooni põhjal vales suunas).
mis järgmistest ei ole tüüpiline tööriist või tehnika, mida kasutatakse reageerivas kujunduses?
 Samuti kogu vool, mis kustub stcut_flow voolab lõpuks (otseselt või kaudselt) terminali sõlm (ülaltoodud). Kui me liigutame sõlm n sektsioonis t kogu vool, mis siseneb n partitsioonist s tuleb lisada uuele väärtusele n; aga kogu vool, mis kustub stcut_flow tuleb uuest väärtusest lahutada n; lahutatakse otse voo osa, mis läheb otse sektsiooni t, kuna see voog on nüüd uue sektsiooni t sisemine ja seda ei loeta stcut_flow
 Voolu osa asendist stcut_flow aastal sõlmed sektsioonist s tuleb lahutada ka n: pärast stcut_flow liigub sektsiooni t, suunatakse need voogud sektsiooni s asendist t ja seetõttu ei tohiks neid n -s arvesse võtta, kuna need voogud kõrvaldavad sisendi sektsioonis s ja neid tuleb vähendada neid voogusid ja väljavoolu sektsioonist s sektsiooni -t (kus kõik voog st peavad lõppema) tuleb sama palju vähendada. Nagu sõlm stcut_flow oli enne protsessi tasakaalus, lisab värskendus uuele väärtusele sama väärtuse n lahutades lahkub ettepanek E pärast täiendamist selge. Programmi kehtivus ettepanek E siis jätkame sektsiooni t suuruse induktsioonis.
 Siin on mõned näited vooluvõrgud aidata visualiseerida vähem ilmseid juhtumeid, kus ettepanek E see hoiab; Pildil tähistavad punased alad s partitsiooni, sinised alad t partitsiooni ja vibud roheline tähistab a lõika s-t **. Teisel pildil vool ** sõlme vahel Kuni ja sõlm B suureneb sissevoolu ajal terminali sõlm t ei muutu.
  
  
  Järeldus: Puudub väärtus nihkevool s-t võib ületada s-t lõigatud .
  Lause F. (maksimaalne vooluhulk ja minimaalse lõikelause): Olgu stcut_flow olla vool s-t . Järgmised 3 tingimust on samaväärsed:
   Seal on lõik s-t mille võimsus on võrdne voolu väärtusega f
 
  f on tippvool .
 
  Pole suurendamise viis seoses f.
 
 
 Tingimus 1 tähendab kaasnevat seisundit 2. Tingimus 2 viitab tingimusele 3, kuna suureneva tee olemasolu tähendab kõrgemate väärtustega voo olemasolu, mis on vastuolus maksimaalse f väärtusega. Tingimus 3 tähendab tingimust 1: olgu f kõigi komplekt sõlmed kuhu pääseb C_s koos marsruudi suurenemine kell jääkgraafik . Olgu  s ülejäänud vibud , siis C_t peab olema t (meie oletuse järgi). The vibud see rist alates C_t a C_s siis moodustage a s-t lõigatud sisaldavad ainult vibud  C_t kus a või a.datum.capacity = a.datum.flow. Kui ei, siis sõlmed ühendatud a kaar järelejäänud jääkmahtuga a a.datum.flow = 0.0 oleks komplektis C_s sellest ajast peale oleks olemas a raja kasv alates C_s veel sõlm . Vool läbi s-t lõigatud võrdub võimsusega s-t lõigatud (alates vibud kohta s a C_s vooluhulk on võrdne läbilaskevõimega) ja ka väärtusega voog s-t (kõrval ettepanek E ).
 See lause lause max vooluhulk, min lõigatud tähendab ülaltoodud avaldust Vood võrkudes .
  Järeldus (terviklikkuse omadus): Kui mahtuvus on täisarv, on maksimaalse täisarvu voog ja Ford-Fulkersoni algoritm leiab selle.
 Test: iga kord suurendamise viis suurendab voogu positiivse täisarvu võrra, mis on kaarides kasutamata mahtude miinimum suruma ja voolab võlvides veojõud , mis kõik on alati positiivsed täisarvud.
 See õigustab meetodi kirjeldust Ford-Fulkerson alates CLRS . Meetod on jätkata leidmist marsruutide suurenemine ja rakendades C_t viimaseni augment paremate lahenduste leidmine, kuni enam pole marsruudi suurenemine , mis tähendab, et viimane tippvoolulahus see on optimaalne .
 De Ford-Fulkerson ja Edmonds-Karp
 Ülejäänud küsimused seoses tippvoolu probleemid Nemad on:
   Kuidas neid peaks ehitama suurendamise teed ?
 
  Kas meetod lõpeb, kui kasutame reaalarvusid, mitte täisarvusid?
 
  Kui kaua võtab see aega (kui see lõpeb)?
 
 
 The Edmonds-Karpi algoritm täpsustage, et igaüks suurendamise tee on ehitatud a amplituudi otsing ( BFS ) selle jääkgraafik ; Selgub, et see punktist 1 pärinev otsus sunnib ka algoritmi lõpetama (punkt 2) ja võimaldab asümptootiline aeg ja ruumi keerukus tuleb kindlaks teha.
 Esiteks, siin on rakendus BFS :
 maxFlowSolutionKasutasin a deque pythoni kogumismoodulist .
 Küsimusele 2 vastamiseks kavatsen parafraseerida veel ühe tõendi selle kohta Sedgewick ja Wayne : Ettepanek G. Nende arv kasvuteed vajalik algoritmis Edmonds-Karp sõlmedega 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  Y vibud on maksimaalselt N. Test: iga kord suurendamise tee on kaelakaar kaar - a kaar mis on kustutatud jääkgraafik kuna see vastab hästi kaarele suruma mis on täidetud mahuni või kaareni veojõud mille kaudu vool muutub 0. Iga kord a kaar saab kitsaskohaks kaar , mis tahes pikkus suurendamise tee selle kaudu peaks suurenema 2 korda. Seda seetõttu, et kumbki sõlm sees tee võivad ilmuda ainult üks kord või üldse mitte (määratlusest tee ) Kuna marsruutidel uuritakse kõige lühemalt tee kogu see tähendab, et vähemalt üks sõlm pluss peab läbi pudelikaela külastama järgmist marsruuti sõlm mis tähendab täiendavat 2 vibud teel enne saabumist sõlm . Kuna juurdekasvu tee on maksimaalne pikkus NA/2, iga kaar võib olla maksimaalselt N , juurdekasvu teed, ja koguarv juurdekasvuteed on maksimaalselt N/2. 
 The Edmonds-Karpi algoritm töötab NA/2. Jah, kõige rohkem viise O(NA^2) uuritakse algoritmi käigus ja uuritakse igaüks neist trajektoor koos BFS on NA/2 siis toote kõige olulisem termin ja seetõttu asümptootiline keerukus N+A
 Olgu O(NA^2) olgu see mfp.
maxFlowProblemStateVanem versioon on ebaefektiivne ja keerukam kui 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  kuna see ehitab uue tippvoolulahus ja uus jääkgraafik iga kord (selle asemel, et muuta olemasolevad joonised algoritmi edenedes). Lahenduse leidmiseks O(NA^2) tõsi, algoritm peab säilitama mõlemad digrafo mis tähistab voolu tippvigade olek ja sellega seotud ** jääkgraafik . Seetõttu peaks algoritm vältima asjatut ** kaare kordamist Y sõlmed ja värskendage nende väärtusi ja nendega seotud väärtusi jääkgraafik ainult vajadusel.
 Algoritmi kirjutamiseks Edmonds Karp kiiremini, kirjutasin mitu ülaltoodud koodijuppi ümber. Loodan läbida kood, mis uue tekitas digrafo See oli abiks toimuva mõistmisel. Kiires algoritmis kasutan mõningaid uusi Pythoni trikke ja andmestruktuure, mida ma ei soovi üksikasjalikult kirjeldada. Ma ütlen, et O(NA^2) ja a.fromNode käsitletakse nüüd stringide ja uididena sõlmed . Selle koodi jaoks olgu  a.toNode olema mfps
maxFlowProblemStateSiin on visualiseering sellest, kuidas see algoritm näite lahendab vooluvõrk ülevalt. Visualiseerimine näitab samme, mis kajastuvad digrafo 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  mis esindab vooluvõrku hiljemalt ja kuidas need kajastuvad jääkgraafik selle vooluvõrgu osa. Suurenemise viisid kell jääkgraafik on näidatud punaste marsruutidena ja digrafo mis esindab probleemi komplekti sõlmed Y vibud surmaga mõjutatud suurendamise marsruut on rohelisega esile tõstetud. Mõlemal juhul toongi välja diagrammi muudetavad osad (punane või roheline) ja seejärel kuvan diagrammi pärast muudatusi (ainult must).
  
  
 Siin on veel üks visualiseering selle kohta, kuidas see algoritm lahendab teistsuguse näite vooluvõrk . Pange tähele, et see kasutab reaalarvusid ja sisaldab mitut vibud samade väärtustega G ja fromNode.
  Pange tähele ka seda, et kuna kaared, millel on ResidualDatum 'tõmme', võivad olla osa tõusvast teest, ei tohi vooluvõrgu skeemi_ mõjutatud sõlmed olla rajal  toNode 
 Kahepoolne graafika
 Oletame, et meil on a digrafo G!, G see on kahepoolne kui on võimalik jaotada sõlmed aastal G kahes komplektis (G.setOfNodes ja part_1) nii, et mis tahes kaar part_2 aastal a ei See võib olla tõsi et G.setOfArcs aastal a.fromNode ja part_1 aastal a.toNode Kumbagi See võib olla tõsi et part_1 aastal a.fromNode ja part_2 aastal a.toNode
 Teisisõnu: part_2 see on kahepoolne kui selle saab jagada kaheks sõlmed nii, et igaüks kaar peab ühendama a sõlm komplektis sõlmele teises komplektis. 
 Kahepoolne testimine
 Oletame, et meil on a digrafo G, tahame testida, kas see on kahepoolne . Saame seda teha G kahevärvilise tabeli ahne värv.
 Esiteks peame looma uue digrafo O(|G.setOfNodes|+|G.setOfArcs|). Sellel graafikul on sama hulk sõlmed meeldib H, kuid neid on veel vibud kui G. Iga kaar  G aastal a loob 2 vibud aastal  G esimene kaar on identne H ja teisega kaar investeerib a direktor (a).
kuidas ma saan bootstrapi kasutada
b = Arc(a.toNode,a.fromNode,a.datum)Vasted ja maksimaalsed vasted
 Oletame, et meil on a digrafo 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)  ja G on alamhulk vibud kohta  matching G.setOfArcs on sobitamine jah kahele digrafo matching ja a aastal b: matching. Teisisõnu, ei kaar sees kokkusattumus jagama a sõlm .
 The kokkusattumus len(frozenset( {a.fromNode} ).union( {a.toNode} ).union( {b.fromNode} ).union( {b.toNode} )) == 4 on maksimaalne vaste, kui muud pole kokkuleppele matching aastal alt_matching nii palju, et G. Teisisõnu: len(matching)  on maksimaalne vaste Kui see on pikim komplekt vibud aastal matching mis vastab endiselt kombinatsioon (lisades kõik kaar seda pole veel matšis, murrab kombinatsioon määratlus).
 A maksimaalne kombinatsioon G.setOfArcs on täiuslik kombinatsioon jah igale sõlm matching aastal n seal on kaar G.setOfArcs aastal a kus matching.
 Maksimaalne kaheosaline kombinatsioon
 A maksimaalne kahest sektsioonist koosnev kombinatsioon on maksimaalne kombinatsioon sees digrafo a.fromNode == n or a.toNode == n Mis see on kahes jaotuses .
 Kuna G see on kahes jaotuses , probleem a kahepoolne maksimaalne kombinatsioon saab teisendada a tippvoolu probleem lahendatav algoritmiga autor Edmonds-Karp ja siis maksimaalne kahepoolne sidestus saab taastada lahusest kuni tippvoolu probleem .
 Olgu G olema a kahepoolne kohta bipartition
 Selleks pean genereerima uue digrafo (G) mõne uue sõlmed (H) ja mõned vibud uus (H.setOfNodes). H.setOfArcs sisaldab kõiki sõlmed aastal H.setOfNodes ja kaks sõlmed veel, G.setOfNodes (a allikasõlm ) ja s (a terminali sõlm ).
 t sisaldab a kaar iga H.setOfArcs kohta. Kui a kaar G.setOfArcs on a a ja G.setOfArcs asub a.fromNode ja bipartition.firstPart asub a.toNode ja seejärel sisaldab bipartition.secondPart aastal a (lisades H).
 Kui FlowArcDatum(1,0) on a a.fromNode ja bipartition.secondPart on a.toNode, siis lisage bipartition.firstPart aastal Arc(a.toNode,a.fromNode,FlowArcDatum(1,0))
 Diagrammi määratlemine kahes jaotuses tagab, et ei kaar ühendage ükskõik milline sõlm kus mõlemad sõlmed nad on samal sektsioonil. H.setOfArcs sisaldab ka a kaar alates sõlm H.setOfArcs igale sõlm aastal s Lõpuks  bipartition.firstPart sisaldab a kaar iga sõlm aastal H.setOfArcs a sõlm  bipartition.secondPart. t kõigile a.datum.capacity = 1 aastal a
 Esimene jaotis sõlmed aastal H.setOfArcs kaks komplekti (G.setOfNodes ja part1) eraldatud nii palju, et ei kaar aastal part2 läheb ühest komplektist samasse komplekti (see partitsioon on võimalik, kuna G.setOfArcs on kahes jaotuses ). Seejärel lisage kõik vibud aastal G mis on suunatud G.setOfArcs -st kuni part1 part2 suunas. Seejärel looge üks sõlm allikas H.setOfArcs ja ühe sõlme terminal s ja loo rohkem vibud 
 Seejärel ehitage  t.
maxFlowProblemStateMinimaalne sõlme kate
 Sõlmekate a joonistus 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  See on komplekt sõlmed (G) pärit cover nii palju, et mis tahes kaar G.setOfNodes kohta a see peab olema tõsi: G.setOfArcs.
 Minimaalne sõlmekate on väikseim komplekt sõlmed graafikul, mis on endiselt a sõlmekate . Königi teoreem näitab seda graafikul kahes jaotuses , suurus maksimaalne vaste selles graafikus on võrdne minimaalne sõlmekate ja soovitab, kuidas sõlmekatet saab a-st taastada maksimaalne vaste :
 Oletame, et meil on kahepoolne (a.fromNode en cubierta) o (a.toNode en cubierta) ja maksimaalne vaste bipartition. Määratlege uus digrafo matching, H, vibud aastal H.setOfNodes=G.setOfNodes need on kahe komplekti liit.
 Esimene komplekt vibud H.setOfArcs sisse a, muutusega, et kui matching ja a.fromNode in bipartition.firstPart siis a.toNode en bipartition.secondPart ja a.fromNode vahetatakse akro loodud nad annavad selliseid vibud atribuut a.toNode näidata, et need on saadud vibud sees kokkusattumus .
 Teine komplekt on vibud a.datum.inMatching = True EI sees a, muutusega, et kui  matching ja a.fromNode en bipartition.secondPart siis  a.toNode en bipartition.firstPart ja a.fromNode vahetatakse kaar loodud (annab sellise kaar atribuut  a.toNode).
 Seejärel käivitage a esimene sügavusotsing ( DFS ) sõlm a.datum.inMatching = False aastal n mis ei ole  bipartition.firstPart ega n == a.fromNode Iga kaar  n == a.toNodes aastal a DFS-i ajal mõned sõlmed külastatakse ja teisi mitte (salvestage see teave väljale  matching). The minimaalne sõlmekate on liit sõlmed n.datum.visited ja sõlmed {a.fromNode para a en H.setOfArcs si ((a.datum.inMatching) y (a.fromNode.datum.visited))} . 
 Seda saab näidata sõitmaks a-st maksimaalne vaste kuni a minimaalne sõlmekate poolt a tõend vastuolu abil , võtke a kaar {a.fromNode para a en H.setOfArcs si (a.datum.inMatching) y (no a.toNode.datum.visited)} mida väidetavalt ei käsitletud, ja kaaluge kõiki nelja juhtumit selle kohta, kas a ja a.fromNode kuuluvad (kas nimega a.toNode või  toNode) kaar aastal kokkusattumus fromNode. Iga juhtum toob kaasa vastuolu DFS-i külastuste järjekorra tõttu sõlmed ja asjaolu, et matching on maksimaalne sobitamine .
 Oletame, et meil on funktsioon nende sammude käivitamiseks ja hulga tagastamiseks sõlmed mis sisaldab minimaalne sõlmekate kui talle antakse digrafo matching ja maksimaalne vaste G:
matchingLineaarse määramise probleem
 Lineaarse määramise probleem seisneb kaalude maksimaalse kokkulangevuse leidmises kaalutud kahepoolses graafis.
 Selliseid probleeme nagu see, mis ilmus selle postituse alguses, võib väljendada probleemina lineaarne määramine . Arvestades töötajate komplekti, ülesannete komplekti ja funktsiooni, mis näitab töötaja ülesandele määramise tasuvust, tahame maksimeerida kõigi tehtud ülesannete summat; see on lineaarse määramise probleem .
 Oletame, et ülesannete ja töötajate arv on võrdne, kuigi ma näitan, et seda eeldust on lihtne eemaldada. Rakenduses esindan ma vibu raskused atribuudiga 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  jaoks kaar a.datum.weight.
aKuhni-Munkresi algoritm
 Kuhni-Munkresi algoritm lahendab lineaarse määramise probleem . Hea rakendamine võib võtta aega WeightArcDatum = namedtuple('WeightArcDatum', [weight]) , (kus O(N^{4}) on arv sõlmed kell digrafo mis esindavad probleemi). Rakendus, mida on lihtsam seletada, võtab N (versiooni jaoks, mis taastub digrafos ) ja O (N ^ {5}) for (versiooni jaoks, mis hoiab digrafos ). See sarnaneb algoritmi kahe erineva rakendusega Edmonds-Karp .
 Selle kirjelduse jaoks töötan ainult täieliku kaheosalise graafikaga (nendega, kus pool graafikast) sõlmed on osa kahepoolne ja teine pool teises osas). Töötajas tähendab ülesande motiveerimine seda, et töötajaid on sama palju kui ülesandeid.
 See tundub märkimisväärne tingimus (mis siis, kui need komplektid pole võrdsed?), Kuid seda probleemi on lihtne lahendada; Sellest, kuidas seda teha, räägin viimases osas.
 Siin kirjeldatud algoritmi versioon kasutab kasulikku mõistet nullkaalu vibud . Kahjuks on sellel kontseptsioonil mõte vaid siis, kui lahendame a minimeerimine (Kui selle asemel, et maksimeerida oma töötajate tööülesannetest tulenevaid eeliseid, minimeerime hoopis selliste ülesannete maksumuse).
mis on disaini põhimõtted kunstis
 Õnneks on a teisendamine lihtne maksimaalse lineaarse määramise probleem sees minimaalne lineaarse määramise probleem iga kaalu määramine kaar O (N ^ {4}) aastal a kus  M-a.datum.weight. Maksimeerimisprobleemi lahendus originaal on identne lahusega pärast raskuste muutmist probleemi minimeerimine of Arc . Oletame, et ülejäänud osas teeme selle muudatuse.
 The Kuhni-Munkresi algoritm lahendada miinimumkaal kaalutud kahest jaotatud tabelis järjestusega maksimaalsed vasted graafikas kaalumata kahepoolne. Kui leiame ühe täiuslik vaste aastal digrafi esitamine lineaarse määramise probleemi ja kui iga kaalu kaar aastal kokkusattumus on null, seega oleme leidnud minimaalne kaal kuna see kokkusattumus viitab sellele, et kõik sõlmed kell digrafos on olnud paaris jaoks kaar võimalikult väikeste kuludega (ükski kulu ei või varasemate määratluste põhjal olla väiksem kui 0).
 Ei kedagi teist vibud saab lisada kokkusattumus (Kuna kõik sõlmed on juba paaritatud) ja ei vibud tuleb eemaldada kokkulangev sest võimalik asendamine kaar on vähemalt sama suur kaalu väärtus.
 Kui leiame a maksimaalne vaste selle subgrafo kohta M=max({a.datum.weight for a in G.setOfArcs}) sisaldavad ainult nullkaalu vibud ja see pole a täiuslik vaste , meil pole täielikku lahendust (alates kombinatsioon See ei ole täiuslik ). Siiski saame toota uut digrafo G muutes kaalu vibud aastal H nii et ilmuks uus 0-kaal vibud ja 'H' optimaalne lahendus on sama mis 'G' optimaalne lahendus. Kuna me garanteerime, et vähemalt üks nullkaalu vibu esineb igas iteratsioonis, garanteerime, et jõuame a täiuslik vaste aastal mitte rohkem kui | G.setOfNodes | 2 = N 2 sellistes kordustes.
 Oletame, et kahepoolne  G.setOfArcs, bipartition sisaldab sõlmed töötajate esindamine ja bipartition.firstPart See esindab sõlmed mis samal ajal kujutab endast tõendeid.
 Algoritm algab uue genereerimisega digrafo bipartition.secondPart. H. Mõned vibud aastal H.setOfNodes = G.setOfNodes Nemad on sõlmed H loodud n Iga sõlm bipartition.firstPart genereerib a kaar n aastal b Igaühele kaar H.setOfArcs aastal a kus bipartition.G.setOfArcs või a.fromNode = n, a.toNode = n kus b=Arc(a.fromNode, a.toNode, a.datum.weight - z).
 Lisaks vibud aastal z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) on loodud sõlmed H aastal n Igaüks neist sõlmed bipartition.secondPart genereerib a kaar n aastal b Igaühele kaar H.setOfArcs aastal a kus bipartition.G.setOfArcs või a.fromNode = n, a.toNode = n kus b=Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)).
  KMA: Seejärel moodustage uus digrafo z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) koosneb ainult nullkaalu vibud K ja sõlmed   intsident nendes vibud . Vormi a H aastal sõlmed sisse bipartition, seejärel kasutage K Selle saamiseks maksimaalne kombinatsioon (solve_mbm( bipartition )) matching. Kui K on täiuslik kombinatsioon aastal matching ( vibud aastal H Nemad on intsident kõigis sõlmed aastal matching), siis H.setOfNodes on optimaalne lahendus lineaarse määramise probleem .
 Vastasel juhul, kui matching See ei ole täiuslik , genereerib minimaalne sõlmekate kohta matching kasutades  K. Seejärel määrake node_cover = get_min_node_cover(matching, bipartition(K)). Määratlege 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)} sümbol ülaltoodud avaldises toimib operaatorina XOR . Siis !=. Siis arcs = arcs1.union(arcs2.union(arcs3)). Tagasi brändi juurde KMA . Algoritm jätkub kuni a täiuslik kombinatsioon . On kombinatsioon on ka lahendus lineaarse määramise probleem .
H=DiGraph(nodes,arcs)See rakendus on 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  sest see genereerib uue maksimaalne kombinatsioon O(N^{5}) igas iteratsioonis; sarnane kahe eelmise rakendusega Edmonds-Karp Seda algoritmi saab vaste jälgimiseks muuta ja arukalt igale iteratsioonile kohandada. Kui see on tehtud, muutub keerukus matching. Selle algoritmi täpsemat ja uuemat versiooni (mis nõuab mõnda täpsemat andmestruktuuri) saab käivitada O(N^{4}) Üksikasjad ülaltoodud lihtsama ja täpsema rakendamise kohta leiate aadressilt see postitus mis motiveeris seda blogi.
 Ükski operatsioon kaaluga kaar modifitseerib algoritmi tagastatud lõpliku omistamise. Seetõttu: Kuna meie sisendgraafikud on alati täielikult jagatud graafika , peab lahendus määrama igaüks sõlm ühes partitsioonis teise sõlm teises jaotises kaar nende kahe vahel sõlmed . Pange tähele, et toimingud, mis tehakse kaaluga kaar ärge kunagi muutke vibud vahejuhtumid üheski sõlmes eriti .
 Seega, kui algoritm lõpeb a täiuslik ja täielik sobiv kahesektsiooniline , iga sõlm on määratud a kaare nullkaal , kuna suhteline järjekord vibud millest sõlm ei ole algoritmi ajal muutunud ja kuna a nullkaalu vibu see on vibu võimalikult odav ja täiuslik kaheosaline täiendus tagab, et on olemas kaar igaühele sõlm . See tähendab, et loodud lahendus on tegelikult sama mis probleemilahendus algne lineaarne kaardistamine ilma kaalude muutmata kaar .
 Tasakaalustamata eraldised
 Näib, et algoritm on üsna piiratud, kuna kirjeldatud viisil töötab see ainult täielik kahepoolne graafika (need, kus pool sõlmed on osa kahepoolne ja teine pool teises osas). Töötajas tähendab ülesande motiveerimine seda, et töötajaid on nii palju kui on ülesandeid (see tundub üsna piirav).
 Siiski on olemas lihtne teisendus, mis eemaldab selle piirangu. Oletame, et töötajaid on vähem kui ülesandeid, lisame mõned näivtöötajad (piisab, et saadud graafik a täielik kahepoolne graafika ). Igal väljamõeldud töötajal on a kaar suunab töötaja igale ülesandele. Igaüks neist kaar kaal on 0 (matši panemine ei anna mingit täiendavat kasu). Pärast seda muudatust on graafik a täielik kahepoolne graafika mida saame lahendada. Fiktiivsele töötajale määratud ülesandeid ei alustata.
 Oletame, et ülesandeid on rohkem kui töötajaid. Lisasime mõned näivülesanded (piisavalt, et saadud graafik a täisjagatud graafik ). Igal väljamõeldud ülesandel on a kaar suunatakse igalt tööliselt fiktiivsele ülesandele. Igaüks neist kaar selle kaal on 0 (matši panemine ei anna mingit täiendavat kasu). Pärast seda muudatust on graafik a täisjagatud graafik mida saame lahendada. Ükski väljamõeldud ülesandega töötaja ei ole selle aja jooksul tööle võetud.
 Lineaarse määramise näide
 Lõpuks teeme näite koodiga, mida olen kasutanud. Ma muudan probleemi näidet alates siin . Meil on 3 ülesannet: meil on vaja vannitoa puhastamiseks , põrandat pühkima , Y pese aknaid .
 Saadaval töötajad on Alice , Bob , Charlie Y Diane . Iga töötaja annab meile palga, mida ta vajab ühe ülesande kohta. Siin on palgad töötaja kohta:
     Puhastage vannituba  Põrandat pühkima  Peske Windows  
 
  Alice  2 dollarit  3 dollarit  3 dollarit  
  Bob  3 dollarit  2 dollarit  3 dollarit  
  Charlie  3 dollarit  3 dollarit  2 dollarit  
  Diane  9 dollarit  9 dollarit  1 dollar  
 
 
 Kui tahame maksta kõige vähem raha, kuid saame siiski kõik ülesanded tehtud, siis kes peaks millist ülesannet tegema? Alustage kaheosalist probleemi esindava digraafi jaoks näiv ülesande sisestamine.
     Puhastage vannituba  Põrandat pühkima  Peske Windows  Ära tee midagi  
 
  Alice  2 dollarit  3 dollarit  3 dollarit  0 dollarit  
  Bob  3 dollarit  2 dollarit  3 dollarit  0 dollarit  
  Charlie  3 dollarit  3 dollarit  2 dollarit  0 dollarit  
  Diane  9 dollarit  9 dollarit  1 dollar  0 dollarit  
 
 
 Eeldades, et probleem on kodeeritud a digrafo , siis O (N ^ {3}) lahendab probleemi ja tagastab ülesande. On lihtne kontrollida, kas optimaalne eraldamine (madalaim hind) maksab 5 dollarit.
 Siin on ülaltoodud koodi genereeritud lahenduse visualiseerimine:
  
  
 See on kõik . Nüüd teate kõike, mida peate teadma lineaarse määramise probleemi kohta.
 Kogu selle artikli koodi leiate aadressilt GitHub .

	Puhastage vannituba	Põrandat pühkima	Peske Windows
Alice	2 dollarit	3 dollarit	3 dollarit
Bob	3 dollarit	2 dollarit	3 dollarit
Charlie	3 dollarit	3 dollarit	2 dollarit
Diane	9 dollarit	9 dollarit	1 dollar

	Puhastage vannituba	Põrandat pühkima	Peske Windows	Ära tee midagi
Alice	2 dollarit	3 dollarit	3 dollarit	0 dollarit
Bob	3 dollarit	2 dollarit	3 dollarit	0 dollarit
Charlie	3 dollarit	3 dollarit	2 dollarit	0 dollarit
Diane	9 dollarit	9 dollarit	1 dollar	0 dollarit


    
    
    
        
            
                
                    
                        
                             Arendajate töövood: parema kasutajaliidese / kasutajaliidese pakkumine ajas ja vormis 
                             Elustiil 
                                
                        
                        
                             
                        
                    
                
                
                    
                        
                             
                        
                        
                             Miks ma vahetasin AngularJS-lt React-le 
                             Tehnoloogia 
                                
                        
                    
                
            
        
    
    
    
    
        

	
		
			
				
					Lemmik Postitused
					
						   
						
							 Rubiini algoritmi dokumentatsioon koos AsciiDoci ja Knitriga 
						
					

						   
						
							 Ärge laske end lollitada: arvutage töötajate ja konsultantide tegelikud kulud 
						
					

						   
						
							 Töötajate säilitamise strateegiad 101: töökohaõpe 
						
					

						   
						
							 AngularJSi õpetus: kohandatud direktiivide demüstifitseerimine 
						
					

						   
						
							 Vilgas riistvara koos sisseehitatud tarkvaraarendusega 
						
					
				
			
			
				
					 
					
						   
						
							 Masinõppe manused: keerukate andmete lihtsustamine 
						
					

						   
						
							 Forexi algoritmiline kauplemine: praktiline lugu inseneridele 
						
					

						   
						
							 Twitteri andmekaevandus: Pythoni abil suurandmete analüüsi juhend 
						
					

						   
						
							 Tehisintellekti investeeringute põhialus: põhitööde rajamine (I osa) 
						
					

						   
						
							 ApeeScape'i nimekiri parimatest tasuta programmeerimisraamatutest 
						
					
					
				
			
			
				
					Lemmik Postitused
					 Kreeka võlakriisi põhjused
parim sait c ++ õppimiseks
kuidas saavad biotehnoloogiaettevõtted raha teenida
llc c corp vs llc s corp
pythoni masinõpe näite järgi
javascripti kuupäeva ja kellaaja vorming
 
							
					
				
			
			
				
					Kategooriad
					 Elustiil  Tagumine Ots  Mobiilne Disain  Jaotatud Võistkonnad  Tööriistad Ja Õpetused  Vilgas Talent  Tulud Ja Kasv  Ux Disain  Veebi Kasutajaliides  Investorid Ja Rahastamine 
				
			
		
	




	
		
			© 2021 | Kõik Õigused Kaitstud
			 apeescape2.com