최대 흐름과 선형 할당 문제

여기 문제가 있습니다. 귀하의 비즈니스는 계약을 이행할 계약자를 지정합니다. 명단을 살펴보고 1개월 계약에 사용할 수 있는 계약자를 결정하고 사용 가능한 계약을 살펴보고 그 중 어떤 계약자가 1개월짜리 작업인지 확인합니다. 각 계약자가 각 계약을 얼마나 효과적으로 이행할 수 있는지 알고 있는 경우 해당 월의 전체 효과를 최대화하기 위해 계약자를 어떻게 지정합니까?

이것은 할당 문제의 예이며 문제는 고전적인 헝가리 알고리즘으로 풀 수 있습니다.

헝가리 알고리즘(Kuhn-Munkres 알고리즘이라고도 함)은 가중 이분 그래프에서 가중치 일치를 최대화하는 다항식 시간 알고리즘입니다. 여기에서 계약자와 계약은 이분 그래프로 모델링할 수 있으며 그 효율성은 계약자와 계약 노드 사이의 가장자리 가중치로 나타납니다.

이 기사에서는 Edmonds-Karp 알고리즘을 사용하여 선형 할당 문제를 해결하는 헝가리 알고리즘 구현에 대해 학습합니다. 또한 Edmonds-Karp 알고리즘이 Ford-Fulkerson 방법을 약간 수정한 방법과 이 수정이 얼마나 중요한지 배우게 됩니다.

최대 흐름 문제

최대 흐름 문제 자체는 비공식적으로 단일 소스에서 단일 터미널로 파이프 네트워크를 통해 일부 유체 또는 가스를 이동하는 문제로 설명할 수 있습니다. 이것은 네트워크의 압력이 유체 또는 가스가 파이프 또는 파이프 피팅의 길이에 관계없이 머무를 수 없도록 하기에 충분하다는 가정 하에 수행됩니다(다양한 길이의 파이프가 만나는 장소).

그래프를 약간 변경하면 할당 문제가 최대 흐름 문제로 바뀔 수 있습니다.

예선

이러한 문제를 해결하는 데 필요한 아이디어는 많은 수학과 공학 분야에서 발생하며 종종 유사한 개념이 다른 이름으로 알려져 있고 다른 방식으로 표현됩니다(예: 인접 행렬 및 인접 목록). 이러한 아이디어는 매우 난해하기 때문에 주어진 설정에 대해 이러한 개념을 얼마나 일반적으로 정의할지에 대한 선택이 이루어집니다.

이 기사는 약간의 입문 세트 이론 이상의 사전 지식을 가정하지 않습니다.

이 게시물의 구현은 문제를 방향 그래프(digraph)로 나타냅니다.

다이그래프

digraph 에는 setOfNodes 및 setOfArcs 의 두 가지 속성이 있습니다. 이 두 속성은 모두 집합입니다(순서 없는 컬렉션). 이 게시물의 코드 블록에서는 실제로 Python의 frozenset을 사용하고 있지만 그 세부 사항은 특별히 중요하지 않습니다.

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

(참고: 이 코드와 이 기사의 다른 모든 코드는 Python 3.6으로 작성되었습니다.)

노드

노드 n 은 두 가지 속성으로 구성됩니다.

• n.uid : 고유 식별자입니다.

  이는 임의의 두 노드 x 및 y 에 대해 ,

 x.uid != y.uid

• n.datum : 모든 데이터 객체를 나타냅니다.

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

호

호 a 세 가지 속성으로 구성됩니다.

• a.fromNode : 위에서 정의한 노드 입니다.

• a.toNode : 위에서 정의한 노드 입니다.

• a.datum : 모든 데이터 개체를 나타냅니다.

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

digraph 의 호 세트는 digraph 의 노드 에 대한 이진 관계를 나타냅니다. arc a 의 존재는 a.fromNode 와 a.toNode 사이에 관계가 존재함을 의미합니다.

유향 그래프(무향 그래프와 반대)에서 a.fromNode 와 a.toNode 사이의 관계가 존재한다고 해서 a.toNode 와 a.fromNode 사이에 유사한 관계가 존재한다는 의미는 아닙니다 .

이는 무방향 그래프에서 표현되는 관계가 반드시 대칭인 것은 아니기 때문입니다.

다이그래프

노드 와 호 를 사용하여 digraph 를 정의할 수 있지만 편의상 아래 알고리즘에서는 digraph 를 사전으로 사용하여 표현합니다.

다음은 위의 그래프 표현을 이와 유사한 사전 표현으로 변환할 수 있는 방법입니다.

 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_as_dict 이를 참조합니다.

때로는 uid (고유 식별자)를 통해 digraph G 에서 노드 를 가져오는 것이 도움이 됩니다.

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

