férfiak és nők.férfi szabad, és minden nő elérhető.férfiak iteratívan ajánlatot tesznek preferenciarangsoruk szerint a nőknek:
nő szabad, elfogadja az ajánlatot.nő már el van foglalva, összehasonlítja az új ajánlattevőt a jelenlegi partnerével, és a preferencia alapján dönt:
function GaleShapley(men, women):
Minden férfi legyen szabad.
Minden nő legyen szabad.
amíg van olyan férfi, aki szabad és még nem tett ajánlatot az összes nőnek:
válassz egy ilyen férfit (férfi).
válaszd ki a következő nőt a preferencialistájáról, akinek még nem tett ajánlatot.
ha a nő szabad:
párosítsd a férfit és a nőt.
különben:
ha a nő előnyben részesíti az új férfit a jelenlegi partnerével szemben:
a nő elutasítja a jelenlegi partnerét.
párosítsd a férfit és a nőt.
különben:
a nő elutasítja a férfit.
térj vissza a párosításokkal.
def gale_shapley(men_preferences, women_preferences):
free_men = list(men_preferences.keys()) # Kezdetben minden férfi szabad
proposals = {man: for man in men_preferences} # Nyomon követjük, ki kinek tett ajánlatot
engagements = {} # A jelenlegi párosítások
while free_men:
man = free_men # Vegyük a következő szabad férfit
man_pref = men_preferences
# Találjuk meg a következő nőt, akinek még nem tett ajánlatot
for woman in man_pref:
if woman not in proposals:
proposals.append(woman)
if woman not in engagements: # Ha a nő szabad
engagements = man
free_men.pop(0) # A férfi most már foglalt
break
else:
current_partner = engagements
woman_pref = women_preferences
# Ha a nő előnyben részesíti az új férfit a jelenlegivel szemben
if woman_pref.index(man) < woman_pref.index(current_partner):
engagements = man
free_men.pop(0) # A férfi most már foglalt
free_men.append(current_partner) # A korábbi partner most szabad
break
return engagements
# Példa használat
men_preferences = {
"A": ,
"B": ,
"C":
}
women_preferences = {
"X": ,
"Y": ,
"Z":
}
result = gale_shapley(men_preferences, women_preferences)
print("Párosítások:", result)
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
// Segédfüggvény: Megadja egy nő preferencialistájában a férfi helyét
int getPreferenceRank(vector<int>& preferences, int man) {
for (int i = 0; i < preferences.size(); i++) {
if (preferences == man) {
return i;
}
}
return -1;
}
unordered_map<int, int> galeShapley(
unordered_map<int, vector<int>>& menPreferences,
unordered_map<int, vector<int>>& womenPreferences
) {
unordered_map<int, int> engagements; // Nők és férfiak párosításai
unordered_map<int, bool> freeMen; // Szabad férfiak
unordered_map<int, vector<int>::iterator> nextProposal; // Következő ajánlat nőknek
// Kezdetben minden férfi szabad
for (auto& man : menPreferences) {
freeMen = true;
nextProposal = menPreferences.begin();
}
while (true) {
int freeMan = -1;
for (auto& man : freeMen) {
if (man.second) {
freeMan = man.first;
break;
}
}
if (freeMan == -1) break; // Minden férfi foglalt
int woman = *nextProposal; // Következő nő, akinek ajánlatot tesz
nextProposal++;
if (engagements.find(woman) == engagements.end()) {
engagements = freeMan; // A nő elfogadja az ajánlatot
freeMen = false;
} else {
int currentMan = engagements;
auto& womanPreferences = womenPreferences;
if (getPreferenceRank(womanPreferences, freeMan) < getPreferenceRank(womanPreferences, currentMan)) {
engagements = freeMan; // A nő elutasítja a jelenlegi partnert
freeMen = false;
freeMen = true; // Az előző partner most szabad
}
}
}
return engagements;
}
int main() {
unordered_map<int, vector<int>> menPreferences = {
{1, {1, 2, 3}},
{2, {2, 1, 3}},
{3, {1, 2, 3}}
};
unordered_map<int, vector<int>> womenPreferences = {
{1, {1, 2, 3}},
{2, {2, 1, 3}},
{3, {1, 2, 3}}
};
auto result = galeShapley(menPreferences, womenPreferences);
cout << "Párosítások:" << endl;
for (auto& pair : result) {
cout << "Nő " << pair.first << " - Férfi " << pair.second << endl;
}
return 0;
}
A Gale-Shapley-algoritmus hatékony megoldást nyújt a stabil párosítás problémájára, garantáltan stabil párosítást talál, és időbonyolultsága (O(n^2)), ahol (n) a résztvevők száma. Ezért jól alkalmazható kisebb méretű problémák esetén, például egyetemek és diákok párosítására vagy munkavállalók és munkáltatók megfelelő párosítására.