Algorithme de répartition

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.

Citation:

---

Envoyé par molini_a

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".

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 ?:ccool:

Citation:

---

Envoyé par molini_a

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 ? :koi:

Citation:

---

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

---

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.