Максимальный поток и линейная задача о назначениях

Вот проблема: ваш бизнес назначает подрядчиков для выполнения контрактов. Вы просматриваете свои списки и решаете, какие подрядчики доступны для работы в течение одного месяца, и вы просматриваете свои доступные контракты, чтобы увидеть, какие из них предназначены для выполнения задач продолжительностью в один месяц. Учитывая, что вы знаете, насколько эффективно каждый подрядчик может выполнить каждый контракт, как вы назначаете подрядчиков, чтобы максимизировать общую эффективность в этом месяце?

Это пример задачи о назначениях, которую можно решить с помощью классического венгерского алгоритма.

Венгерский алгоритм (также известный как алгоритм Куна-Мункреса) представляет собой алгоритм с полиномиальным временем, который максимизирует совпадение весов во взвешенном двудольном графе. Здесь подрядчики и контракты могут быть смоделированы как двудольный граф с их эффективностью как веса ребер между подрядчиком и узлами контракта.

В этой статье вы узнаете о реализации венгерского алгоритма, который использует алгоритм Эдмондса-Карпа для решения линейной задачи о назначениях. Вы также узнаете, что алгоритм Эдмондса-Карпа является небольшой модификацией метода Форда-Фалкерсона и насколько важна эта модификация.

Проблема максимального потока

Саму задачу о максимальном потоке можно неофициально описать как задачу о перемещении некоторого количества жидкости или газа по сети труб от одного источника к одному терминалу. Это делается в предположении, что давление в сети достаточно для того, чтобы жидкость или газ не могли задерживаться на каком-либо участке трубы или патрубка (тех местах, где сходятся трубы разной длины).

Внеся определенные изменения в граф, задачу о назначениях можно превратить в задачу о максимальном потоке.

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

Идеи, необходимые для решения этих задач, возникают во многих математических и инженерных дисциплинах, часто схожие понятия известны под разными именами и выражаются по-разному (например, матрицы смежности и списки смежности). Поскольку эти идеи довольно эзотеричны, делается выбор в отношении того, как в целом эти концепции будут определяться для любого заданного окружения.

В этой статье не предполагается каких-либо предварительных знаний, кроме небольшой вводной теории множеств.

Реализации в этом посте представляют задачи в виде ориентированных графов (орграф).

диграфы

Орграф имеет два атрибута: setOfNodes и setOfArcs . Оба этих атрибута являются наборами (неупорядоченными коллекциями). В блоках кода в этом посте я на самом деле использую замороженный набор Python, но эта деталь не особенно важна.

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

(Примечание: этот и весь остальной код в этой статье написаны на Python 3.6.)

Узлы

Узел n состоит из двух атрибутов:

• n.uid : уникальный идентификатор.

  Это означает, что для любых двух узлов x и y

 x.uid != y.uid

• n.datum : представляет любой объект данных.

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

Дуги

Дуга a состоит из трех атрибутов:

• a.fromNode : это узел , как определено выше.

• a.toNode : это узел , как определено выше.

• a.datum : представляет любой объект данных.

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

Набор дуг в орграфе представляет собой бинарное отношение узлов в орграфе . Существование дуги a подразумевает, что существует связь между a.fromNode и a.toNode .

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

Это связано с тем, что в неориентированном графе выражаемая связь не обязательно симметрична.

диграфы

Для определения орграфа можно использовать узлы и дуги , но для удобства в приведенных ниже алгоритмах орграф будет представлен с использованием словаря.

Вот метод, который может преобразовать представление графа выше в представление словаря, подобное этому:

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

А вот еще один, который преобразует его в словарь словарей, еще одна операция, которая будет полезна:

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

Когда в статье говорится об орграфе , представленном словарем, для ссылки на него упоминается G_as_dict .

Иногда полезно получить узел из орграфа G по нему вверх через его uid (уникальный идентификатор):

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

При определении графов люди иногда используют термины « узел » и «вершина» для обозначения одного и того же понятия; то же самое верно для терминов дуга и ребро.

Два популярных представления графов в Python: одно использует словари, а другое использует объекты для представления графов. Представление в этом посте находится где-то посередине между этими двумя часто используемыми представлениями.

Это мое представление орграфа . Таких много, но этот мой.

Прогулки и дорожки

Пусть S_Arcs — конечная последовательность (упорядоченный набор) дуг в орграфе G такая, что если a — любая дуга в S_Arcs кроме последней, и b следует a в последовательности, то должен быть узел n = a.fromNode в G.setOfNodes такой, что a.toNode = b.fromNode .

Начиная с первой дуги в S_Arcs и продолжая до последней дуги в S_Arcs , соберите (в порядке обнаружения) все узлы n , как определено выше, между каждыми двумя последовательными дугами в S_Arcs . Пометьте упорядоченный набор узлов , собранных во время этой операции, S_{Nodes} .

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

• Если какой-либо узел появляется более одного раза в последовательности S_Nodes , вызовите S_Arcs как обход по орграфу G

• В противном случае вызовите S_Arcs как путь из list(S_Nodes)[0] в list(S_Nodes)[-1] на орграфе G .

Исходный узел

Вызвать node 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

Порезы и порезы

cut связного орграфа G — это подмножество дуг из G.setOfArcs , которое разбивает набор узлов G.setOfNodes в G G связен, если каждый узел n в G.setOfNodes и имеет хотя бы одну дугу a в G.setOfArcs такую, что либо n = a.fromNode , либо n = a.toNode , но a.fromNode != a.toNode .

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

Приведенное выше определение относится к подмножеству дуг , но оно также может определять разбиение узлов G.setOfNodes .

Для функций predecessors_of и successors_of n — это узел в наборе G.setOfNodes орграфа G , а cut — разрез G :

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

Пусть cut будет разрезом орграфа G .

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

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

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

Потоковые сети

Вы можете использовать орграф G для представления потоковой сети.

Назначьте каждому узлу n , где n находится в G.setOfNodes , n.datum , который является FlowNodeDatum :

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

Назначьте каждой дуге a , где a находится в G.setOfArcs и a.datum , который является FlowArcDatum .

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

flowNodeDatum.flowIn и flowNodeDatum.flowOut — положительные действительные числа.

flowArcDatum.capacity и flowArcDatum.flow также являются положительными действительными числами.

Для каждого узла node n в G.setOfNodes :

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

Диграф G теперь представляет сеть потоков .

