전체적인 내용 수정 예정입니다. 최근에 제대로 다시 공부했는데 개인적으로 introduction to algorithm에 있는 설명이 훨씬 좋더군요. 종만북에서 유량의 속성으로 유량의 대칭성을 소개하는데 그것보다 residual network를 설명하는 편이 더 이해하기 좋을거같아요. 유량 네트워크에서 역방향 간선에 flow를 뺀다는건 너무 뜬금없게 느껴졌거든요.. 보니까 역방향 간선에 flow를 뺀다는게 사실 유량 네트워크의 속성이기보다는 포드-풀커슨에서 cancelling을 구현하기 위함이고 introduction to algorithm에서는 유량의 대칭성 같은 속성이 있다고는 하지 않더라고요.
서론
먼저 최단 경로 알고리즘(Shortest Path Algorithm)과 대조하며 새로운 지식으로 확장해보자. 최단 경로 알고리즘은 일상 생활에서 쉽게 접할 만한 문제이며 플로우 알고리즘보다는 상대적으로 쉬워서 먼저 배웠을 것이다.
일단 최단 경로 알고리즘은 어떤 목표 상태에 도달하기 위한 비용을 최소화하기 위한 알고리즘이다. 따라서 최소 비용(minimum cost) 알고리즘이라고도 불린다.
반면 이제부터 살펴볼 유량 네트워크라는 자료구조에서 살펴볼 문제는 최대 유량(maximum flow) 문제이다. 말 그대로 유량(flow)를 최대화 해야한다. 유량은 말그대로 시작점부터 도착점까지의 흐름이다. 그리고 유량 네트워크에서의 간선의 가중치는 비용이 아니라 용량(capacity)이다. 용량은 그 간선에서 흐를 수 있는 최대 유량이다. 그리고 여기서는 최소 유량 문제를 고려하지 않는다. 유량을 흘러보내지 않으면 그것이 최소이기 때문이다.
https://en.wikipedia.org/wiki/Maximum_flow_problem
Maximum flow problem - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search Pi denotes the pets. wi denotes their preference of species. Ri denotes the humans. Source and sink are the start and end of the flow diagram. Each edge on the network indicates the ma
en.wikipedia.org
아래 그래프를 보고 두 개념을 비교해보자.
일단 그래프의 간선을 비용(cost)이라고 한다면 S에서 E까지 도달하는 비용은 모두 더해서 14이다.
하지만 여기서 그래프의 간선을 용량(capacity)이라고 한다면 S에서 E까지 흐를 수 있는 유량은 2이다.
최단 경로 문제는 한가지 경로만 찾으면 되지만
최대 유량 문제는 유량이 흐를 수 있는 경로들을 모두 구해야하고
최단 경로 문제는 하나의 간선에 대해서는 선택하는가 또는 선택하지 않는가 둘 중에 하나지만
최대 유량 문제는 어떤 간선에 '얼마나' 흘려보내는가를 선택해야한다.
따라서 최대 유량 문제는 최단 경로 문제보다 더 복잡하다.
유량 네트워크
유량 네트워크(flow network) : 간선에 용량이라는 속성이 있는 그래프이다.
소스(source) : 유량이 시작하는 정점. 유일하게 유량이 발생하는 정점.
싱크(sink) : 유량이 도착해야하는 정점.
용량(capacity) : 각 간선에 대해서 흐를 수 있는 최대 유량. c(u, v)
유량(flow) : 각 간선에 대해서 다음 constraints를 만족하는 값. f(u,v)
- 용량의 제한(capacity constraint) : 유량은 그 간선의 용량을 초과할 수 없다.
- 유량의 보존(conservation of flows) : 소스와 싱크를 제외한 정점에는 들어오는 유량과 나가는 유량은 같다.
유량의 대칭성(skew symmetry) : u→v로 f만큼의 유량이 흐르면 v→u로 -f만큼 유량이 흐른다고 생각한다.
value of flow : 소스에서 싱크로 흘러가는 유량의 크기이다. 소스에서 나오는 유량은 모두 싱크로 흘러가므로 이는 소스에서 나오는 유량의 합과 같다.
최대 유량 문제(maximum flow problem) : value of flow의 최댓값을 구하는 문제이며 이를 구하는 알고리즘을 최대 유량 알고리즘이라고 한다.
포드-풀커슨 알고리즘(Ford–Fulkerson Algorithm)
포드-풀커슨 알고리즘은 다음과 같다. (s : 소스, t : 싱크)
- 만약 s에서 t까지 모든 간선의 용량이 0보다 큰 경로 p를 구한다. 없으면 종료한다.
- 그 경로의 용량의 최솟값 c를 구한다.
- p에 포함된 모든 간선 (u, v)에 대해서 유량에 c를 더한다
- 유량의 보존에 의해서 반대 간선인 (v, u)에는 유량에 c를 뺀다.
- 1로 돌아간다.
한마디로 증가경로를 찾고 흘려보내는 것을 반복하는 것이다. 이는 잘 동작할까?
다음과 같은 경우를 생각할 수 있다. (종만북에 있는 예제다.)
각 간선에 표시된 값은 [유량 / 용량]이다. 최대 유량을 손으로 구해보면 다음과 같이 |f| = 2이다.
하지만 다음과 같이 흘려보내면 어떨까?
분명 최대 유량을 구하지 못했는데 더 이상 증가 경로가 없는 것처럼 보인다.
하지만 유량의 대칭성을 만족하기 위해서 포드-풀커슨 알고리즘에서는 (4)에서 반대 간선에 유량을 뺐다.
따라서 그림은 다음과 같다.
이제 증가 경로가 보이는가? -1 < 0이므로 (b, a)는 용량보다 유량이 작고 따라서 유량을 흘려보낼 수 있다.
b에서 a로 흘려보내면서 반대 경로에는 유량을 빼주는 것을 잊지말자.
결국 (a,b)의 유량이 0이 되었는데 이는 유량의 상쇄라고도 한다.
포드-풀커슨 알고리즘도 탐욕법의 일종이다. 어느 경로든 계속 채워 나가는것이 잘 동작할듯 하지만 정당성은 설명하기 어렵다... 정당성이 궁금하면 다음 링크를 참고하자. 이분 매칭도 다음 링크로 설명이 될 것 같다.
https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
Max-flow min-cut theorem - Wikipedia
In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in the minimum cut, i.e. the smallest total we
en.wikipedia.org
최소 컷 최대 유량 정리이고 종만북에도 잘 설명되어있다.
포드-풀커슨 알고리즘의 시간복잡도는 최대 유량 f에 대해서 증가 경로를 찾기위해 많아도 탐색을 f번 하므로 O(|V|+|E|) * f = O(|E|f)이다.
에드몬드 카프 알고리즘(Edmonds-Karp Algorithm)
포드-풀커슨 알고리즘 (1)에서 증가경로를 찾을 때 BFS를 쓰면 O(VE^2) 안에 찾을 수 있다고 알려져있다. 증명은 Introduction to Algorithms에 설명이 되어있다고 하며 구사과님 블로그에도 정말 잘 설명되어있다. 포드-풀커슨 알고리즘에서 BFS를 쓴 최대 유량 알고리즘을 에드몬드 카프 알고리즘(Edmonds-Karp Algorithm)이라고 한다.
이제 에드몬드 카프 알고리즘을 이용해서 문제를 하나 풀어보자.
https://www.acmicpc.net/problem/6086
6086번: 최대 유량
문제 농사꾼 존은 소들이 충분한 물을 마시길 원했다. 그래서 농장에서 우물에서 외양간을 잇는 N개의 배수관의 지도를 만들기로 했다. 존은 아주 다양한 크기의 배수관들이 완전히 우연한 방법으로 연결돼있음을 알았다. 존은 파이프를 통과하는 유량을 계산하고 싶다. 두개의 배수관이 한줄로 연결 돼 있을 때 두 관의 유량 중 최솟값으로 흐르게 된다. 예를 들어 용량이 5인 파이프가 용량이 3인 파이프와 연결되면 한개의 용량 3짜리 파이프가 된다. +---5---+
www.acmicpc.net
# 'A'~'Z' => 0~25, 'a'~'z' => 26~51
h = lambda x: ord(x) - ord('A') if x <= 'Z' else ord(x) - ord('a') + 26
def make_flow(S, T, path):
c = 10**9
cur = T
while cur != S:
c = min(c, capacity[path[cur]][cur] - flow[path[cur]][cur])
cur = path[cur]
cur = T
while cur != S:
flow[path[cur]][cur] += c
flow[cur][path[cur]] -= c
cur = path[cur]
return c
def bfs(S, T):
path = [-1] * 52
queue = [S]
for u in queue:
for v in adj[u]:
if capacity[u][v] - flow[u][v] > 0 and path[v] < 0:
queue.append(v)
path[v] = u
if v == T:
return make_flow(S, T, path)
return 0
def edmonds_karp(S, T):
max_flow = 0
while True:
c = bfs(S, T)
if c > 0:
max_flow += c
else:
break
return max_flow
if __name__ == '__main__':
flow = [[0] * 52 for _ in range(52)]
capacity = [[0] * 52 for _ in range(52)]
adj = [[] for _ in range(52)]
N = int(input())
for _ in range(N):
u, v, c = input().split()
u, v, c = h(u), h(v), int(c)
capacity[u][v] += c
capacity[v][u] += c
adj[u].append(v)
adj[v].append(u)
S = h('A')
T = h('Z')
max_flow = edmonds_karp(S, T)
print(max_flow)
※ O(|E|f) vs O(VE^2)
애드몬드 카프 알고리즘의 시간복잡도는 정확하게는 min(O(|E|f), O(VE^2))이다. 간선은 복잡한 그래프지만 흘려야하는 유량(f)이 적으면 O(|E|f) < O(VE^2) 가 될 수 있기 때문이다.
이와 비슷하게 이 글에서 다루지 않은 이분매칭 알고리즘은 포드-풀커슨을 단순화한 알고리즘인데 최대 흐르는 유량(f)이 정점 수(V)만큼이기 때문에 시간 복잡도는 O(|E|f) = O(VE)가 된다.