最大フローと線形割り当て問題

公開: 2022-03-11

ここに問題があります：あなたのビジネスは契約を履行するために請負業者を割り当てます。 名簿を調べて、1か月の契約に利用できる請負業者を決定し、利用可能な契約を調べて、1か月のタスクに利用できる請負業者を確認します。 各請負業者が各契約をどれだけ効果的に履行できるかを知っているとしたら、その月の全体的な効果を最大化するために請負業者をどのように割り当てますか？

これは割り当て問題の例であり、この問題は古典的なハンガリーのアルゴリズムで解決できます。

二部マッチング

ハンガリーのアルゴリズム（Kuhn-Munkresアルゴリズムとも呼ばれます）は、重み付き2部グラフの重みマッチングを最大化する多項式時間アルゴリズムです。 ここで、請負業者と契約は2部グラフとしてモデル化でき、請負業者と契約ノードの間のエッジの重みとしての有効性があります。

この記事では、エドモンズ・カープアルゴリズムを使用して線形割り当て問題を解決するハンガリーアルゴリズムの実装について学習します。 また、エドモンズ・カープアルゴリズムがフォード・ファルカーソン法のわずかな修正である方法と、この修正がどのように重要であるかについても学習します。

最大フロー問題

最大フロー問題自体は、パイプのネットワークを介して単一のソースから単一のターミナルに流体またはガスを移動させる問題として非公式に説明できます。 これは、ネットワーク内の圧力が、流体またはガスがパイプまたはパイプ継手の長さ（異なる長さのパイプが出会う場所）にとどまらないようにするのに十分であるという前提で行われます。

グラフに特定の変更を加えることにより、割り当て問題を最大フロー問題に変えることができます。

予選

これらの問題を解決するために必要なアイデアは、多くの数学および工学の分野で発生します。多くの場合、同様の概念は異なる名前で知られており、異なる方法で表現されます（たとえば、隣接行列や隣接リスト）。 これらのアイデアは非常に難解であるため、特定の設定に対してこれらの概念がどの程度一般的に定義されるかについて選択が行われます。

この記事では、少し入門的な集合論以外の予備知識は想定していません。

この投稿の実装は、問題を有向グラフ（有向グラフ）として表しています。

DiGraphs

有向グラフには、 setOfNodesとsetOfArcsの2つの属性があります。 これらの属性は両方ともセット（順序付けられていないコレクション）です。 この投稿のコードブロックでは、実際にPythonのfrozensetを使用していますが、その詳細は特に重要ではありません。

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

（注：これ、およびこの記事の他のすべてのコードは、Python 3.6で記述されています。）

ノード

ノードnは、次の2つの属性で構成されます。

  • n.uid ：一意の識別子。

    これは、任意の2つのノードxおよびyについて、

 x.uid != y.uid
  • n.datum ：これは任意のデータオブジェクトを表します。
 Node = namedtuple('Node', ['uid','datum'])

アーク

アークaは、次の3つの属性で構成されます。

  • a.fromNode ：これは上記で定義したノードです。

  • a.toNode ：これは上記で定義されたノードです。

  • a.datum ：これは任意のデータオブジェクトを表します。

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

有向グラフの円弧のセットは、有向グラフのノード上の2値関係を表します。 アークaの存在は、 a.fromNodeとa.toNodeの間に関係が存在することを意味します。

（無向グラフとは対照的に）有向グラフでは、 a.toNode a.fromNode a.fromNode a.toNodeに同様の関係が存在することを意味するものではありません。

これは、無向グラフでは、表現される関係が必ずしも対称であるとは限らないためです。

DiGraphs

ノードとアークを使用して有向グラフを定義できますが、便宜上、以下のアルゴリズムでは、有向グラフは辞書として使用して表されます。

上記のグラフ表現を次のような辞書表現に変換できるメソッドは次のとおりです。

 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で人気のある2つのグラフ表現は、辞書を使用するものと、オブジェクトを使用してグラフを表現するものです。 この投稿の表現は、これら2つの一般的に使用される表現の間のどこかにあります。

これは私の有向グラフ表現です。 似たようなものはたくさんありますが、これは私のものです。

散歩と小道

S_Arcsを有向グラフGのアークの有限シーケンス（順序付けられたコレクション）とし、 aが最後を除くS_Arcsのアークであり、 bがシーケンスaの後に続く場合、ノードn = a.fromNodeが存在する必要があります。 G.setOfNodes a.toNode = b.fromNodeとなるようなG.setOfNodes。