그래프를 정의할 때 사람들은 때때로 노드 와 꼭짓점이라는 용어를 사용하여 동일한 개념을 나타냅니다. 호 와 모서리라는 용어도 마찬가지입니다.

Python에서 널리 사용되는 두 가지 그래프 표현은 사전을 사용하는 것과 객체를 사용하여 그래프를 표현하는 것입니다. 이 게시물의 표현은 일반적으로 사용되는 이 두 표현 사이의 어딘가에 있습니다.

이것은 내 이중 그래프 표현입니다. 비슷한게 많지만 이건 제꺼에요.

산책로와 길

a가 마지막을 제외하고 S_Arcs 에서 임의의 호 이고 b 가 시퀀스에서 a 를 따르는 a 노드 n = a.fromNode S_Arcs 있어야 하도록 S_Arcs를 이중 그래프 G 에 있는 호의 유한 시퀀스(순서화된 컬렉션)라고 가정합니다. G.setOfNodes a.toNode = b.fromNode 와 같은 G.setOfNode .

S_Arcs 의 첫 번째 호 에서 시작하여 S_Arcs 의 마지막 호 까지 계속 S_Arcs 의 연속적인 두 호 사이에 위에서 정의한 대로 모든 노드 n 을 만나는 순서대로 수집 S_Arcs . 이 작업 동안 수집된 노드 의 정렬된 컬렉션에 레이블을 지정합니다. S_{Nodes} .

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

• 노드 가 시퀀스 S_Nodes 에서 두 번 이상 나타나면 S_Arcs 를 digraph G 에서 Walk로 호출합니다.

• 그렇지 않으면, 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 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

컷 및 세인트 컷

연결된 digraph G 의 컷 cut 은 G 의 노드 집합 G.setOfArcs 를 분할하는 G.setOfNodes 의 호 부분 집합입니다. G.setOfNodes 의 모든 노드 n 이 연결되고 G.setOfArcs 에 n = a.fromNode 또는 n = a.toNode 이지만 a.fromNode != a.toNode G.setOfArcs 같은 하나 이상의 호 a 가 있으면 G 가 연결됩니다.

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

위의 정의는 arc 의 하위 집합을 참조하지만 G.setOfNodes 노드 의 파티션을 정의할 수도 있습니다.

predecessors_of _of 및 successors_of _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

cut 을 digraph 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 은 다음과 같은 경우 이중 그래프 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})

Digraph G 는 이제 흐름 네트워크 를 나타냅니다.

G 의 흐름 은 G 의 모든 호 a 에 대한 a.flow 을 나타냅니다.

실현 가능한 흐름

이중 그래프 G 가 흐름 네트워크 를 나타냅니다.

G 로 표시되는 흐름 네트워크 는 다음과 같은 경우 실행 가능한 흐름 을 갖습니다.

1. 소스 노드 와 터미널 노드 를 제외한 G.setOfNodes 의 모든 노드 n 에 대해: n.datum.flowIn = n.datum.flowOut .

2. G.setOfNodes의 모든 호 a 에 G.setOfNodes : a.datum.capacity <= a.datum.flow .

조건 1을 보존 제약 조건이라고 합니다.

조건 2를 용량 제약 조건이라고 합니다.

절단 용량

이중 그래프 G 로 표시되는 흐름 네트워크 의 소스 노드 s 와 터미널 노드 t 가 있는 st 절단 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)

흐름을 없애기

나는 digraph G 를 취하고 G.setOfNodes의 모든 노드 와 G.setOfNodes 의 모든 호 에서 모든 흐름 데이터를 제거한 결과인 digraph 를 참조하고 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)

최대 유량 문제

digraph 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 에 대한 최적의 솔루션이기도 합니다.

즉, 실현 가능한 최대 흐름 솔루션 은 다음과 같은 digraph 로 나타낼 수 있습니다.

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 Flow Value 라고 합니다.

허락하다:

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

이것은 maxFlowProblem 가 mfps 의 후속 상태 라는 것을 의미합니다. 즉, maxFlowProblem.setOfArcs의 a.flow 값이 a.flow 의 arc a 에 a maxFlowProblem.setOfArcs 와 다를 수 있다는 점을 제외하고는 mfps 가 a.flow 과 maxFlowProblem 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 와 함께 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 에 대한 솔루션이 digraph H 로 표시된 흐름 네트워크 로 표현되도록 합니다.

maxFlowProblem.G 을 minStCut 로 표시되는 흐름 네트워크 의 최소 용량 컷 이라고 합니다.

최대 흐름 문제 에서 흐름은 단일 소스 노드 에서 시작하여 단일 터미널 노드 에서 종료되고 용량 제약 및 보존 제약 으로 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의 Flows in Networks 책에서 최대 흐름, 최소 절단 정리 (정리 5.1)에 대한 설명은 다음과 같습니다.