Поток G относится к a.flow для всех дуг a в G

Возможные потоки

Пусть орграф G представляет сеть потоков .

Сеть потоков, представленная G , имеет допустимые потоки , если:

1. Для каждого узла n в G.setOfNodes кроме исходных узлов и конечных узлов : n.datum.flowIn = n.datum.flowOut .

2. Для каждой дуги a в G.setOfNodes : a.datum.capacity <= a.datum.flow .

Условие 1 называется ограничением сохранения.

Условие 2 называется ограничением мощности.

Режущая способность

Пропускная способность st разреза stCut с исходным узлом s и конечным узлом t сети потоков, представленной орграфом G , равна:

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

Отключение минимальной мощности

Пусть stCut = stCut(s,t,cut) — st-разрез сети потоков, представленный орграфом G .

stCut — это минимальное отсечение пропускной способности поточной сети , представленное G , если в этой поточной сети нет другого st cut stCutCompetitor , такого что:

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

Удаление потоков

Я хотел бы сослаться на орграф , который будет результатом взятия орграфа G и удаления всех данных потока со всех узлов в G.setOfNodes а также всех дуг в G.setOfArcs .

 def strip_flows(G): new_nodes= frozenset( (Node(n.uid, FlowNodeDatum(0.0,0.0)) for n in G.setOfNodes) ) new_arcs = frozenset([]) for a in G.setOfArcs: new_fromNode = Node(a.fromNode.uid, FlowNodeDatum(0.0,0.0)) new_toNode = Node(a.toNode.uid, FlowNodeDatum(0.0,0.0)) new_arc = Arc(new_fromNode, new_toNode, FlowArcDatum(a.datum.capacity, 0.0)) new_arcs = new_arcs.union(frozenset([new_arc])) return DiGraph(new_nodes, new_arcs)

Проблема максимального расхода

Потоковая сеть, представленная в виде орграфа G , исходного узла s в G.setOfNodes и конечного узла t в G.setOfNodes , G может представлять проблему максимального потока, если:

 (len(list(source_nodes(G))) == 1) and (next(iter(source_nodes(G))) == s) and (len(list(terminal_nodes(G))) == 1) and (next(iter(terminal_nodes(G))) == t)

Обозначьте это представление:

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

Где sourceNodeUid = s.uid , terminalNodeUid = t.uid и maxFlowProblemStateUid — это идентификатор экземпляра проблемы.

Решение с максимальным расходом

Пусть maxFlowProblem представляет задачу о максимальном потоке . Решение maxFlowProblem может быть представлено сетью потоков, представленной в виде орграфа H .

Диграф H является допустимым решением задачи максимального потока на входе python maxFlowProblem , если:

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

2. H является потоковой сетью и имеет допустимые потоки .

Если в дополнение к 1 и 2:

1. Не может быть другой сети потоков, представленной орграфом K , такой, что strip_flows(G) == strip_flows(K) и find_node_by_uid(t.uid,G).flowIn < find_node_by_uid(t.uid,K).flowIn .

Тогда H также является оптимальным решением maxFlowProblem .

Другими словами, возможное решение максимального потока может быть представлено орграфом , который:

1. Идентичен орграфу G соответствующей задачи о максимальном потоке за исключением того, что n.datum.flowIn , n.datum.flowOut и a.datum.flow любых узлов и дуг могут быть разными.

2. Представляет сеть потоков с допустимыми потоками .

И это может представлять собой оптимальное решение для максимального расхода, если дополнительно:

1. flowIn для узла , соответствующего конечному узлу в задаче о максимальном потоке , максимально велик (когда еще выполняются условия 1 и 2).

Если орграф H представляет возможное решение для максимального потока : find_node_by_uid(s.uid,H).flowOut = find_node_by_uid(t.uid,H).flowIn это следует из теоремы о максимальном потоке и минимальном разрезе (обсуждаемой ниже). Неформально, поскольку предполагается, что H имеет допустимые потоки , это означает, что поток не может быть ни «создан» (кроме исходного узла s ), ни «уничтожен» (кроме конечного узла t ) при пересечении любого (другого) узла ( ограничения сохранения ).

Поскольку задача о максимальном потоке содержит только один исходный узел s и один конечный узел t , весь поток, «созданный» в s , должен быть «уничтожен» в t , иначе в потоковой сети не будет допустимых потоков ( ограничение сохранения было бы нарушено). ).

Пусть орграф H представляет допустимое решение максимального потока ; указанное выше значение называется st Flow Value 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 st 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 — срез mfps.G Поток резки 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

st cut flow представляет собой сумму потоков из раздела, содержащего исходный узел , в раздел, содержащий конечный узел , за вычетом суммы потоков из раздела, содержащего конечный узел , в раздел, содержащий исходный узел .

Макс. расход, мин. отсечка

Пусть maxFlowProblem представляет задачу о максимальном потоке, а решение maxFlowProblem представлено сетью потоков, представленной в виде орграфа H .

Пусть minStCut будет минимальным ограничением пропускной способности сети потоков, представленной maxFlowProblem.G .

Поскольку в задаче о максимальном потоке поток возникает только в одном исходном узле и заканчивается в одном конечном узле , и из-за ограничений пропускной способности и ограничений сохранения мы знаем, что весь поток, входящий в maxFlowProblem.terminalNodeUid должен пересечь любой разрез , в частности он должен пересекать minStCut . Это означает:

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

Решение задачи о максимальном потоке

Основная идея решения задачи о максимальном потоке maxFlowProblem состоит в том, чтобы начать с решения о максимальном потоке, представленного орграфом H . Такой отправной точкой может быть H = strip_flows(maxFlowProblem.G) . Затем задача состоит в том, чтобы использовать H и с помощью некоторой жадной модификации значений a.datum.flow некоторых дуг a в H.setOfArcs получить другое решение максимального потока, представленное орграфом K , такое, что K все еще не может представлять сеть потоков с допустимыми потоками . и get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) . Пока этот процесс продолжается, качество ( get_flow_value(K, maxFlowProblem) ) последнего найденного решения максимального потока ( K ) лучше, чем любого другого найденного решения максимального потока . Если процесс достигает точки, когда он знает, что никакие другие улучшения невозможны, процесс может завершиться и возвратить оптимальное решение максимального потока .

