선호하는 파트너를 세 그룹으로 연결하는 알고리즘
https://stackoverflow.com/questions/294660
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
이 문제를 해결하는 좋은 알고리즘은 무엇입니까?
저는 A그룹, B그룹, C그룹이라는 세 그룹의 사람들을 가지고 있습니다.각 그룹에는 동일한 수의 사람들이 있습니다.그들은 각자 기꺼이 함께 일하고 싶은 다른 그룹의 사람들 목록을 가지고 있습니다.나는 이 모든 사람들을 3명의 그룹(A에서 1명, B에서 1명, C에서 1명)으로 그룹화하여 그룹의 모든 사람이 해당 그룹의 다른 사람들과 함께 일하고 싶어하도록 하고 싶습니다.
어떻게 하면 이러한 그룹을 빠르게 찾을 수 있나요?모두를 행복하게 만들 수 없다면, 알고리즘은 먼저 서로 협력하고 싶은 세 사람이 있는 그룹을 최대한 많이 만든 다음, 다른 그룹의 사람들도 최대한 행복하게 만들어야 합니다.
마지막 요점:사람들은 누구와 함께 일하고 싶은지에 동의합니다(만약 x라는 사람이 y라는 사람과 함께 일하고 싶어하면 y도 x와 함께 일하고 싶어합니다).알고리즘의 실행 시간에 대해 큰 O를 제공할 수 있다면 좋을 것입니다!
해결책
이는 안정적인 결혼 문제와 비슷하지만 두 당사자가 아닌 세 당사자가 필요합니다.
이전 문제(양분할 그래프 매칭)에 대한 효율적인 솔루션을 살펴보고 이를 필요에 맞게 조정하세요.
http://en.wikipedia.org/wiki/Stable_marriage_problem
한 가지 적응은 먼저 그룹 A와 B에서만 작업 쌍을 구축하는 것입니다.그런 다음 이 쌍은 각각 그룹 C의 작업자와 쌍을 이루어야 합니다.쌍은 쌍의 두 구성원이 모두 동의하는 작업자(목록이 제공됨)만 선호하도록 합니다.이는 지역 최적값만 제공한다는 점에 유의하세요.
k-partite 매칭에 대한 최적의 솔루션은 NP-찾기가 어렵습니다.
http://www.math.tau.ac.il/~safra/PapersAndTalks/k-DM.ps
k-partite 일치 문제에 대한 최적이 아닌 솔루션은 이 문서를 참조하세요.
검색할 용어를 알았으니 이제 Google에서 다른 사람을 직접 찾을 수 있을 것이라고 확신합니다.k=3에 대한 최적의 솔루션을 제공하는 효율적인 알고리즘이 있는지 모르겠습니다.
다른 팁
이것은 안정적인 결혼 문제의 확장과는 다릅니다. 왜냐하면 내가 OP의 질문을 이해하기 때문에 각 그룹의 사람들은 누구와 함께 일하고 싶은지 가장 많은 사람부터 적은 사람까지 순서대로 나열한 목록을 가지고 있지 않기 때문입니다.그것은 이진 관계(의지/의지 없음)입니다.
이는 매우 빠르게 풀 수 있는 정수 계획법 문제로 공식화될 수 있습니다.나는 아래 문제의 수학적 공식을 제시합니다.glpk 또는 AMPL/CPLEX와 같은 패키지를 사용하여 데이터를 처리할 수 있습니다.
다음 행렬을 정의합니다.
M1 = |A| x |B| 행렬, 여기서
M1(a,b) = 1 a(A의 지정된 멤버)가 b(B의 지정된 멤버)와 작업할 의향이 있는 경우, 그렇지 않은 경우 0
M2 = |A| x |C| 행렬, 여기서 M2(a,c) = 1 a(A의 지정된 멤버)가 c(C의 지정된 멤버)와 작업할 의향이 있는 경우, 그렇지 않은 경우 0
M2 = |B| x |C| 행렬, 여기서
M3(b,c) = 1 b(주어진 B 멤버)가 c(주어진 C 멤버)와 작업할 의향이 있는 경우, 그렇지 않은 경우 0
이제 최대화에 사용할 새 행렬을 정의합니다.
X = |A| x |B| x |C| 행렬, 여기서
X(a,b,c) = 1 a, b, c를 함께 작동하게 하면요.
이제 목적 함수를 정의합니다.
//그룹 수 최대화
최대화하다 Sum[(all a, all b, all c) X(a,b,c)]
다음과 같은 제약 조건이 적용됩니다.
//아무도 두 그룹에 속하지 않도록 하기 위해
a의 모든 값에 대해: Sum[(all j, k) X(a, j, k)] <= 1
b의 모든 값에 대해: Sum[(all i, k) X(i, b, k)] <= 1
c의 모든 값에 대해: Sum[(all i, j) X(i, j, c)] <= 1
//모든 그룹이 호환 가능한 개인으로 구성되었는지 확인하기 위해
모든 a,b,c에 대해: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3
이 문제에 대해 간단히 알아보세요.첫째, 이는 안정된 결혼 문제의 예도 아니고 실제로 그것의 연장도 아니다(즉,3D 안정 매칭 문제).그럼에도 불구하고 이는 NP-hard로 알려진 3D 매칭 문제입니다(Garey 및 Johnson 참조).이러한 문제를 합리적인 방법으로 해결하려면 제약 조건, 정수 또는 선형 프로그래밍(다른 방법도 있음) 형식을 사용해야 할 가능성이 높습니다.유용하게 사용할 수 있는 것은 새로운 Microsoft Solver Foundation이므로 확인해 보세요.
우선, 두 당사자가 세 번째 그룹에서 함께 일할 사람에 대한 서로 다른 목록을 가지고 있는 사실을 제거할 수 있습니다.그런 다음 무차별 대입, 깊이 우선 검색을 시작하고 항상 가장 인기가 없는 것부터 가장 인기 있는 것까지 선택합니다.
또는 위의 제거와 동일하게 가능한 모든 트리오의 목록을 작성하고 그 대신 작업하십시오.
비슷한 문제가 발생하여 무차별 대입 스크립트를 작성했습니다. http://grouper.owoga.com/
나의 초기 생각은 다음과 같습니다.무차별 공격을 하기에는 너무 큰 더 큰 그룹의 경우 어떤 유형의 유전 알고리즘이 있습니까?N번 무작위 교환을 M번 수행합니다.'행복' 기능을 사용하여 각각의 새로운 배열에 점수를 매깁니다.가장 좋은 몇 가지를 선택하고 번식하고 반복하십시오.
소규모 그룹의 경우 몇 개의 그룹을 반복하면서 '가장 좋은' 교환(가장 높은 전체 '행복' 이득을 가져온 교환)을 찾은 다음 이를 반복함으로써 더 나은 결과를 얻었습니다.
