felvi.hu


A magyarországi felvételi besoroló algoritmusok rövid bemutatása

2008.10.10

Az alábbiakban közzétesszük a nemrég elvégzett, hazai felvételi algoritmusokat érintő kutatás összefoglalóját. A cikket a kutatást végző hazai matematikusok, vagyis Dr. Biró Péter, a University of Glasgow (Department of Computing Science, Számítástudományi Tanszék) és Dr. Fleiner Tamás, Budapesti Műszaki és Gazdaságtudományi Egyetem (Számítástudományi és Információelméleti Tanszék) kutatója készítették.

Magyarországon a középiskolai és a felsőoktatási felvételi eljárások koordinációja központosított rendszereken keresztül valósul meg. A programok alapvető célja a jelentkezők és az iskolák igényeinek egyaránt megfelelő, "igazságos" megoldások szolgáltatása. Ezek kiszámítása speciális párosító algoritmusok segítségével történik. A következő rövid összefoglalóban bemutatásra kerül az implementált alapalgoritmus elméleti háttere, főbb gyakorlati alkalmazásai, illetve a hazai rendszerek sajátosságai.

 

Elméleti háttér: stabil párosítások

 

A felvételi probléma alapmodelljében a szereplőket nevezzük egyszerűen diákoknak és iskoláknak. Tegyünk fel, hogy minden diák rangsorolja azon iskolákat, ahová jelentkezni szeretne. Ugyanígy, minden iskola sorrendet állít fel a hozzá jelentkező és alapszintet elérő diákok között, illetve megadja a keretszámát, amelynél több diákot nem kíván felvenni. A felvételi probléma megoldása egy párosítás, amelyben mindegyik diák legfeljebb egy helyre van felvéve és semelyik iskola nem lépi túl a keretszámát.

 

Milyen megoldást tekinthetünk "igazságosnak"?

 

Gale és Shapley 1962-ben publikált cikkében ["College admissions and the stability of marriage", American Mathematical Monthly, 69:9-15] az igazságosság alapfeltételeként definiálják a stabilitást. Egy párosítást stabilnak nevezünk, ha bármelyik össze nem párosított diák-iskola párt tekintve a következő indokok egyike biztosan teljesül: vagy a diák lett felvéve egy számára kedvezőbb helyre, vagy az iskola töltötte fel a keretszámát jobb diákokkal. A cikk szerzői egy igen természetes mechanizmust adtak a stabil megoldás létezésének bizonyítására.

Gale-Shapley algoritmus: Az eljárás első körében minden diák adja be a jelentkezését a rangsorán szereplő első helyre. Ezután minden olyan iskola, amelyik túl sok jelentkezést kapott, tartson meg annyi jelentkezőt a legjobbak közül, amennyi a keretszáma, a többieket utasítsa vissza. A második körben minden diák, akit visszautasítottak az első körben, adja be a jelentkezését a listáján szereplő második iskolába, és ismét minden iskola utasítsa vissza azokat a gyengébb jelentkezőket, akik nem férnek be a keretbe. Ezt a metódust ismételjük, amennyiszer szükséges.

A cikkben a következő két állítást látják be a szerzők a kapott megoldásról:

- Stabilitás: Ennek igazolása nagyon egyszerű. Az eljárás során minden iskolában növekszik a jelentkezők száma, illetve javul a jelentkezők összetétele, hiszen csak rosszabb diákok szorulhatnak ki a keretből. Ezért, ha egy diákot az eljárás során visszautasított egy iskola, akkor őt az eljárás végén is biztosan visszautasítaná. Ezen kívül már csak akkor nem lehet összepárosítva egy adott diák-iskola pár, ha a diák nem is küldte be a jelentkezését az iskolába, mivel az eljárás alatt végig jobb helyen volt aktív a jelentkezése; ez igaz a legutolsó párosításra is.

