Fluxo Máximo e o Problema de Atribuição Linear

Aqui está um problema: sua empresa designa empreiteiros para cumprir contratos. Você examina suas listas e decide quais contratados estão disponíveis para um contrato de um mês e examina seus contratos disponíveis para ver quais deles são para tarefas de um mês. Dado que você sabe com que eficiência cada contratado pode cumprir cada contrato, como você designa contratados para maximizar a eficácia geral desse mês?

Este é um exemplo do problema de atribuição, e o problema pode ser resolvido com o algoritmo húngaro clássico.

O algoritmo húngaro (também conhecido como algoritmo de Kuhn-Munkres) é um algoritmo de tempo polinomial que maximiza a correspondência de peso em um gráfico bipartido ponderado. Aqui, os contratantes e os contratos podem ser modelados como um grafo bipartido, com sua eficácia como os pesos das arestas entre o contratante e os nós do contrato.

Neste artigo, você aprenderá sobre uma implementação do algoritmo húngaro que usa o algoritmo de Edmonds-Karp para resolver o problema de atribuição linear. Você também aprenderá como o algoritmo de Edmonds-Karp é uma pequena modificação do método Ford-Fulkerson e como essa modificação é importante.

O problema do fluxo máximo

O problema de fluxo máximo em si pode ser descrito informalmente como o problema de mover algum fluido ou gás através de uma rede de tubos de uma única fonte para um único terminal. Isso é feito com a suposição de que a pressão na rede é suficiente para garantir que o fluido ou gás não permaneça em nenhum comprimento de tubo ou encaixe de tubo (aqueles locais onde diferentes comprimentos de tubo se encontram).

Ao fazer algumas alterações no gráfico, o problema de atribuição pode ser transformado em um problema de fluxo máximo.

Preliminares

As idéias necessárias para resolver esses problemas surgem em muitas disciplinas matemáticas e de engenharia, muitas vezes conceitos semelhantes são conhecidos por nomes diferentes e expressos de maneiras diferentes (por exemplo, matrizes de adjacência e listas de adjacência). Uma vez que essas idéias são bastante esotéricas, as escolhas são feitas em relação a quão geralmente esses conceitos serão definidos para qualquer cenário.

Este artigo não assumirá nenhum conhecimento prévio além de um pouco de teoria dos conjuntos introdutória.

As implementações neste post representam os problemas como grafos direcionados (dígrafo).

DiGraphs

Um dígrafo tem dois atributos, setOfNodes e setOfArcs . Ambos os atributos são conjuntos (coleções não ordenadas). Nos blocos de código deste post, na verdade estou usando o frozenset do Python, mas esse detalhe não é particularmente importante.

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

(Observação: este e todos os outros códigos neste artigo são escritos em Python 3.6.)

Nós

Um nó n é composto por dois atributos:

• n.uid : Um identificador exclusivo.

  Isso significa que para quaisquer dois nós x e y ,

 x.uid != y.uid

• n.datum : Representa qualquer objeto de dados.

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

Arcos

Um arco a é composto por três atributos:

• a.fromNode : Este é um nó , conforme definido acima.

• a.toNode : Este é um nó , conforme definido acima.

• a.datum : Representa qualquer objeto de dados.

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

O conjunto de arcos no dígrafo representa uma relação binária nos nós do dígrafo . A existência de arc a implica que existe um relacionamento entre a.fromNode e a.toNode .

Em um gráfico direcionado (em oposição a um gráfico não direcionado), a existência de um relacionamento entre a.fromNode e a.toNode não implica que exista um relacionamento semelhante entre a.toNode e a.fromNode .

Isso ocorre porque em um grafo não direcionado, a relação que está sendo expressa não é necessariamente simétrica.

DiGraphs

Nós e arcos podem ser usados ​​para definir um dígrafo , mas por conveniência, nos algoritmos abaixo, um dígrafo será representado usando como um dicionário.

Aqui está um método que pode converter a representação gráfica acima em uma representação de dicionário semelhante a esta:

 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

E aqui está outro que o converte em um dicionário de dicionários, outra operação que será útil:

 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

Quando o artigo fala sobre um dígrafo representado por um dicionário, ele mencionará G_as_dict para se referir a ele.

Às vezes é útil buscar um nó de um dígrafo G por meio de seu uid (identificador exclusivo):

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

Na definição de grafos, as pessoas às vezes usam os termos nó e vértice para se referir ao mesmo conceito; o mesmo vale para os termos arco e aresta.

Duas representações gráficas populares em Python são esta que usa dicionários e outra que usa objetos para representar gráficos. A representação neste post está em algum lugar entre essas duas representações comumente usadas.

Esta é a minha representação em dígrafo . Há muitos assim, mas este é meu.

Caminhadas e Caminhos

Seja S_Arcs uma sequência finita (coleção ordenada) de arcos em um dígrafo G tal que se a é qualquer arco em S_Arcs exceto o último, e b segue a na sequência, então deve haver um nó n = a.fromNode em G.setOfNodes tal que a.toNode = b.fromNode .

Começando do primeiro arco em S_Arcs , e continuando até o último arco em S_Arcs , colete (na ordem encontrada) todos os nós n conforme definido acima entre cada dois arcos consecutivos em S_Arcs . Rotule a coleção ordenada de nós coletados durante esta operação 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

• Se algum nó aparecer mais de uma vez na sequência S_Nodes , então chame S_Arcs de Walk no dígrafo G .

• Caso contrário, chame S_Arcs um caminho de list(S_Nodes)[0] para list(S_Nodes)[-1] no dígrafo G .

Nó de origem

