Наука За Данни И Бази Данни

Пиков поток и проблем с линейното присвояване

Ето проблем: Вашата компания назначава изпълнители за изпълнение на договори. Разглеждате списъците си и решавате кои изпълнители са на разположение за едномесечен договор и преглеждате наличните си договори, за да видите кои са за едномесечни задачи. Тъй като знаете колко ефективно всеки изпълнител може да изпълни всеки договор, как определяте изпълнителите, за да увеличите максимално ефективността за този месец?

Това е пример за проблема с присвояването и проблемът може да бъде решен с класическия Унгарски алгоритъм .

Двустранно съвпадение

Унгарският алгоритъм (известен също като алгоритъм на Kuhn-Munkres) е полиномиален времеви алгоритъм, който максимизира теглото на тежестта върху претеглена двустранна графика. Тук изпълнителите и договорите могат да бъдат моделирани като двустранна графика, като тяхната ефективност е тежестта на ръбовете между изпълнителя и възлите на договора.

В тази статия ще научите за изпълнението на унгарския алгоритъм, който използва Алгоритъм на Едмъндс-Карп за решаване на проблема с линейното присвояване. Също така ще научите как алгоритъмът Edmonds-Karp е малка модификация на Форд-Фулкърсън и значението на тази модификация.

Проблемът с пиковия поток

Самият проблем с пиковия поток може да бъде неофициално описан като проблем с преместването на някаква течност или газ през мрежа от тръби от един източник до един терминал. Това се прави с предположението, че налягането в мрежата е достатъчно, за да гарантира, че флуидът или газът не могат да останат в която и да е дължина на тръбата или фитинга на тръбата (местата, където се срещат различни дължини на тръбата).

Чрез извършване на определени промени в графиката, проблемът с разпределението може да се превърне в проблем с пиков поток.

Предварителни

Идеите, необходими за решаването на тези проблеми, възникват в много математически и инженерни дисциплини, често подобни понятия са известни с различни имена и се изразяват по различни начини (например матрици за съседство и списъци за съседство). Тъй като тези идеи са доста езотерични, се прави избор за това как тези понятия обикновено ще бъдат дефинирани за дадена обстановка.

Тази статия няма да предполага никакви предварителни познания освен кратка теория на уводния набор.

Реализациите в тази публикация представляват проблемите като насочени графики (диграф).

Digrafo

A digrafo има две атрибути , setOfNodes Y. setOfArcs . И двата атрибута са комплекти (разхвърляни колекции). В блоковете с кодове в тази публикация използвам Python замразени , но тази подробност не е особено важна.

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

(Забележка: Този и всички останали кодове в тази статия са написани на Python 3.6.)

Възли

A възел n Състои се от два атрибута:

n.uid: A Уникален идентификатор .

Това означава, че за всеки от двата възела x и y,

x.uid != y.uid

n.datum: Това представлява всеки обект от данни.

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

Дъга

A дъга a Състои се от три атрибута:

a.fromNode: Това е a възел , както е определено по-горе.
a.toNode: Това е a възел , както е определено по-горе.
a.datum: Това представлява всеки обект от данни.

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

Комплектът от лъкове в диграф представлява двоична връзка в възли в диграф . Съществуването на дъга a предполага, че има връзка между a.fromNode и a.toNode.

В насочена графика (за разлика от неориентираната графика), съществуването на връзка между a.fromNode и a.toNode не предполагат, че подобна връзка между a.toNode и a.fromNode съществува.

гещалт закон на фигурата и основата

Това е така, защото в ненасочена графика връзката, която се изразява, не е непременно симетрична.

Цифри

Възли Y. лъкове може да се използва за дефиниране на диграф , но за удобство, в следните алгоритми, a диграф използвайки като a речник .

Ето метод, който може да преобразува горното графично представяне в речник, подобен на е :

def digraph_to_dict(G): G_as_dict = dict([]) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) pdg(G) raise KeyError(err_msg) if(a.toNode not in G.setOfNodes): err_msg = 'There is no Node {a.toNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) pdg(G) raise KeyError(err_msg) G_as_dict[a.fromNode] = (G_as_dict[a.fromNode].union(frozenset([a]))) if (a.fromNode in G_as_dict) else frozenset([a]) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if a.toNode not in G_as_dict: G_as_dict[a.toNode] = frozenset([]) return G_as_dict

И ето още един, който го превръща в речник на речници, друга операция, която ще ви бъде полезна:

def digraph_to_double_dict(G): G_as_dict = dict([]) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if(a.toNode not in G.setOfNodes): err_msg = 'There is no Node {a.toNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if(a.fromNode not in G_as_dict): G_as_dict[a.fromNode] = dict({a.toNode : frozenset([a])}) else: if(a.toNode not in G_as_dict[a.fromNode]): G_as_dict[a.fromNode][a.toNode] = frozenset([a]) else: G_as_dict[a.fromNode][a.toNode] = G_as_dict[a.fromNode][a.toNode].union(frozenset([a])) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if a.toNode not in G_as_dict: G_as_dict[a.toNode] = dict({}) return G_as_dict

Когато статията говори за a диграф тъй като речникът го представя, той ще спомене G_as_dict за справка.

Понякога помага да се вземе възел на а диграф G докато вашият uid (Уникален идентификатор):

def find_node_by_uid(find_uid, G): nodes = {n for n in G.setOfNodes if n.uid == find_uid} if(len(nodes) != 1): err_msg = 'Node with uid {find_uid!s} is not unique.'.format(**locals()) raise KeyError(err_msg) return nodes.pop()

Когато идентифицират графики, хората понякога използват термините възел и връх, за да се отнасят към едно и също понятие; същото се казва и за термините дъга и ръб.

В Python има две графични изображения, е който използва речници и други който използва обекти за представяне на графики. Представянето в тази публикация попада между тези две общи представителства.

Това е моето представяне на a диграф . Има много такива, но това е мое.

Пътища и писти

Нека S_Arcs бъди a последователност окончателно (подредена колекция) на лъкове в диграф G дотолкова, че ако a е всеки дъга в S_Arcs с изключение на последния и b следва a в последователността, тогава трябва да има a възел n = a.fromNode в G.setOfNodes като a.toNode = b.fromNode.

Започвайки от първия дъга в S_Arcs и продължава до последното дъга в S_Arcs, събира (в намерения ред) всички възли n както ги дефинираме по-горе между всеки два лъкове последователно в S_Arcs. Маркирайте поръчаната колекция от възли събрани по време на тази операция S_{Nodes}.

def path_arcs_to_nodes(s_arcs): s_nodes = list([]) arc_it = iter(s_arcs) step_count = 0 last = None try: at_end = False last = a1 = next(arc_it) while (not at_end): s_nodes += [a1.fromNode] last = a2 = next(arc_it) step_count += 1 if(a1.toNode != a2.fromNode): err_msg = 'Error at index {step_count!s} of Arc sequence.'.format(**locals()) raise ValueError(err_msg) a1 = a2 except StopIteration as e: at_end = True if(last is not None): s_nodes += [last.toNode] return s_nodes

Ако някой възел се появява повече от веднъж в последователността S_Nodes след това се обадете S_Arcs а Път от диграф G.
В противен случай извикайте S_Arcs а чрез от list(S_Nodes)[0] a list(S_Nodes)[-1] в диграф G.

Изходен възел

Обърнете се към възел s а изходен възел в диграф G ако s е в G.setOfNodes и G.setOfArcs няма дъга a като a.toNode = s.

def source_nodes(G): to_nodes = frozenset({a.toNode for a in G.setOfArcs}) sources = G.setOfNodes.difference(to_nodes) return sources

Терминален възел

Обърнете се към възел t а терминален възел в диграф G ако t е в G.setOfNodes и G.setOfArcs няма дъга a като a.fromNode = t.

def terminal_nodes(G): from_nodes = frozenset({a.fromNode for a in G.setOfArcs}) terminals = G.setOfNodes.difference(from_nodes) return terminals

Cortes y Cortes s-t

A разрез cut на а диграф G свързани е подмножество от лъкове от G.setOfArcs който част множеството от възли G.setOfNodes в G. G е свързан, ако всеки възел n в G.setOfNodes има поне един дъга a в G.setOfArcs като n = a.fromNode или n = a.toNode, но не a.fromNode != a.toNode.

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

Дефиницията по-горе се отнася до подгрупата на лъкове , но можете също да дефинирате дял на възли от G.setOfNodes.

За функции predecessors_of и successors_of, n е възел в комплекта G.setOfNodes от диграф G и cut е разрез от G:

def cut_predecessors_of(n, cut, G): allowed_arcs = G.setOfArcs.difference(frozenset(cut.setOfCutArcs)) predecessors = frozenset({}) previous_count = len(predecessors) reach_fringe = frozenset({n}) keep_going = True while( keep_going ): reachable_from = frozenset({a.fromNode for a in allowed_arcs if (a.toNode in reach_fringe)}) reach_fringe = reachable_from predecessors = predecessors.union(reach_fringe) current_count = len(predecessors) keep_going = current_count - previous_count > 0 previous_count = current_count return predecessors def cut_successors_of(n, cut, G): allowed_arcs = G.setOfArcs.difference(frozenset(cut.setOfCutArcs)) successors = frozenset({}) previous_count = len(successors) reach_fringe = frozenset({n}) keep_going = True while( keep_going ): reachable_from = frozenset({a.toNode for a in allowed_arcs if (a.fromNode in reach_fringe)}) reach_fringe = reachable_from successors = successors.union(reach_fringe) current_count = len(successors) keep_going = current_count - previous_count > 0 previous_count = current_count return successors

