2009-09-05 10 views
0

permet de dire que j'ai un million de personnes des objets qui, lorsqu'ils ont été évalués à l'aideRegroupement et algorithme de tri aide

person1.Matches(person2);

return true ou false.

Je veux les mettre dans des groupes. Ces groupes sont créés par une personne qui correspond à une autre personne du groupe. Donc, toute personne d'un groupe ne sera pas un match avec une personne d'un autre groupe. Toute personne appartenant à un groupe correspond à au moins une personne du même groupe. Par exemple, si un individu est asexué, il formera un groupe d'une personne. Un couple marié FIDELE formera un groupe de deux. Un mari et sa femme et sa maîtresse et le mari maîtresses formeraient un groupe de 4.

Juste pour que vous sachiez, cet algorithme serait utilisé pour analyser des géométries.

Répondre

5

Ce problème ressemble exactement au problème connected components. Vos sommets de graphe étant les personnes, et les arêtes du graphe étant la relation "Correspondances". Il pourrait être résolu soit par BFS soit par DFS (lire à ce sujet dans le lien de wikipedia, il donne une bonne explication à ce sujet).