Chame o nó s um nó fonte no dígrafo G se s estiver em G.setOfNodes e G.setOfArcs não contiver nenhum arco a tal que 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

Nó Terminal

Chame o nó t de um nó terminal no dígrafo G se t estiver em G.setOfNodes e G.setOfArcs não contiver nenhum arco a tal que 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 e st Cortes

Um cut de um dígrafo conectado G é um subconjunto de arcos de G.setOfArcs que particiona o conjunto de nós G.setOfNodes em G . G é conectado se cada nó n em G.setOfNodes e tem pelo menos um arco a em G.setOfArcs tal que n = a.fromNode ou n = a.toNode , mas a.fromNode != a.toNode .

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

A definição acima se refere a um subconjunto de arcos , mas também pode definir uma partição dos nós de G.setOfNodes .

Para as funções predecessors_of e successors_of , n é um nó no conjunto G.setOfNodes do digrafo G e cut é um corte de 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

Seja cut um corte do dígrafo 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 é um corte do dígrafo G se: (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 é chamado de corte xy se (x in get_first_part(cut, G)) and (y in get_second_part(cut, G) ) and (x != y) . Quando o nó x em um cut xy é um nó fonte e o nó y no corte xy é um nó terminal , então esse corte é chamado de st corte .

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

Redes de fluxo

Você pode usar um dígrafo G para representar uma rede de fluxo.

Atribua a cada nó n , onde n está em G.setOfNodes um n.datum que é um FlowNodeDatum :

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

Atribua a cada arco a , onde a está em G.setOfArcs e a.datum que é um FlowArcDatum .

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

flowNodeDatum.flowIn e flowNodeDatum.flowOut são números reais positivos.

flowArcDatum.capacity e flowArcDatum.flow também são números reais positivos.

Para cada nó nó n em 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})

O dígrafo G agora representa uma rede de fluxo .

O fluxo de G refere-se ao a.flow a para todos os arcos a em G .

Fluxos Viáveis

Deixe o dígrafo G representar uma rede de fluxo .

A rede de fluxos representada por G tem fluxos viáveis ​​se:

1. Para cada nó n em G.setOfNodes , exceto para nós de origem e nós terminais : n.datum.flowIn = n.datum.flowOut .

2. Para cada arco a em G.setOfNodes : a.datum.capacity <= a.datum.flow .

A condição 1 é chamada de restrição de conservação.

A condição 2 é chamada de restrição de capacidade.

Capacidade de corte

A capacidade de corte de um st cut stCut com nó fonte s e nó terminal t de uma rede de fluxo representada por um dígrafo 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

Corte de Capacidade Mínima

Seja stCut = stCut(s,t,cut) um st corte de uma rede de fluxo representada por um dígrafo G .

stCut é o corte mínimo de capacidade da rede de fluxo representado por G se não houver outro st cut stCutCompetitor nesta rede de fluxo tal que:

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

Tirando os Fluxos

Eu gostaria de me referir ao dígrafo que seria o resultado de pegar um dígrafo G e retirar todos os dados de fluxo de todos os nós em G.setOfNodes e também todos os arcos em 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)

Problema de fluxo máximo

Uma rede de fluxo representada como um dígrafo G , um nó de origem s em G.setOfNodes e um nó terminal t em G.setOfNodes , G pode representar um problema de fluxo máximo se:

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

Rotule esta representação:

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

Em que sourceNodeUid = s.uid , terminalNodeUid = t.uid e maxFlowProblemStateUid é um identificador para a instância do problema.

Solução de fluxo máximo

Deixe maxFlowProblem representar um problema de fluxo máximo . A solução para maxFlowProblem pode ser representada por uma rede de fluxo representada como um dígrafo H .

O dígrafo H é uma solução viável para o problema de fluxo máximo na entrada python maxFlowProblem se:

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

2. H é uma rede de fluxo e tem fluxos viáveis .

Se além de 1 e 2:

1. Não pode haver nenhuma outra rede de fluxo representada pelo dígrafo K tal que strip_flows(G) == strip_flows(K) e find_node_by_uid(t.uid,G).flowIn < find_node_by_uid(t.uid,K).flowIn .

Então H também é uma solução ótima para maxFlowProblem .

Em outras palavras, uma solução de fluxo máximo viável pode ser representada por um dígrafo , que:

1. É idêntico ao dígrafo G do problema de fluxo máximo correspondente com a exceção de que o n.datum.flowIn , n.datum.flowOut e o a.datum.flow de qualquer um dos nós e arcos podem ser diferentes.

2. Representa uma rede de fluxos que possui fluxos viáveis .

E pode representar uma solução de fluxo máximo ideal se adicionalmente:

1. O flowIn para o nó correspondente ao nó terminal no problema de fluxo máximo é o maior possível (quando as condições 1 e 2 ainda são satisfeitas).

Se o dígrafo H representa uma solução de fluxo máximo viável : find_node_by_uid(s.uid,H).flowOut = find_node_by_uid(t.uid,H).flowIn isso segue do teorema de fluxo máximo, corte mínimo (discutido abaixo). Informalmente, uma vez que H é assumido como tendo fluxos viáveis, isso significa que o fluxo não pode ser 'criado' (exceto no nó de origem s ) nem 'destruído' (exceto no nó terminal t ) enquanto cruza qualquer (outro) nó ( restrições de conservação ).

Uma vez que um problema de fluxo máximo contém apenas um único nó fonte s e um único nó terminal t , todo fluxo 'criado' em s deve ser 'destruído' em t ou a rede de fluxo não possui fluxos viáveis ​​(a restrição de conservação teria sido violada ).

Deixe o dígrafo H representar uma solução de fluxo máximo viável ; o valor acima é chamado de valor de fluxo de H .