Нека cut Бъдете a разрез от диграф G.

def get_first_part(cut, G): firstPartFringe = frozenset({a.fromNode for a in cut.setOfCutArcs}) firstPart = firstPartFringe for n in firstPart: preds = cut_predecessors_of(n,cut,G) firstPart = firstPart.union(preds) return firstPart def get_second_part(cut, G): secondPartFringe = frozenset({a.toNode for a in cut.setOfCutArcs}) secondPart = secondPartFringe for n in secondPart: succs= cut_successors_of(n,cut,G) secondPart = secondPart.union(succs) return secondPart

cut е разрез от диграф G ако: (get_first_part(cut, G).union(get_second_part(cut, G)) == G.setOfNodes) y (len(get_first_part(cut, G).intersect(get_second_part(cut, G))) == 0) cut се нарича a х-у разрез ако (x in get_first_part(cut, G)) y (y in get_second_part(cut, G) ) y (x != y). Когато възел x в х-у разрез cut е изходен възел и възел y в х-у разрез е терминален възел , след това това разрез се нарича a s-t изрязване .

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

Поточни мрежи

Можете да използвате диграф G да представлява поточна мрежа.

Задайте всеки възел n, където n е в G.setOfNodes a n.datum което е FlowNodeDatum:

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

Задайте всеки дъга a, където a е G.setOfArcs и a.datum което е FlowArcDatum.

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

flowNodeDatum.flowIn и flowNodeDatum.flowOut Те са реални числа положителен .

flowArcDatum.capacity и flowArcDatum.flow те също са положителни реални числа.

Урок за уеб сървър на raspberry pi

За всеки възел възел n в G.setOfNodes:

n.datum.flowIn = sum({a.datum.flow for a in G.Arcs if a.toNode == n}) n.datum.flowOut = sum({a.datum.flow for a in G.Arcs if a.fromNode == n})

The Диграф G сега представлява поточна мрежа .

The поток от G се отнася до потока a.flow за всички лъкове a в G.

Възможни потоци

Оставете го диграф G представляват a поточна мрежа .

The поточна мрежа представено от G имат възможни потоци да:

За всеки възел n в G.setOfNodes с изключение на изходни възли Y. терминални възли : n.datum.flowIn = n.datum.flowOut.
За всеки дъга a в G.setOfNodes: a.datum.capacity <= a.datum.flow.

Извиква се условие 1 консервационно ограничаване .

Извиква се условие 2 ограничаване на капацитета .

Капацитет на рязане

The капацитет на рязане на а s-t изрязване stCut с изходен възел s и а терминален възел t на а поточна мрежа представляван от a диграф G то е:

def cut_capacity(stCut, G): part_1 = get_first_part(stCut.cut,G) part_2 = get_second_part(stCut.cut,G) s_part = part_1 if stCut.s in part_1 else part_2 t_part = part_1 if stCut.t in part_1 else part_2 cut_capacity = sum({a.datum.capacity for a in stCut.cut.setOfCutArcs if ( (a.fromNode in s_part) and (a.toNode in t_part) )}) return cut_capacity

Намаляване на минималния капацитет

Нека stCut = stCut(s,t,cut) Бъдете a s-t изрязване на а поточна мрежа представляван от a диграф G.

stCut той ли е минимален капацитет на рязане от поточна мрежа представено от G ако няма друга s-t изрязване stCutCompetitor в това поточна мрежа като:

 cut_capacity(stCut, G) Оголване на потоците
 Бих искал да се позова на диграф какъв би бил резултатът от приемането на диграф G и изчистете всички данни за потока от всички възли в G.setOfNodes а също и всички лъкове в G.setOfArcs.
def strip_flows(G): new_nodes= frozenset( (Node(n.uid, FlowNodeDatum(0.0,0.0)) for n in G.setOfNodes) ) new_arcs = frozenset([]) for a in G.setOfArcs: new_fromNode = Node(a.fromNode.uid, FlowNodeDatum(0.0,0.0)) new_toNode = Node(a.toNode.uid, FlowNodeDatum(0.0,0.0)) new_arc = Arc(new_fromNode, new_toNode, FlowArcDatum(a.datum.capacity, 0.0)) new_arcs = new_arcs.union(frozenset([new_arc])) return DiGraph(new_nodes, new_arcs) Проблем с пиковия поток
 A поточна мрежа представен като a диграф G, а изходен възел s в G.setOfNodes и а терминален възел t в G.setOfNodes, G може да представлява a проблем с пиковия поток да:
(len(list(source_nodes(G))) == 1) and (next(iter(source_nodes(G))) == s) and (len(list(terminal_nodes(G))) == 1) and (next(iter(terminal_nodes(G))) == t) Маркирайте това представяне:
MaxFlowProblemState = namedtuple('MaxFlowProblemState', ['G','sourceNodeUid','terminalNodeUid','maxFlowProblemStateUid']) Където sourceNodeUid = s.uid, terminalNodeUid = t.uid и maxFlowProblemStateUid е идентификатор за екземпляра на проблема.
 Решение за пиков поток
 Нека maxFlowProblem представляват a проблем с пиковия поток . Решението на проблема maxFlowProblem може да бъде представено чрез a поточна мрежа представен като a диграф H.
 The Диграф H е решение осъществимо за него проблем с пиковия поток на входа python maxFlowProblem да:
   strip_flows(maxFlowProblem.G) == strip_flows(H).
 
  H е поточна мрежа и има възможни потоци .
 
 
 Ако в допълнение към 1 и 2:
  Не може да има друг поточна мрежа представляван от диграф K като strip_flows(G) == strip_flows(K) и find_node_by_uid(t.uid,G).flowIn .
 
 Тогава H това също е решение оптимално за maxFlowProblem.
 С други думи, а възможно решение за пиков поток може да се представи с a диграф , че:
   Той е идентичен с диграф G на съответния проблем с пиковия поток с изключение на потока n.datum.flowIn, n.datum.flowOut и потока a.datum.flow на някой от възли Y. лъкове те могат да бъдат различни.
 
  Представлява a поточна мрежа какво не е наред с него възможни потоци .
 
 
 И може да представлява a оптимално решение за пиков поток ако допълнително:
  flowIn за него възел което съответства на терминален възел в проблем с пиковия поток е възможно най-голям (когато условията 1 и 2 все още са изпълнени).
 
 Да диграф H представлява a решение за пиков поток : find_node_by_uid(s.uid,H).flowOut = find_node_by_uid(t.uid,H).flowIn това следва от максимален дебит, минимална теорема за срязване (обсъдено по-долу). Неформално, тъй като H имат жизнеспособни потоци това означава, че поток не може да бъде „създаден“ (с изключение на изходен възел s), нито 'унищожен' (с изключение на терминален възел t) при пресичане на който и да е (друг) възел ( консервационни ограничения ).
 Тъй като a проблем с пиковия поток   съдържа само един изходен възел s и сингъл терминален възел t, всеки поток 'създаден' в s трябва да бъде „унищожен“ в t вълна поточна мрежа   не имат възможни потоци ( консервационно ограничение е бил изнасилен).
 Оставете го диграф H представляват a възможно решение за пиков поток ; извиква се горната стойност Стойност на потока s-t от H.
 Позволява:
mfps=MaxFlowProblemState(H, maxFlowProblem.sourceNodeUid, maxFlowProblem.terminalNodeUid, maxFlowProblem.maxFlowProblemStateUid) Това означава, че mfps е наследник държава от  maxFlowProblem, което означава, че mfps е точно като maxFlowProblem с изключение на това, че стойностите на a.flow за дъги a в maxFlowProblem.setOfArcs може да се различава от a.flow за дъги a в mfps.setOfArcs.
def get_mfps_flow(mfps): flow_from_s = find_node_by_uid(mfps.sourceNodeUid,mfps.G).datum.flowOut flow_to_t = find_node_by_uid(mfps.terminalNodeUid,mfps.G).datum.flowIn if( (flow_to_t - flow_from_s) > 0): raise Exception('Infeasible s-t flow') return flow_to_t Това е показване на mfps заедно със своите maxFlowProb асоциирани. Всеки дъга a в изображението има етикет, тези етикети са a.datum.flowFrom/a.datum.flowTo, всеки възел n в изображението има етикет и тези етикети са n.uid {n.datum.flowIn / a.datum.flowOut}.
  
 Срязващ поток
 Нека mfps представляват проблемно състояние MaxFlowProblemState и нека stCut представляват a разрез от mfps.G. The срязващ поток stCut се дефинира по следния начин:
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  прекъсване на потока s-t е сумата от потоците на дяла, съдържащ изходен възел за дяла, съдържащ терминален възел минус сумата от потоците на дяла, съдържащ терминален възел за дяла, съдържащ изходен възел .
 Максимален дебит, минимално срязване
 Какво maxFlowProblem представляват a проблем с пиковия поток и че решението на maxFlowProblem е представен от a поточна мрежа представен като диграф H.
 Нека minStCut на минимален капацитет на рязане от поточна мрежа представено от maxFlowProblem.G.
 Защото в потока на пиков поток потокът произхожда от единичен изходен възел и завършва в един възел терминал и, поради ограничения на капацитета и консервационни ограничения , знаем, че целият поток, влизащ в maxFlowProblem.terminalNodeUid трябва да пресече всеки s-t изрязване , по-специално трябва да пресича minStCut. Това означава:
къде е дневника за грешки в php
get_flow_value(H, maxFlowProblem) <= cut_capacity(minStCut, maxFlowProblem.G) Решение на проблема с пиковия поток
 Основната идея за решаване на a проблем с пиковия поток maxFlowProblem е да започнете с a решение за пиков поток представен от диграф H. Такава отправна точка може да бъде H = strip_flows(maxFlowProblem.G).
 След това задачата е да се използва H и от някои алчен промяна на стойностите a.datum.flow на някои лъкове a в H.setOfArcs за да произведе друг решение за пиков поток представен от диграф K така че K все още не може да представлява поточна мрежа с жизнеспособни потоци и get_flow_value(H, maxFlowProblem) . Докато този процес продължава, качеството (get_flow_value(K, maxFlowProblem)) на решение за пиков поток (K), намерен наскоро по-добър от всеки друг решение за пиков поток което е намерено. Ако процесът достигне точка, в която знае, че не е възможно по-нататъшно подобрение, процесът може да прекрати и ще върне решение за пиков поток   оптимално .
 Описанието по-горе е общо и пропуска много тестове, като например, ако такъв процес е възможен или колко време може да отнеме, ще дам още подробности и алгоритъма.
 Теорема за максималния поток, минимално срязване
 От книгата Потоци в мрежи на Форд и Фулкерсън , декларацията на Теорема за максималния поток, минимално срязване (Теорема 5.1) е:
   За всяка мрежа максималната стойност на потока от s a t е равна на минималната режеща способност на всички разфасовки, които се разделят s и t.
 
 Използвайки дефинициите в този пост, това означава:
 Решението на maxFlowProblem представляван от a поточна мрежа представен като диграф H то е оптимално да:
get_flow_value(H, maxFlowProblem) == cut_capacity(minStCut, maxFlowProblem.G)  Харесва ми този тест на теоремата и Уикипедия има други .
 The теоремата за максимален дебит, минимално срязване се използва за демонстриране на правилността и пълнотата на Метод на Форд-Фулкерсън .
 Също така ще дам доказателство за теоремата в раздела след начини за увеличаване .
 Методът на Форд-Фулкърсън и алгоритъмът на Едмъндс-Карп
  CLRS дефинирайте метода на Форд-Фулкерсън (раздел 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 Остатъчна графика
 The Остатъчна графика на а поточна мрежа представен като диграф 'G' може да бъде представено като a диграф G_f:
ResidualDatum = namedtuple('ResidualDatum', ['residualCapacity','action']) def agg_n_to_u_cap(n,u,G_as_dict): arcs_out = G_as_dict[n] return sum([a.datum.capacity for a in arcs_out if( (a.fromNode == n) and (a.toNode == u) ) ]) def agg_n_to_u_flow(n,u,G_as_dict): arcs_out = G_as_dict[n] return sum([a.datum.flow for a in arcs_out if( (a.fromNode == n) and (a.toNode == u) ) ]) def get_residual_graph_of(G): G_as_dict = digraph_to_dict(G) residual_nodes = G.setOfNodes residual_arcs = frozenset([]) for n in G_as_dict: arcs_from = G_as_dict[n] nodes_to = frozenset([find_node_by_uid(a.toNode.uid,G) for a in arcs_from]) for u in nodes_to: n_to_u_cap_sum = agg_n_to_u_cap(n,u,G_as_dict) n_to_u_flow_sum = agg_n_to_u_flow(n,u,G_as_dict) if(n_to_u_cap_sum > n_to_u_flow_sum): flow = round(n_to_u_cap_sum - n_to_u_flow_sum, TOL) residual_arcs = residual_arcs.union( frozenset([Arc(n,u,datum=ResidualDatum(flow, 'push'))]) ) if(n_to_u_flow_sum > 0.0): flow = round(n_to_u_flow_sum, TOL) residual_arcs = residual_arcs.union( frozenset([Arc(u,n,datum=ResidualDatum(flow, 'pull'))]) ) return DiGraph(residual_nodes, residual_arcs)   agg_n_to_u_cap(n,u,G_as_dict) върнете се към сумата от a.datum.capacity за лъкове в подмножеството на G.setOfArcs където той дъга a е в подмножеството, ако a.fromNode = n и a.toNode = u.
 
  agg_n_to_u_cap(n,u,G_as_dict) връща сумата от a.datum.flow за всички лъкове в подмножеството на G.setOfArcs където той дъга a е в подмножеството, ако a.fromNode = n и a.toNode = u.
 
 
 Накратко, остатъчна графика G_f представлява определени действия, които могат да бъдат извършени върху диграф `G`.
 Всяка двойка възли n, u в G.setOfNodes от поточна мрежа представен от диграф G може да генерира 0,1 или 2 лъкове в остатъчна графика G_f на „G“.
   Двойката n, u не генерира лъкове в G_f ако няма дъга a в G.setOfArcs като a.fromNode = n и a.toNode = u.
 
  Двойката n, u генерира дъга a в G_f.setOfArcs където a представлява a дъга обозначени като a импулсен поток от n a u a = Arco (n, u, datum = ResidualNode (n_to_u_cap_sum - n_to_u_flow_sum)) ако n_to_u_cap_sum> n_to_u_flow_sum.
 
  Двойката n, u генерира дъга a в G_f.setOfArcs където a представлява a дъга обозначени като a издърпайте поток дъга от n a u a = Arco (n, u, datum = ResidualNode (n_to_u_cap_sum - n_to_u_flow_sum)) ако n_to_u_flow_sum> 0.0.
 
 
   Всеки дъга на изтласкващия поток в G_f.setOfArcs представлява действието на добавяне на общ поток x <= n_to_u_cap_sum - n_to_u_flow_sum да се лъкове в подмножеството на G.setOfArcs където той дъга a е в подмножеството, ако a.fromNode = n и a.toNode = u.
 
  Всеки дъга на теглещия поток в G_f.setOfArcs представлява действието на изваждане на общия поток x <= n_to_u_flow_sum да се лъкове в подмножеството на G.setOfArcs където дъга a е в подмножеството, ако a.fromNode = n и a.toNode = u.
 
 
 Извършете индивидуално действие като Натиснете или все още от G_f в лъкове приложимо в G може да генерира поточна мрежа без възможни потоци защото ограничения на капацитета или консервационни ограничения може да бъде изнасилено в генерирана поточна мрежа .
 Ето визуализация на остатъчна графика от предишния пример за показване на a решение за пиков поток , на дисплея всеки дъга a представлява a.residualCapacity.
  
 Нарастващ път
 Нека maxFlowProblem Бъдете a проблем с пиковия поток , и нека G_f = get_residual_graph_of (G) бъда остатъчна графика от maxFlowProblem.G.
 A път нагоре augmentingPath за maxFlowProblem е всеки чрез от find_node_by_uid(maxFlowProblem.sourceNode,G_f) a find_node_by_uid(maxFlowProblem.terminalNode,G_f).
 Оказва се, че а път за увеличаване augmentingPath може да се приложи към a решение за пиков поток представляван от диграф H генериращ друг решение за пиков поток представляван от диграф K където get_flow_value (H, maxFlowProblem)  ако H Не е оптимално .
 Тук виждате как:
def augment(augmentingPath, H): augmentingPath = list(augmentingPath) H_as_dict = digraph_to_dict(H) new_nodes = frozenset({}) new_arcs = frozenset({}) visited_nodes = frozenset({}) visited_arcs = frozenset({}) bottleneck_residualCapacity = min( augmentingPath, key=lambda a: a.datum.residualCapacity ).datum.residualCapacity for x in augmentingPath: from_node_uid = x.fromNode.uid if x.datum.action == 'push' else x.toNode.uid to_node_uid = x.toNode.uid if x.datum.action == 'push' else x.fromNode.uid from_node = find_node_by_uid( from_node_uid, H ) to_node = find_node_by_uid( to_node_uid, H ) load = bottleneck_residualCapacity if x.datum.action == 'push' else -bottleneck_residualCapacity for a in H_as_dict[from_node]: if(a.toNode == to_node): test_sum = a.datum.flow + load new_flow = a.datum.flow new_from_node_flow_out = a.fromNode.datum.flowOut new_to_node_flow_in = a.toNode.datum.flowIn new_from_look = {n for n in new_nodes if (n.uid == a.fromNode.uid)} new_to_look = {n for n in new_nodes if (n.uid == a.toNode.uid) } prev_from_node = new_from_look.pop() if (len(new_from_look)>0) else a.fromNode prev_to_node = new_to_look.pop() if (len(new_to_look)>0) else a.toNode new_nodes = new_nodes.difference(frozenset({prev_from_node})) new_nodes = new_nodes.difference(frozenset({prev_to_node})) if(test_sum > a.datum.capacity): new_flow = a.datum.capacity new_from_node_flow_out = prev_from_node.datum.flowOut - a.datum.flow + a.datum.capacity new_to_node_flow_in = prev_to_node.datum.flowIn - a.datum.flow + a.datum.capacity load = test_sum - a.datum.capacity elif(test_sum <0.0): new_flow = 0.0 new_from_node_flow_out = prev_from_node.datum.flowOut - a.datum.flow new_to_node_flow_in = prev_to_node.datum.flowIn - a.datum.flow load = test_sum else: new_flow = test_sum new_from_node_flow_out = prev_from_node.datum.flowOut - a.datum.flow + new_flow new_to_node_flow_in = prev_to_node.datum.flowIn - a.datum.flow + new_flow load = 0.0 new_from_node_flow_out = round(new_from_node_flow_out, TOL) new_to_node_flow_in = round(new_to_node_flow_in, TOL) new_flow = round(new_flow, TOL) new_from_node = Node(prev_from_node.uid, FlowNodeDatum(prev_from_node.datum.flowIn, new_from_node_flow_out)) new_to_node = Node(prev_to_node.uid, FlowNodeDatum(new_to_node_flow_in, prev_to_node.datum.flowOut)) new_arc = Arc(new_from_node, new_to_node, FlowArcDatum(a.datum.capacity, new_flow)) visited_nodes = visited_nodes.union(frozenset({a.fromNode,a.toNode})) visited_arcs = visited_arcs.union(frozenset({a})) new_nodes = new_nodes.union(frozenset({new_from_node, new_to_node})) new_arcs = new_arcs.union(frozenset({new_arc})) not_visited_nodes = H.setOfNodes.difference(visited_nodes) not_visited_arcs = H.setOfArcs.difference(visited_arcs) full_new_nodes = new_nodes.union(not_visited_nodes) full_new_arcs = new_arcs.union(not_visited_arcs) G = DiGraph(full_new_nodes, full_new_arcs) full_new_arcs_update = frozenset([]) for a in full_new_arcs: new_from_node = a.fromNode new_to_node = a.toNode new_from_node = find_node_by_uid( a.fromNode.uid, G ) new_to_node = find_node_by_uid( a.toNode.uid, G ) full_new_arcs_update = full_new_arcs_update.union( {Arc(new_from_node, new_to_node, FlowArcDatum(a.datum.capacity, a.datum.flow))} ) G = DiGraph(full_new_nodes, full_new_arcs_update) return G В горното, TOL е стойност на толеранс за закръглявам стойностите на потока в мрежата. Това е, за да се избегне каскадата на неточност на изчисленията с плаваща запетая . Така например използвах „TOL = 10“ за закръгляване до 10 значими цифри .
 Оставете K = augment (augmentingPath, H), след това K представлява a възможно решение за пиков поток за maxFlowProblem. За да е вярно твърдението, поточна мрежа представено от K  трябва да има възможни потоци (да не се нарушава ограничение на капацитета вълна ограничение за опазване . Ето защо: В горния метод всеки възел добавен към новия поточна мрежа представен от диграф K е точно копие на възел от диграф H или а възел n който е добавил същия номер към вашия n.datum.flowIn като вашия n.datum.flowOut. Това означава, че ограничение за опазване то е изпълнено в „К“, стига да е изпълнено в „Н“. The ограничение за опазване е удовлетворен, защото изрично проверяваме дали някой дъга нов a в мрежата имате a.datum.flow <= a.datum.capacity; следователно, докато лъкове от множеството H.setOfArcs които бяха копирани непроменени в K.setOfArcs не нарушават ограничение на капацитета , тогава K не нарушава ограничение на капацитета .
 Вярно е също, че get_flow_value (H, maxFlowProblem)  ако H Не е оптимално .
 Ето защо: За увеличаване на маршрута augmentingPath съществува в диграф представянето на остатъчна графика G_f на а проблем с пиковия поток maxFlowProblem после последната дъга a в augmentingPath трябва да е a дъга 'Push' и трябва да има a.toNode == maxFlowProblem.terminalNode. A път за увеличаване се определя като завършващ на терминален възел от проблем с пиковия поток за което е a път за увеличаване . От дефиницията на остатъчна графика , ясно е, че последните дъга в начин на увеличаване в това остатъчна графика трябва да е a дъга 'Натиснете', защото всеки дъга 'Издърпване' b в начин на увеличаване ще има b.toNode == maxFlowProblem.terminalNode и b.fromNode! = maxFlowProblem.terminalNode от дефиницията на чрез . Освен това от дефиницията на чрез , е ясно, че терминален възел Той се модифицира само веднъж с метода augment Така че augment промяна  maxFlowProblem.terminalNode.flowIn точно веднъж и увеличава стойността на maxFlowProblem.terminalNode.flowIn защото последният дъга в augmentingPath трябва да е Той дъга което причинява модификацията в maxFlowProblem.terminalNode.flowIn по време на augment. От дефиницията на augment, тъй като се отнася за лъкове 'Push', maxFlowProblem.terminalNode.flowIn може само да се увеличава, а не да се намалява.
 Някои доказателства за Sedgewick и Wayne
 Книгата Алгоритми, четвърто издание от Робърт Седжуич и Кевин Уейн има някои прекрасни кратки тестове (страници 892-894), които ще бъдат полезни. Ще ги пресъздам тук, въпреки че ще използвам език, който отговаря на горните определения. Моите етикети за тестовете са същите като в книгата на Sedgewick.
  Предложение E: За всеки диграф H което представлява a възможно решение за пиков поток още проблем с пиковия поток maxFlowProblem, за всеки stCut get_stcut_flow(stCut,H,maxFlowProblem) = get_flow_value(H, maxFlowProblem).
  Тест: Оставете stCut=stCut(maxFlowProblem.sourceNode,maxFlowProblem.terminalNode,set([a for a in H.setOfArcs if a.toNode == maxFlowProblem.terminalNode])). Предложение Е се държи от stCut директно от дефиницията на стойност на потока s-t . Да предположим, че искаме да преместим a възел n от дял s (get_first_part(stCut.cut, G)) и на дял (get_second_part(stCut.cut, G)), за да направим това, трябва да променим stCut.cut, което може да се промени stcut_flow = get_stcut_flow(stCut,H,maxFlowProblem) и обезсилва предложение E . Нека обаче да видим как стойността на stcut_flow ще се промени, докато правим тази промяна. The възел n е в равновесие, което означава, че сумата на потока в възел n е равна на сумата от потока от това (това е необходимо, за да H представлява a възможно решение ).
 Обърнете внимание, че целият поток, който е част от stcut_flow влизайки в възел n го въвежда от дял s (потокът, влизащ възел n тъй като дялът t го прави директно или индиректно от него, той не би бил отчетен в стойността stcut_flow защото върви в грешна посока въз основа на дефиницията). Забележете, че целият поток, който е част от stcut_flow който влиза в възел n го въвежда от дял s (потокът, който влиза в възел n от дял t директно или индиректно не са отчетени в стойността stcut_flow защото се насочвате в грешна посока въз основа на дефиницията).
 Също така целият поток, който излиза n в крайна сметка ще се влее (пряко или косвено) в терминален възел (демонстрирано по-горе). Когато преместваме възел n в дял t, целият поток, влизащ n от дяла трябва да се добави към новата стойност stcut_flow; обаче целият поток, който излиза n трябва да се извади от новата стойност stcut_flow; частта от потока, която отива директно към дял t, се изважда, тъй като този поток вече е вътрешен в новия дял t и не се брои като stcut_flow.
 Частта от потока от позиция n в възли от дял s също трябва да се извади от stcut_flow: След n се премества към дял t, тези потоци ще бъдат насочени от позиция на дял t в дял s и следователно не трябва да се вземат предвид в stcut_flow, тъй като тези потоци елиминират входа в дял s и трябва да бъдат намалени със сумата от тези потоци и изтичането от дял s към дял -t (където всички потоци от st трябва да завършат) трябва да бъдат намалени със същата сума. Като възел n е в равновесие преди процеса, актуализацията ще е добавила същата стойност към новата стойност stcut_flow когато се изважда, оставяйки предложение E изчистване след надстройка. Валидността на предложение E след това продължаваме в индукцията върху размера на дяла t.
 Ето няколко примера за поточни мрежи за да ви помогне да визуализирате по-малко очевидните случаи, когато предложение Е запазва; В изображението червените области показват s дяла, сините области представляват t дяла, а лъкове зелено означава а изрежете s-t **. Във второто изображение потокът между ** възел Към и възел B се увеличава, докато потокът навлиза терминален възел t не се променя.
  
  
  Следствие: Няма стойност на срязващ поток s-t може да надвишава капацитета на s-t изрязване .
  Предложение Е. (теорема за максимален дебит и минимален разрез): Нека f да бъде поток s-t . Следните 3 условия са еквивалентни:
   Има разрез s-t чийто капацитет е равен на стойността на потока f.
 
  f е пиков поток .
 
  Няма начин на увеличаване по отношение на f.
 
 
 Условие 1 предполага условие 2 от следствието. Условие 2 предполага условие 3, тъй като съществуването на нарастващ път предполага съществуването на поток с по-високи стойности, противоречащ на максимума на „f“. Условие 3 предполага условие 1: Нека C_s множеството от всички възли до които може да се стигне от  s с увеличаване на маршрута в остатъчна графика . Нека C_t на останали лъкове , тогава t трябва да е в C_t (според нашето предположение). The лъкове този кръст от C_s a  C_t след това образувайте a s-t изрязване съдържащи само лъкове a където a.datum.capacity = a.datum.flow или a.datum.flow = 0.0. Ако не, възли свързани с a дъга с останалата остатъчна вместимост a C_s ще бъде в набора C_s оттогава ще има увеличение на пистата от s още възел . Потокът през s-t изрязване е равен на капацитета на s-t изрязване (тъй като лъкове от C_s a C_t имат поток, равен на капацитета), а също и на стойността на поток s-t (от предложение E ).
 Това твърдение на теоремата максимален дебит, минимално рязане предполага горното твърдение на Потоци в мрежи .
  Следствие (свойство на интегралност): Когато капацитетите са цели числа, има поток от максимално цяло число и алгоритъмът на Форд-Фулкерсън го намира.
 Тест: Всеки начин на увеличаване увеличава потока с положително цяло число, минимумът на неизползваните капацитети в дъгите натиснете и тече в арките сцепление , всички от които винаги са положителни цели числа.
 Това оправдава описанието на метода Форд-Фулкърсън от CLRS . Методът е да продължите да намирате нарастващи маршрути и прилагане augment до последния  maxFlowSolution намиране на по-добри решения, докато няма повече нарастващ маршрут , което означава, че последният решение за пиков поток то е оптимално .
 De Ford-Fulkerson a Edmonds-Karp
 Останалите въпроси относно разрешаването на проблеми с пиковия поток Те са:
   Как трябва да бъдат изградени пътища за увеличаване ?
 
  Ще завърши ли методът, ако използваме реални числа, а не цели числа?
 
  Колко време ще отнеме да завърши (ако го направи)?
 
 
 The Алгоритъм на Едмъндс-Карп посочете, че всеки път за увеличаване се изгражда от a търсене по амплитуда ( BFS ) от остатъчна графика ; Оказва се, че това решение от точка 1 също ще принуди алгоритъма да прекрати (точка 2) и позволява асимптотичното време и сложността на пространството да се определи.
 Първо, тук има изпълнение 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 Използвах a deque от модула за колекции на python .
 За да отговоря на въпрос 2, ще перифразирам още едно доказателство за Sedgewick и Wayne : Предложение Ж. Броят на пътища на нарастване необходими в алгоритъма Едмъндс-Карп с възли N Y. лъкове е най-много NA/2. Тест: Всеки път за увеличаване има лък за врата дъга - а дъга който се изтрива от остатъчна графика защото добре отговаря на дъга натиснете който е запълнен до капацитет или дъга сцепление през които потокът става 0. Всеки път а дъга се превръща в пречка дъга , дължината на която и да е път за увеличаване чрез него трябва да се увеличи с коефициент 2. Това е така, защото всеки възел в маршрут може да се появи само веднъж или изобщо да не се появи (от дефиницията на маршрут ) Тъй като маршрути се изследват от най-краткото маршрут през което означава, че поне един възел плюс трябва да бъдат посетени по следния път през тесното място възел което означава допълнителни 2 лъкове по пътя, преди да пристигнете в възел . Тъй като инкремент път е максималната дължина N, всяка дъга може да има максимум N/2 , пътища за увеличаване, и общия брой на инкрементни пътища е най-много NA/2. 
 The Алгоритъм на Едмъндс-Карп работи на O(NA^2). Да най-много начините NA/2 ще бъдат изследвани по време на алгоритъма и ще бъдат изследвани всеки траектория с BFS е N+A тогава най-значимият термин на продукта и следователно асимптотичната сложност O(NA^2).
 Нека mfp нека бъде maxFlowProblemState.
def edmonds_karp(mfp): sid, tid = mfp.sourceNodeUid, mfp.terminalNodeUid no_more_paths = False loop_count = 0 while(not no_more_paths): residual_digraph = get_residual_graph_of(mfp.G) try: asource = find_node_by_uid(mfp.sourceNodeUid, residual_digraph) aterm = find_node_by_uid(mfp.terminalNodeUid, residual_digraph) apath = bfs(asource, aterm, residual_digraph) paint_mfp_path(mfp, loop_count, apath) G = augment(apath, mfp.G) s = find_node_by_uid(sid, G) t = find_node_by_uid(tid, G) mfp = MaxFlowProblemState(G, s.uid, t.uid, mfp.maxFlowProblemStateUid) loop_count += 1 except StopIteration as e: no_more_paths = True return mfp По-старата версия е неефективна и има по-лоша сложност от O(NA^2) тъй като изгражда нов решение за пиков поток и нов остатъчна графика всеки път (вместо да модифицирате съществуващи диграфи с напредването на алгоритъма). Да се намери решение O(NA^2) вярно, алгоритъмът трябва да поддържа и двете digrafo какво представлява състояние на проблем с пиковия поток и свързаната с него ** остатъчна графика . Следователно алгоритъмът трябва да избягва ненужно повтаряне на ** дъги Y. възли и актуализирайте техните стойности и свързаните с тях стойности в остатъчна графика само когато е необходимо.
 Да напише алгоритъм Едмъндс Карп по-бързо пренаписах няколко кодови фрагмента от горното. Надявам се да премина през кода, който генерира нов digrafo Полезно беше да разберем какво става. В бързия алгоритъм използвам някои нови трикове на Python и структури от данни, които не искам да детайлизирам. Ще кажа, че a.fromNode и  a.toNode сега се третират като низове и uids към възли . За този код нека mfps бъде a maxFlowProblemState
import uuid def fast_get_mfps_flow(mfps): flow_from_s = {n for n in mfps.G.setOfNodes if n.uid == mfps.sourceNodeUid}.pop().datum.flowOut flow_to_t = {n for n in mfps.G.setOfNodes if n.uid == mfps.terminalNodeUid}.pop().datum.flowIn if( (flow_to_t - flow_from_s) > 0.00): raise Exception('Infeasible s-t flow') return flow_to_t def fast_e_k_preprocess(G): G = strip_flows(G) get = dict({}) get['nodes'] = dict({}) get['node_to_node_capacity'] = dict({}) get['node_to_node_flow'] = dict({}) get['arcs'] = dict({}) get['residual_arcs'] = dict({}) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if(a.toNode not in G.setOfNodes): err_msg = 'There is no Node {a.toNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) get['nodes'][a.fromNode.uid] = a.fromNode get['nodes'][a.toNode.uid] = a.toNode lark = Arc(a.fromNode.uid, a.toNode.uid, FlowArcDatumWithUid(a.datum.capacity, a.datum.flow, uuid.uuid4())) if(a.fromNode.uid not in get['arcs']): get['arcs'][a.fromNode.uid] = dict({a.toNode.uid : dict({lark.datum.uid : lark})}) else: if(a.toNode.uid not in get['arcs'][a.fromNode.uid]): get['arcs'][a.fromNode.uid][a.toNode.uid] = dict({lark.datum.uid : lark}) else: get['arcs'][a.fromNode.uid][a.toNode.uid][lark.datum.uid] = lark for a in G.setOfArcs: if a.toNode.uid not in get['arcs']: get['arcs'][a.toNode.uid] = dict({}) for n in get['nodes']: get['residual_arcs'][n] = dict() get['node_to_node_capacity'][n] = dict() get['node_to_node_flow'][n] = dict() for u in get['nodes']: n_to_u_cap_sum = sum(a.datum.capacity for a in G.setOfArcs if (a.fromNode.uid == n) and (a.toNode.uid == u) ) n_to_u_flow_sum = sum(a.datum.flow for a in G.setOfArcs if (a.fromNode.uid == n) and (a.toNode.uid == u) ) if(n_to_u_cap_sum > n_to_u_flow_sum): flow = round(n_to_u_cap_sum - n_to_u_flow_sum, TOL) get['residual_arcs'][n][u] = Arc(n,u,ResidualDatum(flow, 'push')) if(n_to_u_flow_sum > 0.0): flow = round(n_to_u_flow_sum, TOL) get['residual_arcs'][u][n] = Arc(u,n,ResidualDatum(flow, 'pull')) get['node_to_node_capacity'][n][u] = n_to_u_cap_sum get['node_to_node_flow'][n][u] = n_to_u_flow_sum return get def fast_bfs(sid, tid, get): parent_of = dict([]) visited = frozenset([]) deq = coll.deque([sid]) while len(deq) > 0: n = deq.popleft() if n == tid: break for u in get['residual_arcs'][n]: if (u not in visited): visited = visited.union(frozenset({u})) parent_of[u] = get['residual_arcs'][n][u] deq.extend([u]) path = list([]) curr = tid while(curr != sid): if (curr not in parent_of): err_msg = 'No augmenting path from {} to {}.'.format(sid, curr) raise StopIteration(err_msg) path.extend([parent_of[curr]]) curr = parent_of[curr].fromNode path.reverse() return path def fast_edmonds_karp(mfps): sid, tid = mfps.sourceNodeUid, mfps.terminalNodeUid get = fast_e_k_preprocess(mfps.G) no_more_paths, loop_count = False, 0 while(not no_more_paths): try: apath = fast_bfs(sid, tid, get) get = fast_augment(apath, get) loop_count += 1 except StopIteration as e: no_more_paths = True nodes = frozenset(get['nodes'].values()) arcs = frozenset({}) for from_node in get['arcs']: for to_node in get['arcs'][from_node]: for arc in get['arcs'][from_node][to_node]: arcs |= frozenset({get['arcs'][from_node][to_node][arc]}) G = DiGraph(nodes, arcs) mfps = MaxFlowProblemState(G, sourceNodeUid=sid, terminalNodeUid=tid, maxFlowProblemStateUid=mfps.maxFlowProblemStateUid) return mfps Ето визуализация как този алгоритъм решава примера поточна мрежа отгоре. Визуализацията показва стъпките, които са отразени в digrafo G представляваща поточната мрежа последен и как те са отразени в остатъчна графика от тази поточна мрежа. Начините за увеличаване в остатъчна графика са показани като червени маршрути, а digrafo което представлява проблема от множеството възли Y. лъкове засегнати от матрица маршрута за увеличаване е подчертано в зелено. Във всеки случай ще подчертая частите на графиката, които ще бъдат променени (червени или зелени) и след това ще покажа диаграмата след промените (само в черно).
  
  
 Ето още една визуализация на това как този алгоритъм решава различен пример поточна мрежа . Забележете, че това използва реални числа и съдържа няколко лъкове със същите стойности fromNode и  toNode.
  Също така имайте предвид, че тъй като Arcs с ResidualDatum 'pull' може да бъде част от Rising Path, засегнатите възли в Flow Network Diagram_cannot не са на G! path. 
 Двустранна графика
 Да предположим, че имаме a digrafo G, G то е двустранен ако е възможно да се раздели възли в G.setOfNodes в два комплекта (part_1 и part_2), така че за всеки дъга a в G.setOfArcs не Може да е истина че a.fromNode в part_1 и a.toNode в part_1. Нито едното Може да е истина че a.fromNode в part_2 и a.toNode в part_2.
 С други думи, G то е двуделение ако може да се раздели на два набора от възли по такъв начин, че всеки дъга трябва да се свържете a възел в набор до възел в другия набор. 
 Двустранно тестване
 Да предположим, че имаме a digrafo G, искаме да тестваме дали е така двуделение . Можем да направим това в O(|G.setOfNodes|+|G.setOfArcs|) чрез алчен цвят на двуцветната диаграма.
 Първо, трябва да генерираме ново digrafo H. Тази графика ще има същия набор от възли като G, но ще има и повече лъкове отколкото  G. Всеки дъга a в  G ще създаде 2 лъкове в H; първият дъга ще бъде идентичен с a, а вторият дъга инвестира директора на a (b = Arc(a.toNode,a.fromNode,a.datum)).
Bipartition = coll.namedtuple('Bipartition',['firstPart', 'secondPart', 'G']) def bipartition(G): nodes = frozenset(G.setOfNodes arcs = frozenset(G.setOfArcs) arcs = arcs.union( frozenset( {Arc(a.toNode,a.fromNode,a.datum) for a in G.setOfArcs} ) ) H = DiGraph(nodes, arcs) H_as_dict = digraph_to_dict(H) color = dict([]) some_node = next(iter(H.setOfNodes)) deq = coll.deque([some_node]) color[some_node] = -1 while len(deq) > 0: curr = deq.popleft() for a in H_as_dict.get(curr): if (a.toNode not in color): color[a.toNode] = -1*color[curr] deq.extend([a.toNode]) elif(color[curr] == color[a.toNode]): print(curr,a.toNode) raise Exception('Not Bipartite.') firstPart = frozenset( {n for n in color if color[n] == -1 } ) secondPart = frozenset( {n for n in color if color[n] == 1 } ) if( firstPart.union(secondPart) != G.setOfNodes ): raise Exception('Not Bipartite.') return Bipartition(firstPart, secondPart, G) Мачове и максимални мачове
 Да предположим, че имаме a digrafo G и  matching е подмножество на лъкове от G.setOfArcs. matching е съчетаване да за двама digrafo a и b в matching: len(frozenset( {a.fromNode} ).union( {a.toNode} ).union( {b.fromNode} ).union( {b.toNode} )) == 4. С други думи, не дъга в съвпадение споделете a възел .
 The съвпадение matching, е максимално съвпадение, ако няма друго споразумение alt_matching в G толкова много, че len(matching) . С други думи, matching е максимално съвпадение Ако е най-дългият набор от лъкове в G.setOfArcs което все още удовлетворява дефиницията на комбинация (добавяне на който и да е дъга което още не е в мача ще прекъсне комбинация определение).
 A максимална комбинация matching е перфектна комбинация да за всеки възел n в G.setOfArcs има дъга a в matching където a.fromNode == n or a.toNode == n.
 Максимална двуразделна комбинация
 A максимална двуразделна комбинация е максимална комбинация в digrafo G Какво е двуразделен .
 Тъй като G то е двуразделен , проблемът с намирането на a двустранна максимална комбинация може да се трансформира в a проблем с пиковия поток разрешим с алгоритъм от Едмъндс-Карп и след това максимално двустранно свързване може да бъде възстановен от разтвор до проблем с пиковия поток .
истинската цена на калкулатора за служител
 Нека bipartition бъди a двуделение от G.
 За това трябва да генерирам нов digrafo (H) с някои нови възли (H.setOfNodes) и някои лъкове нов (H.setOfArcs). H.setOfNodes съдържа всички възли в G.setOfNodes и две възли повече, s (а изходен възел ) и t (а терминален възел ).
 H.setOfArcs ще съдържа a дъга за всеки G.setOfArcs. Ако дъга a е G.setOfArcs и a.fromNode е в bipartition.firstPart и a.toNode е в bipartition.secondPart и след това включва a в H (добавяне на FlowArcDatum(1,0)).
 Ако a.fromNode е bipartition.secondPart и a.toNode е bipartition.firstPart, след това включете Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) в H.setOfArcs.
 Определяне на диаграма двуразделен гарантира, че не дъга свържете всеки възел където и двете възли те са на един дял. H.setOfArcs също съдържа a дъга от възел s за всеки възел в  bipartition.firstPart. И накрая, H.setOfArcs съдържа a дъга всеки възел в  bipartition.secondPart а възел t. a.datum.capacity = 1 за всички a в H.setOfArcs.
 Първи дял на възли в G.setOfNodes двата набора (part1 и part2) разделени толкова много, че не дъга в G.setOfArcs преминава от един набор към същия набор (този дял е възможен, защото G е двуразделен ). След това добавете всички лъкове в G.setOfArcs които са насочени от part1 към part2 към H.setOfArcs. След това създайте единичен възел източник s и един възел терминал  t и създайте повече лъкове 
 След това изградете maxFlowProblemState.
def solve_mbm( bipartition ): s = Node(uuid.uuid4(), FlowNodeDatum(0,0)) t = Node(uuid.uuid4(), FlowNodeDatum(0,0)) translate = {} arcs = frozenset([]) for a in bipartition.G.setOfArcs: if ( (a.fromNode in bipartition.firstPart) and (a.toNode in bipartition.secondPart) ): fark = Arc(a.fromNode,a.toNode,FlowArcDatum(1,0)) arcs = arcs.union({fark}) translate[frozenset({a.fromNode.uid,a.toNode.uid})] = a elif ( (a.toNode in bipartition.firstPart) and (a.fromNode in bipartition.secondPart) ): bark = Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) arcs = arcs.union({bark}) translate[frozenset({a.fromNode.uid,a.toNode.uid})] = a arcs1 = frozenset( {Arc(s,n,FlowArcDatum(1,0)) for n in bipartition.firstPart } ) arcs2 = frozenset( {Arc(n,t,FlowArcDatum(1,0)) for n in bipartition.secondPart } ) arcs = arcs.union(arcs1.union(arcs2)) nodes = frozenset( {Node(n.uid,FlowNodeDatum(0,0)) for n in bipartition.G.setOfNodes} ).union({s}).union({t}) G = DiGraph(nodes, arcs) mfp = MaxFlowProblemState(G, s.uid, t.uid, 'bipartite') result = edmonds_karp(mfp) lookup_set = {a for a in result.G.setOfArcs if (a.datum.flow > 0) and (a.fromNode.uid != s.uid) and (a.toNode.uid != t.uid)} matching = {translate[frozenset({a.fromNode.uid,a.toNode.uid})] for a in lookup_set} return matching Минимално покритие на възела
 Покритие на възел в a диграф G Това е набор от възли (cover) от G.setOfNodes толкова много, че за всеки дъга a от G.setOfArcs това трябва да е вярно: (a.fromNode en cubierta) o (a.toNode en cubierta).
 Минималното покритие на възела е най-малкият набор от възли в графиката, която все още е капак на възела . Теоремата на Кьониг показва това на графика двуразделен , размера на максимално съвпадение в тази графика е равна на размера на минимално покритие на възела , и предлага как покритието на възела може да бъде възстановено от a максимално съвпадение :
 Да предположим, че имаме двуделение bipartition и максимално съвпадение matching. Определете нов digrafo H, H.setOfNodes=G.setOfNodes, лъкове в H.setOfArcs те са обединението на две множества.
 Първият набор от лъкове a в matching, с промяната, че ако a.fromNode in bipartition.firstPart и a.toNode en bipartition.secondPart тогава a.fromNode и a.toNode се обменят в създаден акро те дават такива лъкове атрибут a.datum.inMatching = True за да посочи, че са получени от лъкове в съвпадение .
 Вторият набор е лъкове a НЕ е в  matching, с промяната, че ако a.fromNode en bipartition.secondPart и  a.toNode en bipartition.firstPart тогава a.fromNode и  a.toNode се обменят в дъга създаден (дава такива дъга атрибут a.datum.inMatching = False).
 След това стартирайте a първо търсене в дълбочина ( DFS ) от всеки възел n в  bipartition.firstPart което не е n == a.fromNode нито  n == a.toNodes За всеки дъга a в  matching. По време на DFS някои възли са посетени, а други не (съхранявайте тази информация в поле n.datum.visited). The минимално покритие на възела е обединението на възли {a.fromNode para a en H.setOfArcs si ((a.datum.inMatching) y (a.fromNode.datum.visited))}  и възли {a.fromNode para a en H.setOfArcs si (a.datum.inMatching) y (no a.toNode.datum.visited)}. 
 Това може да се покаже за шофиране от максимално съвпадение до a минимално покритие на възела от а доказателство чрез противоречие , вземете a дъга a което уж не беше обхванато и разгледайте и четирите случая дали a.fromNode и a.toNode принадлежат (или като  toNode или fromNode) на който и да е дъга в съвпадение matching. Всеки случай води до противоречие поради реда, в който DFS посещава възли и факта, че matching е максимално съвпадение .
 Да предположим, че имаме функция за изпълнение на тези стъпки и връщане на набора от възли който включва минимално покритие на възела когато му се даде digrafo G, и максимално съвпадение matching:
ArcMatchingDatum = coll.namedtuple('ArcMatchingDatum', ['inMatching' ]) NodeMatchingDatum = coll.namedtuple('NodeMatchingDatum', ['visited']) def dfs_helper(snodes, G): sniter, do_stop = iter(snodes), False visited, visited_uids = set(), set() while(not do_stop): try: stack = [ next(sniter) ] while len(stack) > 0: curr = stack.pop() if curr.uid not in visited_uids: visited = visited.union( frozenset( {Node(curr.uid, NodeMatchingDatum(False))} ) ) visited_uids = visited.union(frozenset({curr.uid})) succ = frozenset({a.toNode for a in G.setOfArcs if a.fromNode == curr}) stack.extend( succ.difference( frozenset(visited) ) ) except StopIteration as e: stack, do_stop = [], True return visited def get_min_node_cover(matching, bipartition): nodes = frozenset( { Node(n.uid, NodeMatchingDatum(False)) for n in bipartition.G.setOfNodes} ) G = DiGraph(nodes, None) charcs = frozenset( {a for a in matching if ( (a.fromNode in bipartition.firstPart) and (a.toNode in bipartition.secondPart) )} ) arcs0 = frozenset( { Arc(find_node_by_uid(a.toNode.uid,G), find_node_by_uid(a.fromNode.uid,G), ArcMatchingDatum(True) ) for a in charcs } ) arcs1 = frozenset( { Arc(find_node_by_uid(a.fromNode.uid,G), find_node_by_uid(a.toNode.uid,G), ArcMatchingDatum(True) ) for a in matching.difference(charcs) } ) not_matching = bipartition.G.setOfArcs.difference( matching ) charcs = frozenset( {a for a in not_matching if ( (a.fromNode in bipartition.secondPart) and (a.toNode in bipartition.firstPart) )} ) arcs2 = frozenset( { Arc(find_node_by_uid(a.toNode.uid,G), find_node_by_uid(a.fromNode.uid,G), ArcMatchingDatum(False) ) for a in charcs } ) arcs3 = frozenset( { Arc(find_node_by_uid(a.fromNode.uid,G), find_node_by_uid(a.toNode.uid,G), ArcMatchingDatum(False) ) for a in not_matching.difference(charcs) } ) arcs = arcs0.union(arcs1.union(arcs2.union(arcs3))) G = DiGraph(nodes, arcs) bip = Bipartition({find_node_by_uid(n.uid,G) for n in bipartition.firstPart},{find_node_by_uid(n.uid,G) for n in bipartition.secondPart},G) match_from_nodes = frozenset({find_node_by_uid(a.fromNode.uid,G) for a in matching}) match_to_nodes = frozenset({find_node_by_uid(a.toNode.uid,G) for a in matching}) snodes = bip.firstPart.difference(match_from_nodes).difference(match_to_nodes) visited_nodes = dfs_helper(snodes, bip.G) not_visited_nodes = bip.G.setOfNodes.difference(visited_nodes) H = DiGraph(visited_nodes.union(not_visited_nodes), arcs) cover1 = frozenset( {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (a.fromNode.datum.visited) ) } ) cover2 = frozenset( {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (not a.toNode.datum.visited) ) } ) min_cover_nodes = cover1.union(cover2) true_min_cover_nodes = frozenset({find_node_by_uid(n.uid, bipartition.G) for n in min_cover_nodes}) return min_cover_nodes Проблемът с линейното присвояване
 Задачата за линейното присвояване се състои в намиране на максимално съвпадение на тежести в претеглена двуделна графика.
 Проблеми като този, който се появява в началото на тази публикация, могат да бъдат изразени като проблем линейно задание . Като се има предвид набор от работници, набор от задачи и функция, която показва рентабилността на дадено назначение на работник към задача, ние искаме да увеличим максимално сумата от всички задачи, които правим; това е линейна задача за присвояване .
 Да предположим, че броят на задачите и работниците са равни, въпреки че ще покажа, че това предположение е лесно да се премахне. В изпълнение, аз представлявам лъкови тежести с атрибут a.datum.weight за дъга a.