모든 네트워크에 대해 s 에서 t s t 하는 모든 절단 s 최소 절단 용량과 같습니다.

이 게시물의 정의를 사용하면 다음과 같이 번역됩니다.

이중 그래프 H 로 표시되는 흐름 네트워크 로 표시되는 maxFlowProblem 에 대한 솔루션은 다음과 같은 경우에 최적입니다.

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

나는 이 정리의 증명을 좋아하고 Wikipedia에는 ​​또 다른 증명이 있습니다.

최대 유량, 최소 절단 정리 는 Ford-Fulkerson 방법 의 정확성과 완전성을 증명하는 데 사용됩니다.

나는 또한 경로를 보강 한 후 섹션에서 정리의 증명을 제공할 것입니다.

포드-풀커슨 방법과 에드먼즈-카프 알고리즘

CLRS는 다음과 같이 Ford-Fulkerson 방법을 정의합니다(섹션 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 의 합계를 반환합니다. 여기서 arc a 는 a.fromNode = n 및 a.toNode = u 경우 하위 집합에 있습니다.

• agg_n_to_u_cap(n,u,G_as_dict) 는 a.fromNode = n 및 a.toNode = u 경우 arc a 가 하위 집합에 있는 G.setOfArcs 의 하위 집합에 있는 모든 호 에 대한 a.datum.flow 의 합계를 반환합니다.

간단히 말해서, 잔차 그래프 G_f 는 이중 그래프 G 에서 수행할 수 있는 특정 작업을 나타냅니다.

이중 그래프 G 로 표시되는 흐름 네트워크 의 G.setOfNodes 에 있는 노드 n,u 의 각 쌍은 G 의 잔차 그래프 G_f 에서 0, 1 또는 2개의 호 를 생성할 수 있습니다.

1. n,u 쌍은 a.fromNode = n 및 a.toNode = u 와 같이 G.setOfArcs 에 호 a 가 없으면 G_f 에 호 를 생성하지 않습니다.

2. 쌍 n,u 는 G_f.setOfArcs 에서 호 a 를 생성합니다. 여기서 a 는 n 에서 u 로의 푸시 흐름 호 레이블이 지정된 호를 나타냅니다. a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) if n_to_u_cap_sum > n_to_u_flow_sum

3. 쌍 n,u 는 G_f.setOfArcs 에서 호 a 를 생성합니다. 여기서 a 는 n_to_u_flow_sum > 0.0 경우 n a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) u 로 끌어당기는 흐름 호로 레이블된 호 를 나타냅니다.

• G_f.setOfArcs 의 각 푸시 흐름 아크 는 총 x <= n_to_u_cap_sum - n_to_u_flow_sum 흐름을 G.setOfArcs 의 하위 집합에 있는 아크 에 추가하는 작업을 나타냅니다. 여기서 아크 a 는 a.fromNode = n 및 a.toNode = u 인 경우 하위 집합에 있습니다. a.toNode = u .

• G_f.setOfArcs 의 각 끌어당기는 흐름 호 는 총 x <= n_to_u_flow_sum 흐름을 G.setOfArcs 하위 집합의 호로 빼는 작업을 나타냅니다. 여기서 arc 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 경로 AugmentingPath는 find_node_by_uid(maxFlowProblem.sourceNode,G_f) 에서 find_node_by_uid(maxFlowProblem.terminalNode,G_f) (maxFlowProblem.terminalNode,G_f) 까지의 모든 경로 입니다.

H 가 최적 이 get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) digraph augmentingPath 로 K 되는 또 다른 최대 흐름 솔루션을 생성하는 digraph H 로 표시되는 최대 흐름 솔루션에 AugmentingPath AugmentingPath를 적용할 수 있습니다.

방법은 다음과 같습니다.

 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) 것도 사실입니다.

이유는 다음과 같습니다. G_f 가 최대 흐름 문제 maxFlowProblem 의 잔차 그래프 augmentingPath 의 이중 그래프 표현에 존재하려면 maxFlowProblem 의 마지막 호 a 는 '푸시' 호 여야 하고 augmentingPath a.toNode == maxFlowProblem.terminalNode . 증가 경로 는 증가 경로인 최대 흐름 문제 의 터미널 노드 에서 종료되는 경로 로 정의됩니다. 잔차 그래프의 정의에서, 그 잔차 그래프 의 증대 경로 에 있는 마지막 호 는 '푸시' 호 여야 합니다. 왜냐하면 증대 경로 의 모든 '당기기' 호 b 에는 b.toNode == maxFlowProblem.terminalNode path 정의에서 b.toNode == maxFlowProblem.terminalNode 및 b.fromNode != maxFlowProblem.terminalNode . 또한 path 의 정의를 보면 augment 방식으로 터미널 노드 가 한 번만 수정됨을 알 수 있습니다. 따라서 AugmentingPath 의 마지막 호 는 maxFlowProblem.terminalNode.flowIn augment 수정을 일으키는 호 여야 augment 때문에 Augment는 maxFlowProblem.terminalNode.flowIn 을 정확히 한 번 수정하고 maxFlowProblem.terminalNode.flowIn 의 값을 augmentingPath 시킵니다. 'push' arc 에 적용되는 maxFlowProblem.terminalNode.flowIn augment 증가할 수만 있고 감소할 수는 없습니다.

