Algorithme hongrois et facteurs multiples

Question

J'ai parfois besoin d'assigner des personnes à plusieurs événements. Si nous avions juste un prix comme facteur, tout irait bien, mais il y a un certain nombre de facteurs qui entrent en jeu.

Tout d’abord, un peu d’arrière-plan. Ceci est pour un organisme à but non lucratif qui fait la promotion des heures de conte pour les enfants hospitalisés pour une raison quelconque, ils dépendent donc du travail bénévole pour le faire. Donc, comme ils comptent sur la bonne volonté des gens, ils donnent aux gens autant de travail que les gens peuvent / veulent faire, ce qui varie de la manière suivante:

• Certaines personnes ne peuvent faire que le matin et d'autres ne peuvent faire que l'après-midi;
• Certaines personnes ne peuvent faire que les lundis et les jeudis, d'autres ne peuvent pas y aller en août ou en décembre;
• Certaines personnes ne peuvent y aller qu'une fois par mois, d'autres 4 fois (et même d'autres personnes ont la priorité dans ces actions car elles sont plus expérimentées et peuvent le faire 10 fois par mois)

Donc, j'ai un peu compris les deux premiers. Puisque l'algorithme hongrois concerne le prix, je leur donnerais un prix stupidement élevé pour les moments où ils ne peuvent pas aller. Cependant, comment feriez-vous les autres?

J'ai pensé leur donner une sorte de score. Quelque chose dans le genre: une personne qui peut le faire une fois par mois coûte environ 1000 points. Si une personne peut y aller 10 fois par mois, elle coûte 100 points (1 000 divisant par 10). En outre, le moyen de le distribuer serait d’augmenter le prix chaque fois qu’une action distincte serait effectuée, comme cela (les personnes sélectionnées ont un * sur le coût qui leur est associé):

Première itération

         | August 1st 2009
Person A | 1000
Person B | 500 *

Deuxième itération

         | August 8th 2009
Person A | 1000 *
Person B | 1000 

Ce serait le moyen de répartir en conséquence entre toutes les personnes, en donnant plus de priorité à celles qui peuvent le faire plusieurs fois.

Qu'en penses-tu et comment le ferais-tu?

Answer 1

Il s’agit d’un problème de planification / d’optimisation. La question clé est donc de savoir quelle quantité voulez-vous maximiser? J'imagine que vous cherchez à maximiser le nombre total d'heures travaillées sur l'ensemble de vos volontaires sans heurts, sous réserve des contraintes d'horaire de chaque bénévole. Vous mentionnez également la priorité donnée aux volontaires les plus expérimentés. Il semble donc que vous dites que "certains volontaires sont préférés par rapport à d'autres".

C’est alors un problème de correspondance bipartite classique. Voir par exemple p.498 de Manuel de conception d'algorithmes (2e éd.), de Steven Skiena. L'approche de base consiste à construire un graphique avec des sommets représentant à la fois l'ensemble des volontaires et l'ensemble des créneaux horaires que vous essayez de remplir. Les bords relient les volontaires aux créneaux horaires valides. La solution optimale est alors le plus grand ensemble possible d’arêtes où aucun créneau volontaire ou de temps n’est répété. Ceci est une correspondance.

Certains de vos volontaires pourront peut-être occuper plus d’une place. cela peut être modélisé en répliquant ce sommet volontaire plusieurs fois.

Si vous souhaitez mettre en œuvre la définition des priorités des volontaires, cela ajoute une pondération à chaque bord, en présentant l'expérience de ce volontaire pour cette tâche. Dans ce cas, comme vous le pensiez, vous aurez besoin de quelque chose comme l'algorithme hongrois. Si vous pouvez vous en passer, vous pouvez transformer le problème en un graphe de flux équivalent, et appliquer un algorithme de flux de réseau. Voici un exemple de code implémentant à la fois les correspondances pondérée et non pondérée .

Si vous souhaitez plus de détails, y compris d’autres alternatives, et plus de liens vers des implémentations, je vous recommande vivement de vous procurer une copie du manuel de conception d’algorithmes, c’est une référence étonnamment claire et pratique.