Deixar:

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

Isso significa que mfps é um estado sucessor de maxFlowProblem , o que significa apenas que mfps é exatamente como maxFlowProblem com a exceção de que os valores de a.flow para arcos a em maxFlowProblem.setOfArcs podem ser diferentes de a.flow para arcos a em 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

Aqui está uma visualização de um mfps junto com seu maxFlowProb associado. Cada arco a na imagem tem um rótulo, esses rótulos são a.datum.flowFrom / a.datum.flowTo , cada nó n na imagem tem um rótulo e esses rótulos são n.uid {n.datum.flowIn / a.datum.flowOut} .

Fluxo de corte

Deixe mfps representar um MaxFlowProblemState e deixe stCut representar um corte de mfps.G . O fluxo de corte do stCut é definido:

 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

o fluxo de corte é a soma dos fluxos da partição que contém o nó de origem para a partição que contém o nó terminal menos a soma dos fluxos da partição que contém o nó terminal para a partição que contém o nó de origem .

Fluxo máximo, corte mínimo

Deixe maxFlowProblem representar um problema de fluxo máximo e deixe a solução para maxFlowProblem ser representada por uma rede de fluxo representada como dígrafo H .

Seja minStCut o corte mínimo de capacidade da rede de fluxo representada por maxFlowProblem.G .

Porque no problema de fluxo máximo o fluxo se origina em apenas um único nó de origem e termina em um único nó terminal e, devido às restrições de capacidade e às restrições de conservação , sabemos que todo o fluxo que entra em maxFlowProblem.terminalNodeUid deve cruzar qualquer st corte , em particular deve cruzar minStCut . Isso significa:

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

Resolvendo o problema de fluxo máximo

A idéia básica para resolver um problema de fluxo máximo maxFlowProblem é começar com uma solução de fluxo máximo representada pelo dígrafo H . Esse ponto de partida pode ser H = strip_flows(maxFlowProblem.G) . A tarefa é então usar H e por alguma modificação gulosa dos valores a.datum.flow de alguns arcos a em H.setOfArcs para produzir outra solução de fluxo máximo representada pelo dígrafo K tal que K ainda não possa representar uma rede de fluxo com fluxos viáveis e get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) . Enquanto esse processo continuar, a qualidade ( get_flow_value(K, maxFlowProblem) ) da solução de fluxo máximo encontrada mais recentemente ( K ) é melhor do que qualquer outra solução de fluxo máximo encontrada. Se o processo chegar a um ponto em que sabe que nenhuma outra melhoria é possível, o processo pode terminar e retornará a solução de fluxo máximo ideal.

A descrição acima é geral e pula muitas provas como se tal processo é possível ou quanto tempo pode demorar, vou dar mais alguns detalhes e o algoritmo.

O fluxo máximo, teorema de corte mínimo

Do livro Flows in Networks de Ford e Fulkerson, o enunciado do fluxo máximo, teorema de corte mínimo (Teorema 5.1) é:

Para qualquer rede, o valor máximo do fluxo de s para t é igual à capacidade mínima de corte de todos os cortes que separam s e t .

Usando as definições neste post, isso se traduz em:

A solução para um maxFlowProblem representado por uma rede de fluxo representada como dígrafo H é ótima se:

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

Eu gosto desta prova do teorema e a Wikipedia tem outra.

O teorema do fluxo máximo, corte mínimo é usado para provar a exatidão e completude do método de Ford-Fulkerson .

Também darei uma prova do teorema na seção após aumentar os caminhos .

O Método Ford-Fulkerson e o Algoritmo Edmonds-Karp

O CLRS define o método Ford-Fulkerson assim (seção 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

Gráfico residual

O gráfico residual de uma rede de fluxo representado como o dígrafo G pode ser representado como um dígrafo 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) retorna a soma de a.datum.capacity para todos os arcos no subconjunto de G.setOfArcs onde arc a está no subconjunto se a.fromNode = n a.toNode = u .

• agg_n_to_u_cap(n,u,G_as_dict) retorna a soma de a.datum.flow para todos os arcos no subconjunto de G.setOfArcs onde arc a está no subconjunto se a.fromNode = n a.toNode = u .

Resumidamente, o grafo residual G_f representa certas ações que podem ser realizadas no dígrafo G .

Cada par de nós n,u em G.setOfNodes da rede de fluxo representada pelo digrafo G pode gerar 0, 1 ou 2 arcos no grafo residual G_f de G .

1. O par n,u não gera nenhum arco em G_f se não houver arco a em G.setOfArcs tal que a.fromNode = n a.toNode = u .

2. O par n,u gera o arco a em G_f.setOfArcs onde a representa um arco rotulado como um arco de fluxo push de n a u a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) se n_to_u_cap_sum > n_to_u_flow_sum .

3. O par n,u gera o arco a em G_f.setOfArcs onde a representa um arco rotulado como um arco de fluxo puxado de n para u a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) se n_to_u_flow_sum > 0.0 .

• Cada arco de fluxo push em G_f.setOfArcs representa a ação de adicionar um total de x <= n_to_u_cap_sum - n_to_u_flow_sum fluxo n_to_u_flow_sum para arcos no subconjunto de G.setOfArcs onde arc a está no subconjunto se a.fromNode = n e a.toNode = u .

• Cada arco de fluxo pull em G_f.setOfArcs representa a ação de subtrair um total de fluxo x <= n_to_u_flow_sum para arcos no subconjunto de G.setOfArcs onde arco a está no subconjunto se a.fromNode = n a.toNode = u .

