1
최소 비용 흐름 문제에서 최대 흐름 문제로의 감소가 있습니까? 혹은 그 반대로도? 최대 흐름 문제를 풀기 위해 최소 비용 흐름 알고리즘을 사용하고 싶습니다.최대 흐름까지의 최소 비용 흐름
A
답변
2
죄송합니다. 질문을 처음 오해 한 것 같습니다. 예, Minimum Cost은 최대 유량을위한 특별한 경우입니다. 최대 유량보다는 최소 비용이 각 모서리를 통과 한 후 유량에 대한 비용이 있다고 가정합니다. 따라서 각 모서리의 비용을 0으로 설정하면 최소 비용이 최대 흐름으로 줄어 듭니다.
편집 : 최소 비용 문제가 미리 정의 된 필요한 흐름을 필요로
부터 시작하는 보낼 수 있습니다. 최대 값을 검색하려면 위의 알고리즘 (가장자리 비용 c(u, v) = 0)을 여러 번 실행해야합니다. 주어진 값 범위에 대해 binary search을 사용하면 최대 값을보다 효율적으로 찾을 수 있습니다.
Min Cut Max Flow을 의미합니까? (편집 : 당신이 이것을 의미하지 않는다고 생각합니다. 그러나 이것은 최대 흐름을 증명할 수있는 기초입니다. 그렇지 않은 경우보고 가치가 있습니다.) 그래프를 떨어 뜨리고 분을 자르면 이해하기 쉽습니다.
+0
답변 해 주셔서 감사합니다. 예, 저는 Min Cut Max Flow 문제를 의미했습니다. 그래서 당신이 의미하는 바를 짐작할 수 있습니다 : 공급을 가정하고 모든 비용을 0으로 만드십시오. 최소 비용 흐름 문제를 해결하십시오. 가능한 경우 공급을 늘리고 그렇지 않으면 공급을 줄이면서 알고리즘을 다시 실행하십시오. 우리는 이와 같은 공급 가치를 찾아야합니다. 내가 맞습니까? – user2464953
+0
동의합니다. for 루프가 필요합니다. 다른 사람은 바이너리 검색을 제안합니다. http://en.wikipedia.org/wiki/Minimum-cost_flow_problem – grc
1
Wikipedia에 따르면 최소 비용 흐름 문제를 해결하기위한 연속적인 최단 경로 및 용량 확장 방법은 최대 흐름 문제를 해결하기위한 Ford-Fulkerson 알고리즘의 일반화입니다. 또한, 비용 스케일링 알고리즘은 push-relabel 알고리즘의 일반화로 볼 수 있습니다. –