WeightArcDatum = namedtuple('WeightArcDatum', [weight]) Алгоритъм на Kuhn-Munkres
 Алгоритъмът на Kuhn-Munkres решава линейна задача за присвояване . Една добра реализация може да отнеме време O(N^{4}), (където N е броят на възли в digrafo представляващи проблема). Едно изпълнение, което е по-лесно за обяснение, отнема O (N ^ {5}) (за версия, която се регенерира диграфос ) и O (N ^ {4}) за (за версия, която поддържа диграфос ). Това е подобно на двете различни реализации на алгоритъма Едмъндс-Карп .
 За това описание работя само с пълна двустранна графика (тези, където половината от възли са в част от двуделение а другата половина във втората част). При работника мотивацията на задачите означава, че има толкова работници, колкото са и задачите.
 Това изглежда като значително условие (какво, ако тези набори не са равни?), Но този проблем е лесен за отстраняване; Говоря за това как да го направя в последния раздел.
 Версията на алгоритъма, описана тук, използва полезната концепция за лъкове с нулево тегло . За съжаление тази концепция има смисъл само когато решаваме a минимизиране (Ако вместо да увеличим максимално ползите от задачите на нашите работници, ние вместо това намаляваме разходите за такива задачи).
кога да използвате apache spark
 За щастие е лесно да конвертирате a максимален проблем с линейно задание в минимален проблем с линейно задание установяване на всяка от тежестите на дъга a в  M-a.datum.weight където M=max({a.datum.weight for a in G.setOfArcs}). Решението на проблема за максимизиране оригиналът ще бъде идентичен с решението минимизиране на проблема след смяна на тежестите на дъгата . Така че за останалото, да предположим, че правим тази промяна.
 The Алгоритъм на Kuhn-Munkres решаване минимално тегло в претеглена двуразделна диаграма чрез последователност от максимални съвпадения в графика непретеглено двустранен. Ако намерим такъв перфектно съвпадение в представяне на диграф на задачата за линейно присвояване и ако теглото на всеки дъга в съвпадение е нула, така че намерихме минимално тегло тъй като това съвпадение предполага, че всички възли в диграфос бил е сдвоени за дъга с възможно най-ниските разходи (никой разход не може да бъде по-малък от 0, въз основа на предишни дефиниции).
 Няма друг лъкове може да се добави към съвпадение (Тъй като всички възли вече са сдвоени) и не лъкове трябва да се премахне от съвпадение защото всяка възможна подмяна дъга ще има поне толкова голяма стойност на теглото.
 Ако намерим a максимално съвпадение от субграфо от G съдържащи само лъкове с нулево тегло , и не е перфектно съвпадение , нямаме цялостно решение (тъй като комбинацията Не е перфектно ). Ние обаче можем да произведем нов digrafo H промяна на тежестите на лъкове в  G.setOfArcs така че да се появят нови 0-тежести лъкове и оптималното решение на 'H' е същото като оптималното решение на 'G'. Тъй като ние гарантираме, че поне един лък с нулево тегло се случва във всяка итерация, гарантираме, че ще достигнем a перфектно съвпадение в не повече от | G.setOfNodes | 2 = N 2 в такива повторения.
 Да предположим, че в двуделение bipartition, bipartition.firstPart съдържа възли представляващи работници и bipartition.secondPart Той представлява възли което същевременно представлява доказателство.
 Алгоритъмът започва с генериране на нов digrafo H. H.setOfNodes = G.setOfNodes. Някои лъкове в H Те са възли n генерирано в bipartition.firstPart. Всеки възел n генерира a дъга b в H.setOfArcs За всеки дъга a в bipartition.G.setOfArcs където a.fromNode = n или a.toNode = n, b=Arc(a.fromNode, a.toNode, a.datum.weight - z) където z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )).
 Плюс това лъкове в H се генерират от възли n в bipartition.secondPart. Всеки един от тях възли n генерира a дъга b в H.setOfArcs За всеки дъга a в bipartition.G.setOfArcs където a.fromNode = n или a.toNode = n, b=Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) където z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )).
  KMA: След това оформете нов digrafo K съставен само от лъкове с нулево тегло от H, и възли   инцидент в тези лъкове . Форма a bipartition в възли в K, след това използвайте solve_mbm( bipartition ) За да се сдобиете с такъв максимална комбинация (matching) в K. Ако matching е перфектна комбинация в H ( лъкове в matching Те са инцидент във всички възли в H.setOfNodes), след това matching е оптимално решение за линейно задание .
 В противен случай, ако matching Не е перфектно , генерира минимално покритие на възела от  K използвайки node_cover = get_min_node_cover(matching, bipartition(K)). След това дефинирайте z=min({a.datum.weight for a in H.setOfArcs if a not in node_cover}). Определете nodes = H.setOfNodes, arcs1 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh-z)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) and (a.toNode not in node_cover)}, arcs2 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) != (a.toNode not in node_cover)}, arcs3 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh+z)) for a in H.setOfArcs if ( (a.fromNode in node_cover) and (a.toNode in node_cover)}. != символ в горния израз действа като оператор XOR . Тогава arcs = arcs1.union(arcs2.union(arcs3)). Тогава H=DiGraph(nodes,arcs). Върнете се към марката KMA . Алгоритъмът продължава, докато a перфектна комбинация . Е комбинация е и решението на линейна задача за присвояване .