Executar uma ação individual de empurrar ou puxar de G_f nos arcos aplicáveis ​​em G pode gerar uma rede de fluxo sem fluxos viáveis ​​porque as restrições de capacidade ou as restrições de conservação podem ser violadas na rede de fluxo gerada.

Aqui está uma visualização do gráfico residual da visualização de exemplo anterior de uma solução de fluxo máximo , na visualização cada arco a representa a.residualCapacity .

Caminho de aumento

Seja maxFlowProblem um problema de fluxo máximo , e seja G_f = get_residual_graph_of(G) o grafo residual de maxFlowProblem.G .

Um caminho de augmentingPath augmentingPath para maxFlowProblem é qualquer caminho de find_node_by_uid(maxFlowProblem.sourceNode,G_f) para find_node_by_uid(maxFlowProblem.terminalNode,G_f) .

Acontece que um caminho de augmentingPath pode ser aplicado a uma solução de fluxo máximo representada pelo dígrafo H gerando outra solução de fluxo máximo representada pelo dígrafo K onde get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) se H não for ideal .

Veja como:

 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

Acima, TOL é algum valor de tolerância para arredondar os valores de fluxo na rede. Isso é para evitar a imprecisão em cascata dos cálculos de ponto flutuante. Então, por exemplo, usei TOL = 10 para significar arredondamento para 10 dígitos significativos.

Seja K = augment(augmentingPath, H) , então K representa uma solução de fluxo máximo viável para maxFlowProblem . Para que a afirmação seja verdadeira, a rede de fluxo representada por K deve ter fluxos factíveis (não violar a restrição de capacidade ou a restrição de conservação .

Aqui está o porquê: No método acima, cada nó adicionado à nova rede de fluxo representada pelo dígrafo K é uma cópia exata de um nó do dígrafo H ou um nó n que teve o mesmo número adicionado ao seu n.datum.flowIn como seu n.datum.flowOut . Isso significa que a restrição de conservação é satisfeita em K desde que seja satisfeita em H A restrição de conservação é satisfeita porque verificamos explicitamente que qualquer novo arco a na rede possui a.datum.flow <= a.datum.capacity ; assim, desde que os arcos do conjunto H.setOfArcs que foram copiados sem modificação em K.setOfArcs não violem a restrição de capacidade , então K não viola a restrição de capacidade .

Também é verdade que get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) se H não for ideal .

Aqui está o porquê: Para um caminho de augmentingPath existir na representação G_f do grafo residual G_f de um problema de fluxo máximo maxFlowProblem então o último arco a em augmentingPath deve ser um arco 'push' e deve ter a.toNode == maxFlowProblem.terminalNode . Um caminho de aumento é definido como aquele que termina no nó terminal do problema de fluxo máximo para o qual é um caminho de aumento . A partir da definição do grafo residual , fica claro que o último arco em um caminho de aumento nesse grafo residual deve ser um arco de 'push' porque qualquer arco de 'puxão' b no caminho de aumento terá b.toNode == maxFlowProblem.terminalNode e b.fromNode != maxFlowProblem.terminalNode da definição de path . Além disso, a partir da definição de path , fica claro que o nó terminal é modificado apenas uma vez pelo método de augment . Assim, augment modifica maxFlowProblem.terminalNode.flowIn exatamente uma vez e aumenta o valor de maxFlowProblem.terminalNode.flowIn porque o último arco em augmentingPath deve ser o arco que causa a modificação em maxFlowProblem.terminalNode.flowIn durante augment . A partir da definição de augment como se aplica a arcos 'push', o maxFlowProblem.terminalNode.flowIn só pode ser aumentado, não diminuído.

Algumas provas de Sedgewick e Wayne

O livro Algorithms, quarta edição de Robert Sedgewich e Kevin Wayne tem algumas provas maravilhosas e curtas (páginas 892-894) que serão úteis. Vou recriá-los aqui, embora use uma linguagem que se encaixe nas definições anteriores. Meus rótulos para as provas são os mesmos do livro de Sedgewick.

Proposição E: Para qualquer dígrafo H representando uma solução de fluxo máximo viável para um problema de fluxo máximo maxFlowProblem , para qualquer stCut get_stcut_flow(stCut,H,maxFlowProblem) = get_flow_value(H, maxFlowProblem) .

Prova: Seja stCut=stCut(maxFlowProblem.sourceNode,maxFlowProblem.terminalNode,set([a for a in H.setOfArcs if a.toNode == maxFlowProblem.terminalNode])) . A proposição E vale para stCut diretamente da definição do valor de fluxo st . Suponha que desejamos mover algum nó n da partição s ( get_first_part(stCut.cut, G) ) e para a partição t (get_second_part(stCut.cut, G)) , para isso precisamos alterar stCut.cut , que poderia alterar stcut_flow = get_stcut_flow(stCut,H,maxFlowProblem) e invalidar a proposição E . No entanto, vamos ver como o valor de stcut_flow mudará à medida que fizermos essa alteração. o nó n está em equilíbrio, o que significa que a soma do fluxo no nó n é igual à soma do fluxo que sai dele (isso é necessário para que H represente uma solução viável ). Observe que todo o fluxo que faz parte do stcut_flow que entra no nó n entra na partição s (o fluxo que entra no nó n da partição t direta ou indiretamente não teria sido contado no valor stcut_flow porque está indo na direção errada com base na definição). Além disso, todo o fluxo que sai de n eventualmente (direta ou indiretamente) fluirá para o nó terminal (comprovado anteriormente). Quando movemos o nó n para a partição t, todo o fluxo que entra n da partição s deve ser adicionado ao novo valor stcut_flow ; entretanto, todo fluxo que sai de n deve ser subtraído do novo valor de stcut_flow ; a parte do fluxo que se dirige diretamente para a partição t é subtraída porque esse fluxo agora é interno à nova partição t e não é contado como stcut_flow . A parte do fluxo de n indo para os nós na partição s também deve ser subtraída de stcut_flow : Após n ser movido para a partição t, esses fluxos serão direcionados da partição t para a partição s e assim não deve ser contabilizado no stcut_flow , pois esses fluxos são removidos do fluxo de entrada na partição s e devem ser reduzidos pela soma desses fluxos, e o fluxo de saída da partição s para a partição t (onde todos os fluxos de st deve terminar) deve ser reduzido no mesmo valor. Como o nó n estava em equilíbrio antes do processo, a atualização terá adicionado o mesmo valor ao novo valor stcut_flow que subtraiu, deixando a proposição E verdadeira após a atualização. A validade da proposição E segue então da indução sobre o tamanho da partição t.

