5032124663

20

1. PROJEKTOWANIE I ANALIZA ALGORYTMÓW

TABELA 1.2.

Jeden ze sposobów pokolorowania grafu z rysunku 1.2 za pomocą „zachłannego” algorytmu

Kolor

Wierzchołki

Ekstra

niebieski    AB, AC, AD, BA, DC, ED

BA, DC, ED AD, BA, DC, ED BA, DC, EA, ED

czerwony    BC, BD, EA

zielony    DA, DB

żółty    EB,    EC

Rozstrzygniemy tę wątpliwość za pomocą elementarnych wiadomości z teorii grafów. Nazwijmy k-kliką zbiór k wierzchołków, w których każde dwa połączone są krawędziami. Jest oczywiste, że nie da się pokolorować A:-kliki przy użyciu mniej niż k kolorów. Gdy spojrzymy uważnie na rysunek 1.2 spostrzeżemy, że wierzchołki AC, DA, BD i EB tworzą 4-klikę, wykluczone jest zatem pokolorowanie grafu wykorzystując mniej niż 4 kolory, zatem nasze rozwiązanie jest optymalne pod względem liczby faz. □

Pseudojęzyki i stopniowe precyzowanie

Gdy tylko znajdziemy odpowiedni model matematyczny dla rozwiązywanego problemu, możemy przystąpić do formułowania algorytmu w kategoriach tego modelu. Początkowa wersja takiego algorytmu składa się zazwyczaj z bardzo ogólnych instrukcji, które w kolejnych krokach należy uściślić, czyli zastąpić instrukcjami bardziej precyzyjnymi. Przykładowo, sformułowanie „wybierz dowolny niepokolorowany jeszcze wierzchołek” jest intuicyjnie zrozumiałe dla osoby studiującej algorytm, lecz aby z algorytmu tego stworzyć program możliwy do wykonania przez komputer, sformułowania takie muszą zostać poddane stopniowej formalizacji. Postępowanie takie nazywa się stopniowym precyzowaniem (ang. stepwise refinement) i prowadzi do uzyskania programu w pełni zgodnego ze składnią konkretnego języka programowania.

Przykład 1.2. Poddajmy więc stopniowemu precyzowaniu „zachłanny” algorytm kolorowania grafu, a dokładniej jego część związaną z konkretnym kolorem. Zakładamy wstępnie, że mamy do czynienia z grafem G, którego niektóre wierzchołki mogą być pokolorowane. Poniższa procedura tworzy zbiór wierzchołków newclr, którym należy przyporządkować odnośny kolor. Procedura ta wywoływana jest cyklicznie tak długo, aż wszystkim węzłom grafu przyporządkowane zostaną kolory. Pierwsze, najbardziej ogólne sformułowanie wspomnianej procedury może wyglądać tak, jak na listingu 1.1.

LISTING 1.1.

Początkowa wersja procedury greedy

procedurę greedy ( var G: GRAPH; var newclr: SET );

{ greedy zapisuje w newclr zbiór wierzchołków, którym należy przyporządkować ten sam kolor } begin

{1}    newclr:= 0;²

Symbol 0 oznacza zbiór pusty.