zad05, Analiza, Analiza algorytmów, Analiza strukturalna danych
[ Pobierz całość w formacie PDF ]
//-->Zadanie2Dany jest skończony graf niezorientowany. Zaproponuj algorytm kolorowania krawędzi tego grafu,w taki sposób, by krawędzie incydentne miały przyporządkowane różne kolory. Zastosuj metodęzachłanną konstrukcji algorytmu i postaraj się aby algorytm używał możliwie małej liczby kolorów.Czy Twoje rozwiązanie pozwala wyznaczyć minimalną liczbę kolorów konieczną dopokolorowania krawędzi grafu?Wymagania:• W tekście rozwiązania musi się znaleźć nazwisko autora i jego numer indeksu oraz treśćrozwiązywanego zadania.• Rozwiązanie powinno zawierać:•••••specyfikację zadania,opis słowny metody rozwiązania,algorytm zachłanny rozwiązujący (ew. jego implementację),analizę kosztu ianalizę poprawności algorytmu względem podanej specyfikacji (podaj argumentyświadczące o tym, że Twój algorytm zasługuje na miano "zachłanny").Rozwiązanie:•Specyfikacja zadania:pre={G=<V, E>: V- skończone v, v'V, (v,v')E wttw (v',v)E∧ ������������. ������������(����) ≤ 2}Oznaczenia:v, v'- dowolne dwa wierzchołkiE- etykietyV- wierzchołkimax.val- największy stopień wierzchołka G.post={∀ m1∈ {1,...,��������,����}∀ m2∈ {1,...,��������,����}��������,����(����1)≠��������,����i=1,...,I }(����2)Oznaczenia:m- numer krawędzi łączącej wierzchołki��������,����- ilość wszystkich krawędzi łączących wierzchołki��������i����������������,����- ilość wszystkich krawędzi łączących wierzchołki��������i��������(����1) (����2)��������,����,��������,����- kolory krawędzi•Opis słowny metody rozwiązania:Z racji, że w treści zadania użyte jest określenie zaproponuj a nie wymyśl, do rozwiązania problemupostanowiłam posłużyć się algorytmem NTL (Nishizeki, Terada, Leven). Jest on jednym zalgorytmów przybliżonych (heurystycznych). Polega on na kolejnym kolorowaniu krawędzi, a wrazie konieczności przekolorowaniu już pokolorowanych.Działanie algorytmu opiera się na następującej własności grafu:Niech wszystkie krawędzie grafu G z wyjątkiem v zostały pokolorowane na����(G)+1kolorami.Wiadome jest, że u i v mają przynajmniej dwa kolory brakujące. Jeżeli F jestmaksymalnym wachlarzem przy v, to albo kolor c(��������) jest brakujący także w wierzchołku v, czylic(��������) należy do C(v), albo pewna krawędź w F jest pokolorowanakolorem c(��������) .Do rozwiązania algorytmu konieczne jest zdefiniowanie pojęcia wachlarza:Wachlarzem F przy wierzchołku v rozpoczynającym się krawędzią {v,����}nazywamy taki ciągkrawędzi {v,����},...,{v,��������}, że {v,��������} ma przydzielony kolorc(��������-1), i>0. Liczba s to rozpiętość wachlarza.Jak na samym początku wspomniałam, pokolorowane krawędzie mogą zmieniać swójkolor. Do tego celu używa się proceduryRecolor,która wygląda nastepująco:1.Kolorujemy krawędź {u,v}2.Wyznaczamy maksymalny wachlarz F (musi spełniać warunek, że u=����) przywierzchołku v.3.Rozpatrujemy przypadki:a) jeżeli m(��������) należy do M(v), gdzie i to rozpiętość wachlarza, wtedy kolorujemy krawędź {u,��������}barwą m(��������) dla kazdego i=1,...,s.b) jeżeli m(��������)nienależy do M(v), wtedy:•zakładamy, że P jest ścieżką w grafie G zaczynającą się w��������, składającąsię z krawędzi pokolorowanych kolorami c(v) i c(��������).•jeśli P nie osiąga wierzchołka v, to zamieniamy przeciwne kolory, które użyliśmy dopokolorowania P i przesuwamy cykliczne kolory poszczególnych krawędzi {v,��������}, malując jekolorami c(��������) dla każdego0 ≤ ���� ≤ ����,a potem zamalowujemy {u,��������} kolorem c(v).•jeśli P osiaga v, to niech��������, gdzie0 ≤ ���� ≤ ���� − 2będziewierzchołkiem spełniającymrówność c(��������−1)=c(��������). Niech P będzie drogą zaczynającą się w��������i pomalowaną kolorami m(v) im(��������). Dla takiej okoliczności przesuwamy kolory wachlarza, malując każdą krawędź u,��������kolorem c(��������) dla0 ≤ ���� ≤ ���� − 2,potem zmieniamy kolory drogi P i malujemy krawędź {v,��������−����}kolorem c(v).•Algorytm zachłanny rozwiązujący:algorytm KolorujNTL(G)beginif Delta(G)<=2 thenkoloruj G zachłannnie odwiedzając wszystkie ścieżki oraz cykle;else beginq:=Delta(G)+1;G':=(V, pusty);for każda e w E do beginG':=G'+e;if e={u,v}nie mogę otrzymać wspólnego koloru brakującego w u i v thenRecolor(u, v);koloruj e;endendend•Analiza kosztu:Algorytm NTL pozwala na uzyskanie wyniku w czasie wielomianowym. Jego koszt możnaoszacować jako O(����4).•Analiza poprawności algorytmu względem podanej specyfikacji:Zaproponowany algorytn daje wynikowe pokolorowanie, które jest rozwiązaniemprzybliżone. Samo pomalowanie można nazwać legalnym (właściwym), ponieważ dwasąsiadujące ze sobą krawędzie nie będą miały tego samego koloru.Z faktu, że algorytm jest rozwiązywany metodą ''zachłanną” , a wynik staje sięprzybliżony, można wywnioskować, że do pokolorowania wykorzystana zostanie małaliczba kolorów. Niestety nie najmniejsza. Zatem odpowiedź na zamieszczone w treścizadania pytanie, jest przecząca.Argumenty świadczące o tym, że podany algorytm jest zachłanny:1.Kolorowanie grafu rozpoczynamy w kolejności uporządkowanej.2.W otrzymanym wyniku uzyskujemy rozwiązanie przybliżone.3.Algorytm jest rozwiązywany ''po kawałku''. Na każdym etapie kolorowania,w którym trzeba ustalić dalszy tok postępowania wybieramy ten wariant, który daje namrozwiązanie lokalnie optymalne. Zatem takie, które w danym momencie działania algorytmuwydaje się być najlepsze (kolorujemy w dowolny sposób krawędzie, dopiero później stosujemyproceduręRecolor,która działa etapowo).4.Jest on szybkim rozwiązaniem danego problemu, ale nie wykorzystuje najmniejszej liczbykolorów. [ Pobierz całość w formacie PDF ]