Aqui estão alguns exemplos de redes de fluxo para ajudar a visualizar os casos menos óbvios em que a proposição E é válida; na imagem, as áreas vermelhas indicam a partição s, as áreas azuis representam a partição t e os arcos verdes indicam um st corte . Na segunda imagem, o fluxo entre o nó A e o nó B aumenta enquanto o fluxo no nó terminal t não muda.:

Corolário: Nenhum valor de fluxo de corte pode exceder a capacidade de qualquer corte .

Proposição F. (fluxo máximo, teorema de corte mínimo): Seja f um st fluxo . As 3 condições a seguir são equivalentes:

1. Existe um st corte cuja capacidade é igual ao valor da vazão f .

2. f é um fluxo máximo .

3. Não há caminho aumentante em relação a f .

A condição 1 implica a condição 2 pelo corolário. A condição 2 implica a condição 3 porque a existência de um caminho aumentante implica a existência de um fluxo com valores maiores, contrariando a maximalidade de f . A condição 3 implica a condição 1: Seja C_s o conjunto de todos os nós que podem ser alcançados a partir de s com um caminho aumentado no grafo residual . Sejam C_t os arcos restantes, então t deve estar em C_t (por nossa suposição). Os arcos que cruzam de C_s para C_t formam então um st corte que contém apenas arcos a onde a.datum.capacity = a.datum.flow ou a.datum.flow = 0.0 . Caso contrário, os nós conectados por um arco com capacidade residual remanescente a C_s estariam no conjunto C_s , pois haveria então um caminho aumentado de s para tal nó . O fluxo através do st corte é igual à capacidade do st corte (já que os arcos de C_s a C_t têm vazão igual à capacidade) e também ao valor do st fluxo (pela proposição E ).

Esta declaração do teorema de fluxo máximo, corte mínimo implica a declaração anterior de Fluxos em Redes.

Corolário (propriedade de integralidade): Quando as capacidades são inteiras, existe um fluxo máximo de valor inteiro e o algoritmo de Ford-Fulkerson o encontra.

Prova: Cada caminho de aumento aumenta o fluxo por um número inteiro positivo, o mínimo das capacidades não utilizadas nos arcos 'push' e os fluxos nos arcos 'puxar', todos os quais são sempre inteiros positivos.

Isso justifica a descrição do método Ford-Fulkerson do CLRS . O método é continuar encontrando caminhos de aumento e aplicando augment ao maxFlowSolution mais recente, chegando a soluções melhores, até que não haja mais caminho de aumento, o que significa que a solução de fluxo máximo mais recente é ideal .

De Ford-Fulkerson a Edmonds-Karp

As questões restantes sobre a resolução de problemas de fluxo máximo são:

1. Como os caminhos de aumento devem ser construídos?

2. O método terminará se usarmos números reais e não inteiros?

3. Quanto tempo vai demorar para terminar (se for)?

O algoritmo de Edmonds-Karp especifica que cada caminho de aumento é construído por uma busca em largura (BFS) do grafo residual ; verifica-se que esta decisão do ponto 1 acima também forçará o algoritmo a terminar (ponto 2) e permitirá que a complexidade assintótica de tempo e espaço seja determinada.

Primeiro, aqui está uma implementação do 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

Eu usei um deque do módulo de coleções python.

Para responder à pergunta 2 acima, vou parafrasear outra prova de Sedgewick e Wayne: Proposição G. O número de caminhos de aumento necessários no algoritmo de Edmonds-Karp com N nós e A arcos é no máximo NA/2 . Prova: Todo caminho de aumento tem um arco de gargalo - um arco que é excluído do grafo residual porque corresponde a um arco 'push' que fica cheio até a capacidade ou um arco 'puxar' através do qual o fluxo se torna 0. arc se torna um arco de gargalo , o comprimento de qualquer caminho aumentado através dele deve aumentar por um fator de 2. Isso ocorre porque cada nó em um caminho pode aparecer apenas uma vez ou não aparecer (a partir da definição de caminho ) já que os caminhos estão sendo explorado do caminho mais curto para o mais longo, o que significa que pelo menos mais um nó deve ser visitado pelo próximo caminho que passa pelo nó de gargalo específico, o que significa 2 arcos adicionais no caminho antes de chegarmos ao nó . Como o caminho de aumento tem comprimento no máximo N , cada arco pode estar em no máximo N/2 caminhos de aumento , e o número total de caminhos de aumento é no máximo NA/2 .

O algoritmo de Edmonds-Karp é executado em O(NA^2) . Se no máximo NA/2 caminhos forem explorados durante o algoritmo e explorar cada caminho com BFS for N+A , então o termo mais significativo do produto e, portanto, a complexidade assintótica é O(NA^2) .

Seja mfp um 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

