Udoskonalanie partycji
W projektowaniu algorytmów udoskonalanie partycji to technika przedstawiania partycji zbioru jako struktury danych , która umożliwia udoskonalanie partycji poprzez podzielenie jej zestawów na większą liczbę mniejszych zestawów. W tym sensie jest dualna w stosunku do struktury danych typu union-find , która również utrzymuje podział na zbiory rozłączne , ale w której operacje łączą pary zbiorów. W niektórych zastosowaniach udoskonalania partycji, takich jak przeszukiwanie leksykograficzne wszerz , struktura danych zachowuje również uporządkowanie zbiorów w podziale.
Udoskonalanie partycji stanowi kluczowy składnik kilku wydajnych algorytmów na grafach i automatach skończonych , w tym minimalizacji DFA , algorytmu Coffmana-Grahama do planowania równoległego i leksykograficznego przeszukiwania grafów wszerz.
Struktura danych
Algorytm udoskonalania partycji utrzymuje rodzinę zbiorów rozłącznych Si . Na początku algorytmu ta rodzina zawiera pojedynczy zestaw wszystkich elementów w strukturze danych. Na każdym kroku algorytmu przedstawiany jest algorytmowi zestaw X , a każdy zbiór Si ∩ X S i w rodzinie zawierającej elementy X jest dzielony na dwa zbiory, przecięcie i różnicę S i \ X .
Algorytm taki można wydajnie zaimplementować, utrzymując struktury danych reprezentujące następujące informacje:
- Uporządkowana sekwencja zestawów S i w rodzinie, w postaci takiej jak podwójnie połączona lista , która umożliwia wstawianie nowych zestawów w środek sekwencji
- Z każdym zestawem S i związany jest zbiór jego elementów S i , w postaci takiej jak podwójnie połączona lista lub tablicowa struktura danych , która pozwala na szybkie usuwanie poszczególnych elementów ze zbioru. Alternatywnie, ten składnik struktury danych może być reprezentowany przez przechowywanie wszystkich elementów wszystkich zestawów w pojedynczej tablicy, posortowanej według tożsamości zbioru, do którego należą, oraz poprzez reprezentację zbioru elementów w dowolnym zbiorze S i przez jego pozycje początkową i końcową w tej tablicy.
- Powiązany z każdym elementem, zestawem, do którego należy.
Aby wykonać operację udoskonalania, algorytm przechodzi przez elementy danego zbioru X . Dla każdego takiego elementu x znajduje zbiór S i zawierający x i sprawdza, czy drugi zbiór dla S i ∩ X został już uruchomiony. Jeśli nie, tworzy drugi zestaw i dodaje S i do listy L zestawów podzielonych przez operację. Następnie niezależnie od tego, czy powstał nowy zbiór, algorytm usuwa x z S i i dodaje ją do S i ∩ X . W reprezentacji, w której wszystkie elementy są przechowywane w jednej tablicy, przenoszenie x z jednego zestawu do drugiego można wykonać poprzez zamianę x z końcowym elementem S i , a następnie zmniejszenie indeksu końcowego Si i indeksu początkowego nowego ustawić. Wreszcie, po przetworzeniu wszystkich elementów X w ten sposób, algorytm wykonuje pętlę przez L , oddzielając każdy bieżący zbiór S i z drugiego zestawu, który został z niego oddzielony, i zgłasza oba te zestawy jako nowo utworzone w wyniku operacji udoskonalania.
Czas wykonania pojedynczej operacji uściślenia w ten sposób wynosi O (| X |) , niezależnie od liczby elementów w rodzinie zbiorów, a także niezależnie od całkowitej liczby zbiorów w strukturze danych. Zatem czas na sekwencję udokładnień jest proporcjonalny do całkowitej wielkości zestawów przekazanych algorytmowi na każdym etapie uściślenia.
Aplikacje
Wczesne zastosowanie udoskonalania partycji było w algorytmie Hopcrofta (1971) do minimalizacji DFA . W tym problemie jako dane wejściowe podaje się deterministyczny automat skończony , i musi znaleźć równoważny automat z jak najmniejszą liczbą stanów. Algorytm Hopcrofta utrzymuje podział stanów automatu wejściowego na podzbiory, z tą właściwością, że dowolne dwa stany w różnych podzbiorach muszą być odwzorowane na różne stany automatu wyjściowego. Początkowo istnieją dwa podzbiory, jeden zawierający wszystkie akceptujące stany automatu i drugi zawierający pozostałe stany. W każdym kroku wybierany jest jeden z podzbiorów S i oraz jeden z symboli wejściowych x automatu, a podzbiory stanów są udokładniane do stanów, dla których przejście oznaczone x prowadziłoby do S i , oraz stany, dla których przejście przez x prowadziłoby gdzie indziej. Kiedy zbiór Si ; , który został już wybrany, jest dzielony przez uściślenie, tylko jeden z dwóch wynikowych zbiorów (mniejszy z dwóch) musi być ponownie wybrany w ten sposób każdy stan uczestniczy w zbiorach X dla kroków udoskonalania O ( s log n ) , a cały algorytm zajmuje czas O ( ns log n ) , gdzie n to liczba stanów początkowych, a s to rozmiar alfabetu.
Udoskonalanie partycji zostało zastosowane przez Sethi (1976) w wydajnej implementacji algorytmu Coffmana – Grahama do szeregowania równoległego. Sethi wykazał, że można go użyć do skonstruowania leksykograficznie uporządkowanego topologicznego sortowania danego skierowanego grafu acyklicznego w czasie liniowym; to leksykograficzne uporządkowanie topologiczne jest jednym z kluczowych etapów algorytmu Coffmana – Grahama. W tej aplikacji elementami zbiorów rozłącznych są wierzchołki grafu wejściowego i zbiorów X używane do uszczegółowienia podziału to zbiory sąsiadów wierzchołków. Ponieważ całkowita liczba sąsiadów wszystkich wierzchołków jest po prostu liczbą krawędzi w grafie, algorytm potrzebuje czasu liniowego względem liczby krawędzi, czyli wielkości wejściowej.
Udoskonalenie partycji stanowi również kluczowy krok w leksykograficznym przeszukiwaniu wszerz , algorytmie wyszukiwania grafów z aplikacjami do rozpoznawania grafów akordowych i kilku innych ważnych klas grafów. Ponownie, rozłącznymi elementami zbioru są wierzchołki, a zbiór X reprezentuje zbiory sąsiadów , więc algorytm zajmuje czas liniowy.