Rekurencyjny algorytm największego pierwszego

Recursive Largest First ( RLF ) jest heurystyką dla NP-trudnego problemu kolorowania grafów . Został pierwotnie zaproponowany przez Franka Leightona w 1979 roku.

Algorytm RLF przypisuje kolory wierzchołkom wykresu, konstruując każdą klasę kolorów pojedynczo. Dokonuje tego poprzez identyfikację maksymalnego niezależnego zestawu wierzchołków na wykresie, przypisanie im tego samego koloru, a następnie usunięcie tych wierzchołków z wykresu. Czynności te powtarza się na pozostałym podgrafie, aż nie pozostaną żadne wierzchołki.

Aby utworzyć rozwiązania wysokiej jakości (rozwiązania wykorzystujące kilka kolorów), algorytm RLF wykorzystuje wyspecjalizowane reguły heurystyczne, próbując zidentyfikować niezależne zbiory „dobrej jakości”. Te heurystyki sprawiają, że algorytm RLF jest dokładny w przypadku dwudzielnych , cykli i kołów . Ogólnie jednak algorytm jest przybliżony i może zwrócić rozwiązania, które wykorzystują więcej kolorów niż liczba chromatyczna wykresu .

Opis

Algorytm można opisać trzema następującymi krokami. $wierzchołków$ koniec tego procesu daje podział reprezentujący wykonalną $sol$${\ displaystyle G}$ wykresu .

1. Niech $rozwiązaniem$ . Niech także będzie grafem, który chcemy pokolorować, zawierającym zbiór wierzchołków $sol = ( V , mi )$ zbiór krawędzi $=$$E$ }
2. Zidentyfikuj $_$ zbiór _ Aby to zrobić:
   1. Pierwszy wierzchołek dodany do $powinien$ być wierzchołkiem w $który$ największą liczbę sąsiadów.
   2. $($ wierzchołki dodane do należy wybrać jako te, które (a) nie sąsiadują obecnie z żadnym wierzchołkiem w i b) mają maksymalną liczbę sąsiadów sąsiadujących z wierzchołkami w ${\ displaystyle S}$${\ displaystyle S}$ . $ma$ w warunku (b) można zerwać, wybierając wierzchołek z minimalną liczbą sąsiadów, których nie . $,$ są dodawane w ten sposób dopóki nie będzie możliwe dodanie kolejnych wierzchołków.
3. Teraz ustaw ${\ displaystyle {\ mathcal {S}} = {\ mathcal {S}} \ puchar \ {S \}}$ i usuń wierzchołki ${\ displaystyle S}$ z ${\ styl wyświetlania G}$ . Jeśli $wierzchołki$ , wróć do kroku 2; inaczej koniec.

Przykład

Wykres kołowy z siedmioma wierzchołkami

$_$ wykres _ Jest to wykres kołowy i dlatego zostanie optymalnie pokolorowany przez RLF. Wykonanie algorytmu powoduje wybranie i pokolorowanie wierzchołków w następującej kolejności:

1. Wierzchołek sol $\ displaystyle g}$ (kolor 1)
2. Wierzchołek ${\ displaystyle a}$ , ${\ displaystyle c}$ , a następnie (kolor 2) ${\ displaystyle e}$
3. Wierzchołek ${\ displaystyle b}$ , ${\ displaystyle d}$ , a następnie (kolor 3) ${\ displaystyle f}$

Daje to ostateczne rozwiązanie trójkolorowe. $\ displaystyle {\ mathcal {S}} = \ {\ {g \}, \{a,c,e\},\{b,d,f\}\}}$ .

Wydajność

Niech $będzie$ liczbą wierzchołków wykresu i niech $.$ krawędzi Używając notacji dużego O , w swojej oryginalnej publikacji Leighton stwierdza, że ​​złożoność RLF wynosi ${\ displaystyle {\ mathcal {O}} (n ^ {3})}$ ; można to jednak poprawić. Duża część kosztów tego algorytmu wynika z kroku 2, w którym wyboru wierzchołków dokonuje się zgodnie z regułami heurystycznymi podanymi powyżej. Rzeczywiście, za każdym razem, gdy wierzchołek jest wybierany w celu dodania do zbioru niezależnego $sąsiadów$ ponownie obliczyć dla każdego niepokolorowanego wierzchołka. $}} ( mn)}$ te można wykonać w czasie, co oznacza, $m$ ​​ogólna złożoność RLF wynosi .

$zostaną$ złożoność tego algorytmu zmniejsza się do jednakże wynikowy algorytm zwykle zwróci rozwiązania o niższej jakości w porównaniu z rozwiązaniami RLF. Będzie to teraz również niedokładne w przypadku dwudzielnych , cykli i kół .

W empirycznym porównaniu przeprowadzonym przez Lewisa w 2021 r. wykazano, że RLF zapewnia znacznie lepsze kolorowanie wierzchołków niż alternatywne heurystyki, takie jak zachłanny algorytm i O ( $displaystyle {\ mathcal {O}} (n+m)}$${\ Displaystyle {\ mathcal {O}} ((n + m) \ lg n)} Algorytm$ DSatur na losowych wykresach . Jednak czas wykonania z RLF również okazał się dłuższy niż w przypadku tych alternatyw ze względu na jego większą ogólną złożoność.

Linki zewnętrzne

• Wysokowydajne algorytmy kolorowania grafów Zestaw algorytmów kolorowania grafów (zaimplementowanych w języku C++) wykorzystanych w książce A Guide to Graph Colouring: Algorithms and Applications (Springer International Publishers, 2021).