Discussion :

[molini_a]

Bonjour,

je cherche à faire un algo qui serait le suivant :

J'ai une entreprise avec 100 employés qui travaillent tous un nombre de jours différents par mois. exemple l'employé 1 travail 10 jour, l'employé 2 travaille 25 jours etc... et donc j'aimerais faire un algo qui groupe par 3-4 personnes, les employés qui travaillent principalement ensemble, exempe si un employé travail 20 jours et qu'un autre travail 10 jours et qu'ils ont au moins 7 jours en commun, alors j'estime qu'il travaillent ensemble.

J'avasi donc penser à utiliser des graphes de plus cours chemin, avec du Diskstra ou Floyd Bellman, etc... mais j'ai des doutes sur la faisabilité d'un telle algo ???

ne serait-il pas d'une complexité en exponentielle ?

Sinon, pourriez-vous me dire dans quelle direction je doit chercher svp ??

merci d'avance.

[pseudocode]

Sinon, pourriez-vous me dire dans quelle direction je doit chercher svp ??

Vu que tu as déjà construit le graphe, regarde du coté de l'algo "graph cut".

[molini_a]

je me suis renseigné rapidement sur le sujet et on ne trouve pas vraiment d'explications clair sur ce que je voudrais. D'après ce que j'ai pu tiré de ca:

• c'est de la recherche opérationnelle
• Il faut utiliser la recherche du flot maximal, c'est à dire, je pensais avoir un graphe avec en noeud, les employés et en arretes les ratio du nombre de jour que deux employés ont en communs.
• Il faudrait utiliser l'algorithme de Ford-Fulkerson
• Ca suit la même logique que la recherche de personnes sur un réseau social en fonction de critère définis.

Par contre, le problème est le suivant :
si un employé 1 à un gros ratio avec l'employé 2 et que l'employé 2 à un gros ratio avec l'employé 3, on est pas certain que l'employé 3 est un fort ratio avec l'employé 1.

Avec 3 employés, c'est encore faisable, mais si on en a 100, il faudra refaire des dizaine de milliers de tests, non ?

[pseudocode]

Par contre, le problème est le suivant :
si un employé 1 à un gros ratio avec l'employé 2 et que l'employé 2 à un gros ratio avec l'employé 3, on est pas certain que l'employé 3 est un fort ratio avec l'employé 1.

heu... certes. Mais quel rapport avec le graph-cut ?

Avec 3 employés, c'est encore faisable, mais si on en a 100, il faudra refaire des dizaine de milliers de tests, non ?

100 employés, ca fait effectivement une matrice d'adjacence de 100*100 = 10.000 valeurs (dont sans doute pas mal de valeurs nulles). Mais ce n'est vraiment pas beaucoup pour ce genre d'algo.