Algorithme d'optimisation d'attribution

Bonjour a tous,

Je suis d'avance désolé si mon sujet est déjà traité quelque part mais je n'ai pas trouvé de réponse a ma question pour l'instant.

Je ne suis pas un grand connaisseur en algorithme ni en développement mais j'ai quelques petites bases, j'aimerai avoir des pistes de réflexions pour résoudre mon problème ( ou la solution si possible :p)

Je posséde deux listes:
- une liste de 150 personnes
- une liste de 150 objets

Je veux attribuer un et un seul objet à chaque personne.
Chaque personne remplit une liste de vœux ordonné (de 1 à 10 par exemple)

Je cherche à trouver la répartition objet/personne qui minimisera le rang moyen de l'objet attribué, autrement dit je cherche a trouver la répartition qui stratifiera au mieux chaque personne

Je ne pense pas qu'il faille s'orienter vers une solution qui teste chaque combinaison et qui prenne celle dont la moyenne est la plus petite (beaucoup trop de combinaisons possibles 150! si je ne me trompe ?)

Avez vous des pistes ?

Merci d'avance

Citation:

---

Envoyé par Perc0

Je cherche à trouver la répartition objet/personne qui minimisera le rang moyen de l'objet attribué, autrement dit je cherche a trouver la répartition qui stratifiera au mieux chaque personne

---

C'est un problème d'optimisation combinatoire, et plus particulièrement un problème d'affectation (Assignment problem).

L'algorithme "hongrois" permet par exemple de résoudre ce genre de problème.



PS: Si tu cherches du stratifié, je te conseille saint-maclou ou castorama. :P

arg mauvaise correction orthographique :)

je me renseigne avec ta réponse, je reviens vers vous si j'ai besoin de plus d'aide :)

merci