Wikiszótár

Gale-Shapley-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈɡɒlɛʃhɒplɛiɒlɡoritmuʃ]

Főnév

Gale-Shapley-algoritmus

  1. (matematika) A Gale-Shapley-algoritmus (más néven stabil házasság problémája) egy algoritmus, amely két egyenlő méretű halmaz elemei között talál stabil párosítást az egyes elemek preferenciarangsorai alapján. Egy stabil párosítás azt jelenti, hogy nincs olyan két elem, akik kölcsönösen előnyben részesítenék egymást a jelenlegi párosításuk helyett.


Elméleti leírás

  1. Probléma megfogalmazása:
    • Két halmaz van: például férfiak és nők.
    • Mindegyik elemnek van egy preferencialistája, amely rangsorolja a másik halmaz elemeit.
    • Az algoritmus célja, hogy olyan párosítást találjon, ahol nincs “blokkoló pár” (két olyan elem, akik kölcsönösen előnyben részesítenék egymást a jelenlegi párosításukkal szemben).
  2. Algoritmus működése:
    • Kezdetben minden férfi szabad, és minden nő elérhető.
    • A férfiak iteratívan ajánlatot tesznek preferenciarangsoruk szerint a nőknek:
      • Ha egy nő szabad, elfogadja az ajánlatot.
      • Ha egy nő már el van foglalva, összehasonlítja az új ajánlattevőt a jelenlegi partnerével, és a preferencia alapján dönt:
        • Ha az új ajánlattevő előnyösebb, elutasítja a jelenlegi partnerét, és az új ajánlattevőt választja.
        • Ha az új ajánlattevő kevésbé előnyös, elutasítja őt.
    • Ez folytatódik, amíg mindenki párba nem kerül.
  3. Az algoritmus garantáltan véget ér, és az eredmény stabil párosítás lesz.


Pszeudokód

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.

Python implementáció

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[0]  # Vegyük a következő szabad férfit
        man_pref = men_preferences[man]

        # 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[man]:
                proposals[man].append(woman)
                if woman not in engagements:  # Ha a nő szabad
                    engagements[woman] = man
                    free_men.pop(0)  # A férfi most már foglalt
                    break
                else:
                    current_partner = engagements[woman]
                    woman_pref = women_preferences[woman]
                    # 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[woman] = 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": ["X", "Y", "Z"],
    "B": ["Y", "X", "Z"],
    "C": ["X", "Y", "Z"]
}

women_preferences = {
    "X": ["A", "B", "C"],
    "Y": ["B", "A", "C"],
    "Z": ["A", "B", "C"]
}

result = gale_shapley(men_preferences, women_preferences)
print("Párosítások:", result)

C++ implementáció

#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[i] == 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[man.first] = true;
        nextProposal[man.first] = menPreferences[man.first].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[freeMan]; // Következő nő, akinek ajánlatot tesz
        nextProposal[freeMan]++;

        if (engagements.find(woman) == engagements.end()) {
            engagements[woman] = freeMan; // A nő elfogadja az ajánlatot
            freeMen[freeMan] = false;
        } else {
            int currentMan = engagements[woman];
            auto& womanPreferences = womenPreferences[woman];
            if (getPreferenceRank(womanPreferences, freeMan) < getPreferenceRank(womanPreferences, currentMan)) {
                engagements[woman] = freeMan; // A nő elutasítja a jelenlegi partnert
                freeMen[freeMan] = false;
                freeMen[currentMan] = 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;
}

Összegzés

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.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Gale-Shapley-algoritmus&oldid=3480142”