Приведенное выше описание является общим и пропускает многие доказательства, например, возможен ли такой процесс или сколько времени он может занять, я дам еще несколько деталей и алгоритм.

Теорема о максимальном потоке и минимальном разрезе

Из книги Форда и Фулкерсона «Потоки в сетях» формулировка теоремы о максимальном потоке и минимальном разрезе (теорема 5.1):

Для любой сети максимальное значение потока от s до t равно минимальной пропускной способности всех разрезов, разделяющих s и t .

Используя определения в этом посте, это означает:

Решение maxFlowProblem , представленное сетью потоков, представленной в виде орграфа H , является оптимальным, если:

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

Мне нравится это доказательство теоремы, а в Википедии есть еще одно.

Теорема о максимальном потоке и минимальном разрезе используется для доказательства правильности и полноты метода Форда-Фалкерсона .

Я также приведу доказательство теоремы в разделе после увеличения путей .

Метод Форда-Фалкерсона и алгоритм Эдмондса-Карпа

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

Остаточный график

Остаточный граф потоковой сети, представленный в виде орграфа G , может быть представлен в виде орграфа G_f :

 ResidualDatum = namedtuple('ResidualDatum', ['residualCapacity','action']) def agg_n_to_u_cap(n,u,G_as_dict): arcs_out = G_as_dict[n] return sum([a.datum.capacity for a in arcs_out if( (a.fromNode == n) and (a.toNode == u) ) ]) def agg_n_to_u_flow(n,u,G_as_dict): arcs_out = G_as_dict[n] return sum([a.datum.flow for a in arcs_out if( (a.fromNode == n) and (a.toNode == u) ) ]) def get_residual_graph_of(G): G_as_dict = digraph_to_dict(G) residual_nodes = G.setOfNodes residual_arcs = frozenset([]) for n in G_as_dict: arcs_from = G_as_dict[n] nodes_to = frozenset([find_node_by_uid(a.toNode.uid,G) for a in arcs_from]) for u in nodes_to: n_to_u_cap_sum = agg_n_to_u_cap(n,u,G_as_dict) n_to_u_flow_sum = agg_n_to_u_flow(n,u,G_as_dict) if(n_to_u_cap_sum > n_to_u_flow_sum): flow = round(n_to_u_cap_sum - n_to_u_flow_sum, TOL) residual_arcs = residual_arcs.union( frozenset([Arc(n,u,datum=ResidualDatum(flow, 'push'))]) ) if(n_to_u_flow_sum > 0.0): flow = round(n_to_u_flow_sum, TOL) residual_arcs = residual_arcs.union( frozenset([Arc(u,n,datum=ResidualDatum(flow, 'pull'))]) ) return DiGraph(residual_nodes, residual_arcs)

• agg_n_to_u_cap(n,u,G_as_dict) возвращает сумму a.datum.capacity для всех дуг в подмножестве G.setOfArcs где дуга a находится в подмножестве, если a.fromNode = n и a.toNode = u .

• agg_n_to_u_cap(n,u,G_as_dict) возвращает сумму a.datum.flow для всех дуг в подмножестве G.setOfArcs где дуга a находится в подмножестве, если a.fromNode = n и a.toNode = u .

Вкратце, остаточный граф G_f представляет определенные действия, которые можно выполнить над орграфом G

Каждая пара узлов n,u в G.setOfNodes потоковой сети , представленной орграфом G , может генерировать 0, 1 или 2 дуги в остаточном графе G_f графа G

1. Пара n,u не порождает никаких дуг в G_f , если не существует дуги a в G.setOfArcs такой, что a.fromNode = n и a.toNode = u .

2. Пара n,u генерирует дугу a в G_f.setOfArcs , где a представляет дугу , помеченную как дуга выталкивающего потока от n до u a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) если n_to_u_cap_sum > n_to_u_flow_sum .

3. Пара n,u создает дугу a в G_f.setOfArcs , где a представляет собой дугу , помеченную как дуга вытягивающего потока от n до u a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) если n_to_u_flow_sum > 0.0 .

• Каждая дуга проталкиваемого потока в G_f.setOfArcs представляет собой действие по добавлению общего потока x <= n_to_u_cap_sum - n_to_u_flow_sum к дугам в подмножестве G.setOfArcs где дуга a находится в подмножестве, если a.fromNode = n и a.toNode = u .

• Каждая дуга вытягивающего потока в G_f.setOfArcs представляет собой действие вычитания общего потока x <= n_to_u_flow_sum из дуг в подмножестве G.setOfArcs где дуга a находится в подмножестве, если a.fromNode = n и a.toNode = u .

Выполнение отдельного действия проталкивания или вытягивания из G_f на применимых дугах в G может создать поточную сеть без допустимых потоков , потому что в созданной потоковой сети могут быть нарушены ограничения пропускной способности или ограничения сохранения .

Вот визуализация остаточного графа предыдущего примера визуализации решения максимального потока , в визуализации каждая дуга a представляет a.residualCapacity .

Дополняющий путь

Пусть maxFlowProblem будет задачей максимального потока , а G_f = get_residual_graph_of(G) будет остаточным графом maxFlowProblem.G .

Дополняющий путь augmentingPath для maxFlowProblem — это любой путь от find_node_by_uid(maxFlowProblem.sourceNode,G_f) до find_node_by_uid(maxFlowProblem.terminalNode,G_f) .

Оказывается, что увеличивающий путь augmentingPath можно применить к решению максимального потока, представленному орграфом H , генерируя другое решение максимального потока, представленное орграфом K , где get_flow_value(H, maxFlowProblem) < get_flow_value(K, 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 представляет возможное решение максимального потока для maxFlowProblem . Чтобы утверждение было верным, сеть потоков, представленная K , должна иметь допустимые потоки (не нарушающие ограничение пропускной способности или ограничение сохранения) .

И вот почему: в приведенном выше методе каждый узел , добавленный в новую поточную сеть , представленную орграфом K , является либо точной копией узла из орграфа H , либо узлом n , к n.datum.flowIn которого добавлено то же число, что и его n.datum.flowOut . Это означает, что ограничение сохранения выполняется в K до тех пор, пока оно выполняется в H . Ограничение сохранения выполняется, потому что мы явно проверяем, что любая новая дуга a в сети имеет a.datum.flow <= a.datum.capacity ; таким образом, пока дуги из набора H.setOfArcs , которые были скопированы без изменений в K.setOfArcs , не нарушают ограничение емкости , тогда K не нарушает ограничение емкости .

Также верно, что get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) если H не является оптимальным .

