ALG&2

262 RozdziaMO, Elementy algorylmiki grafów

Dlaczego jest on rozwiązywany przy pomocy grafów? Cóż, chyba najlepiej zilustruje to rysunek 10 - 13.

262 RozdziaMO, Elementy algorylmiki grafów

Rys. W- 13.

Problem doboru.

studenci

tematy prac (promotorzy)

Rysunek przedstawia jedno z możliwych rozwiązań problemu doboru dla N-5 studentów i prac. Zadanie jest przedstawione w postaci specjalnego grafu, w którym węzły są pogrupowane według kategorii i ustaw ione obok siebie. Waito sobie jednak zdawać sprawę, że taka fonna wizualizacji jest przydatna wyłącznie dla człowieka, gdyż komputer nie widzi różnicy pomiędzy ustawieniem „ładnym” i „brzydkim”, (Struktura graficzna konkretnego doboru jest po prostu grafem, w którym mamy do czynienia z pewną liczbą/wr węzłów). Jeśli węzły i oraz j są ze sobą połączone, to oznacza to, że zostały one dobrane (nieważne czy dobrze, czy źle). Oznacza to, żc niedopuszczalne jest wykorzystanie węzła więcej niż jeden raz.

Analizując problem doboru, stajemy nieuchronnie wobec problemu wyrażania preferencji. Każdy student musi mieć opinię o danej pracy i jej promotorze, każdy promotor musi jasno określić swoje preferencje dotyczące określonych osób. Okazuje się, że naturalną metodą są tzw. listy rankingowe: opinią studenta X na temat pracy Y będzie jej pozycja na jego liście rankingowej prac magisterskich, podobne listy będą musieli stworzyć profesorowie o studentach.

Omówiona sytuacja jest przedstawiona na rysunku 10 - 14.

Rys. 10 - 14.    preferencje studentów    preferencje promotorów

Listy rankingowe w problemie doboru.

© ©0 © 0 © © ® © ® ® ©