최소 비용 최대 흐름 알고리즘 (맞춤형 비용 함수 포함)

Question

최소 비용 최대 흐름 알고리즘에는 어떤 종류의 비용 함수를 사용할 수 있습니까?

것이 가능 유사한 비용 함수를 갖는 것이다 :

• 모서리에 흐름이 [1, X, 선정 = FixedCost + C1 + 유동 * cost_per_flow [C1]
• 경우 사이에 있다면 모서리에 흐름 사이 [X + 1, Y, 선정 FixedCost = + C2 + 유동 cost_per_flow * [C2]
등

이 어떠한 방식으로 알고리즘을 변경할 수 있는가?

Answer 1

고정 된 비용을 더하고 방정식에서 제거 할 수 있습니다. 그런 다음 각 모서리를 2 개의 모서리로 나눕니다. 각 모서리는 적절히 계산 된 비용을가집니다.

Answer 2

최소 비용 최대 흐름 알고리즘은 특정 종류의 선형 프로그램에 대한 해법 일뿐입니다.

선형 프로그램을 효율적으로 해결할 수있는 것은 convexity입니다.이 경우, 두 개의 가능한 흐름 F와 G가있는 경우 [0, 1]의 모든 t에 대해 흐름 tF + (1-t) G가 가능합니다. 비용 (T) + (1-t) G) ≤ 비용 (F) + (1-t) 비용 (G)을 갖는다. 사용자의 목적은이 기본적으로 FixedCost 수단 [1, X, C1 ≤ C2에서 FixedCost 0 [X + 1, Y]는 (C1 - C2) X 같은 것을 보인다 ≤ 0 :

6|  . 
5|  . 
4|  . 
3|  . 
2| . 
1| . 
0.---------- 
0 1 X 

을

아마 [1, X]> 0의 FixedCost가 중요하지만 NP-hard 문제가됩니다. 그래프에서 Steiner 트리를 줄이면 각 에지의 용량을 무한대로 만들고 Steiner 트리 문제에 의해 지정된 첫 번째 유닛과 그 이후의 유닛에 대해 0이됩니다. k - 1 슈타이너 터미널 중 하나를 용량 k - 1의 소스로 만들고 다른 하나는 용량 1로 싱크하십시오. k - 1 단위의 가장 저렴한 플로우를 요청하십시오.