- Diák-optimalitás: Belátható, hogy nem létezik olyan stabil párosítás, amelyben akár csak egy diák is kedvezőbb helyre lenne felvéve, mint az algoritmus adta megoldásban. Ennek igazolása szintén nem igényel mély matematikai ismereteket, de terjedelme miatt itt nem kerül ismertetésre.
Ez az egyszerű felvételi eljárás tehát központi koordináció nélkül is a kívánt megoldást adná, de a gyakorlatban mégsem működőképes, mert túl lassú volna. Ha azonban egy központi program szimulálja az eljárást, akkor - a diákok és iskolák rangsorainak ismeretében - az algoritmus közvetlenül szolgáltatja a megfelelő megoldást. Az algoritmusnak további két rendkívül előnyös ismérve van.

- Gyors futásidő: Az az észrevétel már az eredeti cikkben is szerepel, hogy a körök száma az eljárásban nem lehet több, mint a jelentkezések száma, hiszen semelyik diák nem jelentkezik ugyanarra a helyre kétszer. Pontos implementációval ugyanakkor elérhető a lineáris futásidő is. Ez azt jelenti, hogy az algoritmus lépésszáma a jelentkezések számával egyenesen arányosan nő. Ha például a magyarországi felvételin alkalmazott program futásideje 10 másodperc, akkor egy nagyjából 6-szor akkora feladatot, például az Egyesült Királyság felvételi problémáját, ugyanaz a program körülbelül egy perc alatt oldaná meg.

- Stratégiailag biztos: A mechanizmus nem manipulálható, vagyis egyik diák sem járhat jobban akkor, ha nem az igazi preferenciája szerint cselekszik az eljárás során, avagy nem a valódi rangsorán küldi be a felvételi központba. Ez egy igen fontos tulajdonsága a mechanizmusnak.
A stabil párosítások elméletét mind a matematikában és algoritmuselméletben, mind pedig a közgazdaságtanban és játékelméletben intenzíven tanulmányozták az utóbbi évtizedekben, a megjelent publikációk száma több ezerre becsülhető. A tudományos érdeklődés alapvető magyarázata a gyakorlati alkalmazások nagy száma és sikeressége.

 

Alkalmazások világszerte

 

A legelső ismert alkalmazást, amelyben a Gale-Shapley algoritmus szolgáltatott stabil megoldást, az amerikai kórházi gyakornokok elhelyezésének koordinálására hozták létre. A központi programot először 1952-ben (vagyis 10 évvel a fenti cikk megjelenése előtt!) futtatták, amely jól mutatja, hogy erre a természetes megoldásra a piac szereplői és koordinálói maguktól is könnyen rátalálhatnak. A program a mai napig gyakorlatilag változatlan formában működik, és minden évben mintegy 30 ezer rezidenst allokálnak kórházakhoz ezen keresztül (lásd www.nrmp.org). Gyakornokok elhelyezésére egyre több országban és szakmában indítanak hasonló programokat.

Az iskolai felvételiket tekintve jóval kevesebb hiteles információ található a szakirodalomban. Magyarországon kívül még a spanyolországi és törökországi felsőoktatási felvételikről tudható, hogy központi program segíti őket, de a legtöbb országban vagy nincs ilyen koordináció (pl. Lengyelország, Szlovákia vagy az Egyesült Királyság), avagy nincs róluk leírás. A középiskolai programokat tekintve több országban és városban lehet sejteni a központi koordináció jelenlétét, de részletes leírás csak az újonnan bevezetett New York-i és bostoni programokról található. A központi felvételi rendszerek hasznosságáról, így például a kiszámítható hallgatói és osztálylétszámokból adódó gazdaságossági előnyökről sem született még tanulmány.

Központosított programokat, más, tágabb értelemben vett párosítási problémák megoldására is használnak a gyakorlatban. Ha például nem kétoldalú a piac, akkor az úgynevezett szobatárs probléma áll elő. Ilyen szituációkat oldanak meg az inkompatibilis beteg-donor párokat összepárosító vesecsere-programokban (USA, UK, Hollandia), vagy például a sakkversenyek párosító szoftverei is. Szintén fontos modellcsaládot kapunk, ha a kétoldalú piacokon figyelembe vesszük a lehetséges pénzügyi tranzakciókat. Itt fontos alkalmazásként említhetők az algoritmizált aukciók.

 