def kuhn_munkres( bipartition ): nodes = bipartition.G.setOfNodes arcs = frozenset({}) for n in bipartition.firstPart: z = min( {x.datum.weight for x in bipartition.G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )} ) arcs = arcs.union( frozenset({Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) }) ) for n in bipartition.secondPart: z = min( {x.datum.weight for x in bipartition.G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )} ) arcs = arcs.union( frozenset({Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) }) ) H = DiGraph(nodes, arcs) assignment, value = dict({}), 0 not_done = True while( not_done ): zwarcs = frozenset( {a for a in H.setOfArcs if a.datum.weight == 0} ) znodes = frozenset( {n.fromNode for n in zwarcs} ).union( frozenset( {n.toNode for n in zwarcs} ) ) K = DiGraph(znodes, zwarcs) k_bipartition = bipartition(K) matching = solve_mbm( k_bipartition ) mnodes = frozenset({a.fromNode for a in matching}).union(frozenset({a.toNode for a in matching})) if( len(mnodes) == len(H.setOfNodes) ): for a in matching: assignment[ a.fromNode.uid ] = a.toNode.uid value = sum({a.datum.weight for a in matching}) not_done = False else: node_cover = get_min_node_cover(matching, bipartition(K)) z = min( frozenset( {a.datum.weight for a in H.setOfArcs if a not in node_cover} ) ) nodes = H.setOfNodes arcs1 = frozenset( {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh-z)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) and (a.toNode not in node_cover)} ) arcs2 = frozenset( {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) != (a.toNode not in node_cover)} ) arcs3 = frozenset( {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh+z)) for a in H.setOfArcs if ( (a.fromNode in node_cover) and (a.toNode in node_cover)} ) arcs = arcs1.union(arcs2.union(arcs3)) H = DiGraph(nodes,arcs) return value, assignment Това изпълнение е O(N^{5}) защото генерира ново максимална комбинация matching във всяка итерация; подобно на предишните две реализации на Едмъндс-Карп Този алгоритъм може да бъде модифициран, за да следи мача и интелигентно да го адаптира към всяка итерация. Когато това се направи, сложността става O(N^{4}). По-усъвършенствана и по-нова версия на този алгоритъм (изискваща по-усъвършенствани структури от данни) може да се изпълнява на O (N ^ {3}) Подробности за по-простото изпълнение по-горе и по-напредналото изпълнение можете да намерите на този пост което мотивира този блог.
 Нито една от операциите върху тежестите на дъга променя окончателното задание, върнато от алгоритъма. Следователно: Тъй като нашите графики за въвеждане са винаги пълна двуразделна графика , решение трябва да присвои всеки възел в един дял към друг възел във втория дял, чрез дъга между тези две възли . Имайте предвид, че операциите, извършени върху тежестите на дъга никога не променяйте реда (сортиран по тегло) на лъкове инциденти без възел особено .
 Следователно, когато алгоритъмът завършва в a перфектен и пълен съвпадащ би-дял , всеки възел е назначен a нулево тегло на дъгата , тъй като относителният ред на лъкове от какво възел не се е променил по време на алгоритъма и от а лък с нулево тегло това е лъкът възможно най-евтино и перфектно пълно двустранно допълнение гарантира, че има a дъга за всеки възел . Това означава, че генерираното решение всъщност е същото като решението на проблема оригинално линейно картографиране без промяна на тежестите на дъга .
 Небалансирани разпределения
 Изглежда, че алгоритъмът е доста ограничен, тъй като както е описано, той работи само на пълна двустранна графика (тези, където половината от възли са в част от двуделение а другата половина във втората част). При работника мотивацията на задачите означава, че има толкова работници, колкото са и задачите (изглежда доста ограничаващо).
 Има обаче лесна трансформация, която премахва това ограничение. Да предположим, че работниците са по-малко от задачите, добавяме няколко фиктивни работници (достатъчно, за да направим получената графика a пълна двустранна графика ). Всеки измислен работник има дъга насочени от работника към всяка от задачите. Всеки един от тях дъга има тегло 0 (поставянето му в мач не носи никаква допълнителна полза). След тази промяна графиката е a пълна двустранна графика които можем да решим. Не се стартират задачи, възложени на фиктивен работник.
 Да предположим, че има повече задачи от работниците. Добавихме няколко фиктивни задачи (достатъчно, за да направим получената графика a пълна двуразделна графика ). Всяка измислена задача има a дъга насочени от всеки работник към фиктивната задача. Всеки един от тях дъга има тежест 0 (поставянето му в мач не носи никаква допълнителна полза). След тази промяна графиката е a пълна двуразделна графика които можем да решим. Всеки работник, възложен на измислената задача, не е нает през периода.
 Пример за линейно присвояване
 Накрая ще направим пример с кода, който използвах. Ще модифицирам примера на проблема от тук . Имаме 3 задачи: имаме нужда за почистване на банята , помети пода , Y измийте прозорците .
 Наличните работници са Алис , Боб , Чарли Y. Даян . Всеки от работниците ни дава заплатата, която се изисква за задача. Ето заплатите на работник:
     Почисти банята  Помети пода  Измийте Windows  
 
  Алис  $ 2  $ 3  $ 3  
  Боб  $ 3  $ 2  $ 3  
  Чарли  $ 3  $ 3  $ 2  
  Даян  9 долара  9 долара  $ 1  
 
 
 Ако искаме да платим най-малко пари, но все пак да изпълним всички задачи, кой каква задача трябва да изпълни? Започнете, като въведете фиктивна задача за диграфа, който представлява двустранен проблем.
     Почисти банята  Помети пода  Измийте Windows  Не правете нищо  
 
  Алис  $ 2  $ 3  $ 3  $ 0  
  Боб  $ 3  $ 2  $ 3  $ 0  
  Чарли  $ 3  $ 3  $ 2  $ 0  
  Даян  9 долара  9 долара  $ 1  $ 0  
 
 
 Ако приемем, че проблемът е кодиран в digrafo , тогава kuhn_munkres( bipartition(G) ) ще реши проблема и ще върне заданието. Лесно е да се провери, че оптималното разпределение (най-ниската цена) ще струва 5 долара.
 Ето визуализация на решението, което генерира горният код:
  
  
 Това е всичко . Вече знаете всичко, което трябва да знаете за проблема с линейното присвояване.
 Можете да намерите целия код за тази статия на адрес GitHub .

	Почисти банята	Помети пода	Измийте Windows