S_Arcsの最初のアークから開始し、 S_Arcsの最後のアークまで継続して、 S_Arcsの各2つの連続するアーク間で、上記で定義したすべてのノード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を有向グラフGのlist(S_Nodes)[0]からlist(S_Nodes)[-1]へのパスと呼びます。

ソースノード

sがG.setOfNodesにあり、 G.setOfArcsにa.toNode = s aなアークが含まれていない場合、ノードsを有向グラフGのソースノードと呼びます。

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

ターミナルノード

tがG.setOfNodesにあり、 G.setOfArcsにa.fromNode = t aようなアークが含まれていない場合は、ノードtを有向グラフGのターミナルノードと呼びます。

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

カットとstカット

接続された有向グラフGのカットcutは、 G.setOfArcsからのアークのサブセットであり、 GのノードG.setOfNodesのセットを分割します。 Gは、G.setOfNodes内のすべてのノードnが接続され、 G.setOfNodes内に少なくとも1つのアークaがあり、 n = a.fromNode G.setOfArcs n = a.toNode a.toNodeのいずれかですが、 a.fromNode != a.toNodeです。

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

上記の定義はアークのサブセットを参照していますが、 G.setOfNodesのノードのパーティションを定義することもできます。

関数predecessors_ofおよびsuccessors_ofの場合、 nは有向グラフGの集合G.setOfNodes内のノードであり、 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

カットを有向グラフGのcutとします。

 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は、（ get_first_part （ 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は、 (x in get_first_part(cut, G)) and (y in get_second_part(cut, G) ) and (x != y)の場合にxyカットと呼ばれます。 xyカットcutのノードxがソースノードであり、 xyカットのノードyがターミナルノードである場合、このカットは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も正の実数です。

G.setOfNodesのすべてのノードノードnについて：

 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のフローは、 G内のすべてのアークaのa.flowを指します。

実行可能なフロー

有向グラフGがフローネットワークを表すとします。

Gで表されるフローネットワークには、次の場合に実行可能なフローがあります。

  1. ソースノードとターミナルノードを除くG.setOfNodesのすべてのノードn ： n.datum.flowIn = n.datum.flowOut 。

  2. G.setOfNodesのすべてのアークaについて： a.datum.capacity <= a.datum.flow 。

条件1は保存制約と呼ばれます。

条件2は容量制約と呼ばれます。

容量の削減

有向グラフGで表されるフローネットワークのソースノードsとターミナルノードtを持つstCutのカット容量は次のとおりです。

 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)を、有向グラフGで表されるフローネットワークのstカットとします。

stCutは、このフローネットワークに次のような他のst cut stCutCompetitorがない場合に、 Gで表されるフローネットワークの最小容量カットです。

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

流れを取り除く

有向グラフGを取得し、G.setOfNodesのすべてのノードと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として表されるフローネットワーク、G.setOfNodesのソースノードs 、およびG.setOfNodesのターミナルノードt 、 Gは、 G.setOfNodesの場合に最大フロー問題を表すことができます。

 (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として表されるフローネットワークで表すことができます。

Digraph Hは、次の場合に入力python maxFlowProblemの最大フロー問題に対する実行可能なソリューションです。

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

  2. Hはフローネットワークであり、実行可能なフローがあります。

1と2に加えて：

  1. strip_flows(G) == strip_flows(K)およびfind_node_by_uid(t.uid,G).flowIn < find_node_by_uid(t.uid,K).flowInのような有向グラフKで表される他のフローネットワークはありません。

その場合、 HはmaxFlowProblemの最適なソリューションでもあります。

言い換えると、実行可能な最大フローソリューションは、次のような有向グラフで表すことができます。

  1. n.datum.flowIn 、 n.datum.flowOut 、およびノー​​ドとアークのいずれかのa.datum.flowが異なる可能性があることを除いて、対応する最大フロー問題の有向グラフGと同じです。

  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が実行可能な最大フロー解を表すとします。 上記の値は、 Hのstフロー値と呼ばれます。

させて：

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

これは、 mfpsがmaxFlowProblemの継承状態であることを意味します。つまり、maxFlowProblem.setOfArcsのアークaのa.flowの値が、 a.flowのアークaのmaxFlowProblem.setOfArcsと異なる場合があることを除いて、 mfpsはmaxFlowProblemとa.flow同じ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} 。

最大流れの可視化

