Bonjour
Je cherche une piste pour résoudre mon problème.
Je dois créer un soft qui va regrouper un population (originalement 500 personnes) par groupes (configurable, initialement 20).
Mais il y aura des poids entre les gens, ça va varier entre "Untel doit être avec untel" jusque "Untel ne doit jamais être avec untel".
Et donc sur une échelle de -10 (pas ensemble) à +10 (obligatoirement ensemble), le défaut étant 0 (neutre).
Bon, c'est assez simple comme problème finalement.
J'avais pensé au départ à faire un graphe pondéré et utiliser un algo de parcours de graphe, mais une fois avancé sur la réflexion je n'arrive pas à visualiser comment faire. Le graphe me semble bon pour la représentation des données, mais je ne vois pas comment le parcourir pour atteindre le but.
Il faudrait pouvoir le parcourir sur N point (N=Nombre de personne dans le groupe), ce qui ferait le groupe.
Et ensuite pour le 2e groupe il faudrait le reparcourir mais en ignorant les points déjà sélectionnés pour le 1er groupe.
Ca me semble bizarre comme méthode, car si il existe une multitude de possibilité pour le 1er groupe, il en existera déjà moins pour le 2e, ..., et ensuite plus du tout pour le dernier. Mais dans ce cas, comment être sûr qu'on a la solution optimale ? En choisissant une solution différente pour le 1er groupe (si il y a plusieurs solution ayant le même poids minimum) on pourrait arriver a une meilleure solution au dernier groupe.
Bref je cherche des idées car mes connaissances en algo sont assez limitée, et déjà comment s'appelle ce type d'algo ? Car je ne connais pas le nom donc pour les recherches c'est pas facile
En tout cas, un grand merci pour tout aide
Partager