Tanulmányunkban a frissen végzett orvostanhallgatók/leendő rezidensek hatékony beosztásának problémáját vizsgáltuk. Ez egy gyakorlatban is rendkívül releváns probléma, hiszen számos országban központi mechanizmusok bonyolítják le ezt a feladatot, többek közt az USA-ban, Kanadában és Japánban is. A feladat egy fontos tulajdonsága, hogy a kapcsolódó piac (kórházak és leendő rezidensek) mindkét osztálya rendelkezik preferencia listákkal a lehetséges kimeneteleken, amiket figyelembe kell vennünk az igazságosság érdekében. A rezidenseknél ez azt jelenti, hogy megadhatják, hogy mely kórházi pozíciókat tartják elfogadhatónak, illetve hogy ezek között melyiket szeretnék legjobban, második legjobban, stb. A kórházaknál pedig a preferenciák a hozzájuk jelentkező hallgatókat rangsorolják valamilyen sorrendben.
Az igazságosság garantálásaként az egyik fő elvárás ezekben a programokban, hogy a talált megoldás stabil legyen, ami azt jelenti, hogy ne legyen olyan rezidens-kórház pár, hogy mind a rezidens jobban kedveli a kórházat, mint ahová osztottuk (vagy nem osztottuk szegényt sehova sem) és a kórháznak is vagy van üres helye, vagy jobban kedveli a rezidenst, mint valamelyik hozzá osztott másik hallgatót. Alapesetben ez egy jól ismert, úgynevezett stabil párosítási feladathoz vezet, melyet hatékonyan és egyszerűen meg lehet oldani. Mióta a rezidensek között házaspárok is részt vehetnek a programokban, akik együttes jelentkezéseket adhatnak be kórházpárokhoz – például mert azt szeretnék, hogy földrajzilag közeli kórházakban helyezkedhessenek el – matematikailag rendkívül bonyolulttá, méghozzá NP-nehézzé válik a stabil megoldások keresése, mely durván fogalmazva annyit jelent, hogy nagyon valószínű, hogy nem létezik rá gyors algoritmus. Ez még olyan rendkívül speciális esetekben is igaz, mint például amikor minden preferencia lista csak legfeljebb 2 hosszú. Ennek a nehézségnek a leküzdéseként a jelenlegi szoftverek főleg heurisztikákat használnak, melyek, bár eddig meglepően jól működtek, azonban a futásidejükre nincs matematikai garancia.
⮚ Tovább a teljes cikkre
Címlapkép forrása: Shutterstock