stカットフロー

mfpsが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に入るすべてのフローは任意のstカットを通過する必要があることがわかります。特に、 minStCutと交差する必要があります。 これの意味は：

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

最大フロー問題の解決

最大フロー問題maxFlowProblemを解くための基本的な考え方は、有向グラフHで表される最大フロー解から始めることです。 このような開始点は、 H = strip_flows(maxFlowProblem.G)です。 次に、 Hを使用し、 H.setOfArcs内のいくつかのアークaのa.datum.flow値を貪欲に変更して、 Kが実行可能なフローを持つフローネットワークを表すことができないように、有向グラフKで表される別の最大フローソリューションを生成します。およびget_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) 。 このプロセスが続く限り、最後に遭遇した最大フローソリューション（ K ）の品質（ get_flow_value(K, maxFlowProblem) ）は、見つかった他の最大フローソリューションよりも優れています。 プロセスが他の改善が不可能であることがわかっているポイントに達すると、プロセスは終了し、最適な最大フローソリューションを返します。

上記の説明は一般的なものであり、そのようなプロセスが可能かどうかや所要時間など、多くの証明をスキップします。いくつかの詳細とアルゴリズムについて説明します。

最大フロー、最小カット定理

FordとFulkersonによる著書FlowsinNetworksから、最大フロー、最小カット定理（定理5.1）のステートメントは次のとおりです。

どのネットワークでも、 s t s t分離するすべてのカットの最小カット容量に等しくなります。

この投稿の定義を使用すると、次のようになります。

有向グラフHとして表されるフローネットワークによって表されるmaxFlowProblemのソリューションは、次の場合に最適です。

 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)は、 G.setOfArcsのサブセット内のすべてのアークのa.datum.capacityの合計を返します。ここで、 a.fromNode = nおよびa.toNode = uの場合、アークaはサブセット内にあります。

  • agg_n_to_u_cap(n,u,G_as_dict)は、 G.setOfArcsのサブセット内のすべてのアークのa.datum.flowの合計を返します。ここで、 a.fromNode = nおよびa.toNode = uの場合、アークaはサブセット内にあります。

簡単に言えば、残差グラフG_fは、有向グラフGで実行できる特定のアクションを表します。

有向グラフGで表されるフローネットワークのG.setOfNodesのノードn,uの各ペアは、 Gの残差グラフG_fに0、1、または2つのアークを生成できます。

  1. a.fromNode = nおよびa.toNode = uのようなG.setOfArcsにアークaがない場合、ペアn,uはG_fにアークを生成しません。

  2. ペアn,uは、 G_f.setOfArcsでアークaを生成します。ここでaは、 n_to_u_cap_sum > n_to_u_flow_sumの場合a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) nからuへのプッシュフローアークとラベル付けされたアークを表します。

  3. ペアn,uは、 G_f.setOfArcsでアークaを生成します。ここでaは、 n_to_u_flow_sum > 0.0の場合a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) nからuへのプルフローアークとラベル付けされたアークを表します。

  • G_f.setOfArcsの各プッシュフローアークは、合計x <= n_to_u_cap_sum - n_to_u_flow_sumフローをG.setOfArcsのサブセットのアークに追加するアクションを表しG.setOfArcs 。ここで、アークaは、 a.fromNode = nおよびa.toNode = uの場合にサブセットに含まれます。 a.toNode = u 。

  • G_f.setOfArcsの各プルフローアークは、 G_f.setOfArcsのサブセット内のアークへの合計x <= n_to_u_flow_sum G.setOfArcsを差し引くアクションを表します。ここで、アークaは、 a.fromNode = nおよびa.toNode = uの場合にサブセット内にあります。

Gの該当するアークでG_fから個別のプッシュまたはプルアクションを実行すると、生成されたフローネットワークで容量の制約または保存の制約に違反する可能性があるため、実行可能なフローのないフローネットワークが生成される可能性があります。

これは、最大フローソリューションの前の例の視覚化の残差グラフの視覚化です。視覚化では、各アークaはa.residualCapacityを表します。

最大流れの可視化（残差）

パスの拡張

maxFlowProblemを最大フロー問題とし、 G_f = get_residual_graph_of(G)をmaxFlowProblem.Gの残差グラフとします。

maxFlowProblem augmentingPath 、 find_node_by_uid(maxFlowProblem.sourceNode,G_f)からfind_node_by_uid(maxFlowProblem.terminalNode,G_f) ）への任意のパスです。

