ALG&3

17. Problem właściwego doboru ?63

Nietrudno zauważyć, że o ile samo dobranie N dwójek {student, praca} jest trywialne, to jednoczesne sprostanie bardzo zróżnicowanym wymaganiom tylu osób nie jest bynajmniej takie proste. Weźmy pod uwagę następującą propozycję: D-0, E-I, A-2, B-3, C-4 Jest to niewątpliwie jakieś rozwiązanie problemu doboru (bowiem żaden węzeł nie jest wykorzystany więcej niż raz), ale czy na pewno dobre? Student D dostał temat 0. który na jego liście zajmował dalekie, trzecie miejsce. Zgodnie ze swoimi wymaganiami wolałby on zapewne dostać temat J. Temat 3 przypadł jednak studentowi B. Promotor zajmujący się tematem i. na swojej liście preferencyjnej umieścił bardzo wysoko studenta D, a tymczasem „dostał" studenta A! Mamy więc dość zabawną sytuację:

17. Problem właściwego doboru ?63

D-0

D woli bardziej 3 od U

B-3

i w'ol i bardziej D od B

Rozwiązanie zaproponowane powyżej jest zwane niestabilnym, gdyż rodzi potencjalne konłlikty personalne... Ideałem byłoby znalezienie takiego algorytmu, który proponowałby możliwie najbardziej stabilny wybór, uwzględniający w- największym możliwym stopniu dostarczone listy rankingowe. Pamiętając o tzw. czynniku ludzkim, powinno być jasne, dlaczego zadanie nie jest łatwe do rozwiązania: listy rankingowa będą miały po prostu bardzo nierówmomierne rozkłady. Pewne tematy będą łubiane przez przeważającą większość, inne znajdą się na szarym końcu. O ile samo dobranie N dwójek wydaje się nieklopotliwe z programistycznego punktu widzenia, to sprawdzenie stabilności wydaje się dość złożone. Kłopot sprawia tu mnogość potencjalnych rozwiązań, z których każde należałoby sprawdzić pod kątem jego stabilności. Zatem algorytm typu brute-force. który najpierw losuje potencjalne rozwiązanie (jest ich przecież skończona liczba), a potem sprawdza jego stabilność, byłby bardzo nieefektywny.

Zagadnienie doboru było wszechstronnie studiowane i wydaje się, że zostało znalezione rozwiązanie, które charakteryzuje się pewną „inteligencją” w porównaniu z bezmyślnym algorytmem typu brule-force. Jego idea polega na systematycznym powtarzaniu schematu cząstkowego doboru:

• student i proponuje temat /, który znajduje się najwyżej na jego liście rankingowej :

jeśli promotor / nie wybrał jeszcze studenta, to „związek" (i,j) jest tymczasowo akceptowany.

jeśli promotor / zaakceptował już tymczasowo studenta k. to związek (k, j) może zostać złamany na rzecz studenta / pod warunkiem, że promotor lubi bardziej j niż wcześniej wybranego k. W konsekwencji student k znów staje się wolny i w jednym z następnych etapów będzie musiał zaproponować lemat ze swojej listy rankingowej, następny po uprzednio odrzuconym.