A versão acima é ineficiente e tem complexidade pior do que O(NA^2) , pois constrói uma nova solução de fluxo máximo e um novo gráfico residual a cada vez (em vez de modificar os dígrafos existentes à medida que o algoritmo avança). Para obter uma solução O(NA^2) verdadeira, o algoritmo deve manter tanto o dígrafo que representa o estado do problema de fluxo máximo quanto seu grafo residual associado. Portanto, o algoritmo deve evitar iterar sobre arcos e nós desnecessariamente e atualizar seus valores e valores associados no grafo residual somente quando necessário.

Para escrever um algoritmo de Edmonds Karp mais rápido, reescrevi vários trechos de código acima. Espero que passar pelo código que gerou um novo dígrafo tenha ajudado a entender o que está acontecendo. No algoritmo rápido, eu uso alguns novos truques e estruturas de dados Python que não quero detalhar. Eu direi que a.fromNode e a.toNode agora são tratados como strings e uids para nós . Para este código, deixe mfps ser um 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

Aqui está uma visualização de como esse algoritmo resolve a rede de fluxo de exemplo acima. A visualização mostra as etapas conforme elas são refletidas no dígrafo G representando a rede de fluxo mais atualizada e como elas são refletidas no gráfico residual dessa rede de fluxo. Os caminhos de aumento no grafo residual são mostrados como caminhos em vermelho, e o dígrafo que representa o problema, o conjunto de nós e arcos afetados por um determinado caminho de aumento, é destacado em verde. Em cada caso, destacarei as partes do gráfico que serão alteradas (em vermelho ou verde) e mostrarei o gráfico após as alterações (apenas em preto).

Aqui está outra visualização de como esse algoritmo resolve uma rede de fluxo de exemplo diferente. Observe que este usa números reais e contém vários arcos com os mesmos valores fromNode e toNode .

** Observe também que, como Arcos com um ResidualDatum 'puxado' podem fazer parte do Caminho Aumentado, os nós afetados no DiGraph da Rede Voada _podem não estar em um caminho em G! .

Gráficos Bipartidos

Suponha que temos um dígrafo G , G é bipartido se for possível particionar os nós em G.setOfNodes em dois conjuntos ( part_1 e part_2 ) tal que para qualquer arco a em G.setOfArcs não pode ser verdade que a.fromNode em part_1 e a.toNode em part_1 . Também não pode ser verdade que a.fromNode em part_2 e a.toNode em part_2 .

Em outras palavras, G é bipartido se pode ser particionado em dois conjuntos de nós , de modo que cada arco deve conectar um nó em um conjunto a um nó no outro conjunto.

Teste bipartido

Suponha que temos um dígrafo G , queremos testar se é bipartido . Podemos fazer isso em O(|G.setOfNodes|+|G.setOfArcs|) colorindo gananciosamente o gráfico em duas cores.

Primeiro, precisamos gerar um novo dígrafo H . Este grafo terá o mesmo conjunto de nós que G , mas terá mais arcos que G . Cada arco a em G criará 2 arcos em H ; o primeiro arco será idêntico a a , e o segundo arco inverte o diretor de 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)

Correspondências e Correspondências Máximas

Suponha que temos um dígrafo G e a matching é um subconjunto de arcos de G.setOfArcs . matching é uma correspondência se para quaisquer dois arcos a e b na matching : len(frozenset( {a.fromNode} ).union( {a.toNode} ).union( {b.fromNode} ).union( {b.toNode} )) == 4 . Em outras palavras, dois arcos em uma correspondência não compartilham um nó .

Matching matching , é um casamento máximo se não houver nenhum outro alt_matching correspondente em G tal que len(matching) < len(alt_matching) . Em outras palavras, a matching é uma correspondência máxima se for o maior conjunto de arcos de G.setOfArcs que ainda satisfaz a definição de correspondência (a adição de qualquer arco que ainda não esteja na correspondência quebrará a definição de correspondência ).

Uma correspondência matching máxima é uma correspondência perfeita se cada para nó n em G.setOfArcs existe um arco a na matching onde a.fromNode == n or a.toNode == n .

Máxima correspondência bipartida

Um emparelhamento máximo bipartido é um emparelhamento máximo em um dígrafo G que é bipartido .

Dado que G é bipartido , o problema de encontrar um emparelhamento bipartido máximo pode ser transformado em um problema de fluxo máximo solucionável com o algoritmo de Edmonds-Karp e então o emparelhamento bipartido máximo pode ser recuperado da solução para o problema de fluxo máximo .

Seja bipartition uma bipartição de G .

Para fazer isso, preciso gerar um novo dígrafo ( H ) com alguns novos nós ( H.setOfNodes ) e alguns novos arcos ( H.setOfArcs ). H.setOfNodes contém todos os nós em G.setOfNodes e mais dois nós , s (um nó de origem ) t (um nó terminal ).

H.setOfArcs conterá um arco para cada G.setOfArcs . Se um arco a estiver em G.setOfArcs e a.fromNode estiver em bipartition.firstPart e a.toNode estiver em bipartition.secondPart , inclua a em H (adicionando um FlowArcDatum(1,0) ).

Se a.fromNode estiver em bipartition.secondPart e a.toNode estiver em bipartition.firstPart , inclua Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) em H.setOfArcs .

A definição de um grafo bipartido garante que nenhum arco conecte nenhum nó onde ambos os nós estejam na mesma partição. H.setOfArcs também contém um arco do nó s para cada nó em bipartition.firstPart . Finalmente, H.setOfArcs contém um arco de cada nó em bipartition.secondPart para o nó t . a.datum.capacity = 1 para todo a em H.setOfArcs .