augmenting Path augmentingPathは、ダイグラフHで表される最大フローソリューションに適用して、ダイグラフKで表される別の最大フローソリューションを生成できます。ここで、 Hが最適でない場合はget_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem)です。

方法は次のとおりです。

 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.datum.flowInに同じ番号が追加されたノードnのいずれかです。そのn.datum.flowOut 。 これは、 Hで満たされている限り、 Kで保存制約が満たされることを意味します。 ネットワーク内の新しいアークaがa.datum.flow <= a.datum.capacity ;であることを明示的にチェックするため、保存の制約が満たされます。 したがって、変更せずにK.setOfArcsにコピーされたセットH.setOfArcsからのアークが容量制約に違反しない限り、 Kは容量制約に違反しません。

Hが最適でない場合get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem)あることも事実です。

その理由は次のとおりです。拡張パスaugmentingPathが最大フロー問題maxFlowProblemの残差グラフG_fの有向グラフ表現に存在するためには、augmentingPathの最後のアークaが「プッシュ」アークであり、 a.toNode == maxFlowProblem.terminalNode augmentingPathある必要があります。 a.toNode == maxFlowProblem.terminalNode 。 拡張パスは、拡張パスである最大フロー問題の終端ノードで終了するパスとして定義されます。 残差グラフの定義から、その残差グラフの拡張パスの最後のアークは「プッシュ」アークでなければならないことは明らかです。これは、拡張パスの「プル」アークbにはb.toNode b.toNode == maxFlowProblem.terminalNodeパスの定義からのb.toNode == maxFlowProblem.terminalNodeおよびb.fromNode != maxFlowProblem.terminalNode 。 さらに、パスの定義から、ターミナルノードはaugmentメソッドによって一度だけ変更されることが明らかです。 したがって、 augmentはmaxFlowProblem.terminalNode.flowInを1回だけ変更し、maxFlowProblem.terminalNode.flowInの値を増やします。これは、 maxFlowProblem.terminalNode.flowInの最後のアークが、 maxFlowProblem.terminalNode.flowIn augmentingPath変更を引き起こすアークである必要があるaugmentです。 'push'アークに適用されるaugmentの定義から、 maxFlowProblem.terminalNode.flowInは増加のみ可能であり、減少することはできません。

セジウィックとウェインからのいくつかの証拠

RobertSedgewichとKevinWayneによる本Algorithms、第4版には、役立ついくつかの素晴らしく短い証明（892〜894ページ）があります。 ここでそれらを再作成しますが、以前の定義に適合する言語を使用します。 証明の私のラベルは、Sedgewickの本と同じです。

命題E：最大フロー問題maxFlowProblemの実行可能な最大フローソリューションを表す任意の有向グラフHの場合、任意の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は、 stフロー値の定義から直接stCutに当てはまります。 あるノードnをsパーティション（ get_first_part(stCut.cut, G) ）からtパーティション(get_second_part(stCut.cut, G))に移動したいとします。そのためには、 stCut.cutを変更する必要があります。 stCut.cut 。これにより、 stcut_flow = get_stcut_flow(stCut,H,maxFlowProblem)が変更され、命題Eが無効になる可能性があります。 ただし、この変更を行うと、 stcut_flowの値がどのように変化するかを見てみましょう。 ノードnは平衡状態にあり、ノードnへの流れの合計がノードnからの流れの合計に等しいことを意味します（これは、 Hが実行可能な解を表すために必要です）。 ノードnに入るstcut_flowの一部であるすべてのフローがsパーティションから入ることに注意してください（tパーティションから直接または間接的にノードnに入るフローは、間違った方向に向かっているため、 stcut_flow値にカウントされませんでした。定義に基づく）。 さらに、 nを出るすべてのフローは、最終的に（直接的または間接的に）ターミナルノードに流れ込みます（前述のとおり）。 ノードnをtパーティションに移動するとき、sパーティションからnに入るすべてのフローを新しいstcut_flow値に追加する必要があります。 ただし、 nを出るすべてのフローは、新しいstcut_flow値から差し引く必要があります。 このフローは新しいtパーティションの内部にあり、 stcut_flowとしてカウントされないため、tパーティションに直接向かうフローの部分が差し引かれます。 nからsパーティションのノードに向かうフローの一部もstcut_flowから差し引く必要がありますnがtパーティションに移動された後、これらのフローはtパーティションからsパーティションに送られます。これらのフローはsパーティションへのstcut_flowが削除され、これらのフローの合計、およびsパーティションからtパーティションへの流出（すべてのフローがstは終了する必要があります）同じ量だけ減らす必要があります。 ノードnはプロセスの前に平衡状態にあったため、更新により、差し引かれたのと同じ値が新しいstcut_flow値に追加され、更新後に命題Eが真のままになります。 命題Eの有効性は、tパーティションのサイズの帰納法から得られます。

