Stabiilse sobitamise probleem

Allikas: testwiki
Mine navigeerimisribale Mine otsikasti

Stabiilse sobitamise probleem on matemaatikas, majandusteaduses ja informaatikas esinev probleem, kus tuleb kahe ühesuuruse grupi vahel moodustada paarid nii, et tekkinud sobitus oleks stabiilne ehk ei esineks olukorda, kus

  1. esimeses grupis leidub element A, mis eelistab endaga sobitatud elemendile elementi B teisest grupist, ja
  2. element B eelistab endaga sobitatud elemendile elementi A.

Stabiilse sobitamise probleemi sõnastasid 1962. aastal USA matemaatikud ja majandusteadlased David Gale ja Lloyd Shapley, kes esitasid probleemile ka lahenduse: Gale'i-Shapley algoritmi.[1]

Ajalugu

David Gale
Lloyd Shapley

1962. aastal avaldasid USA matemaatikud ja majandusteadlased David Gale ja Lloyd Shapley ajakirjas American Mathematics Monthly artikli "Vastuvõtud kolledžitesse ja abielu püsivus". Nad sõnastasid stabiilse sobitamise probleemi ning pakkusid sellele välja lahenduse Gale'i-Shapley algoritmi näol. Lisaks tõid nad välja, et isegi stabiilne sobitus võib soosida üht osapoolt.[1]

2012. aastal anti Shapleyle ja Alvin Rothile Nobeli majandusauhind "stabiilse jaotuse teooria ja turu planeerimise ellurakendamise eest".[2] Roth on stabiilse sobitamise probleemi ja Gale'i-Shapley algoritmi printsiipe käsitlenud keskkoolidesse kandideerimise[3], meditsiiniüliõpilaste residentuuri määramise[4][5] jaelundidoonorite patsientidega sobitamise[6] võtmes.

Teooria

Gale ja Shapley sõnastasid probleemi järgnevalt[1]: Mall:Cquote

Valdkonnad

1952. aastal loodi USAs meditsiiniüliõpilaste residentuuri määramiseks programm NRMP (National Resident Matching Program). Selle tarbeks lõid John Stalknaker ja F. J. Mullen IBM-i seadmetele kirjutatud algoritmi, mis võttis arvesse nii haiglate kui ka üliõpilaste vastastikuseid eelistusi.[7] 1984. aastal näitas Roth, et süsteemi teoreetilised alused olid samad, mis Gale'i ja Shapley kaheksa aastat hiljem avaldatud artiklis, ning 1999. aastal täiendas süsteemi, tagamaks stabiilseid sobitusi ka juhul, kui arvesse võtta abielupaaride soovi töötada lähestikku.[5][8]

Gale ja Shapley toovad oma artiklis "Vastuvõtud kolledžitesse ja abielu püsivus" näiteks kolledžitesse kandideerimise.[1] 2003. aastal võttis NYCDOE (New York City Department of Education) õpilaste New Yorgi keskkoolides jaotamiseks kasutusele uue, Gale'i-Shapley algoritmist lähtuva ning õpilasi soosiva süsteemi.[3]

Stabiilse sobitamise probleemina käsitletakse ka kasutajate sobitamist veebiserveritega. Kasutaja eelistusjärjekord kujuneb serveri läheduse põhjal ja serveri eelistusjärjekord kujuneb kasutaja ressursinõudlikkuse (jõudlus, mälu, signaali ribalaius) põhjal.[9]

Vaata ka

Viited

Mall:Viited

  1. ↑ 1,0 1,1 1,2 1,3 Viitamistõrge: Vigane <ref>-silt. Viide nimega g&s on ilma tekstita.
  2. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega 8ptjA on ilma tekstita.
  3. ↑ 3,0 3,1 Viitamistõrge: Vigane <ref>-silt. Viide nimega roth on ilma tekstita.
  4. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega WwVTT on ilma tekstita.
  5. ↑ 5,0 5,1 Viitamistõrge: Vigane <ref>-silt. Viide nimega roth1 on ilma tekstita.
  6. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega 58Dk9 on ilma tekstita.
  7. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega aF8jX on ilma tekstita.
  8. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega monrk on ilma tekstita.
  9. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega Mos3V on ilma tekstita.
Pärit leheküljelt "https://et.wiki.beta.math.wmflabs.org/w/index.php?title=Stabiilse_sobitamise_probleem&oldid=1298"