Primeiro particione os nós em G.setOfNodes os dois conjuntos disjuntos ( part1 e part2 ) de forma que nenhum arco em G.setOfArcs seja direcionado de um conjunto para o mesmo conjunto (esta partição é possível porque G é bipartido ). Em seguida, adicione todos os arcos em G.setOfArcs que são direcionados de part1 para part2 em H.setOfArcs . Em seguida, crie um único nó de origem s e um único nó terminal t e crie mais alguns arcos

Em seguida, construa um 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

Cobertura Mínima de Nó

Uma cobertura de nó em um dígrafo G é um conjunto de nós ( cover ) de G.setOfNodes tal que para qualquer arco a de G.setOfArcs isso deve ser verdadeiro: (a.fromNode in cover) or (a.toNode in cover) .

Uma cobertura mínima de nós é o menor conjunto possível de nós no grafo que ainda é uma cobertura de nós . O teorema de Konig afirma que em um grafo bipartido , o tamanho do emparelhamento máximo nesse grafo é igual ao tamanho da cobertura de nó mínimo e sugere como a cobertura de nó pode ser recuperada de um emparelhamento máximo :

Suponha que temos a bipartição bipartition e o matching máximo . Defina um novo dígrafo H , H.setOfNodes=G.setOfNodes , os arcos em H.setOfArcs são a união de dois conjuntos.

O primeiro conjunto é arcos a em matching , com a mudança de que se a.fromNode in bipartition.firstPart e a.toNode in bipartition.secondPart então a.fromNode e a.toNode são trocados no arco criado dão a esses arcos um a.datum.inMatching=True atributo para indicar que eles foram derivados de arcos em um .

O segundo conjunto é arcs a NOT em matching , com a mudança de que se a.fromNode in bipartition.secondPart e a.toNode in bipartition.firstPart então a.fromNode e a.toNode são trocados no arco criado (dê a tais arcos um a.datum.inMatching=False ).

Em seguida, execute uma primeira pesquisa em profundidade (DFS) começando em cada nó n em bipartition.firstPart que não é n == a.fromNode nem n == a.toNodes para qualquer arco a em matching . Durante o DFS, alguns nós são visitados e outros não (armazene esta informação em um campo n.datum.visited ). A cobertura mínima de nós é a união dos nós {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (a.fromNode.datum.visited) ) } e os nós {a.fromNode for a in H.setOfArcs if (a.datum.inMatching) and (not a.toNode.datum.visited)} .

Isso pode ser mostrado para levar de um casamento máximo a uma cobertura mínima de nós por uma prova por contradição, pegue algum arco a que supostamente não foi coberto e considere todos os quatro casos sobre se a.fromNode e a.toNode pertencem (seja como toNode ou fromNode ) para qualquer arco na correspondência matching . Cada caso leva a uma contradição devido à ordem em que o DFS visita os nós e ao fato de que a matching é uma correspondência máxima .

Suponha que tenhamos uma função para executar essas etapas e retornar o conjunto de nós que compreende a cobertura mínima de nós quando dado o dígrafo G e a correspondência máxima de 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

O Problema de Atribuição Linear

O problema de atribuição linear consiste em encontrar um casamento de peso máximo em um grafo bipartido ponderado.

Problemas como o do início deste post podem ser expressos como um problema de atribuição linear . Dado um conjunto de trabalhadores, um conjunto de tarefas e uma função que indica a lucratividade de uma atribuição de um trabalhador a uma tarefa, queremos maximizar a soma de todas as atribuições que fazemos; este é um problema de atribuição linear .

Suponha que o número de tarefas e trabalhadores seja igual, embora eu mostre que essa suposição é fácil de remover. Na implementação, represento pesos de arco com um atributo a.datum.weight para um arco a .

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

Algoritmo de Kuhn-Munkres

O Algoritmo de Kuhn-Munkres resolve o problema de atribuição linear . Uma boa implementação pode levar tempo O(N^{4}) , (onde N é o número de nós no dígrafo que representa o problema). Uma implementação que é mais fácil de explicar leva O(N^{5}) (para uma versão que gera DiGraphs ) e O(N^{4}) para (para uma versão que mantém DiGraphs ). Isso é semelhante às duas implementações diferentes do algoritmo de Edmonds-Karp .

Para esta descrição, estou trabalhando apenas com grafos bipartidos completos (aqueles onde metade dos nós está em uma parte da bipartição e a outra metade na segunda parte). No trabalhador, a motivação da tarefa significa que existem tantos trabalhadores quanto as tarefas.

Esta parece ser uma condição significativa (e se esses conjuntos não forem iguais!), mas é fácil corrigir esse problema; Eu falo sobre como fazer isso na última seção.

A versão do algoritmo aqui descrita usa o conceito útil de arcos de peso zero . Infelizmente, esse conceito só faz sentido quando estamos resolvendo uma minimização (se, em vez de maximizar os lucros de nossas atribuições de tarefas de trabalho, estivermos minimizando o custo de tais atribuições).

Felizmente, é fácil transformar um problema de atribuição linear máxima em um problema de atribuição linear mínima , definindo cada a dos pesos do arco para Ma.datum.weight onde M=max({a.datum.weight for a in G.setOfArcs}) . A solução do problema de maximização original será idêntica à do problema de minimização da solução depois que os pesos dos arcos forem alterados. Portanto, para o restante, suponha que fazemos essa alteração.