命題Eが当てはまるあまり目立たないケースを視覚化するのに役立つフローネットワークの例を次に示します。 画像では、赤い領域はsパーティションを示し、青い領域はtパーティションを表し、緑の弧はstカットを示します。 2番目の画像では、ノードAとノードBの間のフローが増加していますが、ターミナルノードtへのフローは変化していません。

当然の結果： stカットフロー値は、 stカットの容量を超えることはできません。

命題F.（最大フロー、最小カット定理）： fをstフローとします。 次の3つの条件は同等です。

  1. 容量がフローfの値に等しいstカットが存在します。

  2. fは最大フローです。

  3. fに関して拡張パスはありません。

条件1は、当然の結果として条件2を意味します。 条件2は条件3を意味します。これは、拡張パスの存在は、 fの最大性と矛盾する、より大きな値のフローの存在を意味するためです。 条件3は、条件1を意味しますC_sを、残差グラフの拡張パスを使用してsから到達できるすべてのノードのセットとします。 C_tを残りのアークとすると、 tはC_tに含まれている必要があります（私たちの仮定による）。 次に、 C_tからC_sに交差する円弧は、 a.datum.capacity = a.datum.flowまたはa.datum.flow = 0.0のいずれかの円弧aのみを含むstカットを形成します。 そうでなければ、残りの容量がC_sに残っているアークによって接続されたノードは、 sからそのようなノードへの拡張パスがあるため、セットC_sに含まれます。 stカットを横切るフローは、 stカットの容量（ C_tからC_sへのアークのフローは容量に等しいため）およびstフローの値（命題Eによる）に等しくなります。

最大フロー、最小カット定理のこのステートメントは、ネットワークのフローからの以前のステートメントを意味します。

系（完全性プロパティ）：容量が整数の場合、整数値の最大フローが存在し、Ford-Fulkersonアルゴリズムがそれを検出します。

証明：各拡張パスは、フローを正の整数、「プッシュ」アークの未使用容量の最小値、および「プル」アークのフローを増加させます。これらはすべて常に正の整数です。

これは、 CLRSからのフォード-ファルカーソン法の説明を正当化します。 その方法は、拡張パスを見つけ続け、最新のmaxFlowSolutionにaugmentを適用して、最新の最大フローソリューションが最適であることを意味する拡張パスがなくなるまで、より良いソリューションを考え出すことです。

フォード・ファルカーソンからエドモンズ・カープへ

最大フロー問題の解決に関する残りの質問は次のとおりです。

  1. 拡張パスはどのように構築する必要がありますか？

  2. 整数ではなく実数を使用すると、メソッドは終了しますか？

  3. 終了するのにどのくらい時間がかかりますか（終了する場合）？

Edmonds-Karpアルゴリズムは、各拡張パスが残差グラフの幅優先探索（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に答えるために、SedgewickとWayneからの別の証明を言い換えます。命題NノードとAアークを使用するEdmonds-Karpアルゴリズムで必要な拡張パスの数は最大でNA/2です。 証明：すべての拡張パスにはボトルネックアークがあります。これは、容量がいっぱいになる「プッシュ」アークまたはフローが0になる「プル」アークのいずれかに対応するため、残差グラフから削除されるアークです。アークはボトルネックアークになり、それを通る拡張パスの長さは2倍に増加する必要があります。これは、パスが存在するため、パス内の各ノードが1回だけ表示されるか、まったく表示されない可能性があるためです。最短パスから最長パスへと探索されます。つまり、特定のボトルネックノードを通過する次のパスが少なくとももう1つのノードにアクセスする必要があります。つまり、ノードに到達する前に、パス上に2つのアークが追加されます。 拡張パスの長さは最大でNであるため、各アークは最大でN/2の拡張パス上にあり、拡張パスの総数は最大でNA/2です。

Edmonds-KarpアルゴリズムはO(NA^2)で実行されます。 アルゴリズム中に最大でNA/2パスが探索され、 BFSを使用して各パスを探索することがN+Aである場合、積の最も重要な項、したがって漸近的複雑さはO(NA^2)です。

