그룹 할당

Question

세트에 변수를 할당하는 데 문제가 있습니다. 각 집합에는 할당 할 수있는 변수의 한계가 있으며 각 변수는 전체 집합의 일부 하위 집합에 할당 될 수 있습니다.

예:

• a세트 A또는B
• b 세트에있을 수 있습니다 B
• c세트 A또는B
• d 세트에있을 수 있습니다 A

따라서 우리는 A: a, d; B: b, c또는 A: c, d; B: a,b(세트 내의 변수 순서는 중요하지 않습니다) /

물론 모든 변수를 할당 할 수없는 경우, 여러 옵션이있는 경우, 하나의 옵션 만있는 경우도 있습니다.

이 문제의 간단한 버전이있는 것 같지만 손가락을 댈 수없는 것 같습니다. 모든 포인터를 주시면 감사하겠습니다.

Answer 1

최대 유량을 사용하여 효율적으로 해결할 수 있습니다. 소스에서 각 변수로의 단위 용량 호, 각 변수에서 속할 수있는 각 세트로의 단위 용량 호, 각 세트에서 세트의 용량과 동일한 용량의 싱크로의 호로 흐름 네트워크를 준비합니다. . 예를 들면

ARCS

tail head capacity
------------------
s    a    1
s    b    1
s    c    1
s    d    1
a    A    1
a    B    1
b    B    1
c    A    1
c    B    1
d    A    1
A    t    2
B    t    2

적분 흐름을 생성하고 호에 흐름이있는 변수에 따라 할당을 추출하는 좋아하는 최대 흐름 알고리즘을 사용합니다.

Answer 2

이 문제는 NP- 완전으로 이에 대한 다항식 시간 솔루션이 없음을 의미합니다. 이 경우 역 추적을 사용해야합니다.

다음 링크를 살펴보십시오.

https://www.geeksforgeeks.org/vertex-cover-problem-set-1-introduction-approximate-algorithm-2/ https://www.geeksforgeeks.org/set-cover-problem-set-1-greedy-approximate-algorithm/