Divida as pessoas em equipes para mais satisfação

Question

Apenas uma questão de curiosidade. Lembre -se de quando, em grupo de classe, o professor dividiria as pessoas em grupos de um determinado número (n)?

Alguns dos meus professores levariam uma lista de n pessoas que se deseja trabalhar e n pessoas com quem se não quer trabalhar de cada aluno e, em seguida, magicamente os grupos de n Onde os alunos se correspondiam com as pessoas que preferem e evitariam trabalhar com pessoas que não preferem.

Para mim, esse algoritmo parece muito com um problema de mochila, mas pensei em perguntar sobre qual seria sua abordagem para esse tipo de problema.

EDITAR: Encontrado um artigo da ACM descrevendo algo exatamente como minha pergunta. Leia o segundo parágrafo para Deja Vu.

Answer 1

Para mim, parece mais um tipo de Clique problema.

A maneira como vejo o problema, eu configurei o seguinte gráfico:

• Vértices seriam os alunos
• Dois alunos estariam conectados por uma vantagem se ambos os seguintes segurassem:
  1. Pelo menos um dos dois alunos quer trabalhar com o outro.
  2. Nenhum dos dois alunos não quer trabalhar com o outro.

É então uma questão de particionar o gráfico em panelinhas de tamanho n. (Assumindo que o número de alunos é divisível por n)

Se isso não fosse possível, eu provavelmente deixaria a primeira restrição nas bordas deslizarem e tivesse arestas entre duas pessoas, desde que nenhuma delas diga explicitamente que não queira trabalhar com a outra.

Quanto a uma abordagem para resolver isso com eficiência, não tenho idéia, mas, esperançosamente, isso deve aproximá -lo de algumas dicas sobre o problema.

Answer 2

Você pode modelar isso com bastante facilidade como um problema de agrupamento e nem precisaria definir um espaço, você pode realmente definir as distâncias:

Faça duas pessoas muito próximas se ambas quiserem trabalhar juntas. Fechar se um deles quiser trabalhar com o outro. Distância média se houver apenas apatia. Longe se um não quer trabalhar com o outro.

Então você pode apenas encontrar grupos, Yay. Em seguida, divida quaisquer aglomerados de tamanho excessivamente grande, com confiança de que as pessoas nos grupos ficariam bem trabalhando juntos.

Answer 3

Esse problema pode ser forçado a bruto; portanto, minha abordagem seria a primeira a forçar a força e depois consertá-la quando tiver uma idéia melhor.

Answer 4

Existem alguns algoritmos que você pode usar. Um ótimo exemplo é o chamado "problema de casamento estável", que tem uma solução perfeita. Você pode ler mais sobre isso aqui:

http://en.wikipedia.org/wiki/Stable_Marriage_Problem

O problema estável do casamento funciona apenas com dois grupos de pessoas (homens/mulheres no caso do casamento). Se você deseja formar par, pode usar uma variação, o problema estável de colega de quarto. Nesse caso, você cria pares, mas todo mundo vem de uma única piscina.

Mas você pediu uma equipe (que eu traduzi em> 2 pessoas por equipe). Nesse caso, você pode deixar todo mundo preencher o seu melhor para a pior partida e depois executar o