En 1962, D. Gale et L. S. Shapley ont soulevé la question du mariage stable. Chaprey a reçu le prix Nobel d'économie en 2012 pour cette série de réalisations.
Le problème du mariage stable est le suivant. (De Wikipedia)
Un exemple de problème de mariage stable consiste en N hommes et N femmes, et une liste de souhaits pour chaque individu. La liste de souhaits est une liste dans laquelle tous les sexes opposés sont classés dans l'ordre complet en fonction des préférences de chaque individu. La solution au problème du mariage stable est l'appariement stable. Pour l'exemple du problème du mariage stable Une paire que vous aimez plus que l'autre personne que vous formez actuellement (ci-après appelée paire de blocage) Une correspondance qui n'existe pas est appelée correspondance stable.
Le problème du mariage stable est un type de problème d'appariement stable, et le problème d'appariement stable est largement utilisé, comme l'affectation de médecins stagiaires aux hôpitaux et les étudiants universitaires aux laboratoires. L'affectation des stagiaires est utilisée aux États-Unis depuis 1950 environ et a récemment commencé à être utilisée au Japon.
Le problème de correspondance stable est résolu par [stable_matching] de ortoolpy de Python (http://qiita.com/Tsutomu-KKE@github/items/2ec5f7626054f4b4de63) peut faire. Essayons-le.
stable_matching de ortoolpy ne peut être résolu que lorsque le nombre de stagiaires et de cessionnaires est le même. Ici, si le nombre de destinations acceptables A est 2, créons un mannequin de la destination d'affectation telle que la destination d'affectation A_0 et la destination d'affectation A_1 et les associons. Définissez une méthode stable_matching2 qui résout un tel problème de correspondance stable étendu.
python3
from itertools import accumulate
from ortoolpy import stable_matching
def stable_matching2(prefs, prefl, capa):
"""
Correspondance asymétrique
prefs:Préférence pour le lieu d'affectation du stagiaire
prefl:Préférence pour les stagiaires(Toutes les affectations ont la même préférence)
capa:Nombre acceptable de cessionnaires
"""
acca = list(accumulate([0] + capa[:-1])) #Nombre acceptable cumulatif
idx = [i for i, j in enumerate(capa) for _ in range(j)] #Destination d'affectation factice → Liste de conversion de destination d'affectation
prefs = [[j+acca[i] for i in pr for j in range(capa[i])] for pr in prefs] #Sélection factice
res = stable_matching([prefl] * len(prefl), prefs)
return{k:idx[v] for k, v in res.items()} #Remettre le mannequin à l'original
Créez une question au hasard.
python3
lab_capa = [2, 3, 3, 2] #Nombre acceptable de cessionnaires
ns, nl = sum(lab_capa), len(lab_capa) #Nombre de stagiaires et nombre de missions
import numpy as np
np.random.seed(1)
def shuffled(n):
"""0..n-Mélanger et retourner 1"""
a = np.arange(n)
np.random.shuffle(a)
return a.tolist()
performance = shuffled(ns) #Préférence pour les stagiaires
preferences = [shuffled(nl) for i in range(ns)] #Préférence pour le lieu d'affectation
print(performance)
print(preferences)
>>>
[2, 9, 6, 4, 0, 3, 1, 7, 8, 5]
[[2, 0, 1, 3], [3, 0, 1, 2], [3, 1, 2, 0], [3, 1, 0, 2], [1, 3, 2, 0],
[3, 0, 2, 1], [3, 2, 1, 0], [1, 0, 2, 3], [0, 3, 1, 2], [2, 0, 3, 1]]
Résolvez et affichez le résultat.
python3
res = stable_matching2(preferences, performance, lab_capa)
for k, v in res.items():
print('interne en médecine%d ->Assigné à%d'%(k,v))
>>>
Stagiaire 0->Attribué à 2
Stagiaire 1->Attribué à 0
Stagiaire 2->Attribué à 3
Stagiaire 3->Attribué à 1
Stagiaire 4->Attribué à 1
Stagiaire 5->Attribué à 2
Stagiaire 6->Attribué à 3
Stagiaire 7->Attribué à 1
Stagiaire 8->Attribué à 0
Stagiaire 9->Attribué à 2
Le problème d'appariement stable est un problème qui recherche l'appariement sans bloquer les paires, et ce qui nous importe, c'est la valeur relative de l'ordre de préférence. Si la préférence est une valeur absolue en premier lieu, cela devient un problème de correspondance de poids du problème d'optimisation de combinaison.
La valeur absolue est, par exemple, le temps de trajet entre le domicile du stagiaire et le lieu d'affectation. A ce moment, le problème de la minimisation du temps de trajet total de tous les stagiaires est un problème d'appariement de poids qui peut être résolu par la méthode Edmonds ou autre.
La solution du problème d'appariement de poids est l'appariement stable, mais la solution du problème d'appariement stable n'est pas toujours la solution optimale du problème d'appariement de poids.
Après tout, cela ressemble à ceci:
Vous pouvez penser aux poids probables → Problème d'appariement des poids Le poids exact est inconnu, mais l'ordre est connu → Problème d'appariement stable
référence En savoir plus sur l'amour tout en résolvant le problème du mariage stable et en présentant la programmation Haskell c'est tout
Recommended Posts