laurent.sexy

Ma compréhension de l'histoire.

Peut on tester toutes les combinaisons ? Voici un algo pour tout tester : on regarde toutes les configuration pour job1, puis job2, puis job3, etc... Et on note le meilleur truc qu'on a eu.

jobs_dispo = List< Jobs > for e in employes: for j in e.give: jobs_dispo.append(j) count_give_occupied(schedule) { count = 0 for job, employe in schedule: if employe.wish.contains(job): count += 1 return count } best_schedule(schedule_1,schedule_2) { // il peut y avoir plusieur critères comme compter le nombre de give restant // TODO : vérifier si c'est stupide g1 = count_give_occupied(schedule_1) g2 = count_give_occupied(schedule_2) if g1 > g2 : return schedule_1 else : return schedule_2 } algo(schedule,job_index) { // cas terminal : il n'y a plus d'échanges à considérer if job_index == jobs_dispo.size : return schedule // cas non terminal for e1 in employes: schedule_new_1 = schedule.copy() // on va tester un nouveau schedule // cas 1 : e1 essaye de prendre le job current_job = jobs_dispo[job_index] e2 = schedule_CFF[current_job] // l'employé qui a le job if e2.give.has(current_job): // si e2 est d'accord de donner. Ce test est nécessaire // car e2 pourrait avoir obtenu le job par un échange précédent if compatible(schedule): // vérifier que la transaction est valide // car plusieurs wish peuvent être incompatibles schedule_new_1[job] = e1 // e1 prend le job // le job reste dans e1.wish // et n'apparait pas dans e1.give schedule_new_1 = algo(schedule_new_1,job_index+1) else // si e1 n'a pas le choix, alors il n'y a qu'une issue possible return algo(schedule_new_1,job_index+1) schedule_new_2 = schedule.copy() // on va tester un nouveau schedule schedule_new_2 = algo(schedule_new_1,job_index+1) return best_schedule(schedule_new_1,schedule_new_2) } awesome_schedule = algo(schedule_CFF)

Cet algo est bourrin, mais si je ne me trompe pas, parcourt tous les cas possibles d'échanges, et retourne le meilleur, où on a défini meilleur comme étant le schedule qui prend en compte un nombre maximum d'échanges.

Le critère "meilleur" peut être amélioré en disant qu'on veut aussi être égalitaire et maximiser la satisfaction individuelle. Ça peut se faire en ajoutant une pénalité qui augmente lorsque qu'il y a déséquilibre de satisfaction où on définit satisfaction comme satisfaction(employe) = employe.keep.size - employe.give_non_donnés.size

Cette déviation peut être vue comme ([satisfaction(e) for e in employes]).std(), ou une autre fonction qui pénalise encore plus à la moindre inégalité tel que ([satisfaction(e) for e in employes]).min()

On peut faire des échanges 1v1

exchange(employe1,employe2) { inter_1_vers_2 = interesection(employe2.wish,employe1.give) inter_2_vers_1 = interesection(employe1.wish,employe2.give) // TODO : il faut aussi vérifier la compatibilité, // on ne peut pas accepter tous les jobs. // On peut prendre une option au hasard parmis // ce qui est possible ou assigner un score pour // choisir le meilleur choix. employe1.wish.remove(inter_1_vers_2) employe2.wish.remove(inter_2_vers_1) employe1.keep.add(inter_2_vers_1) employe2.keep.add(inter_1_vers_2) }

Puis faire une loop

algo() { for employe1 in employes: for employe2 in employes: exchange(employe1,employe2) }

Mais ça va favoriser les premiers qui ont plus de choix (les derniers n'ont que les miettes).

On pourrait prendre toutes les paires possibles, et les mélanger, ou simplement y aller bourrin en prenant des paires au pif parmis les employés qui ont encore qqch à wish ou give

pool = employes.copy() algo() { while (critère_d_arrêt) { employe1 = pool.pick_at_random() employe2 = pool.pick_at_random() exchange(employe1,employe2) if employe1.wish.size == 0 and employe1.give.size == 0 : pool.remove(employe1) if employe2.wish.size == 0 and employe2.give.size == 0 : pool.remove(employe2) } }

On peut gagner en perf en disant qu'il y a des gens qui ont envie de donner ou recevoir, comme ça on évite les échanges entre des employés qui ne seraient que donneur, ou que receveur.

pool_give = employes.copy() // au début tout le monde est giver et wisher pool_wish = employes.copy() // au début tout le monde est giver et wisher algo() { while (critère_d_arrêt) { wisher = pool_wish.pick_at_random() giver = pool_give.pick_at_random() exchange(pool_wish,pool_give) if giver .give.size == 0 : pool_give.remove(giver) if wisher.wish.size == 0 : pool_wish.remove(wisher) } }

À noter qu'il est quasi-sûr que si le nombre de configuration idéale est rare, on va les louper et rester sur un optimum local. Mais ça a l'avantage de trouver une solution rapidement.

Peut on améliorer ce truc d'optimum local ? Je pense que oui avec une approche "trading". Chaque employé annonce publiquement ce qu'il a à donner, puis il va acheter ce qui lui convient.

init_marché() { marché = List< Pair< Jobs, Employe> > // pour retrouver notre vendeur en cas d'achat for e in employes: for j in e.give: marché.append({j,e}) return marché } marché = init_marché() acheteurs = employés.filter( e => e.wish.size != 0 ) // seulement les gens qui veulent acheter buy(marché,acheteur,job) { marché.remove(job) } algo() { while (critère_d_arrêt) { acheteur = acheteurs.pick_at_random() // disons un seul achat par tour, pour permettre une chance à tout le monde while true: // peut être que des trucs de la wish list ont été achetés entre temps j = acheteur.wish.pick_at_random() if not marché.has(j): acheteur.wish.remove(j) // ce wish ne sera jamais exhausé // remark : si on dit qu'un job peut retourner dans le marché // alors on ne devrait pas le remove, à la place // on peut parcourir acheteur.wish dans un ordre // aléatoire prédéfini else: // TODO : check compatibilité sur l'assomption que les jobs // sur le marché ne sont pris par personne buy(marché,acheteur,j) } }

Et si à la fin il ne reste des jobs incompatibles, on peut les rendre aux personnes qui y étaient assignés à la base, puis relancer un mega-trade.

Et si la situation finale fait que des gens sont super lésés alors que d'autres super avantagés, on peut faire une restitution aléatoire, ou alors des perquisitions de job chez les plus satisfaits pour compenser les gens le plus lésés.

Par ailleurs, cette analogie de marcé peut servir d'heuristique : par ex utiliser un équivalent de l'argent pour gérer les trades :
- prix = nombre d'heure du job ; budget = nombre d'heure de job qu'il vend
- prix = augmente avec la satisfaction (pour mettre en priorité ceux qui sont les plus lésés)

for a in acheteurs: a.budget = ... // on pourrait faire un truc avec ça éventuellement buy(marché,acheteur,job) { if acheteur.budget >= job.price: marché.remove(job) acheteur.budget -= job.price }