Problème de correspondance stable aux problèmes typique d'optimisation de combinaison

Problème typique et méthode d'exécution

Problème de correspondance stable

Étant donné un groupe d'hommes et un groupe de femmes, les hommes ont un ordre de préférence pour les femmes et les femmes ont un ordre de préférence pour les hommes. L'appariement qui n'a pas de paire bloquante lorsqu'une paire est faite par un homme et une femme est appelé appariement stable. Une paire de blocage (m, w) est une paire d'hommes et de femmes non appariés dans un état où «w est préférable à la paire actuelle de m» et «m est préférable à la paire actuelle de w».

[Problème de correspondance stable](https://ja.wikipedia.org/wiki/%E5%AE%89%E5%AE%9A%E7%B5%90%E5%A9%9A%E5%95%8F%E9 % A1% 8C) n'est pas strictement un problème d'optimisation, mais il est inclus dans le problème typique car il s'agit d'un problème important de correspondance. Il peut être résolu efficacement par la solution Gail Shaprey.

Méthode d'exécution

usage


Signature: stable_matching(prefm, preff)
Docstring:
Problème de correspondance stable
contribution
    prefm, preff:Préférence
production
correspondant à

python


from ortoolpy import stable_matching
print(stable_matching([[2,0,1],[2,1,0],[0,2,1]], [[0,1,2],[2,0,1],[2,1,0]]))

résultat


{2: 2, 0: 0, 1: 1}

python


# pandas.DataFrame
from ortoolpy.optimization import StableMatching
StableMatching('data/stable.csv')
male female pref_male pref_female
0 0 0 1 0
4 1 1 1 2
8 2 2 1 0

Les données

Recommended Posts

Problème de correspondance stable aux problèmes typique d'optimisation de combinaison
Optimisation de combinaison - problème typique de correspondance de problème maximum
Problème de correspondance typique de problème-poids par optimisation de combinaison
Optimisation de combinaison - problème typique de problème de sac à dos
Optimisation de combinaison - problème typique de conditionnement n-dimensionnel
Optimisation de combinaison - problème typique - problème de couverture de vertex minimum
Optimisation de combinaison - problème typique d'allocation généralisé
Problème d'optimisation de combinaison-problème typique d'emballage de bac
Optimisation des combinaisons - Problème typique - Problème d'allocation secondaire
Combinaison d'optimisation-problème typique-problème de chemin le plus court
Optimisation combinée - problème typique d'enchères combinées
Optimisation de la combinaison - problème typique - problème de débit maximal
Combinaison d'optimisation-problème typique de couverture d'agrégat
Problème d'optimisation de combinaison-problème typique de placement des installations
Optimisation de la combinaison - problème typique de l'atelier de travail
Optimisation de la combinaison - problème typique - problème de coupe maximale
Optimisation de combinaison - Problème typique - Problème de vendeur circulaire
Problème d'ordonnancement de travail-problème typique d'optimisation de combinaison
Optimisation de combinaison - problème typique - problème d'arborescence de surface minimale
Combinaison optimisation-problème typique-problème d'ensemble stable maximum
Optimisation de la combinaison - problème typique - problème de flux de coût minimal
Optimisation de combinaison-problème typique-problème de livraison postale chinoise
Optimisation des combinaisons - Problème typique - Problème d'itinéraire de transport (optimisation de la livraison)
Problème d'optimisation de la combinaison - coupe minimale
Optimisation des combinaisons - Problème typique - Problème de placement des installations sans contrainte de capacité