Sedgewick과 Wayne의 몇 가지 증거

Robert Sedgewich와 Kevin Wayne의 책 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 에 적용됩니다. 거기에서 s-파티션( get_first_part(stCut.cut, G) )에서 t-파티션 (get_second_part(stCut.cut, G)) 으로 일부 노드 n 을 이동하려는 경우 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-파티션으로 직접 향하는 흐름 부분은 이 흐름이 이제 새 t-파티션 내부에 있고 stcut_flow 로 계산되지 않기 때문에 뺍니다. n 에서 s-파티션의 노드 로 향하는 흐름의 일부는 stcut_flow 에서도 빼야 합니다. n 이 t-파티션으로 이동된 후 이러한 흐름은 t-파티션에서 s-파티션으로 보내집니다. 이러한 흐름은 stcut_flow 파티션으로의 유입을 제거하고 이러한 흐름과 s-파티션에서 t-파티션으로의 유출(여기서 모든 흐름은 st는 끝나야 함) 같은 양만큼 줄여야 합니다. 노드 n 이 프로세스 이전에 평형 상태에 있었기 때문에 업데이트는 뺀 값과 동일한 값을 새 stcut_flow 값에 추가하여 업데이트 후에 명제 E 를 참으로 남깁니다. 그러면 명제 E 의 유효성은 t-분할의 크기에 대한 귀납법에서 나옵니다.

다음은 명제 E 가 성립하는 덜 분명한 경우를 시각화하는 데 도움이 되는 몇 가지 예시 적인 흐름 네트워크입니다 . 이미지에서 빨간색 영역은 s-파티션을 나타내고 파란색 영역은 t-파티션을 나타내며 녹색 호 는 st 컷 을 나타냅니다. 두 번째 이미지에서 노드 A와 노드 B 사이의 흐름은 증가하지만 터미널 노드 t로의 흐름은 변경되지 않습니다.:

결과: 어떤 st cut flow 값도 st cut 의 용량을 초과할 수 없습니다.

명제 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_s 에서 C_s 로 교차하는 호는 C_t a.datum.capacity = a.datum.flow 또는 a.datum.flow = 0.0 인 호 a 만 포함하는 st 컷 을 형성합니다. 그렇지 않은 경우 C_s 에 대한 잔여 용량이 남아 있는 호로 연결된 노드 는 s 에서 그러한 노드 로의 증가 경로 가 있기 때문에 집합 C_s 에 있습니다. st 컷 을 가로지르는 흐름은 st 컷의 용량( C_s 에서 C_s 까지의 호가 용량과 동일한 흐름을 C_t 때문에) 및 st 흐름 의 값( 명제 E 에 의해)과 같습니다.

max flow, min cut theorem 에 대한 이 진술은 Flows in Networks의 이전 진술을 의미합니다.

추론(적분성 속성): 용량이 정수일 때 정수값 최대 흐름이 존재하고 Ford-Fulkerson 알고리즘이 이를 찾습니다.

증명: 각 증가 경로 는 양의 정수만큼 흐름을 증가시키며, '밀기' 호의 사용되지 않은 용량의 최소값과 '당기기' 호의 흐름은 모두 항상 양의 정수입니다.

이것은 CLRS 의 Ford-Fulkerson 방법 설명을 정당화합니다. 방법은 더 이상 증가 경로 가 없을 때까지 증가 경로 를 찾고 최신 maxFlowSolution 에 augment 를 적용하여 더 나은 솔루션을 제공하여 최신 최대 흐름 솔루션 이 최적 임을 의미합니다.

포드-풀커슨에서 에드먼즈-카프까지

최대 흐름 문제 해결에 관한 나머지 질문은 다음과 같습니다.

1. 경로를 보강 하려면 어떻게 해야 합니까?

2. 정수가 아닌 실수를 사용하면 메서드가 종료됩니까?

3. 종료하는 데 얼마나 걸립니까(그렇다면)?

