Dzisiaj rozpatrywać będziemy problem jak połączyć osoby (np. w klasie) w pary tak, aby każda osoba była połączona z możliwie najbardziej oczekiwaną osobą z listy potencjalnych partnerów do tańca. Jako parę uznawać będziemy chłopca i dziewczynkę, tudzież - mężczyznę i kobietę. Warunek, który musimy spełnić, to równoliczność obydwu tych grup. Przedstawię wam algorytm, który na podstawie listy preferencji osób pomoże nam dobrać takie pary, by osoby w parze były z możliwie najbardziej pożądaną osobą.
Oczywiście nie muszę tłumaczyć, że nie jest to algorytm, który w jakiś magiczny sposób zawsze przydzieli nas do osoby, z którą chcemy tańczyć w pierwszej kolejności. Jest on jednak - i to można udowodnić - sprawiedliwym algorytmem zarówno dla części męskiej, jak i żeńskiej.
Niech każda z dwóch grup - kobiet i mężczyzn sporządzi listę osób, z którymi najbardziej chciałaby być w parze (lista preferencji) w kolejności od najbardziej oczekiwanej do najmniej oczekiwanej. Przy stosowaniu powyższej metody ważne jest, aby na liście preferencji chłopców znajdowały się wszystkie dziewczynki, a na liście preferencji dziewcząt - wszyscy chłopcy. Na początku algorytmu nikt nie ma przydzielonej pary, należy więc kilkakrotnie (do momentu, gdy każdy będzie miał parę) wykonać poniższe dwa kroki:
KROK 1. Każdy chłopiec, który nie ma przydzielonej partnerki składa propozycję pary dziewczynie, której jeszcze nie proponował i znajduje się ona najwyżej na jego liście wyboru.
KROK 2. Dziewczęta wybierają tego partnera, który jest najwyżej na ich liście preferencji. Pozostali panowie pozostają bez pary i algorytm wykonuje się ponownie.
Metoda ta pochodzi z publikacji Algorytmy profesora M. Sysły. Warto w tym miejscu wspomnieć słowa profesora, który stwierdził, że „układ par jest trwały, gdy nie ma wśród nich żadnych dwóch par, w których chłopiec z jednej pary a dziewczyna z drugiej pary, a więc tacy, którzy nie tworzą pary, wolą siebie bardziej niż swoich obecnych partnerów”. Możecie to sprawdzić dobierając się w pary i wybierając dwie dowolne osoby, które uważają, że są pokrzywdzone (nie chcieli być ze sobą w parze). Okaże się, że wówczas nie znajdziemy innej pary, która chciałaby być ze sobą bardziej niż oni!
Brak komentarzy:
Prześlij komentarz