И вот почему: чтобы увеличивающий путь augmentingPath существовал в представлении орграфа остаточного графа G_f задачи максимального потока maxFlowProblem , последняя дуга a на augmentingPath должна быть дугой «выталкивания», и она должна иметь a.toNode == maxFlowProblem.terminalNode . Увеличивающий путь определяется как путь, который заканчивается в конечном узле задачи максимального потока, для которой он является увеличивающим путем . Из определения остаточного графа ясно, что последняя дуга в увеличивающем пути на этом остаточном графе должна быть «выталкивающей» дугой , потому что любая «вытягивающая» дуга b в увеличивающем пути будет иметь b.toNode == maxFlowProblem.terminalNode и b.fromNode != maxFlowProblem.terminalNode из определения path . Кроме того, из определения пути ясно, что конечный узел модифицируется только один раз методом augment . Таким образом, augment изменяет maxFlowProblem.terminalNode.flowIn ровно один раз и увеличивает значение maxFlowProblem.terminalNode.flowIn потому что последней дугой в augmentingPath должна быть дуга , вызывающая изменение в maxFlowProblem.terminalNode.flowIn во время augment . Из определения augment применительно к дугам «push» maxFlowProblem.terminalNode.flowIn может только увеличиваться, но не уменьшаться.

Некоторые доказательства от Седжвика и Уэйна

В четвёртом издании Роберта Седжевича и Кевина Уэйна «Алгоритмы» есть замечательные короткие доказательства (стр. 892–894), которые будут полезны. Я воссоздам их здесь, хотя я буду использовать язык, соответствующий предыдущим определениям. Мои ярлыки для доказательств такие же, как в книге Седжвика.

Утверждение E: Для любого орграфа H , представляющего возможное решение задачи максимального потока maxFlowProblem , для любого stCut get_stcut_flow(stCut,H,maxFlowProblem) = get_flow_value(H, maxFlowProblem) .

Доказательство: пусть stCut=stCut(maxFlowProblem.sourceNode,maxFlowProblem.terminalNode,set([a for a in H.setOfArcs if a.toNode == maxFlowProblem.terminalNode])) . Предложение E выполняется для stCut непосредственно из определения st-значения потока . Предположим, что мы хотим переместить некоторый узел n из s-раздела ( get_first_part(stCut.cut, G) ) в t-раздел (get_second_part(stCut.cut, G)) , для этого нам нужно изменить stCut.cut , что может изменить stcut_flow = get_stcut_flow(stCut,H,maxFlowProblem) и сделать предложение E недействительным. Однако давайте посмотрим, как изменится значение stcut_flow , когда мы внесем это изменение. узел n находится в равновесии, что означает, что сумма потоков в узел n равна сумме потоков из него (это необходимо для того, чтобы H представляло допустимое решение ). Обратите внимание, что весь поток, который является частью входящего узла n stcut_flow , входит в него из s-раздела (поток, входящий в узел n из t-раздела, прямо или косвенно, не учитывался бы в значении stcut_flow , потому что он движется в неправильном направлении). на основании определения). Кроме того, весь поток, выходящий из n , в конечном итоге (прямо или косвенно) перейдет в конечный узел (доказано ранее). Когда мы перемещаем узел n в t-раздел, весь поток, входящий в n из s-раздела, должен быть добавлен к новому значению 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-разбиения.

Вот несколько примеров сетей потоков, которые помогут визуализировать менее очевидные случаи, когда утверждение E выполняется; на изображении красные области обозначают s-раздел, синие области — t-раздел, а зеленые дуги — st -раздел. На втором изображении поток между узлом A и узлом B увеличивается, а поток в конечный узел t не меняется:

Следствие: значение расхода st cut не может превышать пропускную способность любого st cut .

Предложение F. (теорема о максимальном потоке, минимальном разрезе): Пусть f — st-поток . Следующие 3 условия эквивалентны:

1. Существует st разрез , пропускная способность которого равна величине потока f .

2. f — максимальный поток .

3. Увеличивающего пути относительно f нет.

Условие 1 влечет за собой условие 2 по следствию. Условие 2 влечет за собой условие 3, поскольку существование увеличивающего пути влечет существование потока с большими значениями, что противоречит максимальности f . Условие 3 подразумевает условие 1: пусть C_s будет набором всех узлов , до которых можно добраться из s с помощью увеличивающего пути в остаточном графе . Пусть C_t — оставшиеся дуги , тогда t должна быть в C_t (по нашему предположению). Дуги , пересекающиеся от C_s до C_t , затем образуют первый разрез , который содержит только дуги a где либо a.datum.capacity = a.datum.flow либо a.datum.flow = 0.0 . Если бы это было иначе, то узлы , соединенные дугой с остаточной пропускной способностью с C_s , находились бы в множестве C_s , поскольку тогда существовал бы увеличивающий путь от s к такому узлу . Поток через первый разрез равен пропускной способности первого разреза (поскольку дуги от C_s до C_t имеют поток, равный пропускной способности), а также величине первого потока (по предложению E ).

Это утверждение теоремы о максимальном потоке и минимальном разрезе подразумевает более раннее утверждение из раздела «Потоки в сетях».

Следствие (свойство целостности): когда мощности являются целыми числами, существует целочисленный максимальный поток, и алгоритм Форда-Фалкерсона находит его.

Доказательство: каждый увеличивающий путь увеличивает поток на положительное целое число, минимум неиспользованных пропускных способностей в «выталкивающих» дугах и потоков в «вытягивающих» дугах , все из которых всегда являются положительными целыми числами.

Это оправдывает описание метода Форда-Фалкерсона из CLRS . Метод заключается в том, чтобы продолжать находить увеличивающие пути и применять augment к последнему maxFlowSolution , получая лучшие решения, пока не перестанет увеличиваться путь , означающий, что последнее решение максимального потока является оптимальным .

От Форда-Фалкерсона к Эдмондс-Карпу

Остались вопросы, касающиеся решения задач максимального потока :

1. Как должны быть построены увеличивающие пути ?

2. Прекратится ли метод, если мы будем использовать реальные числа, а не целые числа?

3. Сколько времени потребуется, чтобы прекратить (если это произойдет)?

