조합론적 최적화/Flow & Circulation (6) 썸네일형 리스트형 서큘레이션 (Circulation) 최대 흐름 문제(maximum flow problem)는 어떤 방향 그래프(directed graph)와 간선 위의 용량(capacity)으로 정의되는 흐름 네트워크(flow network)에서 시점(source)부터 종점(sink)까지 최대한 많은 양의 물을 흘리는 방법을 찾는 문제입니다. 이 문제는 이론적으로는 물론 산업적으로도 깊이 연구된 매우 중요한 조합론적 최적화 문제입니다. 제 블로그에서도 현재까지 다섯 개의 글을 적었을 만큼 매우 비중 있게 다룬 주제입니다. 이번 포스트에서는 이 문제를 보다 확장을 시켜 보고자 합니다. 원래 문제에서는 각 간선에 이 이상은 흘릴 수 없다는 제약을 주는 용량만 있었습니다. 하지만 경우에 따라서는 각 간선마다 적어도 이 정도는 흐르고 있어야 한다는 일종의 필요량.. 디니츠의 알고리즘 (Dinitz' Algorithm) 지금까지 저는 제 블로그에서 최대 흐름 문제(maximum flow problem)를 많은 포스트를 통해서 다루어 왔습니다. 가장 최근에는 최대 흐름 문제를 다항 시간에 해결하는 에드몬즈-카프 알고리즘(Edmonds-Karp algorithm)을 소개해 드렸죠. 이번에는 에드몬즈-카프 알고리즘보다 더 빠른 시간에 최대 흐름 문제를 해결하는 방법 중 하나를 소개하고자 합니다. 바로 우리에게는 디닉의 알고리즘(Dinic's algorithm)으로 더 잘 알려진, 디니츠의 알고리즘(Dinitz' algorithm)입니다. 포탈에 검색해 봤더니 디니츠의 알고리즘을 어떻게 구현하는지 우리말로 설명한 게시글은 적잖이 볼 수 있었습니다. 다만 어째서 디니츠의 알고리즘이 에드몬즈-카프 알고리즘보다 효율적으로 동작하는지.. 에드몬즈-카프 알고리즘 (Edmonds-Karp Algorithm) 최대 흐름 문제(maximum flow problem)는 어떤 흐름 네트워크(flow network)가 주어졌을 때 시점(source)에서 종점(sink)까지 최대로 많은 양의 흐름을 찾는 문제입니다. 이때 흐름은 각 간선에서 용량(capacity)을 넘을 수 없고, 시점과 종점을 제외한 나머지 정점에서는 들어오는 양과 나가는 양이 동일해야 하죠. 지난 포스트에서는 이 문제를 풀기 위하여 잔여 네트워크(residual network)와 증가 경로(augmenting path)가 무엇인지에 대해서 살펴보았으며, 최종적으로는 매번 현재 흐름으로 정의되는 잔여 네트워크 위에서 시점에서 종점으로 향하는 임의의 증가 경로를 찾아 현재 흐름을 증가시켜 주면 (모든 간선의 용량이 유리수일 때) 언젠간 최대 흐름을 찾.. 포드-풀커슨 방법 (Ford-Fulkerson Method) 최대 흐름 문제(maximum flow problem)는 어떤 흐름 네트워크(flow network)가 주어졌을 때, 시점에서 종점으로 흐르는 최대 흐름을 찾는 문제입니다. 지난 두 포스트를 통해 우리는 이 문제에서 최대 흐름이 다음과 같은 흥미로운 특징을 갖는다는 것을 알게 되었습니다. 정리 1. 최대 흐름의 잔여 네트워크의 특징 최대 흐름의 잔여 네트워크(residual network)에서는 시점에서 종점으로 도달할 수 없다. 정리 2. 잔여 네트워크의 종점 비도달성의 특징 어떤 흐름의 잔여 네트워크에서 종점이 시점으로부터 도달 불가능할 때, 그것의 흐름양과 동일한 값의 용량을 갖는 절단(cut)을 찾을 수 있다. 그러므로, 이 흐름은 최대 흐름이다. 정리 1의 증명이 궁금하면 아래 글을 참조하세요... 최대 흐름 최소 절단 정리 (Max-Flow Min-Cut Theorem) 저번 글에서는 최대 흐름 문제(maximum flow problem)가 무엇인지 알아 보고 최대 흐름이 만족하는 성질들도 함께 확인해 보았습니다. 최대 흐름 문제가 무엇인지 잘 모르신다면 이전 포스트를 참조하시기 바랍니다. 2020/08/29 - [기초 강좌/Algorithm analysis] - 최대 흐름 문제 이해하기 (Maximum Flow Problem) 최대 흐름 문제 이해하기 (Maximum Flow Problem) 여러분이 상수도 공사의 직원이라고 해봅시다. 여러분의 업무는 물이 저장된 수원에서 물이 필요한 특정 지역까지 물을 공급하는 것입니다. 물을 공급하는 방법은 수원에서 해당 지역까지 연결 gazelle-and-cs.tistory.com 결론부터 말씀드리면 최대 흐름의 잔여 네트워크(r.. 최대 흐름 문제 이해하기 (Maximum Flow Problem) 여러분이 상수도 공사의 직원이라고 해봅시다. 여러분의 업무는 물이 저장된 수원에서 물이 필요한 특정 지역까지 물을 공급하는 것입니다. 물을 공급하는 방법은 수원에서 해당 지역까지 연결된 수도관을 따라 흘려주는 것입니다. 해당 지역에는 사람도 많고 공단도 있어서 최대한 많은 물을 공급받고 싶어합니다. 만약 두 지점 사이를 잇는 수도관이 딱 하나 있다면 쉽게 해결되겠지만, 문제는 이보다 더 복잡합니다. 바로 수도관이 여러 사정에 의해 매우 얼기설기 설치되어 있기 때문입니다. 게다가 수도관마다 연식이나 제원도 달라서 수도관마다 견딜 수 있는 수압이나 용량도 정해져 있습니다. 과연 물을 어떻게 흘려야 수도관에 무리를 주지 않고 해당 지역으로 최대한 많은 물을 보내줄 수 있을까요? 이 문제는 유명한 최적화 문제인.. 이전 1 다음
