ALG&1

10 6 Przeszukiwanie gratów 261

{

V:ki=l;    // zaznaczamy 'k' jako "zbadany"

kolejka.wstaw(k>;

I

}

1

Sens tego algorytmu może być wyjaśniony znacznie czytelniej w pseudo-kodzie:

szukaj(i)

I

wstaw ’i’ do Kolejki;

dopóki kolejka nie jest pusta wykonuj:

' {

wyjmij z kolejki pewien wierzchołek 's'; zaznacz 's' jako "zbadany";

dla każdego wierzchołka 'k' przyległego do 's' jeśli 'k' nie byl już zbadany t

zaznacz 'k' jako "zbadany"; wstaw 'k' do kolejki;

)

I

)

10.7.Problem właściwego doboru

Kończąc rozważania dotyczące grafów, pragnę zaprezentować bardzo ciekawe i złożone zagadnienie: problem doboru (lub inaczej minimalizowaniu konfliktów). Będzie to kolejny dowód na to, że dobry model ułatwia odnalezienie właściwego rozwiązania.

Ponieważ sformułowanie zagadnienia w postaci czysto matematycznej jest bardzo nieczytelne, prześledźmy jego ideę na przykładzie wzięty m z życia. Wyobraźmy sobie następującą sytuację: mamy N studentów i N tematów prac magisterskich. Do każdej pracy magisterskiej jest przypisany jeden promotor (profesor danej uczelni), zatem z obu stron mamy do czynienia z czynnikiem ludzkim. Każdy student ma pewną opinię (preferencję) na temat danej pracy i z pewnością woli jedne tematy od innych. Również nie każdy profesor lubi jednakowo wszystkich studentów i z pewnością wolałby pracować ze znanym mu studentem X niż z niezbyt mu kojarzącym się studentem Y, który systematycznie opuszcza! jego wykłady...

Oczywiście, problem doboru nie ogranicza się wyłącznie do kręgów akademickich i może być odnaleziony w przeróżnych postaciach w rozmaitych dziedzinach życia.