Алгоритм Эдмондса-Карпа указывает, что каждый увеличивающий путь строится путем поиска в ширину (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

Я использовал деку из модуля коллекций python.

Чтобы ответить на вопрос 2 выше, я перефразирую другое доказательство Седжвика и Уэйна: Предложение G. Количество увеличивающих путей , необходимых в алгоритме Эдмондса-Карпа с N узлами и A дугами , не превышает NA/2 . Доказательство: у каждого увеличивающего пути есть дуга узкого места — дуга , которая удаляется из остаточного графа , потому что она соответствует либо дуге «выталкивания», которая становится заполненной до предела, либо дуге «вытягивания», через которую поток становится равным 0. Каждый раз, когда arc становится дугой узкого места , длина любого увеличивающего пути через нее должна увеличиваться в 2 раза. Это связано с тем, что каждый узел в пути может появиться только один раз или не появиться вообще (из определения пути ), поскольку пути исследуется от кратчайшего пути к самому длинному, что означает, что по крайней мере еще один узел должен быть посещен следующим путем, который проходит через конкретный узел узкого места, что означает дополнительные 2 дуги на пути, прежде чем мы достигнем узла . Поскольку увеличивающий путь имеет длину не более N , каждая дуга может состоять не более чем из N/2 увеличивающих путей , а общее количество увеличивающих путей не превышает NA/2 .

Алгоритм Эдмондса-Карпа выполняется за 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) , алгоритм должен поддерживать как орграф , представляющий состояние задачи максимального потока, так и связанный с ним остаточный граф . Таким образом, алгоритм должен избегать ненужных итераций по дугам и узлам и обновлять их значения и связанные значения в остаточном графе только по мере необходимости.

Чтобы написать более быстрый алгоритм Эдмондса Карпа , я переписал несколько фрагментов кода из приведенного выше. Я надеюсь, что просмотр кода, сгенерировавшего новый орграф , помог понять, что происходит. В быстром алгоритме я использую некоторые новые приемы и структуры данных Python, которые я не хочу подробно описывать. Я скажу, что a.fromNode и a.toNode теперь обрабатываются как строки и uid для узлов . Для этого кода пусть mfps будет maxFlowProblemState

 import uuid def fast_get_mfps_flow(mfps): flow_from_s = {n for n in mfps.G.setOfNodes if n.uid == mfps.sourceNodeUid}.pop().datum.flowOut flow_to_t = {n for n in mfps.G.setOfNodes if n.uid == mfps.terminalNodeUid}.pop().datum.flowIn if( (flow_to_t - flow_from_s) > 0.00): raise Exception('Infeasible st flow') return flow_to_t def fast_e_k_preprocess(G): G = strip_flows(G) get = dict({}) get['nodes'] = dict({}) get['node_to_node_capacity'] = dict({}) get['node_to_node_flow'] = dict({}) get['arcs'] = dict({}) get['residual_arcs'] = dict({}) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if(a.toNode not in G.setOfNodes): err_msg = 'There is no Node {a.toNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) get['nodes'][a.fromNode.uid] = a.fromNode get['nodes'][a.toNode.uid] = a.toNode lark = Arc(a.fromNode.uid, a.toNode.uid, FlowArcDatumWithUid(a.datum.capacity, a.datum.flow, uuid.uuid4())) if(a.fromNode.uid not in get['arcs']): get['arcs'][a.fromNode.uid] = dict({a.toNode.uid : dict({lark.datum.uid : lark})}) else: if(a.toNode.uid not in get['arcs'][a.fromNode.uid]): get['arcs'][a.fromNode.uid][a.toNode.uid] = dict({lark.datum.uid : lark}) else: get['arcs'][a.fromNode.uid][a.toNode.uid][lark.datum.uid] = lark for a in G.setOfArcs: if a.toNode.uid not in get['arcs']: get['arcs'][a.toNode.uid] = dict({}) for n in get['nodes']: get['residual_arcs'][n] = dict() get['node_to_node_capacity'][n] = dict() get['node_to_node_flow'][n] = dict() for u in get['nodes']: n_to_u_cap_sum = sum(a.datum.capacity for a in G.setOfArcs if (a.fromNode.uid == n) and (a.toNode.uid == u) ) n_to_u_flow_sum = sum(a.datum.flow for a in G.setOfArcs if (a.fromNode.uid == n) and (a.toNode.uid == u) ) if(n_to_u_cap_sum > n_to_u_flow_sum): flow = round(n_to_u_cap_sum - n_to_u_flow_sum, TOL) get['residual_arcs'][n][u] = Arc(n,u,ResidualDatum(flow, 'push')) if(n_to_u_flow_sum > 0.0): flow = round(n_to_u_flow_sum, TOL) get['residual_arcs'][u][n] = Arc(u,n,ResidualDatum(flow, 'pull')) get['node_to_node_capacity'][n][u] = n_to_u_cap_sum get['node_to_node_flow'][n][u] = n_to_u_flow_sum return get def fast_bfs(sid, tid, get): parent_of = dict([]) visited = frozenset([]) deq = coll.deque([sid]) while len(deq) > 0: n = deq.popleft() if n == tid: break for u in get['residual_arcs'][n]: if (u not in visited): visited = visited.union(frozenset({u})) parent_of[u] = get['residual_arcs'][n][u] deq.extend([u]) path = list([]) curr = tid while(curr != sid): if (curr not in parent_of): err_msg = 'No augmenting path from {} to {}.'.format(sid, curr) raise StopIteration(err_msg) path.extend([parent_of[curr]]) curr = parent_of[curr].fromNode path.reverse() return path def fast_edmonds_karp(mfps): sid, tid = mfps.sourceNodeUid, mfps.terminalNodeUid get = fast_e_k_preprocess(mfps.G) no_more_paths, loop_count = False, 0 while(not no_more_paths): try: apath = fast_bfs(sid, tid, get) get = fast_augment(apath, get) loop_count += 1 except StopIteration as e: no_more_paths = True nodes = frozenset(get['nodes'].values()) arcs = frozenset({}) for from_node in get['arcs']: for to_node in get['arcs'][from_node]: for arc in get['arcs'][from_node][to_node]: arcs |= frozenset({get['arcs'][from_node][to_node][arc]}) G = DiGraph(nodes, arcs) mfps = MaxFlowProblemState(G, sourceNodeUid=sid, terminalNodeUid=tid, maxFlowProblemStateUid=mfps.maxFlowProblemStateUid) return mfps