mfpを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として扱われるようになりました。 このコードでは、 maxFlowProblemStateをmfpsとします。

 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で影響を受けるノードはG! 。

2部グラフ

有向グラフGがあるとすると、 Gのノードを2つのセット（ G.setOfNodesとpart_2 ）にpart_1でき、 G.setOfArcsのアークaについて、 a.fromNodeのpart_1とa.toNodeのpart_1 。 また、 a.fromNodeのpart_2とa.toNodeのpart_2を真にすることはできません。

言い換えると、すべてのアークが一方のセットのノードをもう一方のセットのノードに接続する必要があるように、Gを2セットのノードに分割できる場合、 Gは2部グラフです。

2部グラフのテスト

有向グラフGがあるとし、それが2部グラフであるかどうかをテストします。 これは、 O(|G.setOfNodes|+|G.setOfArcs|)で、グラフを2色に貪欲に色付けすることで実行できます。

まず、新しい有向グラフHを生成する必要があります。 このグラフには、 Gと同じノードのセットがありますが、 Gよりも多くのアークがあります。 Gのすべてのアークaは、 Hに2つのアークを作成します。 最初のアークはaと同じになり、2番目のアークは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は、マッチングにおける任意の2つのアークaおよびbの場合のmatchingです： len(frozenset( {a.fromNode} ).union( {a.toNode} ).union( {b.fromNode} ).union( {b.toNode} )) == 4 。 つまり、一致する2つのアークがノードを共有することはありません。

マッチングmatchingは、 len(matching) < len(alt_matching)のような他のマッチングalt_matchingがGにない場合の最大マッチングです。 つまり、マッチングの定義をまだ満たすG.setOfArcsのアークの最大セットである場合、 matchingは最大マッチングです（マッチングにまだ含まれていないアークを追加すると、マッチングの定義が壊れます）。

G.setOfArcsのノードnごとに、 a.fromNode == n or a.toNode == nのmatchingにアークaが存在する場合、最大マッチングmatchingは完全マッチングです。

最大二部マッチング

最大二部マッチングは、二部である有向グラフGの最大マッチングです。

Gが2部であるとすると、最大2部マッチングを見つける問題は、エドモンズ・カープアルゴリズムで解決可能な最大フロー問題に変換でき、最大2部マッチングを最大フロー問題の解から復元できます。

bipartitionをGのbipartitionとします。

これを行うには、いくつかの新しいノード（ H.setOfNodes ）といくつかの新しいアーク（ H.setOfArcs ）を使用して新しい有向グラフ（ H ）を生成する必要があります。 H.setOfNodesには、 G.setOfNodes内のすべてのノードと、さらに2つのノードs （ソースノード）とt （ターミナルノード）が含まれます。

H.setOfArcsには、 G.setOfArcsごとに1つのアークが含まれます。 アークaがG.setOfArcsにあり、 a.fromNodeがbipartition.firstPartにあり、 a.toNodeがbipartition.secondPartにある場合は、 Hにaを含めますFlowArcDatum(1,0)を追加します）。

a.fromNodeがbipartition.secondPartにあり、 a.toNodeがbipartition.firstPartにある場合は、H.setOfArcsにArc(a.toNode,a.fromNode,FlowArcDatum(1,0))をH.setOfArcsます。

2部グラフの定義により、両方のノードが同じパーティションにあるノードをアークが接続しないことが保証されます。 H.setOfArcsには、ノードsからbipartition.firstPartの各ノードへのアークも含まれています。 最後に、 H.setOfArcsには、ノードtへのbipartition.secondPartの各ノードのアークが含まれています。 a.datum.capacity = 1 （ H.setOfArcs内のすべてa ）。

まず、 G.setOfNodesのノードが2つの互いに素なセット（ G.setOfArcs part2 part1が1つのセットから同じセットに向けられないようにします（ Gは2部であるため、この分割が可能です）。 次に、part1からpart2 part2向けられたpart1のすべてのアークをG.setOfArcsに追加しH.setOfArcs 。 次に、単一のソースノードsと単一のターミナルノードtを作成し、さらにいくつかのアークを作成します

次に、 maxFlowProblemStateを作成します。

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

最小限のノードカバー

有向グラフGのノードカバーは、G.setOfNodesからのノード（ cover ）のセットであり、 G.setOfNodesの任意のアークa G.setOfArcs 、これは真でなければなりません： (a.fromNode in cover) or (a.toNode in cover) 。

