5032124680

18

I. PROJEKTOWANIE 1 ANALIZA ALGORYTMÓW

TABELA 1.1.

Macierzowa reprezentacja grafu z rysunku 1.2

AB AC AD BA BC BD DA DB DC EA EB EC ED

Zagadnienie kolorowania grafu studiowane było przez dziesięciolecia i obecna wiedza na temat algorytmów zawiera wiele propozycji w tym względzie. Niestety, problem kolorowania dowolnego grafu przy użyciu najmniejszej możliwej liczby kolorów zalicza się do ogromnej klasy tzw. problemów NP-zupelnych, dla których jedynymi znanymi rozwiązaniami są rozwiązania typu „sprawdź wszystkie możliwości”. W przełożeniu na kolorowanie grafu oznacza to sukcesywne próby wykorzystania jednego koloru, potem dwóch, trzech itd. tak długo, aż w końcu liczba użytych kolorów okaże się wystarczająca (czego stwierdzenie również wymaga „sprawdzenia wszystkich możliwości”). Co prawda wykorzystanie specyfiki konkretnego grafu może ten proces nieco przyspieszyć, jednakże w ogólnym wypadku nie istnieje alternatywa dla oczywistego „sprawdzania wszystkich możliwości”.

Okazuje się więc, że znalezienie optymalnego pokolorowania grafu jest w ogólnym przypadku procesem bardzo kosztownym i dla dużych grafów może okazać się zupełnie nie do przyjęcia, niezależnie od tego, jak efektywnie skonstruowany byłby program rozwiązujący zagadnienie. Zastosujemy w związku z tym trzy możliwe podejścia. Po pierwsze, dla małych grafów duży koszt czasowy nie będzie zbytnią przeszkodą i „sprawdzenie wszystkich możliwości” będzie zadaniem wykonalnym w rozsądnym czasie. Drugie podejście polegać będzie na wykorzystaniu specjalnych własności grafu, pozwalających na rezygnację a priori z dość dużej liczby sprawdzeń. Trzecie podejście odwoływać się będzie natomiast do znanej prawdy, że rozwiązanie problemu można znacznie przyspieszyć, rezygnując z poszukiwania rozwiązania optymalnego i zadowalając się rozwiązaniem dobrym, możliwym do zaakceptowania w konkretnych warunkach i często niewiele gorszym od optymalnego — tym bardziej, że wiele rzeczywistych skrzyżowań nie jest aż tak skomplikowanych, jak pokazane na rysunku 1.1. Takie algorytmy, szybko dostarczające dobrych, lecz niekoniecznie optymalnych rozwiązań, nazywane są algorytmami heurystycznymi.

Jednym z heurystycznych algorytmów kolorowania grafu jest tzw. algorytm „zachłanny” (ang. greedy). Kolorujemy pierwszym kolorem tyle wierzchołków, ile tylko możemy. Następnie wybieramy kolejny kolor i wykonać należy kolejno następujące czynności:

(1) Wybierz dowolny niepokolorowany jeszcze wierzchołek i przyporządkuj mu aktualnie używany kolor.