Вот визуализация того, как этот алгоритм решает приведенный выше пример поточной сети . Визуализация показывает этапы в том виде, в каком они отражены в орграфе G , представляющем самую последнюю проточную сеть , и в том виде, в каком они отражены в остаточном графе этой проточной сети. Увеличивающие пути в остаточном графе показаны красными путями, а орграф , представляющий проблему, набор узлов и дуг , на которые влияет данный увеличивающий путь , выделен зеленым цветом. В каждом случае я буду выделять части графика, которые будут изменены (красным или зеленым цветом), а затем показывать график после изменений (только черным цветом).

Вот еще одна визуализация того, как этот алгоритм решает другой пример потоковой сети . Обратите внимание, что здесь используются действительные числа и несколько дуг с одинаковыми fromNode и toNode .

**Также обратите внимание, что, поскольку дуги с ResidualDatum «вытягивания» могут быть частью увеличивающего пути, узлы, затронутые в DiGraph Flown Network, могут не находиться на пути в G! .

Двудольные графы

Предположим, у нас есть орграф G , G является двудольным, если можно разделить узлы в G.setOfNodes на два набора ( part_1 и part_2 ), так что для любой дуги a в G.setOfArcs не может быть истинным , что a.fromNode в part_1 и a.toNode в part_1 . Также не может быть правдой , что a.fromNode в part_2 и a.toNode в part_2 .

Другими словами, G является двудольным , если его можно разделить на два набора узлов так, что каждая дуга должна соединять узел одного набора с узлом другого набора.

Тестирование двудольного

Предположим, у нас есть орграф G , и мы хотим проверить, является ли он двудольным . Мы можем сделать это за O(|G.setOfNodes|+|G.setOfArcs|) , жадно раскрасив граф в два цвета.

Во-первых, нам нужно сгенерировать новый орграф H . Этот граф будет иметь тот же набор узлов , что и G , но будет иметь больше дуг , чем G . Каждая дуга a в 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)

Сопоставления и максимальные соответствия

Предположим, у нас есть орграф G , и matching — это подмножество дуг из G.setOfArcs . matching является сопоставлением, если для любых двух дуг a и b в matching : len(frozenset( {a.fromNode} ).union( {a.toNode} ).union( {b.fromNode} ).union( {b.toNode} )) == 4 . Другими словами, никакие две дуги в паросочетании не имеют общего узла .

Matchingmatching является максимальным matching , если в G нет другого соответствия alt_matching , такого что len(matching) < len(alt_matching) . Другими словами, matching является максимальным сопоставлением , если это самый большой набор дуг из G.setOfArcs , который все еще удовлетворяет определению сопоставления (добавление любой дуги , еще не входящей в сопоставление, нарушит определение сопоставления ).

Сопоставление с максимальным соответствием matching идеальным сопоставлением , если для каждого узла n в G.setOfArcs существует дуга a в matching где a.fromNode == n or a.toNode == n .

Максимальное двудольное сопоставление

Максимальное двудольное паросочетание — это максимальное паросочетание на двудольном орграфе G

Учитывая, что G является двудольным , проблема нахождения максимального двудольного паросочетания может быть преобразована в задачу о максимальном потоке, решаемая с помощью алгоритма Эдмондса-Карпа , а затем максимальное двудольное паросочетание может быть восстановлено из решения задачи о максимальном потоке .

Пусть bipartition будет бипартицией G .

Для этого мне нужно сгенерировать новый орграф ( H ) с новыми узлами ( H.setOfNodes ) и новыми дугами ( H.setOfArcs ). H.setOfNodes содержит все узлы в G.setOfNodes и еще два узла s, s ( исходный узел ) и t ( терминальный узел ).

H.setOfArcs будет содержать одну дугу для каждого 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 также содержит дугу от узла s до каждого узла в bipartition.firstPart . Наконец, H.setOfArcs содержит дугу от каждого узла в bipartition.secondPart до узла t . a.datum.capacity = 1 для всех a в H.setOfArcs .

Сначала разбейте узлы в G.setOfNodes на два непересекающихся множества ( part1 и part2 ) таким образом, чтобы ни одна дуга в G.setOfArcs не была направлена ​​из одного множества в одно и то же множество (такое разделение возможно, потому что G является двудольным ). Затем добавьте все дуги в G.setOfArcs , которые направлены от part1 к H.setOfArcs part2 Затем создайте один исходный узел s и один конечный узел t и создайте еще несколько дуг .

Затем maxFlowProblemState .

 def solve_mbm( bipartition ): s = Node(uuid.uuid4(), FlowNodeDatum(0,0)) t = Node(uuid.uuid4(), FlowNodeDatum(0,0)) translate = {} arcs = frozenset([]) for a in bipartition.G.setOfArcs: if ( (a.fromNode in bipartition.firstPart) and (a.toNode in bipartition.secondPart) ): fark = Arc(a.fromNode,a.toNode,FlowArcDatum(1,0)) arcs = arcs.union({fark}) translate[frozenset({a.fromNode.uid,a.toNode.uid})] = a elif ( (a.toNode in bipartition.firstPart) and (a.fromNode in bipartition.secondPart) ): bark = Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) arcs = arcs.union({bark}) translate[frozenset({a.fromNode.uid,a.toNode.uid})] = a arcs1 = frozenset( {Arc(s,n,FlowArcDatum(1,0)) for n in bipartition.firstPart } ) arcs2 = frozenset( {Arc(n,t,FlowArcDatum(1,0)) for n in bipartition.secondPart } ) arcs = arcs.union(arcs1.union(arcs2)) nodes = frozenset( {Node(n.uid,FlowNodeDatum(0,0)) for n in bipartition.G.setOfNodes} ).union({s}).union({t}) G = DiGraph(nodes, arcs) mfp = MaxFlowProblemState(G, s.uid, t.uid, 'bipartite') result = edmonds_karp(mfp) lookup_set = {a for a in result.G.setOfArcs if (a.datum.flow > 0) and (a.fromNode.uid != s.uid) and (a.toNode.uid != t.uid)} matching = {translate[frozenset({a.fromNode.uid,a.toNode.uid})] for a in lookup_set} return matching

Минимальное покрытие узла

Покрытие узла в орграфе G — это набор узлов ( cover ) из G.setOfNodes , такой, что для любой дуги a из G.setOfArcs это должно быть истинным: (a.fromNode in cover) or (a.toNode in cover) .