Edmonds-Karp 알고리즘 은 각 증가 경로 가 잔차 그래프 의 BFS(Breadth First Search )에 의해 구성됨을 지정합니다. 위의 포인트 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: Proposition G 의 또 다른 증명을 바꿔 말하겠습니다. N 노드 와 A 호가 있는 Edmonds-Karp 알고리즘에 필요한 증대 경로 의 수는 최대 NA/2 입니다. 증명: 모든 증강 경로 에는 병목 호가 있습니다. 이는 용량까지 채워지는 '밀기' 호 또는 흐름이 0이 되는 '당기기' 호 에 해당하기 때문에 잔차 그래프 에서 삭제되는 호 입니다. 호가 병목 호가 되며 이를 통과하는 모든 증가 경로 의 길이 는 2배 증가해야 합니다. 이는 경로 의 각 노드 가 경로 정의에서 한 번만 나타날 수도 있고 전혀 나타나지 않을 수도 있기 때문입니다. 최단 경로 에서 최장 경로로 탐색한다는 것은 특정 병목 노드 를 통과하는 다음 경로가 최소 하나 이상의 노드 를 방문해야 함을 의미합니다. 이는 노드 에 도달하기 전에 경로에 추가 2개의 호 를 의미합니다. 증가 경로 의 길이가 최대 N 이기 때문에 각 호 는 최대 N/2 증가 경로 에 있을 수 있으며 총 증가 경로 수는 최대 NA/2 입니다.

Edmonds-Karp 알고리즘 은 O(NA^2) 에서 실행됩니다. 알고리즘 동안 최대 NA/2 경로 가 탐색되고 BFS 로 각 경로 탐색이 N+A 이면 곱의 가장 중요한 항과 점근적 복잡성은 O(NA^2) 입니다.

mfp 를 maxFlowProblemState 로 설정합니다.

 def edmonds_karp(mfp): sid, tid = mfp.sourceNodeUid, mfp.terminalNodeUid no_more_paths = False loop_count = 0 while(not no_more_paths): residual_digraph = get_residual_graph_of(mfp.G) try: asource = find_node_by_uid(mfp.sourceNodeUid, residual_digraph) aterm = find_node_by_uid(mfp.terminalNodeUid, residual_digraph) apath = bfs(asource, aterm, residual_digraph) paint_mfp_path(mfp, loop_count, apath) G = augment(apath, mfp.G) s = find_node_by_uid(sid, G) t = find_node_by_uid(tid, G) mfp = MaxFlowProblemState(G, s.uid, t.uid, mfp.maxFlowProblemStateUid) loop_count += 1 except StopIteration as e: no_more_paths = True return mfp

위의 버전은 (알고리즘이 발전함에 따라 기존 이중 그래프 를 수정하는 것보다) 매번 새로운 최대 흐름 솔루션 과 새로운 잔차 그래프 를 구성하기 때문에 O(NA^2) 보다 비효율적이고 복잡도가 더 낮습니다. 진정한 O(NA^2) 솔루션을 얻으려면 알고리즘은 최대 흐름 문제 상태 를 나타내는 이중 그래프와 관련 잔차 그래프 를 모두 유지해야 합니다. 따라서 알고리즘은 불필요하게 호 와 노드 를 반복하는 것을 피하고 필요한 경우에만 잔차 그래프 에서 해당 값과 관련 값을 업데이트해야 합니다.

더 빠른 Edmonds Karp 알고리즘을 작성하기 위해 위에서 몇 가지 코드를 다시 작성했습니다. 새로운 digraph 를 생성한 코드를 살펴보는 것이 진행 상황을 이해하는 데 도움이 되었기를 바랍니다. 빠른 알고리즘에서는 자세히 설명하고 싶지 않은 몇 가지 새로운 트릭과 Python 데이터 구조를 사용합니다. 나는 a.fromNode 와 a.toNode 가 이제 node 에 대한 문자열과 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이 있는 Arc가 Augmenting Path의 일부일 수 있기 때문에 Flown Network의 DiGraph에 영향을 받는 노드는 G! .

이분 그래프

이중 그래프 G 가 있다고 가정하고 G.setOfNodes 의 노드 를 두 세트( part_1 및 part_2 )로 분할하여 G.setOfArcs의 모든 호 a 에 대해 a.fromNode 의 G.setOfArcs 가 참일 수 없는 경우 G 는 part_1 입니다. a.toNode in part_1 . part_2 의 a.toNode 와 part_2 의 a.fromNode 도 사실일 수 없습니다 .

다시 말해서 G 는 모든 호가 한 세트의 노드 를 다른 세트의 노드 에 연결해야 하는 두 개의 노드 세트로 분할될 수 있는 경우 이분법 입니다.

이분법 테스트

이중 그래프 G 가 있다고 가정하고 그것이 이분법 인지 테스트하고 싶습니다. O(|G.setOfNodes|+|G.setOfArcs|) 에서 그래프를 두 가지 색상으로 탐욕스럽게 색칠하여 이를 수행할 수 있습니다.

