학생을 N 개의 그룹으로 나누는 알고리즘

Question

M 명의 학생을 N 개의 팀으로 나누고 싶습니다. 어렵지는 않지만 몇 가지 제약 사항이 있습니다.

1.constraint : (A, B) 한 쌍의 학생들이 한 그룹으로 모여 있어야합니다. 그것은 studentA가 studentB와 같은 그룹에 있기를 원한다는 것을 의미합니다.

2.constraints : (A, B) 한 쌍의 학생 (studentA와 studentB)이 하나의 그룹에 있어서는 안됩니다.

나는 M 명의 학생이 있고이 제약 조건에 따라 N 개의 그룹을 만들고 싶습니다. 그들을 나눌 수없는 경우, 최소 제약 조건 위반으로 최상의 솔루션을 찾으십시오.

알고리즘으로 어떻게 해결할 수 있습니까?

Answer 1

graph colouring problem으로 생각하면 도움이 될 것입니다. 이 링크에는 다양한 제안 알고리즘이 포함되어 있습니다.

정점은 학생을 나타내며 색상은 다른 그룹을 나타냅니다.

정점 사이의 모서리는 학생들이 다른 그룹에 있기를 원한다는 것을 나타냅니다. 학생들이 같은 그룹에 속하기를 원하면 정점을 병합하기 만하면됩니다. * 그건