O algoritmo de Kuhn-Munkres resolve a correspondência de peso mínimo em um gráfico bipartido ponderado por uma sequência de correspondências máximas em gráficos bipartidos não ponderados. Se a encontrarmos um emparelhamento perfeito na representação de dígrafo do problema de atribuição linear , e se o peso de cada arco no emparelhamento for zero, então encontramos o emparelhamento de peso mínimo, pois esse emparelhamento sugere que todos os nós no dígrafo foram correspondido por um arco com o menor custo possível (nenhum custo pode ser inferior a 0, com base nas definições anteriores).

Nenhum outro arco pode ser adicionado à correspondência (porque todos os nós já são correspondidos) e nenhum arco deve ser removido da correspondência porque qualquer possível arco de substituição terá pelo menos um valor de peso tão grande.

Se encontrarmos um emparelhamento máximo do subgrafo de G que contém apenas arcos de peso zero , e não é um emparelhamento perfeito , não temos uma solução completa (já que o emparelhamento não é perfeito ). No entanto, podemos produzir um novo dígrafo H alterando os pesos dos arcos em G.setOfArcs de forma que novos arcos de peso 0 apareçam e a solução ótima de H seja a mesma que a solução ótima de G . Como garantimos que pelo menos um arco de peso zero é produzido em cada iteração, garantimos que chegaremos a um casamento perfeito em não mais do que |G.setOfNodes|^{2}=N^{2} de tais iterações.

Suponha que em bipartition bipartition , bipartition.firstPart contém nós que representam trabalhadores e bipartition.secondPart representa nós que representam tarefas.

O algoritmo começa gerando um novo dígrafo H . H.setOfNodes = G.setOfNodes . Alguns arcos em H são gerados a partir de nós n em bipartition.firstPart . Cada um desses nós n gera um arco b em H.setOfArcs para cada arco a em bipartition.G.setOfArcs onde a.fromNode = n ou a.toNode = n , b=Arc(a.fromNode, a.toNode, a.datum.weight - z) onde z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) .

Mais arcos em H são gerados a partir de nós n em bipartition.secondPart . Cada um desses nós n gera um arco b em H.setOfArcs para cada arco a em bipartition.G.setOfArcs onde a.fromNode = n ou a.toNode = n , b=Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) onde z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) .

KMA: Em seguida, forme um novo dígrafo K composto apenas pelos arcos de peso zero de H , e os nós incidentes nesses arcos . Forme uma bipartition nos nós em K , então use solve_mbm( bipartition ) para obter uma matching máxima ( match ) em K . Se matching é um emparelhamento perfeito em H (os arcos no matching são incidentes em todos os nós em H.setOfNodes ), então o matching é uma solução ótima para o problema de atribuição linear .

Caso contrário, se a matching não for perfeita , gere a cobertura mínima de nó de K usando node_cover = get_min_node_cover(matching, bipartition(K)) . Em seguida, defina z=min({a.datum.weight for a in H.setOfArcs if a not in node_cover}) . Defina 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)} . O símbolo != na expressão anterior atua como um operador XOR. Então arcs = arcs1.union(arcs2.union(arcs3)) . Em seguida, H=DiGraph(nodes,arcs) . Volte para o rótulo KMA . O algoritmo continua até que um emparelhamento perfeito seja produzido. Este emparelhamento também é a solução para o problema de atribuição linear .

 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

Esta implementação é O(N^{5}) porque gera uma nova matching máxima em cada iteração; semelhante às duas implementações anteriores de Edmonds-Karp, este algoritmo pode ser modificado para que acompanhe a correspondência e o adapte de forma inteligente a cada iteração. Quando isso é feito, a complexidade se torna O(N^{4}) . Uma versão mais avançada e mais recente deste algoritmo (exigindo algumas estruturas de dados mais avançadas) pode ser executada em O(N^{3}) . Detalhes da implementação mais simples acima e da implementação mais avançada podem ser encontrados nesta postagem que motivou esta postagem no blog.

Nenhuma das operações em pesos de arco modifica a atribuição final retornada pelo algoritmo. Aqui está o porquê: Como nossos grafos de entrada são sempre grafos bipartidos completos , uma solução deve mapear cada nó em uma partição para outro nó na segunda partição, através do arco entre esses dois nós . Observe que as operações realizadas nos pesos dos arcos nunca alteram a ordem (ordenada por peso) dos arcos incidentes em qualquer nó específico.

Assim, quando o algoritmo termina em um casamento bipartido completo perfeito , a cada nó é atribuído um arco de peso zero , uma vez que a ordem relativa dos arcos desse nó não mudou durante o algoritmo, e como um arco de peso zero é o arco mais barato possível e o emparelhamento bipartido completo perfeito garante a existência de um desses arcos para cada nó . Isso significa que a solução gerada é de fato a mesma que a solução do problema de atribuição linear original sem qualquer modificação dos pesos dos arcos .

Atribuições desequilibradas

Parece que o algoritmo é bastante limitado, pois, conforme descrito, ele opera apenas em grafos bipartidos completos (aqueles em que metade dos nós está em uma parte da bipartição e a outra metade na segunda parte). No trabalhador, a motivação da tarefa significa que existem tantos trabalhadores quanto tarefas (parece bastante limitante).

No entanto, há uma transformação fácil que remove essa restrição. Suponha que haja menos trabalhadores do que tarefas, adicionamos alguns trabalhadores fictícios (o suficiente para tornar o grafo resultante um grafo bipartido completo ). Each dummy worker has an arc directed from the worker to each of the tasks. Each such arc has weight 0 (placing it in a matching gives no added profit). After this change the graph is a complete bipartite graph which we can solve for. Any task assigned a dummy worker is not initiated.

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

A Linear Assignment Example

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

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

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

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

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

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

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

Leitura adicional no Blog da Toptal Engineering:

• Gráficos de ciência de dados com Python/NetworkX