Минимальное покрытие узлов — это наименьший возможный набор узлов в графе, который по-прежнему является покрытием узлов . Теорема Кенига утверждает, что в двудольном графе размер максимального соответствия на этом графе равен размеру минимального покрытия узла , и она предлагает, как покрытие узла может быть восстановлено из максимального соответствия :

Предположим, у нас есть bipartition bipartition и максимальное соответствие matching . Определите новый орграф H , H.setOfNodes=G.setOfNodes , дуги в H.setOfArcs являются объединением двух множеств.

Первый набор представляет собой дуги a в matching с тем изменением, что если a.fromNode in bipartition.firstPart и a.toNode in bipartition.secondPart , то a.fromNode и a.toNode меняются местами в созданной дуге , что дает таким дугам a.datum.inMatching=True , чтобы указать, что они были получены из дуг в совпадающем .

Второй набор — это дуги a НЕ в matching , с тем изменением, что если a.fromNode in bipartition.secondPart и a.toNode in bipartition.firstPart , то a.fromNode и a.toNode меняются местами в созданной дуге (дайте таким дугам a a.datum.inMatching=False атрибут).

Затем запустите поиск в глубину (DFS), начиная с каждого узла n в bipartition.firstPart , который не является ни n == a.fromNode , ни n == a.toNodes ни для какой дуги a в matching . Во время DFS некоторые узлы посещаются, а некоторые нет (сохраните эту информацию в поле n.datum.visited ). Минимальное покрытие узла представляет собой объединение узлов {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (a.fromNode.datum.visited) ) } и узлов {a.fromNode for a in H.setOfArcs if (a.datum.inMatching) and (not a.toNode.datum.visited)} .

Можно показать, что это ведет от максимального паросочетания к минимальному покрытию узла с помощью доказательства от противного, взять некоторую дугу a , которая предположительно не была покрыта, и рассмотреть все четыре случая относительно того, принадлежат ли a.fromNode и a.toNode (будь то как toNode или fromNode ) к любой дуге в сопоставлении matching . Каждый случай приводит к противоречию из-за порядка, в котором DFS посещает узлы , и того факта, что matching является максимальным сопоставлением .

Предположим, у нас есть функция для выполнения этих шагов и возврата набора узлов , включающего минимальное покрытие узла при заданном орграфе G и максимальное совпадение matching :

 ArcMatchingDatum = coll.namedtuple('ArcMatchingDatum', ['inMatching' ]) NodeMatchingDatum = coll.namedtuple('NodeMatchingDatum', ['visited']) def dfs_helper(snodes, G): sniter, do_stop = iter(snodes), False visited, visited_uids = set(), set() while(not do_stop): try: stack = [ next(sniter) ] while len(stack) > 0: curr = stack.pop() if curr.uid not in visited_uids: visited = visited.union( frozenset( {Node(curr.uid, NodeMatchingDatum(False))} ) ) visited_uids = visited.union(frozenset({curr.uid})) succ = frozenset({a.toNode for a in G.setOfArcs if a.fromNode == curr}) stack.extend( succ.difference( frozenset(visited) ) ) except StopIteration as e: stack, do_stop = [], True return visited def get_min_node_cover(matching, bipartition): nodes = frozenset( { Node(n.uid, NodeMatchingDatum(False)) for n in bipartition.G.setOfNodes} ) G = DiGraph(nodes, None) charcs = frozenset( {a for a in matching if ( (a.fromNode in bipartition.firstPart) and (a.toNode in bipartition.secondPart) )} ) arcs0 = frozenset( { Arc(find_node_by_uid(a.toNode.uid,G), find_node_by_uid(a.fromNode.uid,G), ArcMatchingDatum(True) ) for a in charcs } ) arcs1 = frozenset( { Arc(find_node_by_uid(a.fromNode.uid,G), find_node_by_uid(a.toNode.uid,G), ArcMatchingDatum(True) ) for a in matching.difference(charcs) } ) not_matching = bipartition.G.setOfArcs.difference( matching ) charcs = frozenset( {a for a in not_matching if ( (a.fromNode in bipartition.secondPart) and (a.toNode in bipartition.firstPart) )} ) arcs2 = frozenset( { Arc(find_node_by_uid(a.toNode.uid,G), find_node_by_uid(a.fromNode.uid,G), ArcMatchingDatum(False) ) for a in charcs } ) arcs3 = frozenset( { Arc(find_node_by_uid(a.fromNode.uid,G), find_node_by_uid(a.toNode.uid,G), ArcMatchingDatum(False) ) for a in not_matching.difference(charcs) } ) arcs = arcs0.union(arcs1.union(arcs2.union(arcs3))) G = DiGraph(nodes, arcs) bip = Bipartition({find_node_by_uid(n.uid,G) for n in bipartition.firstPart},{find_node_by_uid(n.uid,G) for n in bipartition.secondPart},G) match_from_nodes = frozenset({find_node_by_uid(a.fromNode.uid,G) for a in matching}) match_to_nodes = frozenset({find_node_by_uid(a.toNode.uid,G) for a in matching}) snodes = bip.firstPart.difference(match_from_nodes).difference(match_to_nodes) visited_nodes = dfs_helper(snodes, bip.G) not_visited_nodes = bip.G.setOfNodes.difference(visited_nodes) H = DiGraph(visited_nodes.union(not_visited_nodes), arcs) cover1 = frozenset( {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (a.fromNode.datum.visited) ) } ) cover2 = frozenset( {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (not a.toNode.datum.visited) ) } ) min_cover_nodes = cover1.union(cover2) true_min_cover_nodes = frozenset({find_node_by_uid(n.uid, bipartition.G) for n in min_cover_nodes}) return min_cover_nodes

Линейная задача о назначениях

Задача о линейных назначениях состоит в поиске паросочетания максимального веса во взвешенном двудольном графе.

Задачи, подобные той, что в самом начале этого поста, можно выразить как задачу линейного назначения . Имея набор рабочих, набор задач и функцию, показывающую прибыльность назначения одного рабочего на одну задачу, мы хотим максимизировать сумму всех выполняемых нами назначений; это линейная задача о назначениях .

Предположим, что количество задач и рабочих одинаково, хотя я покажу, что это предположение легко убрать. В реализации я представляю веса дуг атрибутом a.datum.weight для дуги a .

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

