Gale-Shapleyev algoritem

Iz MaFiRaWiki

Vsebina


Ozadje

Z Gale-Shapleyevim algoritmom rešujemo (matematični) problem stabilnih porok:

Podanih imamo n moških in n žensk. Vsak/-a izmed njih je ocenil/-a vse osebe nasprotnega spola tako, da jim je podelil/-a vsa števila od 1 do n v vrstnem redu padajoče všečnosti.
Želimo medsebojno poročiti vse moške in ženske tako, da na koncu ne bo moškega in ženske, ki si oba želita eden drugega bolj, kot pa svoja podeljena partnerja. Če nam to uspe, so poroke stabilne.

D. Gale in L. S. Shapley sta l. 1962 dokazala, da je vedno mogoče rešiti problem stabilnih porok tako, da so vse poroke stabilne, za poljubno enako število žensk in moških ter predstavila algoritem, ki to stori.

Opis algoritma

Algoritem poteka v t.i. krogih. Vsak od njih sestoji iz dveh delov: dejanj moških ter dejanj žensk:

  • Vsak moški "prosi za roko" žensk po padajočem redu všečnosti.
    Ko se zaroči, preneha s prošnjami.
    Če zaročenka razdre zaroko, nadaljuje s prošnjami od tam, kjer je ostal.
  • Vsaka ženska čaka na ponudbo nekega snubca.
    Sprejme prvo ponudbo, ki jo dobi.
    Če je že zaročena z moškim m, snubi pa jo boljši moški m', razdre zaroko z m in se zaroči z m'.

Vsaka sprememba zaročenca ženske poveča njeno zadovoljstvo. Vsaka sprememba zaročenke moškega zmanjša njegovo zadovoljstvo.

Shema algoritma

metoda stabilnePoroke{
    nastavi vse m\inM in ž\inŽ na proste

    dokler \exists prost moški m, ki še ima žensko ž za snubit{
        ž = m-jeva najvišje uvrščena taka ženska
        če je ž prosta
            zarôči (m, ž)
        sicer nek par (m', ž) že \exists
            če ima ž raje m kot m'
                (m, ž) se zaročita
                m' postane prost
            sicer
                (m', ž) ostaneta zaročena
    }
}

Uporaba v praksi

Gale in Shapley nista bila prva, ki sta si zamislila in v praksi uporabila algoritem, ki se po njima imenuje. Sta pa do njega prišla neodvisno in prva dokazala, da obstaja pomembno matematično ozadje, ki določa izid algoritma. V Ameriki je bil Gale-Shapleyev model v praktični uporabi že od l. 1952 (takrat še brez imena) za namen uvrščanja študentov medicine v posamezna bolnišnična dela na podlagi ocen študentov s strani bolnic in ocen bolnic s strani študentov. Danes je izboljšana različica sistema znana pod imenom National Resident Matching Program.

Gale-Shapleyev algoritem je uporaben povsod, kjer na dveh množicah enake moči rešujemo problem stabilnega popolnega prirejanja na podlagi prednostnih seznamov. Algoritem je implementiran tudi v programskem jeziku Mathematica.

Glej tudi

Osebna orodja