Rezidentų paskyrimas į ligonines

Vilniaus Gedimino technikos universitetas Fundamentinių mokslų fakultetas Grafinių sistemų katedra Kursinis darbas Rezidentų paskyrimas į ligonines Atliko: Tadas Pocius IG-3 Marius Danauskas IG-3 Tikrino: prof. habil. dr. R. Baušys VGTU 2007 Įžanga Kiekvienais metais Jungtinėse Valstijose medicinos mokyklos paruošia tūkstančius daktarų galinčių atlikti rezidentūrą įvairiose šalies ligoninėse. Tam kad suteikti galimybę kiekvienam baigusiajam rasti geriausią įmanomą rezidentūrą ir ligoninėms rasti tinkamiausius rezidentus, Amerikos medikų asociacija (AMA) vykdo derinimo procesą, kuriame absolventai įvertina ligonines pagal savo pageidavimus, o ligoninės įvertina studentus pagal savo pageidavimus. Tada asociacija paskiria absolbentus į ligonines taip, kad paskyrimai yra „stabilūs“. Paaiškiname ką reiškia stabilus. Tarkime paskyrimas yra nestabilus kai absolventas i nėra priskirtas ligoninei j, bet jis labiau norėtų dirbti ligoninėje j negu ten kur yra paskirtas ir tuo pačiu metu ligoninė j labiau norėtų studento i negu to kuris jai priskirtas. Toks priskyrimas yra nestabilus, nes ir ligoninė j ir studentas i yra nepatenkinti savo paskyrimais ir norėtų juos pakeisti. O mums reikia butent stabilaus paskyrimo. To paties reikia ir AMA. Ši problema yra stabilios santuokos problemos atskiras atvejis. Uždavinio modelis Stabilios santuokos problema yra naujas dvipusių atitikmenų pritaikymas. Šią problemą galima išdėstyti taip. Tarkime konkreti bendruomenė susideda iš n vyrų ir n moterų. Kiekvienas asmuo įvertina visus priešingos lyties asmenis pagal kuriam teikia pirmenybę tapti sutuoktiniu. Toks atitikimas, moters – vyro pora laikoma nestabilia jei jie nėra susituokę, bet teikia vienas kitam didesnę pirmenybę, nei savo esamiems sutuoktiniams. Tobulas atitikimas (santuoka) laikoma stabilia, jei nėra nestabilių porų. Stabilios santuokos problema yra nustatyti tobulą stabilų atititikimą. Mes parodysime, kad bet kokiam įvertinimų rinkiniui galima sudaryti tobulą stabilų atitikimą. Įrodysime šį rezultatą konstruktyviai, apibrėždami algoritmą, kuris sudarys stabilų atitikimą per O(n2) iteracijų. Duomenys stabilios santuokos algoritmui yra dvi n × n matricos. Pirmoje matricoje surašyta kaip kiekvienas vyras vertina kiekvieną moterį, antroje – kaip kiekviena moteris vertina kiekvieną vyrą. Aukštesnis įvertinimas žymi labiau patinkantį asmenį. Neprarandant bendrumo galime sakyti, kad kiekvienas įvertinimas yra sveikas skaičius tarp 1 ir n. Tam kad efektyviai įgyvendinti algoritmą, panaudosime šias matricas sudarydami kiekvienam asmeniui vektorių iš n elementų vadimaną jo arba jos prioritetų sąrašu. Šiame sąraše surašyti priešingos lyties asmenys mažėjančia tvarka pagal tai kaip jie yra įvertinti. Kadangi visi įvertinimai yra sveiki skaičiai tarp 1 ir n, tai galime sudaryti šiuos prioritetų sąrašus per O(n) iteracijų. Algoritmas Stabilios santuokos algoritmas veikia taip. Kiekvienas vyras peršasi moteriai, kuri jam labiausiai patinka, o kiekviena moteris gaunanti daugiau nei vieną pasiūlymą, atmeta visus, išskyrus tą, kuris jai labiausiai patinka iš visų pasipiršusių. Algoritmas palaiko rinkinį – SĄRAŠĄ nepriskirtų vyrų, ir kiekvienam vyrui palaiko indeksą vadinamą esama moteris kuris žymi moterį jo prioritetų sąraše, kuriai jis pasipirš pirmiausiai. Pradžioje SĄRAŠAS lygus N1 – rinkinys visų vyrų ir kiekvieno vyro esama moteris yra pirma moteris jo prioritetų sąraše. Toliau algoritmas veikia taip. Kiekvienos iteracijos metu algoritmas parenka vyrą iš SĄRAŠO, tarkime Bilą ir jis peršasi savo esamai moteriai, tarkime Helenai. Jei Helena vis dar laisva, ji priima pasiūlymą ir Bilas su Helena yra preliminariai priskiriami vienas kitam – jie laikomi susižadėjusiais. Jei Helena yra jau susižadėjusi su kažkuo, tarkime Frenku, ji priima to pasiūlymą, kuris jai labiau patinka ir atmeta kitą. Atmestasis pažymi esama moterim sekančią moterį savo sąraše. Kai algoritmas ima vyrą iš SĄRAŠO, jis yra pašalinamas iš jo, o kai vyras yra atmetamas moters, jis grąžinamas atgal į SĄRAŠĄ. Algoritmas kartoja iteracijas tol kol SĄRAŠAS lieka tuščias – kiekvienam vyrui priskirta moteris. Šį algoritmą galima vadinti pasipiršimo ir atmetimo algoritmu. Lengva įrodyti, kad atitikimas pasiektas šiuo algoritmu yra stabilus. Tarkime, kad Diko prioritetų sąraše pirma yra Laura. Jis jai pasiperša ir ji jį atmeta, nes jai kitas vyras patinka labiau. Kadangi nei viena moteris nepasirinks vyro, kuris jai patinka mažiau, jai jos vyras patinka labiau negu Dikas. Taigi, atitikimas yra stabilus. Tam, kad išanalizuoti stabilios santuokos algoritmo sudėtingumą, pažymime, kad kiekvienos iteracijos metu kiekviena moteris gaunanti pasiūlymą arba (1) priima pirmą pasiūlymą (kas nutinka tiksliai vieną kartą kiekvienai moteriai), arba (2) atmeta kelis pasiūlymus. Kadangi kiekviena moteris atmeta bet kurio vyro pasiūlymą daugiausiai vieną kartą, antras rezultatas įvyksta daugiausiai (n - 1) kartų kiekvienai moteriai. Taigi, algoritmas įvykdo O(n) žingsnių moteriai ir O(n2) žingsnių iš viso. Pažymėtina, kad nei vieno kito algoritmo sudėtingumo ribos nėra geresnės šiai problemai spręsti, nes pasipiršimo ir atmetimo algoritmo vykdymo laikas nuo įvedamų duomenų priklauso tiesiškai. Tokiu būdu gauname rezultatą: TEOREMA Bet kokiai įvertinimų matricai sprendžiant stabilios santuokos problemą galima sudaryti stabilų atitikimą. Pasipiršimo ir atmetimo algoritmas sudaro šį atitikimą per O(n2) iteracijų. Nereikia nei sakyti, kad gali būti keli stabilūs atitikimai. Pasipršimo ir atmetimo algoritmas sudaro vieną iš tokių stabilių atitikimų. Mes kalbame apie porą (i,j) iš vyro i ir moters j kaip apie stabilius partnerius, jei vyras i stabiliai atitinka moterį j. Atitikimas sudarytas mūsų algoritmu įgyja įdomią savybę. Kiekvienas vyras jame yra bent pakankamai tinkamas kaip ir bet kuriame kitame stabiliame atitikime. Kitaip tariant kiekvienas vyras gauna gauna geriausią jam tinkančią stabilią partnerę. Akivaizdu, kad galima tokį atitikimą vadinti vyrui optimaliu atitikimu. Remdamiesi šiuo faktu gauname rezultatą: LEMA pasipiršimo ir atmetimo algoritme moteris niekada neatmeta stabilaus partnerio. Įrodymas : tarkime M* yra atitikimas sudarytas pasipiršimo ir atmetimo algoritmu. Tarkime lema yra neteisinga ir moterys atmeta stabilius partnerius. Tarkime moteris, tarkine Joana pirmą kartą atmeta sstabilų partnerį, tarkime Deivą. Tarkime M° yra stabilus atitikimas kai Joana ir Deivas sudaro stabilią partnerių porą. Tarkime atmetimas įvyko, nes Joana buvo susižadėjusi su Styvu, kuris jai patinka labiau negu Deivas. Pastebėkite, kad prieš atmetimą, nei viena moteris neatmetė stabilaus partnerio, kas reiškia, kad Styvas negali turėti stabilios partnerėskori jam patiktų labiau negu Joana. Atitikime M° leiskime Sju būti stabilia Styvo pora. Pagal mūsų ankstenį pastebėjimą Styvui labiau patinka Joana nei Sju. Anksčiau pastebėjome, kad Sju labiau patinka Styvas negu Deivas. Šie du faktai prieštarauja prielaidai, kad M° yra stabilus atitikimas. Pasipiršimo ir atmetimo algoritme vyrai peršasi moterims mažėjančio prioriteto tvarka ir kadangi nei viena moteris neatmeta stabilaus partnerio, kiekvienas vyras veda labiausiai jam patinkančią įmanomą moterį. Todėl gauname dar vieną teiginį: TEOREMA pasipiršimo ir atmetimo algoritmas sudaro vyrui optimalų stabilų atitikimą. Ši teorema yra stebinantis rezultatas. Jis parodo, kad jei duotume kiekvienam vyrui nepriklausomai geriausią stabilią partnerę, rezultatas bus stabilus atitikimas. Šį optimalumą ganame moterų sąskaita. Tiesą sakant galima įrodyti, kad vyrui optimaliu atveju moteris gauna blogiausią partnerį kokį gali gauti bet kokiame stabiliame atitikime. Programos kodas #include

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!