最小ノードカバーは、依然としてノードカバーであるグラフ内の可能な最小のノードセットです。 Konigの定理は、 2部グラフでは、そのグラフの最大マッチングのサイズが最小ノードカバーのサイズに等しいことを示しており、ノードカバーが最大マッチングからどのように回復できるかを示しています。

二分割二bipartitionと最大一致matchingがあると仮定します。 新しい有向グラフH 、 H.setOfNodes=G.setOfNodesを定義しH.setOfArcsのアークは、2つのセットの和集合です。

最初のセットはmatchingアークaですがa.fromNode in bipartition.firstPartのa.toNode in bipartition.secondPartのa.toNodeの場合、作成されたアークでa.fromNodeとa.toNodeが交換され、そのようなアークにa.datum.inMatching=Trueが与えられます。 a.datum.inMatching=True属性は、それらが一致するアークから派生したことを示します。

2番目のセットは、 matchingしaないアークですa.fromNode in bipartition.secondPartのa.toNode in bipartition.firstPartのa.toNodeの場合、作成されたアークでa.fromNodeとa.toNodeが交換されます（このようなアークa.datum.inMatching=False属性）。

次に、 bipartition.firstPartの各ノードnから開始して深さ優先探索（DFS）を実行します。これは、 matchingアークaに対してn n == a.fromNodeでもn == a.toNodes a.toNodesでもありません。 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

線形割り当て問題

線形割り当て問題は、重み付けされた2部グラフで最大の重みの一致を見つけることで構成されます。

この投稿の冒頭にあるような問題は、線形割り当て問題として表すことができます。 一連のワーカー、一連のタスク、および1つのタスクへの1人のワーカーの割り当ての収益性を示す関数が与えられた場合、行うすべての割り当ての合計を最大化する必要があります。 これは線形割り当ての問題です。

タスクとワーカーの数が等しいと仮定しますが、この仮定は簡単に削除できることを示します。 実装では、アークaの属性a.datum.weightを使用してアークウェイトを表します。

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

Kuhn-Munkresアルゴリズム

Kuhn-Munkresアルゴリズムは、線形割り当て問題を解決します。 適切な実装にはO(N^{4})時間がかかる場合があります（ここで、 Nは問題を表す有向グラフ内のノードの数です）。 説明が簡単な実装では、 O(N^{5}) （ DiGraphsを再生成するバージョンの場合）とO(N^{4}) （ DiGraphsを維持するバージョンの場合）を使用します。 これは、 Edmonds-Karpアルゴリズムの2つの異なる実装に似ています。

この説明では、完全2部グラフ（ノードの半分が2部グラフの一部にあり、残りの半分が2部グラフにあるグラフ）のみを使用しています。 労働者の場合、タスクの動機付けとは、タスクと同じ数の労働者がいることを意味します。

これは重大な状態のように見えますが（これらのセットが等しくない場合はどうなりますか！）、この問題を修正するのは簡単です。 これを行う方法については、前のセクションで説明します。

ここで説明するアルゴリズムのバージョンは、ゼロウェイトアークの便利な概念を使用しています。 残念ながら、この概念は、最小化を解決する場合にのみ意味があります（ワーカーとタスクの割り当ての利益を最大化するのではなく、そのような割り当てのコストを最小化する場合）。

幸い、各アークa重みをMa.datum.weightに設定することで、最大線形割り当て問題を最小線形割り当て問題に簡単に変換できます。ここで、 M=max({a.datum.weight for a in G.setOfArcs}) 。 元の最大化問題の解決策は、アークの重みが変更された後の解決策最小化問題と同じになります。 したがって、残りの部分については、この変更を行うと想定します。

Kuhn-Munkresアルゴリズムは、重み付けされていない2部グラフの最大マッチングのシーケンスによって、重み付けされた2部グラフの最小のウェイトマッチングを解決します。 線形割り当て問題の有向グラフ表現で完全一致が見つかり、一致するすべてのアークの重みがゼロの場合、この一致は有向グラフのすべてのノードが可能な限り低いコストのアークと一致します（以前の定義に基づいて、コストを0より低くすることはできません）。

他のアークをマッチングに追加することはできません（すべてのノードがすでにマッチングされているため）。また、可能な置換アークは少なくとも同じくらい大きな重み値を持つため、アークをマッチングから削除しないでください。