Алис	$ 2	$ 3	$ 3
Боб	$ 3	$ 2	$ 3
Чарли	$ 3	$ 3	$ 2
Даян	9 долара	9 долара	$ 1

	Почисти банята	Помети пода	Измийте Windows	Не правете нищо
Алис	$ 2	$ 3	$ 3	$ 0
Боб	$ 3	$ 2	$ 3	$ 0
Чарли	$ 3	$ 3	$ 2	$ 0
Даян	9 долара	9 долара	$ 1	$ 0


    
    
    
        
            
                
                    
                        
                            Вицепрезидент на маркетинга на растежа
                            Други
                            
                        
                        
                            
                        
                    
                
                
                    
                        
                            
                        
                        
                            Страхотни примери за успех на конкурентната стратегия
                            Финансови Процеси
                            
                        
                    
                
            
        
    
    
    
    
        

	
		
			
				
					Популярни Публикации
					
						
						
							UX портфолио съвети и най-добри практики
						
					

						
						
							Индустрия за онлайн запознанства: Бизнесът на любовта
						
					

						
						
							Визуален срок на годност - Защо илюстрациите в уеб дизайна остаряват
						
					

						
						
							Как ефективно да се определи количествено стойността на продукта - Ръководство за продуктови мениджъри
						
					

						
						
							eCommerce UX за мобилно изживяване
						
					
				
			
			
				
					 
					
						
						
							Партито не е приключило: Погледнете задълбочено защо еднорозите ще се завърнат през 2017 г.
						
					

						
						
							Как да внедрим T9 Search в iOS
						
					

						
						
							Как бързо да превърнете скучните икони в оригинални шедьоври
						
					

						
						
							Тревожност при разделяне: Урок за изолиране на вашата система с пространства от имена на Linux
						
					

						
						
							Проектиране на по-добър уеб портал: Основите първо
						
					
					
				
			
			
				
					Популярни Публикации
					 кое от тях се използва като мярка за общата сума на наличния паричен поток от даден проект?
кога да наемете финансов директор
приложение за изграждане на визуално студио за iOS
там съм сам
часова ставка на свободна практика спрямо заплата
възвръщаемостта на инвестицията мярка за изпълнение:
за какво е ruby on rails
 
							
					
				
			
			
				
					Категории
					Процес И Инструменти
Back-End
Инженерно Управление
Други
				
			
		
	




	
		
			© 2022 | Всички Права Запазени
			portaldacalheta.pt