palacsint weblapja

Könnyen belátható, hogy a feladatnak nincs tökéletes megoldása, csupán közelíteni lehet egy optimumot. A hallgatók és a kívánságaik egy gráfként is elképzelhetőek, ahol a csúcsok jelentenek egy-egy hallgatót, az irányított élek pedig egy-egy „kívánságot”.

1. Ábra: A legegyszerűbb probléma

A legegyszerűbb probléma az 1. ábrán látható. Adott hat hallgató, A, B, C, D, E és F. A B-vel, C D-vel, E pedig F-el szeretne egy szobába kerülni, s ezen kívánságaik kölcsönösek. Ha ezekhez a kívánságokhoz két darab háromágyas szobánk van, akkor lehetetlen teljesíteni a kéréseket. Valamelyik csoportot fel kell osztani. Melyik legyen az?

2. Ábra: Egy újabb problémás helyzet

A problémák tovább szaporodhatnak (2. ábra). Adott három hallgató: A, B és C. Közülük B és C szeretne egy szobába kerülni, de A megjelölte mindkettejüket, mint jövőbeli szobatárs, bár erről a jelöltek egyike sem tud, és talán nem is szívesen töltene el egy évet A-val. B és C között kölcsönös a kapcsolat, míg A és B, illetve A és C között csak egyirányú. Ha ábécé sorrendben teljesítjük a hallgatók kéréseit, akkor itt figyelmen kívül hagynánk B és C egyhangú kérését. Ez a lehetőség egyszerűen kiküszöbölhető számítógépes segítséggel. Elég csak a kölcsönös kapcsolatokat figyelembe venni, A máris hoppon marad.

A kapcsolatok gráfja egyszerűen ábrázolható egy csúcsmátrixszal, vagy kívánság-mátrixszal. A 2. ábra alapján elkészített kívánságmátrix az (1) képlettel adható meg, ahol k_i,j 1-es értéke jeleneti az i hallgató j hallgatóra mutató kívánságának meglétét, 0 értéke pedig a hiányát.

(1)

A mátrix főátlójában értelemszerűen 1-esek szerepelnek (hiszen A A-val mindenképpen egy szobába fog kerülni), bár ez a program szempontjából nem igazán lényeges.

Kölcsönös egy kapcsolatot, ha:

k_{i, j} = k_{j, i} = 1 (2)

Az így ábrázolt gráfból egyszerűen kiszűrhetőek a nem kölcsönös kapcsolatok, ha megszorozzuk a kívánságmátrixot a transzponáltjával (3).

(3)

A megmaradt kívánságok gráfként ábrázolva a 3. ábrán láthatóak.

3. Ábra: Megmaradt kívánságok

A megmaradt kapcsolatokból ezután csoportokat kell alakítani, majd egy-egy csoportot hozzárendelni egy-egy megfelelő ággyal rendelkező szobához. Kétfős csoportok alakítása már lényegében megtörtént, hiszen csak a kétirányú, kölcsönös kapcsolatokat hagytuk meg. További megoldandó feladatot jelentenek, az olyan esetek, amikor egy hallgató több csoporthoz is tartozik. Ez annak a következménye, hogy több embert is meg lehet jelölni leendő szobatársnak.

4. Ábra: Többszörös csoporttagság

Egy ilyen esetet mutat be a 4. ábra. A B-vel és C-vel kerülhetne egy szobába (kétágyas szobákat feltételezve). Az elsőbbség eldöntéséhez valamilyen prioritási rendszer szükséges, vagyis az élekhez prioritási értékeket kell rendelni.

Mivel nem csak kétágyas szobák lehetnek egy kollégiumban, nagyobb csoportok létrehozásával is érdemes próbálkozni. A kettőnél több hallgatót tartalmazó csoportok létrehozásának feltétele megegyezik a kétfős csoportokéval: minden csoporttag között kölcsönös kapcsolatnak kell lennie. Ez n fős csoport esetén n(n-1) kapcsolatot jelent. Erre a legegyszerűbb eljárás az, ha a meglévő kétfős csoportokat próbáljuk bővíteni háromtagúvá, majd később a háromfős csoportokat négyfőssé, stb.

Tehát minden kétfős csoporthoz megpróbáljuk hozzáadni az összes olyan hallgatót, aki még nem tagja a csoportnak. Ehhez a két csoporttag és a leendő új tag közötti kölcsönös kapcsolatok ellenőrzése szükséges. Ha léteznek ezek a kapcsolatok, akkor bekerülhet az új tag a csoportba, ezzel háromfőssé bővítve a csoportot. Ugyanekkor a régi, kétfős csoportot sem töröljük a csoportok listájából, hanem megpróbálunk más hallgatókkal is háromtagúvá bővíteni.

5. Ábra: Négy hallgató és kívánságaik gráfja

Az 5. ábrán látható gráf négy hallgatót, illetve a kívánságaikat ábrázolja. Ebből a néhány kapcsolatból a következő kétfős csoportokat lehet létrehozni: {A, B}, {A, D}, {B, D}, {A, C}, {B, C}. Háromfős csoportok is létrehozhatóak: {A, B, C} és {A, B, D}.

Ilyen egyszerű esetben is, az A öt csoport tagja, de csak egyetlen szobába kerülhet, amiről még azt sem tudjuk, hogy az két-, három vagy esetleg több ágyas-e. A prioritások szükségessége itt még jobban jelentkezik, mint az előző esetben, hiszen el kell döntenünk, hogy az öt csoportból melyik lesz az, amelyik ténylegesen bekerül valamelyik szobába, s melyik lesz az a négy, amit törölnünk kell a csoportlistából.

Minden csoporthoz prioritás értéket kell meghatározni, majd ezen értékük alapján sorrendezni őket, s a sorrend alapján hozzárendelni a szobákhoz a csoportokat. Egy-egy ilyen hozzárendelés után törölni kell az összes olyan csoportot, amelyik tartalmazza a most beosztott hallgatók bármelyikét. Az előző példában ez a maradék négy csoportot jelenti, amelyeket már nem tudunk használni.