문제가 있습니다. 문제가 있습니다. 그 문제는 어디서부터 시작해야 할 지 모릅니다. 그래서 나는 절망적으로 stackoverflow를 사용하고 있습니다.비용 할당 문제가 발생했습니다.
문제는 np-hard가 np-completeness를 증명하면 np-hard 또는 polynomial인지 알아 내고, 그렇지 않으면 알고리즘을 제공하기를 원합니다. 다음
문제는 :
제품은 N 개의 모듈이 존재한다. 약간의 비용 (c_ij, i : 모듈 번호, j : 회사 번호)을 가지고 각 모듈을 구축 할 수있는 두 회사가 있습니다. 모듈 a와 b가 다른 회사에 의해 만들어진 경우 추가 비용 (p_ab)도 있습니다. 모듈 a와 b가 연속적 일 필요는 없지만 동일한 추가 비용이 a와 c에도 적용됩니다. 예상대로 문제는 총 비용이 최소가되도록 모듈을 회사에 할당하려고합니다.
어떤 아이디어가 있습니까?
min cut 문제로 줄일 수 있습니다. 이는 max flow 알고리즘에서 찾을 수 있습니다. 그래서 네트워크는 무엇입니까? 모듈은 그래프의 vertecies가 될 것이고 2 개의 새로운 vertex source와 sink를 추가 할 것입니다. 소스에서 우리는 용량 Ci1을 갖는 모든 모듈 i에 에지를 추가합니다. 모든 모듈 i에서 유사하게 용량 Ci2로 싱크하기 위해 에지를 추가합니다. 또한 모든 모듈 i와 j에 대해 용량 pij 의 에지를 추가합니다 (그래프 방향이므로 두 에지 (i j)와 (j i)가됩니다). min cut의 가치가 문제의 해결책이라는 것을 쉽게 알 수 있습니다 (두 번째 회사에 할당 된 출처와 첫 번째 회사에 모듈을 할당하는 절단의 일부에있는 모듈)
감사합니다 mikleb, 그 질문을 게시했다 2 일 후에 찾은 정확한 대답을했다. 나는 대답을 게시 할 책임이 더 있어야 했음에 틀림없지 만, 그것은 내 마음을 어지럽게했다. 하지만 어쨌든, 당신의 솔루션은 미래에 다른 사람들을 도울 수 있어야합니다. – fizboz
두 개의 회사 또는 두 개의 회사가 있습니까? 각 모듈? – jpalecek
두 회사 만 있습니다. – fizboz