Алгоритм Куна-Мункреса

Алгоритм Куна-Мункреса решает линейную задачу о назначениях . Хорошая реализация может занять O(N^{4}) времени (где N — количество узлов в орграфе , представляющем проблему). Реализация, которую легче объяснить, требует O(N^{5}) (для версии, которая регенерирует DiGraphs ) и O(N^{4}) для (для версии, которая поддерживает DiGraphs ). Это похоже на две разные реализации алгоритма Эдмондса-Карпа .

Для этого описания я работаю только с полными двудольными графами (теми, где половина узлов находится в одной части двудольного графа, а другая половина — во второй части). В рабочей мотивации задач это означает, что рабочих столько, сколько задач.

Это кажется существенным условием (что, если эти множества не равны!), но эту проблему легко исправить; О том, как это сделать, я рассказал в последнем разделе.

Описанная здесь версия алгоритма использует полезную концепцию дуг нулевого веса . К сожалению, эта концепция имеет смысл только тогда, когда мы решаем задачу минимизации (если вместо того, чтобы максимизировать прибыль от наших рабочих задач, мы минимизируем стоимость таких задач).

К счастью, задачу о максимальном линейном назначении легко превратить в задачу о минимальном линейном назначении , установив a каждой дуги веса Ma.datum.weight где M=max({a.datum.weight for a in G.setOfArcs}) . Решение исходной задачи максимизации будет идентично решению задачи минимизации после изменения весов дуг . Итак, в остальном предположим, что мы делаем это изменение.

Алгоритм Куна-Манкреса решает сопоставление минимального веса во взвешенном двудольном графе с помощью последовательности максимальных паросочетаний в невзвешенном двудольном графе. Если a мы находим идеальное паросочетание в представлении орграфа линейной задачи о назначениях и если вес каждой дуги в паросочетании равен нулю, то мы нашли паросочетание минимального веса, поскольку это паросочетание предполагает, что все узлы в орграфе были соответствует дуге с наименьшей возможной стоимостью (стоимость не может быть меньше 0, исходя из предыдущих определений).

Никакие другие дуги не могут быть добавлены к сопоставлению (поскольку все узлы уже сопоставлены) и никакие дуги не должны быть удалены из сопоставления , поскольку любая возможная замещающая дуга будет иметь как минимум такое же значение веса.

Если мы найдем максимальное паросочетание подграфа G , которое содержит только дуги с нулевым весом , и это не идеальное паросочетание , у нас не будет полного решения (поскольку паросочетание не является совершенным ). Однако мы можем создать новый орграф H , изменив веса дуг в G.setOfArcs таким образом, чтобы появились новые дуги с нулевым весом, а оптимальное решение H было таким же, как и оптимальное решение G . Поскольку мы гарантируем, что на каждой итерации создается по крайней мере одна дуга с нулевым весом , мы гарантируем, что мы придем к идеальному паросочетанию не более чем за |G.setOfNodes|^{2}=N^{2} таких итераций.

Предположим, что в bipartition bipartition bipartition.firstPart содержит узлы , представляющие работников, а bipartition.secondPart представляет узлы , представляющие задачи.

Алгоритм начинается с создания нового орграфа H . H.setOfNodes = G.setOfNodes . Некоторые дуги в H генерируются из узлов n в bipartition.firstPart . Каждый такой узел n генерирует дугу b в H.setOfArcs для каждой дуги a в bipartition.G.setOfArcs , где a.fromNode = n или a.toNode = n , b=Arc(a.fromNode, a.toNode, a.datum.weight - z) где z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) .

Дополнительные дуги в H генерируются из узлов n в bipartition.secondPart . Каждый такой узел n генерирует дугу b в H.setOfArcs для каждой дуги a в bipartition.G.setOfArcs , где a.fromNode = n или a.toNode = n , b=Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) где z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) .

KMA: Затем сформируйте новый орграф K , состоящий только из дуг нулевого веса из H и узлов , инцидентных этим дугам . Сформируйте bipartition на узлах в K , затем используйтеsolve_mbm 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 . Алгоритм продолжается до тех пор, пока не будет получено идеальное соответствие . Это соответствие также является решением задачи о линейных назначениях .

 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}) . Подробности как более простой реализации, описанной выше, так и более сложной реализации можно найти в этом посте, который мотивировал этот пост в блоге.

Ни одна из операций над весами дуг не изменяет окончательное назначение, возвращаемое алгоритмом. Вот почему: поскольку наши входные графы всегда являются полными двудольными графами , решение должно сопоставлять каждый узел в одном разделе с другим узлом во втором разделе через дугу между этими двумя узлами . Обратите внимание, что операции, выполняемые над весами дуг , никогда не изменяют порядок (упорядоченный по весам) дуг , попадающих в какой-либо конкретный узел .

Таким образом, когда алгоритм завершается на идеальном полном двудольном паросочетании, каждому узлу присваивается дуга с нулевым весом , поскольку относительный порядок дуг из этого узла не изменился во время алгоритма, и поскольку дуга с нулевым весом является самой дешевой из возможных дуг и совершенное полное двудольное паросочетание гарантирует, что для каждого узла существует одна такая дуга . Это означает, что сгенерированное решение действительно совпадает с решением исходной линейной задачи о назначениях без какой-либо модификации весов дуг .

Несбалансированные задания

Кажется, что алгоритм довольно ограничен, поскольку, как описано, он работает только с полными двудольными графами (теми, у которых половина узлов находится в одной части двудольного раздела , а другая половина - во второй части). В рабочей мотивации задач это означает, что рабочих столько же, сколько и задач (кажется весьма ограничивающим).

Однако существует простое преобразование, которое снимает это ограничение. Предположим, что воркеров меньше, чем задач, мы добавляем несколько фиктивных воркеров (достаточно, чтобы получившийся граф стал полным двудольным графом ). Each dummy worker has an arc directed from the worker to each of the tasks. Each such arc has weight 0 (placing it in a matching gives no added profit). After this change the graph is a complete bipartite graph which we can solve for. Any task assigned a dummy worker is not initiated.

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

A Linear Assignment Example

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

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

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

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

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

Вот и все. You now know everything you need to know about the linear assignment problem.

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

Дальнейшее чтение в блоге Toptal Engineering:

• Наука о графических данных с помощью Python/NetworkX