A magyar felvételi rendszerek sajátosságai

 

A 2000-ben bevezetett új középiskolai felvételi program különlegessége, hogy nincs sajátossága. A modell és az alkalmazott algoritmus teljes mértékben megfelel a Gale és Shapley által leírtaknak. Mindössze annyi különbséggel, hogy hazánkban az iskolák helyett a diákok az iskolák által meghirdetett tagozatokra jelentkezhetnek, és az iskolák is a tagozataikra nézve adják meg a keretszámaikat.

Az 1985-óta működő, 2007-ben megújított felsőoktatási felvételi program már sokkal összetettebb. Az alapmodell és a probléma megoldására szolgáló algoritmus a következő fontosabb sajátosságokkal rendelkezik.

- Holtversenyek: Ha két jelentkező egy adott szakon ugyanazt a pontszámot érte el, akkor ők holtversenyben vannak. Az egyenlő elbírálás elve alapján, Magyarországon (és Spanyolországban hasonlóképpen) az azonos pontszámú jelentkezők vagy mind felvételt nyernek vagy mind el lesznek utasítva. Az amerikai középiskolák esetében, ahol jóval nagyobb holtversenyek jöhetnek létre, sorsolással döntenek. Fontos megjegyezni, hogy a hazai pontszámítási módszer 2007-es finomítása óta a holtversenyek szerepe jelentősen csökkent. Elméletileg igazolható, hogy az általánosabb értelemben vett stabil és diák-optimális megoldás létezése holtversenyek esetében is garantált, és ezt az újonnan implementált hazai algoritmus valóban elő is állítaná, ha nem lennének további speciális feltételek.(1)

- Minimális keretszámok: A felsőoktatási intézmények a maximum létszámkorlátok mellett, alsó korlátotokat is meghatározhatnak minden egyes szakra nézve. Az eredményként adott megoldásban ezért az adott szakon a felvettek száma mindkét korlátot ki kell, hogy elégítse, avagy a szak bezárásra kerül. Az induló szakokra nézve a stabilitást természetesen továbbra is megköveteljük. Nem mondható igazságosnak azonban az a megoldás, amelyre található egy bezárt szak annyi jelentkezővel, amennyi a szak alsó korlátja úgy, hogy egyik jelentkező se lett felvéve jobb helyre. Sajnálatos módon létrejöhet olyan szituáció, amelyre nincs igazságos megoldás. (2) Sőt, az is belátható, hogy a probléma elméleti értelemben "nehéz", nincs remény olyan gyors (polinomiális futásidejű) algoritmus létezésére, amely képes lenne a kérdés megválaszolására.

- Közös korlátok: Az Oktatási és Kulturális Minisztérium országos korlátokat határozhat meg az állami finanszírozású képzéseket tekintve. Emellett 2007 óta az egyetemek is együttes korlátot határoznak meg egy adott képzés államilag finanszírozott és költségtérítéses hallgatói létszámára. Továbbá az egyes egyetemek kapacitása (3) is - melyet képzési területenként határoznak meg - további korlátot jelent. A stabilitás feltétele ez esetben úgy módosul, hogy egy adott szakra leadott jelentkezés akkor is elutasítható, ha egy, a szakot tartalmazó közös keret lett feltöltve jobb jelentkezőkkel. Sajnos ebben az általános modellben sem garantálható a stabil megoldás létezése, és a probléma eldöntése szintén nehéz elméleti értelemben is.

