Discussion :

[Dilettante]

Bonjour,

Pour l'organisation d'une rencontre associative, je dois organiser un café-débat. Le but du café-débat est d'améliorer la qualité des échanges : au lieu d'une réunion en grand groupe, on sépare ce grande groupe (une trentaine de personnes) en petits groupes (4-5 personnes de préférence) constituant autant de petites réunions. Lorsque ces réunions sont finies, on disperse ces groupe et on renouvelle l'opération un certain nombre de fois (fixé, aux alentours de 6), de manière à ce qu'il y ait un bon brassage, c'est à dire le plus de rencontres possibles.

Dans la mesure du possible, on préfère éviter que deux personnes se retrouvent deux fois ou plus dans le même groupe, ou pire, qu'un même groupe se réunisse deux fois.

Un peu plus formellement, on peut présenter ça comme un ensemble de partitions d'un ensemble, de manière à ce que les sous-ensembles générés soient les plus distincts possible.

J'éprouve déjà des difficultés à créer de manière assez performante des partitions dont la taille des sous-ensembles est dans un intervalle fixé, et je constate que ce n'est pas toujours possible.

Je suis aussi à la recherche d'une heuristique qui me permette d'assurer un bon brassage, même s'il n'est pas optimal.

Auriez-vous des idées d'algorithmes ou d'approches qui m'aideraient à résoudre ce problème ?

Merci !

[Graffito]

Il me semble qu'il suffit de créer le n+1 ième round à partir du n iéme round et du stockage des rencontres dèjà effectuées dans les n premiers rounds:

• au départ du traitement du n+1 ième round, les groupes sont vides,
• On traite successivement les participants dans l'ordre du n ième round,
• Pour un participant, on affecte ce participant au meilleur des groupes en cours de constitution
• Le "meilleur" groupe sera celui ayant le poids le plus faible, ce poids étant calculé comme la somme du nombre de rencontres déjà faites avec les autres membres du groupe.

[Dilettante]

En effet, c'est beaucoup plus simple et ça marche beaucoup mieux comme ça !

Merci Graffito !

[DrDarko]

Bonjour,

Je sais que cette discussion est résolue mais je pense qu'avec 2 - 3 règles en plus l'algo serait plus rentable. Car dans certains cas j'ai peur qu'une personne puisse se retrouver avec pas mal de personnes qu'elle a déjà rencontré notamment dans les derniers cycles.

Je pars du principe que tu calcules le meilleur groupe en incluant la personne à placer évidemment. Et non en te basant juste sur les groupes déjà constitués.

Par exemple si on place les personnes en fonction de leur affinité avec le groupe on ne prend pas réellement en compte l'affinité des personnes déjà dans le groupe. C'est à dire qu'une personne pourrait se voir attribuer à chaque fois une personne qu'elle a déjà rencontrer si la personne qui arrive n'a rencontré que cette personne ou une seule personne d'autre dans ce groupe.
Je précise que ce genre de cas arrive en fin de cycle.

Pour y remédier il y a 2 méthodes :
- soit il faudrait avoir moyen de rebouger des personnes qui n'ont pas du tout une bonne affinité avec leur groupe ou simplement de pouvoir les échanger avec la nouvelle personne arrivant (cette méthode peut poser quelques problèmes par exemple si la personne que l'on bouge ne trouve pas groupe sans bouger une autre personne... Boucle plus ou moins infini en mode un peu brute force... Donc il faut bien implémenter cette méthode.
- soit on fait en sorte que si une personne à rencontrer déjà une personne dans le groupe cela donne 1 point, si cette personne a déjà rencontrer 2 personnes on passe à 3 points... Ici il faut faire attention au calcul de des points de tes groupes.


De même une personne peut avoir plus d'affinité pour un groupe qu'une autre alors que le groupe est déjà plein donc il faudrait pouvoir changer ces personnes. Cela revient un peu à la 1ère méthode mais c'est un problème que tu rencontreras surement.

[Dilettante]

En pratique, le nombre de cycles que je dois produire est suffisamment faible pour que le risque soit négligeable, mais ça reste une question intéressante

Rebouger des personnes déjà placée demanderait en effet un algorithme bien plus savant, qui relèverait sans doute davantage de l'intelligence artificielle : A* et compagnie. Ça pourrait être un bon sujet de travaux pratiques !

Du coup, j'ai utilisé un système de score qui ressemble un peu à la deuxième méthode que tu proposes : je stocke dans un dictionnaire tous les groupes ayant déjà été réunis, ainsi que tous les sous-ensembles de ces groupes, et j'associe à chacun d'eux le nombre de fois qu'ils avaient été réunis.

Ainsi, pour évaluer l'affinité d'un candidat à un groupe, je calcule tous les sous-ensembles qu'il constituerait avec les membres de ce groupe, et j'additionne les valeurs associées à ces sous-ensembles dans le dictionnaire. Plus le résultat est petit, plus le candidat a sa place dans ce groupe.

Ça a le mérite d'être rapide à implémenter, et de pénaliser lourdement les gros groupes qui se répètent : 2 personnes qui s'étaient déjà réunies coûtent un point, si elles ont déjà été réunies deux fois auparavant, cela coûte deux point. 3 personnes a, b et c déjà réunies coûtent 4 points (ab, bc, ca et abc), etc.

Je pense aussi que ça marche bien parce que je ne travaille que sur une trentaine de personnes. Si je travaillais sur une population sensiblement plus grande, je pense que la taille du dictionnaire exploserait, ce qui rendrait la méthode inutilisable...