Discussion :

[Fabske]

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

[ToTo13]

Bonjour,

pourquoi ne pas utiliser le principe des Kmeans en remplaçant tout simplement la distance du point au barycentre par une fonction d'énergie qui serait la somme des poids ?

[Graffito]

Bonjour,

Pour trouver plus vite une "bonne" solution, on pourrait classer les individus par ordre de difficulté : les plus difficiles étant à priori ceux dont la somme des valeurs absolues des critères d'affinité est la plus forte.

Les groupes étant vides au départ, on traite en séquence chaque individu du plus difficile au plus facile en le mettant dans le groupe qui maximisera la qualité de la solution portant sur les N individus dèjà traités + l'individu courrant lui-même.

On peut améliorer cette solution en traitant X individus courrants au lieu d'un mais le temps de calcul augmentera exponentiellement avec X.

comment être sûr qu'on a la solution optimale ?

Je ne sais pas si c'est possible compte tenu du nombre de combinaisons.

[Fabske]

ToTo13> J'ai un peu regardé Kmeans, mais de ce que j'ai compris il sert a regrouper des points déjà positionnés. Or dans mon cas les points ne sont pas positionnés. Ou alors il faudrait déduire une position en fonction des liaisons avec d'autres points, et là je pense qu'on complexifie encore le problème, non ? En tk je ne connaissais pas Kmeans, ça m'a permit de découvrir un peu

Graffito> Oui ça faisais partie des optimisations possible auxquelles j'ai aussi pensé, dans le cas où je finirais par faire une moulinette qui teste simplement toutes les combinaisons. Mais comme tu dis, il y a tellement de possibilités...

[ToTo13]

ToTo13> J'ai un peu regardé Kmeans, mais de ce que j'ai compris il sert a regrouper des points déjà positionnés. Or dans mon cas les points ne sont pas positionnés. Ou alors il faudrait déduire une position en fonction des liaisons avec d'autres points, et là je pense qu'on complexifie encore le problème, non ? En tk je ne connaissais pas Kmeans, ça m'a permit de découvrir un peu

Ce que je proposais, c'était justement de le modifier en ce sens.
Au lieu de regarder les distances relatives dans un groupe, on prend la satisfaction des contraintes.