먼저 새로운 digraph H 를 생성해야 합니다. 이 그래프는 G 와 동일한 노드 집합을 가지지만 G 보다 더 많은 호 를 갖습니다. G 의 모든 호 a 는 H 에 2개의 호 를 생성합니다. 첫 번째 호 는 와 동일하고 두 번째 호 는 a 의 방향을 반대로 a ( b = Arc(a.toNode,a.fromNode,a.datum) ).

 Bipartition = coll.namedtuple('Bipartition',['firstPart', 'secondPart', 'G']) def bipartition(G): nodes = frozenset(G.setOfNodes arcs = frozenset(G.setOfArcs) arcs = arcs.union( frozenset( {Arc(a.toNode,a.fromNode,a.datum) for a in G.setOfArcs} ) ) H = DiGraph(nodes, arcs) H_as_dict = digraph_to_dict(H) color = dict([]) some_node = next(iter(H.setOfNodes)) deq = coll.deque([some_node]) color[some_node] = -1 while len(deq) > 0: curr = deq.popleft() for a in H_as_dict.get(curr): if (a.toNode not in color): color[a.toNode] = -1*color[curr] deq.extend([a.toNode]) elif(color[curr] == color[a.toNode]): print(curr,a.toNode) raise Exception('Not Bipartite.') firstPart = frozenset( {n for n in color if color[n] == -1 } ) secondPart = frozenset( {n for n in color if color[n] == 1 } ) if( firstPart.union(secondPart) != G.setOfNodes ): raise Exception('Not Bipartite.') return Bipartition(firstPart, secondPart, G)

일치 및 최대 일치

이중 그래프 G 가 있고 matching 가 G.setOfArcs 에서 G.setOfArcs 호의 하위 집합이라고 가정합니다. len(frozenset( { matching } ) .union a { matching } ) b len(frozenset( {a.fromNode} ).union( {a.toNode} ).union( {b.fromNode} ).union( {b.toNode} )) == 4 . 즉, 일치하는 두 개의 호가 노드 를 공유하지 않습니다.

Matching matching 은 len(matching) < len(alt_matching) 과 같이 G 에 다른 일치하는 alt_matching 이 없는 경우 최대 일치입니다. 즉, matching 정의를 여전히 만족하는 G.setOfArcs 의 가장 큰 호 세트인 경우 일치가 최대 일치 입니다( 일치 에 아직 없는 호 를 추가하면 일치 정의가 깨집니다).

최대 일치 matching 는 G.setOfArcs 의 모든 노드 n 에 대해 a.fromNode == n or a.toNode == n 인 matching 항목에 arc a 가 존재하는 경우 완벽한 일치 입니다.

최대 2분할 매칭

최대 bipartite 매칭 은 bipartite 인 digraph G 에 대한 최대 매칭 입니다.

G 가 bipartite 인 경우 최대 bipartite 매칭 을 찾는 문제는 Edmonds-Karp 알고리즘으로 해결할 수 있는 최대 흐름 문제 로 변환될 수 있으며 최대 바이파티트 매칭 은 솔루션에서 최대 흐름 문제 로 복구될 수 있습니다.

bipartition 을 G 의 bipartition 이라고 하자.

이렇게 하려면 몇 가지 새 노드 ( H.setOfNodes )와 몇 가지 새 호 ( H.setOfArcs )가 있는 새 이중 그래프 ( H )를 생성해야 합니다. H.setOfNodes 는 G.setOfNodes 의 모든 노드 와 두 개의 추가 노드 s ( 소스 노드 ) 및 t ( 터미널 노드 )를 포함합니다.

H.setOfArcs 는 각 G.setOfArcs 에 대해 하나의 호 를 포함합니다. 호 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, H.setOfArcs Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) 을 포함하십시오.

이분 그래프의 정의는 두 노드 가 동일한 파티션에 있는 노드 를 연결하는 호가 없도록 합니다. H.setOfArcs 는 노드 s 에서 bipartition.firstPart 의 각 노드 까지의 호도 포함합니다. 마지막으로 H.setOfArcs 는 bipartition.secondPart 의 각 노드 에서 노드 t 까지의 호 를 포함합니다. a.datum.capacity = 1 H.setOfArcs a

먼저 G.setOfNodes 의 노드 를 두 개의 분리된 세트( part1 및 part2 )로 분할하여 G.setOfArcs 의 호가 한 세트에서 동일한 세트로 향하지 않도록 합니다(이 파티션은 G 가 이분법 이기 때문에 가능합니다). 다음으로 part1 에서 part2 로 H.setOfArcs 의 모든 호 를 G.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) 가 true여야 합니다.

