V návrhu algoritmu je upřesnění oddílu metodou reprezentující oddíl množiny jako datovou strukturu , která umožňuje její množiny rozdělit na více menších množin. V tomto smyslu je upřesnění dělení duální vůči systému disjunktních množin , který také podporuje dělení do disjunktních množin, ale ve kterém operace kombinují dvojice množin. V některých aplikacích pro upřesnění oddílu, jako je lexikografické prohledávání do šířky , struktura dat také zachovává pořadí sad v oddílu.
Zpřesnění oddílů je klíčovou součástí několika účinných algoritmů pro grafy a konečných automatů , včetně minimalizace DFA , Coffman-Grahamova algoritmu pro paralelní plánování a lexikografického prohledávání do šířky . [1] [2] [3]
Algoritmus zpřesnění rozdělení podporuje rodinu disjunktních množin Si . Na začátku algoritmu tato rodina obsahuje jedinou množinu všech prvků v datové struktuře. V každém kroku algoritmus získá množinu X a každá množina S i v rodině obsahující prvky X je rozdělena do dvou množin: průnik S i ∩ X a rozdíl S i \ X
Tento algoritmus lze efektivně implementovat pomocí datových struktur reprezentujících následující informace: [4] [5]
K provedení operace upřesnění algoritmus iteruje prvky dané množiny X . Pro každý takový prvek x najde množinu S i , která obsahuje x a zkontroluje , zda byl proveden průsečík S i ∩ X . Pokud ne, vytvoří druhou množinu a přidá S i do seznamu L množin oddělených operací. Poté, bez ohledu na to, zda byla vytvořena nová množina, algoritmus odstraní x z S i a přidá je k S i ∩ X prohodí s posledním prvkem S i a poté sníží koncový index S i a počáteční index nové množiny. . Nakonec, poté, co byly všechny prvky X tímto způsobem zpracovány, algoritmus prochází L , přičemž rozděluje každou aktuální množinu Si na dvě, přičemž obě tyto množiny považuje za vytvořené v důsledku operace zpřesnění.
Časový odhad pro provedení jedné operace upřesnění tímto způsobem je O (| X |) , bez ohledu na počet prvků v rodině množin a také bez ohledu na celkový počet sad v datové struktuře. Proto je doba provádění upřesňovací sekvence úměrná celkové velikosti sad daných algoritmu v každé fázi upřesňování.
Jedna z prvních aplikací zpřesňování oddílů byla nalezena v Hopcroftově algoritmu pro minimalizaci DFA [6] . V tomto problému je jako vstup zadán deterministický konečný automat a ten musí najít ekvivalentní automat s co nejmenším počtem stavů. Hopcroftův algoritmus podporuje rozdělení stavů vstupního automatu do podmnožin s tou vlastností, že libovolné dva stavy v různých podmnožinách musí být mapovány na různé stavy výstupního automatu. Zpočátku existují dvě podmnožiny, z nichž jedna obsahuje všechny přijímací stavy automatu a druhá obsahuje zbytek. V každém kroku je vybrána jedna podmnožina Si a jeden ze vstupních symbolů x automatu a stavové podmnožiny jsou upřesněny na stavy, pro které přechod označený x povede k S i , a stavy, pro které x povede k jinému. místo. Když je zvolená množina Si rozdělena upřesněním, je třeba znovu uvažovat pouze jednu ze dvou výsledných množin (menší ze dvou); každý stav se tedy účastní množin X během upřesňovacích kroků O ( s log n ) a celkový odhad času algoritmu je O ( ns log n ) , kde n je počet počátečních stavů a s je velikost abecedy. [6]
Zpřesnění oddílů bylo aplikováno Sethi [7] v efektivní implementaci Coffman-Grahamova algoritmu pro paralelní plánování. Sethi ukázal, že může být použit ke konstrukci lexikograficky uspořádaného topologického druhu daného orientovaného acyklického grafu v lineárním čase; toto lexikografické topologické uspořádání je jedním z klíčových kroků v Coffman-Grahamově algoritmu. V této aplikaci jsou prvky disjunktních množin vrcholy vstupního grafu a množiny X použité k upřesnění rozdělení jsou sousední množiny vrcholů. Protože celkový počet sousedů všech vrcholů je jednoduše počet hran v grafu, algoritmus potřebuje čas, který je lineární v počtu hran.
Zpřesnění oddílu je také klíčovým krokem v lexikografickém prohledávání šířky, algoritmu prohledávání grafů s aplikacemi pro rozpoznávání akordických grafů a některých dalších důležitých tříd grafů. V těchto případech jsou prvky disjunktních množin vrcholy a množina X je množina bodů sousedství , takže algoritmus trvá lineárně. [8] [9]