네트워크 흐름 문제
Network flow problem |
조합 최적화에서 네트워크 흐름 문제는 입력이 흐름 네트워크(가장자리에 숫자 용량이 있는 그래프)인 연산 문제의 한 종류로, 용량 제약 조건을 존중하고 모든 정점에서 유입 흐름이 동일한 흐름, 각 가장자리에 숫자 값을 구성하는 것이 목표다.특정 지정 터미널을 제외하고
특정 유형의 네트워크 흐름 문제는 다음과 같다.
- 소스 단자에서 싱크 단자로 유입되는 총 흐름량을 최대화하는 것이 목표인 최대 흐름 문제
- 최소 비용 흐름 문제. 가장자리는 용량뿐만 아니라 비용도 포함하며 목표는 최소 가능한 비용을 가진 주어진 흐름 양(또는 최대 흐름)을 달성하는 것이다.
- 총 흐름량이 용량과 일치하는 서로 다른 상품에 대해 여러 흐름을 구성해야 하는 다중 계류 흐름 문제
- 0이 없는 흐름, 흐름 양이 0이 아닌 값의 유한 집합으로 제한되는 조합학에서 연구된 흐름의 유형
max-flow min-cut 정리는 최대 흐름의 값을 최소 절단의 값, 즉 칸막이의 한 쪽에서 다른 쪽으로 교차하는 에지의 총 용량을 최소화하는 흐름 네트워크의 정점의 파티션과 동일시한다.대략적인 max-flow min-cut 이론은 이 결과를 다중 계통 흐름 문제로 확장시킨다.비방향 유동망의 Gomory-Hu 트리는 서로 다른 쌍의 단자 정점들 사이의 모든 최소 절단을 간결하게 표현한다.
흐름을 구성하는 알고리즘에는 다음이 포함된다.
- Dinic의 알고리즘, 최대 흐름을 위한 강력한 다항식 알고리즘
- 최대 흐름을 위한 보다 빠른 강력한 다항식 알고리즘인 Edmonds-Karp 알고리즘
- Ford-Fulkerson 알고리즘, 일반적으로 강한 다항식이 아닌 최대 흐름에 대한 탐욕스러운 알고리즘
- 선형 프로그래밍을 기반으로 하지만 네트워크 흐름에 특화된 방법인 네트워크 심플렉스 알고리즘
- 최소비용 흐름을 위한 단거리 알고리즘
- 푸시-릴라벨 최대 유량 알고리즘, 최대 유량에 대해 가장 효율적인 것으로 알려진 기법 중 하나
그렇지 않으면, 문제는 좀 더 전통적인 선형 프로그램 또는 유사한 것으로 공식화하여 범용 최적화 해결사를 사용하여 해결할 수 있다.