최소 노드 커버는 여전히 노드 커버 인 그래프에서 가능한 가장 작은 노드 세트입니다. Konig의 정리에 따르면 이분 그래프에서 해당 그래프의 최대 일치 크기는 최소 노드 커버 의 크기와 같으며 노드 커버 가 최대 일치 에서 어떻게 복구될 수 있는지 제안합니다.

bipartition bipartition 과 최대 일치 matching 가 있다고 가정합니다. 새로운 digraph H , H.setOfNodes=G.setOfNodes 를 정의하고 H.setOfArcs 의 호 는 두 세트의 합집합입니다.

첫 번째 세트는 matching 호 a 이며, a.fromNode in bipartition.firstPart 의 a.fromNode 와 a.toNode in bipartition.secondPart 의 a.toNode 가 생성된 호 에서 교체되면 이러한 호 에 a.datum.inMatching=True 이 부여됩니다. a.datum.inMatching=True 속성은 일치하는 호 에서 파생되었음을 나타냅니다.

두 번째 세트는 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)을 실행합니다. 이는 n == a.fromNode 도 아니고 n == a.toNodes == a.toNodes도 아닌 matching 모든 호 a 에 대한 것입니다. 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 가 최대 일치 라는 사실로 인해 모순을 초래합니다.

이 단계를 실행하고 digraph G 가 주어졌을 때 최소 노드 커버 로 구성된 노드 세트를 반환하는 함수가 있고 최대 일치 matching 가 있다고 가정합니다.

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

선형 할당 문제

선형 할당 문제는 가중치 이분 그래프에서 최대 가중치 일치를 찾는 것으로 구성됩니다.

이 포스트의 맨 처음에 나온 것과 같은 문제는 선형 할당 문제 로 표현할 수 있습니다. 작업자 세트, 작업 세트 및 한 작업자를 한 작업에 할당하는 것의 수익성을 나타내는 함수가 주어지면 우리가 수행하는 모든 할당의 합계를 최대화하려고 합니다. 이것은 선형 할당 문제 입니다.

작업과 작업자의 수가 같다고 가정하지만 이 가정은 제거하기 쉽습니다. 구현에서 나는 호 a 에 대한 속성 a.datum.weight 를 사용하여 호 가중치 를 나타냅니다.

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

Kuhn-Munkres 알고리즘

Kuhn-Munkres 알고리즘은 선형 할당 문제 를 해결합니다. 좋은 구현은 O(N^{4}) 시간이 걸릴 수 있습니다(여기서 N 은 문제를 나타내는 이중 그래프 의 노드 수). 설명하기 쉬운 구현은 O(N^{5}) ( DiGraphs 를 재생성하는 버전의 경우) 및 O(N^{4}) for ( DiGraphs 를 유지 관리하는 버전의 경우)를 사용합니다. 이것은 Edmonds-Karp 알고리즘의 두 가지 다른 구현과 유사합니다.

이 설명에서는 완전한 이분 그래프( 노드 의 절반이 이 분할 의 한 부분에 있고 다른 절반이 두 번째 부분에 있는 그래프)로만 작업하고 있습니다. 작업자에게 작업 동기 부여는 작업만큼 많은 작업자가 있음을 의미합니다.

이것은 중요한 조건처럼 보이지만(이 세트가 같지 않으면 어떻게 될까요!) 이 문제를 쉽게 고칠 수 있습니다. 나는 마지막 섹션에서 그것을 하는 방법에 대해 이야기합니다.

여기에 설명된 알고리즘 버전은 0 가중치 호의 유용한 개념을 사용합니다. 불행히도 이 개념은 최소화 를 해결할 때만 의미가 있습니다(작업자 작업 할당의 이익을 최대화하는 대신 할당 비용을 최소화하는 경우).

다행스럽게도 각 호 가중치를 Ma.datum.weight a 설정하여 최대 선형 할당 문제 를 최소 선형 할당 문제 로 바꾸는 것은 쉽습니다. 여기서 M=max({a.datum.weight for a in G.setOfArcs}) . 원래 최대화 문제 에 대한 솔루션은 호 가중치가 변경된 후 솔루션 최소화 문제 와 동일합니다. 따라서 나머지에 대해 이 변경을 수행한다고 가정합니다.

Kuhn-Munkres 알고리즘 은 가중치가 없는 이분 그래프의 최대 일치 시퀀스에 의해 가중치 이분 그래프의 최소 가중치 일치를 해결합니다. 선형 할당 문제 의 digraph 표현에서 완벽한 일치 를 찾고 일치의 모든 호의 가중치 가 0이면 이 일치 가 digraph 의 모든 노드 가 가능한 가장 낮은 비용의 호 와 일치 합니다(이전 정의에 따라 비용은 0보다 낮을 수 없음).