ゼロウェイトアークのみを含むGのサブグラフの最大一致が見つかり、それが完全一致ではない場合、完全解はありません（一致が完全ではないため）。 ただし、新しい0の重みのアークが表示され、 Hの最適解がGの最適解と同じになるように、 G.setOfArcsのアークの重みを変更することにより、新しい有向グラフHを作成できます。 各反復で少なくとも1つのゼロウェイトアークが生成されることを保証するため、 | G.setOfNodes | ^ {2} = N^{2}以下の反復で完全一致に到達することを保証します。

bipartition bipartitionで、 bipartition.firstPartにワーカーを表すノードが含まれ、 bipartition.secondPartがタスクを表すノードを表すとします。

アルゴリズムは、新しい有向グラフHを生成することから始まります。 H.setOfNodes = G.setOfNodes 。 Hの一部のアークは、 bipartition.firstPartのノードnから生成されます。 そのような各ノードnは、 bipartition.G.setOfArcsの各アークaに対してH.setOfArcsにアークbを生成します。ここで、 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のより多くのアークは、 bipartition.secondPartのノードnから生成されます。 そのような各ノードnは、 bipartition.G.setOfArcsの各アークaに対してH.setOfArcsにアークbを生成します。ここで、 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：次に、 Hからのゼロウェイトアークと、それらのアークに入射するノードのみで構成される新しい有向グラフKを作成します。 Kのノードで2分割を形成し、 solve_mbm( bipartition ) bipartition使用して、 Kで最大一致（ matching ）を取得します。 matchingがHでの完全マッチングである場合（ matchingのアークはH.setOfNodesのすべてのノードに入射します）、 matchingは線形割り当て問題の最適なソリューションです。

それ以外の場合、 matchingが完全でない場合は、 node_cover = get_min_node_cover(matching, bipartition(K))を使用して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を生成するためです。 Edmonds-Karpの前の2つの実装と同様に、このアルゴリズムを変更して、マッチングを追跡し、各反復にインテリジェントに適応させることができます。 これが行われると、複雑さはO(N^{4})になります。 このアルゴリズムのより高度でより新しいバージョン（いくつかのより高度なデータ構造が必要）は、 O(N^{3})で実行できます。 上記のより単純な実装とより高度な実装の両方の詳細は、このブログ投稿の動機となったこの投稿にあります。

アークウェイトに対する操作はいずれも、アルゴリズムによって返される最終的な割り当てを変更しません。 理由は次のとおりです。入力グラフは常に完全2部グラフであるため、ソリューションは、これら2つのノード間のアークを介して、1つのパーティションの各ノードを2番目のパーティションの別のノードにマップする必要があります。 アークの重みに対して実行される操作は、特定のノードに入射するアークの順序（重みの順序）を変更しないことに注意してください。

したがって、アルゴリズムが完全完全2部一致で終了すると、各ノードにゼロウェイトアークが割り当てられます。これは、そのノードからのアークの相対的な順序がアルゴリズム中に変更されていないためであり、ゼロウェイトアークが最も安価なアークであり、完全完全2部マッチングは、ノードごとにそのようなアークが1つ存在することを保証します。 これは、生成された解が、アークの重みを変更せずに、元の線形割り当て問題の解と実際に同じであることを意味します。

不均衡な割り当て

説明したように、完全2部グラフ（ノードの半分が2部グラフの一部にあり、残りの半分が2部グラフにあるグラフ）でのみ動作するため、アルゴリズムはかなり制限されているようです。 ワーカーでは、タスクの動機付けは、タスクと同じ数のワーカーがいることを意味します（かなり制限されているようです）。

ただし、この制限を取り除く簡単な変換があります。 タスクよりもワーカーが少ないと仮定して、ダミーワーカーをいくつか追加します（結果のグラフを完全2部グラフにするのに十分です）。 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:

Clean the Bathroom Sweep the Floor Wash the Windows
アリス$ 2 $ 3 $ 3
ボブ$ 3 $ 2 $ 3
チャーリー$ 3 $ 3 $ 2
ダイアン9ドル9ドル$ 1

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.

Clean the Bathroom Sweep the Floor Wash the Windows 何もしない
アリス$ 2 $ 3 $ 3 $ 0
ボブ$ 3 $ 2 $ 3 $ 0
チャーリー$ 3 $ 3 $ 2 $ 0
ダイアン9ドル9ドル$ 1 $ 0

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を使用したグラフデータサイエンス