Az utolsó két speciális feltétel miatt a felsőoktatási felvételi megoldását szolgáltató algoritmusban heurisztikák szerepelnek. A heurisztikák olyan gyors eljárások, amelyek különböző ötleteken alapulva gyors megoldást biztosítanak, de természetesen nem garantálható, hogy megtalálják az igazságos megoldást, akkor sem, ha ilyen létezne az adott feladatra.

Az alsó korlátokra vonatkozó feltételt például a következőképpen kezeli a program. Először a Gale-Shapley algoritmus fut le a felső korlátok figyelembe-vételével, majd ha van olyan szak, amely nem éri el az alsó korlátját, akkor az a szak kerül bezárásra, ahol a felvettek létszámának és minimális korlátnak az aránya a legkisebb (itt van ugyanis a legkevesebb esély arra, hogy a szak a későbbiekben feltöltődhetne). A szakbezárás után újra indul a Gale-Shapley algoritmus, majd ismételt bezárások következnek, amennyiben szükséges.

Az elméletben és gyakorlati alkalmazásokban több hasonló probléma is ismert. Az amerikai kórházi rezidensek programjában például a házaspárok jelentkezhetnek közös listával is (mert érthető módon nem örülnének, ha egymástól túl távoli kórházakhoz osztanák be őket). Ez az általánosított modell szintén adhat olyan eseteket, amelyre nem létezik igazságos megoldás, és a probléma megoldása elméleti értelemben is nehéz, ezért ott is heurisztikákat alkalmaznak az algoritmusban.

 

Összefoglaló, további információk

 

A Magyarországon alkalmazott felvételi programok mindenképpen sikeresnek mondhatók. A középiskolai rendszerben alkalmazott modell és algoritmus tisztasága egyedülálló példaként szolgálhat más országok számára is. A felsőoktatásban létrejött modell már több speciális problémát hordoz magában. Ezek gyakorlati megoldása szintén megfelelő, bár természetesen heurisztikák esetén tökéletes megoldás nem létezik, ezért az algoritmus további elméleti és gyakorlati vizsgálata hasznos lehet.

A stabil párosítások elméletéről és gyakorlati alkalmazásáról további információkat találhat az érdeklődő a Glasgow University algoritmuselméleti csoportjának honlapján: www.optimalmatching.com, illetve a neves amerikai közgazdász, Al Roth oldalán.

A fenti megállapításokat - mindkét program esetében - az algoritmusok összefoglaló leírásainak ismeretében tettük. Ezen leírásokat, illetve további részleteket az alkalmazott módszerekről az Educatio Kht. munkatársai szolgáltattak számunkra.

- Dr. Biró Péter-Dr. Fleiner Tamás -

 

Megjegyzések:

1. Lásd bővebben a következő cikket: "Student admissions in Hungary as Gale and Shapley envisaged" , DCS Technical Report, University of Glasgow, TR-2008-291.

2. Vegyük például a következő esetet. Tegyük fel, hogy a jazztanszéken egyetlen szaxofonost keresnek, és pontosan két gitárost szeretnének felvenni (a gitáros szakon tehát az alsó és felső korlát is kettő). Legyen Ádám és Béla a két jelentkező. Ádám mindkét hangszeren ügyesebb, de az ő listáján a gitár szak szerepel előrébb, míg Béla a szaxofont kedveli jobban. Mivel csak két jelentkezőnk van, az egyik szakot mindenképpen be kell zárni. Ha a gitár szakra vennénk fel mindkettőjüket, akkor az nem lenne igazságos, mert Béla jobban szeretne szaxofonozni, és oda nem vettek fel senkit. Az sem lenne stabil megoldás, ha a szaxofon szak indulna el Béla felvételével, mert Ádám jobb zenész. Végül, ha Ádámot vennék fel a szaxofon szakra, akkor szintén igazságtalan megoldás születne, hiszen a gitár szak elindításának ebben a helyzetben mindketten jobban örülnének.

3. Elképzelhető, hogy egy egyetem összesen 100 - 100 orvos és fogorvos keretet határoz meg, de összességében mégis maximum 150 hallgatót tud felvenni.