(모든 노드 가 이미 일치했기 때문에) 일치 에 다른 호 를 추가할 수 없으며 가능한 대체 호가 최소한 큰 가중치 값을 갖기 때문에 일치 에서 호 를 제거해서는 안됩니다.

가중치가 0인 arc 만 포함하는 G 하위 그래프의 최대 일치 를 찾고 이것이 완벽한 일치 가 아닌 경우 완전한 솔루션이 없는 것입니다( 매칭 이 완벽 하지 않기 때문에). 그러나 새로운 0 가중치 호가 나타나고 H 의 최적 솔루션이 G 의 최적 솔루션과 동일한 방식으로 G.setOfArcs 에서 호의 가중치를 변경하여 새로운 digraph H 를 생성할 수 있습니다. 각 반복에서 최소한 하나의 0 가중치 호가 생성된다는 것을 보장하기 때문에 |G.setOfNodes|^{2}=N^{2} 이상의 반복에서 완벽한 일치 에 도달할 것임을 보장합니다.

bipartition bipartition 에서 bipartition.firstPart 는 작업자를 나타내는 노드 를 포함하고 bipartition.secondPart 는 작업을 나타내는 노드 를 나타냅니다.

알고리즘은 새로운 digraph 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 의 가중치가 0인 호 와 해당 호 에 입사하는 노드 로 구성된 새로운 이중 그래프 K 를 만듭니다. K 의 노드 에 이중 파티션을 형성한 다음 solve_mbm( bipartition ) bipartition 사용하여 K 에서 최대 일치 ( matching )를 얻습니다. matching 이 H 에서 완벽한 매칭 이라면( matching 의 호 는 H.setOfNodes 의 모든 노드 에 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

이 구현은 각 반복에서 새로운 최대 일치 matching 를 생성하기 때문에 O(N^{5}) 입니다. Edmonds-Karp 의 이전 두 가지 구현과 유사하게 이 알고리즘은 일치를 추적하고 각 반복에 지능적으로 적용하도록 수정할 수 있습니다. 이것이 완료되면 복잡성은 O(N^{4}) 이 됩니다. 이 알고리즘의 최신 버전(일부 고급 데이터 구조 필요)은 O(N^{3}) 에서 실행할 수 있습니다. 위의 더 간단한 구현과 더 고급 구현에 대한 세부 정보는 이 블로그 게시물에 동기를 부여한 이 게시물에서 찾을 수 있습니다.

호 가중치에 대한 작업은 알고리즘에서 반환된 최종 할당을 수정하지 않습니다. 이유는 다음과 같습니다. 입력 그래프는 항상 완전한 이분 그래프 이므로 솔루션은 이 두 노드 사이의 호 를 통해 한 파티션의 각 노드 를 두 번째 파티션의 다른 노드 로 매핑해야 합니다. 호 가중치에 대해 수행된 작업은 특정 노드 에 발생한 호의 순서(가중치로 정렬)를 변경하지 않습니다.

따라서 알고리즘이 완벽하게 완전한 이분 매칭 으로 종료될 때 각 노드 에는 가중치가 0인 arc 가 지정됩니다. 그 노드 의 호의 상대적 순서는 알고리즘 동안 변경되지 않고 가중치가 0인 호가 가능한 가장 저렴한 호 이기 때문입니다. 완벽한 완전한 이분법 일치 는 각 노드 에 대해 그러한 호가 하나 존재함을 보장합니다. 이것은 생성된 솔루션이 호 가중치의 수정 없이 원래 선형 할당 문제 의 솔루션과 실제로 동일함을 의미합니다.

불균형 할당

설명된 대로 완전한 이분 그래프 ( 노드 의 절반이 이 분할 의 한 부분에 있고 나머지 절반이 두 번째 부분에 있는 그래프)에서만 작동하기 때문에 알고리즘이 매우 제한적인 것 같습니다. 작업자에게 작업 동기 부여는 작업만큼 많은 작업자가 있음을 의미합니다(상당히 제한적인 것 같습니다).

그러나 이 제한을 제거하는 쉬운 변환이 있습니다. 작업보다 작업자가 적다고 가정하고 더미 작업자를 추가합니다(결과 그래프를 완전한 이분 그래프 로 만들기에 충분함). Each dummy worker has an arc directed from the worker to each of the tasks. Each such arc has weight 0 (placing it in a matching gives no added profit). After this change the graph is a complete bipartite graph which we can solve for. Any task assigned a dummy worker is not initiated.

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

A Linear Assignment Example

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

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

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

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

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

그게 다야 You now know everything you need to know about the linear assignment problem.

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

Toptal 엔지니어링 블로그에 대한 추가 정보:

• Python/NetworkX를 사용한 그래프 데이터 과학