Upřesnění oddílu - Partition refinement
Při navrhování algoritmů , oddíl zjemnění je technika pro znázornění rozdělení množiny jako datové struktury , která umožňuje oddíl k rafinování rozdělením jeho sady do většího množství menších sad. V tomto smyslu je duální pro datovou strukturu union-find , která také udržuje oddíl na disjunktní sady, ale ve kterém operace slučují páry sad. V některých aplikacích zpřesňování oddílů, jako je lexikografické vyhledávání do šířky , datová struktura udržuje také uspořádání sad v oddílu.
Upřesnění oddílů tvoří klíčovou součást několika efektivních algoritmů na grafech a konečných automatech , včetně minimalizace DFA , Coffman-Grahamova algoritmu pro paralelní plánování a lexikografického vyhledávání grafů do šířky .
Datová struktura
Algoritmus upřesnění oddílu udržuje rodinu disjunktních sad S i . Na začátku algoritmu tato rodina obsahuje jedinou sadu všech prvků v datové struktuře. V každém kroku algoritmu, soubor X je předložen algoritmus, a každá sada S i v rodině, která obsahuje členy X, je rozdělena do dvou množin je průsečík S i ∩ X a rozdíl S i \ X .
Takový algoritmus lze efektivně implementovat udržováním datových struktur představujících následující informace:
- Uspořádaná posloupnost sad S i v rodině ve formě, jako je dvojitě propojený seznam, který umožňuje vložení nových sad do středu posloupnosti
- Přidružený ke každé sadě S i , kolekce jejích prvků S i , ve formě, jako je dvojitě propojený seznam nebo datová struktura pole, která umožňuje rychlé vymazání jednotlivých prvků ze sbírky. Alternativně může být tato komponenta datové struktury reprezentována uložením všech prvků všech sad do jednoho pole, seřazeno podle identity sady, do které patří, a reprezentací kolekce prvků v jakékoli sadě S i jeho počáteční a koncové pozice v tomto poli.
- Ke každému prvku je přidružena sada, do které patří.
Chcete-li provést operaci upřesnění, algoritmus prochází prvky dané množiny X . Pro každý takový prvek x najde množinu S i, která obsahuje x , a zkontroluje, zda již byla spuštěna druhá sada pro S i ∩ X. Pokud ne, vytvoří druhou sadu a přidá S i do seznamu L sad, které jsou operací rozděleny. Potom, bez ohledu na to, zda byl vytvořen nový soubor, algoritmus odstraňuje x od S i a přidá ji do S i ∩ X . Ve znázornění, ve které jsou všechny prvky uloženy v jednom poli, pohybující x z jednoho souboru do druhého může být provedena tím, že vymění x s konečným prvkem S i a dekrementaci koncový index S i a začátek index nové soubor. Nakonec, poté, co byly všechny prvky X zpracovány tímto způsobem, algoritmus prochází L , odděluje každou aktuální sadu S i od druhé sady, která z ní byla rozdělena, a hlásí obě tyto sady jako nově vytvořené upřesněním úkon.
Čas k provedení jedné operace upřesnění tímto způsobem je O (| X |) , nezávislý na počtu prvků v rodině sad a také nezávislý na celkovém počtu sad v datové struktuře. Čas pro sekvenci upřesnění je tedy úměrný celkové velikosti sad daných algoritmu v každém kroku upřesnění.
Aplikace
Časná aplikace zpřesnění oddílu byla v algoritmu Hopcroft (1971) pro minimalizaci DFA . V tomto problému je jako vstup zadán deterministický konečný automat a musí se najít ekvivalentní automat s co nejmenším počtem stavů. Hopcroftův algoritmus udržuje rozdělení stavů vstupního automatu do podmnožin s vlastností, že jakékoli dva stavy v různých podskupinách musí být mapovány do různých stavů výstupního automatu. Zpočátku existují dvě podmnožiny, jedna obsahuje všechny přijímající stavy automatu a druhá obsahuje zbývající stavy. V každém kroku je vybrána jedna z podmnožin S i a jeden ze vstupních symbolů x automatu a podmnožiny stavů jsou upřesněny do stavů, pro které by přechod označený x vedl k S i , a stavů, pro které x - přechod by vedl někam jinam. Když je sada S i , která již byla vybrána, rozdělena upřesněním, je třeba znovu vybrat pouze jednu ze dvou výsledných sad (menší z těchto dvou); tímto způsobem se každý stav účastní sad X pro kroky upřesnění O ( s log n ) a celkový algoritmus potřebuje čas O ( ns log n ) , kde n je počet počátečních stavů a s je velikost abecedy.
Upřesnění oddílů použil Sethi (1976) při efektivní implementaci Coffman -Grahamova algoritmu pro paralelní plánování. Sethi ukázal, že by mohl být použit ke konstrukci lexikograficky uspořádaného topologického druhu daného řízeného acyklického grafu v lineárním čase; toto lexikografické topologické uspořádání je jedním z klíčových kroků algoritmu Coffman – Graham. V této aplikaci jsou prvky disjunktních množin vrcholy vstupního grafu a sady X použité k upřesnění oddílu jsou sady sousedů vrcholů. Protože celkový počet sousedů všech vrcholů je pouze počet hran v grafu, algoritmus potřebuje čas lineární v počtu hran, jeho vstupní velikosti.
Upřesnění oddílů také tvoří klíčový krok v lexikografickém hledání od začátku , algoritmus pro vyhledávání grafů s aplikacemi pro rozpoznávání akordických grafů a několik dalších důležitých tříd grafů. Opět platí, že disjunktní množinové prvky jsou vrcholy a množina X představuje množiny sousedů , takže algoritmus potřebuje lineární čas.