Bonjour,
J'ai une problématique assez simple.
J'ai N entités (E) que je souhaite distribuer dans N positions (P), en fonction des préférences des entités pour des positions.
Chaque entité est unique
Chaque position est unique.
Chaque entité doit être affectée à une (et une seule) position
(et chaque position ne peut se voir attribuer qu'une et une seule entité)
J'ai une répartition de base "aléatoire".
Typiquement E1 dans P1, E2 dans P2 etc
Pour chaque couple entité / position, j'ai une valeur de préférence.
Je voudrais trouver la solution optimale qui maximise les préférence des entités (de manière globale)
Par ex voici mes données de départ
E1 - P1 - 10
E1 - P2 - 5
E1 - P3 - 6
...
E1 - Pn - X
...
En - Pn
etc pour chaque couple E/P
(qui peuvent aussi se présenter sous une matrice de taille NxN)
Autrement dit sur les 3 lignes présentées l'entité E1 préfère la position P1 (10), puis la position P3 (6) puis P2 (5)
J'ai une matrice de coûts de transition qui dit que quand on enlève E1 de P1, ça lui fait perdre X points (en l’occurrence 10) et ça luis fait gagner 5 points (si on la met en P2) ou 6 points si on la met en P3.
(et donc quand on mettra une autre entité En en P1 celle ci perdra ses points de la position n pour gagner ceux de la position 1)
Voilà à peu près où j'en suis de la problématique, sachant que je pense programmer ça en C++, avec idéalement un algorithme pas trop gourmand en temps d'exécution, même si je ne compte pas appliquer à plus de N=10 (ce qui en l’occurrence représente quand même 3.628.800 arrangements possibles)
Je me doutes qu'il doit exister des algorithme pour cette problématique mais je ne trouve pas
L'option de dénombrer toutes les possibilités et de calculer la somme des coûts est une option, mais est-ce vraiment efficace ( ? )
Si vous avez des commentaires ou des sources à partager, je vous en serai reconnaissant
Merci
-----