probléme d'obtimisation à indentifier.

[invite0214fc05]

Bonjour,

j'ai un problème qui est le suivant: j'ai n individus, il s'agit de former des groupes à partir de ces individus.
Chacun individu peut se regrouper avec un autre ou non. Cette information est donnée par une matrice binaire symétrique.

Je cherche un algorithme qui me permettrait de créer un minimum de groupes à partir des n individus, sachant que dans un groupe tout ses membre pris 2 à 2 doivent pouvoir se regrouper entre eux.

Est-ce que vous savez si un algorithme déjà existant permettrai de faire cela, ou même donner une solution approchée satisfaisante (mais mieux que l'algorithme glouton).

Merci d'avance
-----

[invitec5eb4b89]

Bonjour,
Il faut regarder du côté de la théorie des graphes et de la décomposition d'un graphe en cliques. Il existe des algorithmes, dont certains sont implémentés en R (voir la fonction "cliques" de la librairie "ggm" par exemple, mais il y en a d'autres !).
Bon courage,
Vincent.

[invite0214fc05]

Merci, j'avais pas pensé au rapprochement avec les cliques dans les graphes

[invite0214fc05]

Je me permet quand même de remarquer que la fonction cliques de ggm donnes toutes les cliques maximales du graphe mais ne permet pas directement de décomposer le graphe en un minimum de cliques, cela requière au minimum un second algorithme. Malheureusement le format de sortie de la fonction cliques ne simplifie pas les choses.

[A voir en vidéo sur Futura]

[invite0214fc05]

Heureusement j'ai une idée,

Il suffit de prendre le graphe qui correspond à la matrice "contraire" (c'est a dire tu met 1 si il ne peuvent pas se regrouper et 0 si il peuvent).
Puis il s'agit d'un bête problème de coloration. Enfin bête NP-complet quand-même, mais il existe des heuristiques telles que welsh et powel ou autre...

Tien d'ailleurs est-ce que quelqu'un sais si il y a un algorithme de coloration sous R?