În proiectarea algoritmului , rafinarea partiției este o metodă de reprezentare a unei partiții a unui set ca o structură de date care permite ca seturile sale să fie împărțite în seturi mai mici. În acest sens, rafinarea partiționării este duală cu sistemul de mulțimi disjuncte , care acceptă și partiționarea în mulțimi disjunse, dar în care operațiunile combină perechi de mulțimi. În unele aplicații de rafinare a partițiilor, cum ar fi căutarea lexicografică pe lățimea întâi , structura de date menține, de asemenea, ordinea seturilor în cadrul partiției.
Rafinarea partiției este o componentă cheie a mai multor algoritmi eficienți pentru grafice și automate finite , inclusiv minimizarea DFA , algoritmul Coffman-Graham pentru programarea paralelă și căutarea lexicografică pe lățimea întâi . [1] [2] [3]
Algoritmul de rafinare a partiției suportă familia de mulțimi disjunse S i . La începutul algoritmului, această familie conține singurul set de toate elementele din structura de date. La fiecare pas, algoritmul obține o mulțime X , iar fiecare mulțime S i din familia care conține elemente ale lui X este împărțită în două mulțimi: intersecția S i ∩ X și diferența S i \ X
Acest algoritm poate fi implementat eficient folosind structuri de date reprezentând următoarele informații: [4] [5]
Pentru a efectua operația de rafinare, algoritmul iterează peste elementele mulțimii date X . Pentru fiecare astfel de element x , găsește o mulțime S i care conține x și verifică dacă intersecția S i ∩ X a fost făcută . Dacă nu, creează un al doilea set și adaugă S i la lista de L seturi separate de operație. Apoi, indiferent dacă s-a format o nouă mulțime, algoritmul elimină x din Si și îl adaugă la S i ∩ X schimbând cu ultimul element S i și apoi micșorând indicele final Si și indicele de început al noii mulțimi . În cele din urmă, după ce toate elementele lui X au fost procesate în acest mod, algoritmul trece prin L , împărțind fiecare mulțime curentă S i în două, considerând ambele mulțimi ca fiind formate ca urmare a operației de rafinare.
Timpul estimat pentru efectuarea unei singure operații de rafinare în acest mod este O (| X |) , indiferent de numărul de elemente din familia de mulțimi și, de asemenea, indiferent de numărul total de mulțimi din structura de date. Prin urmare, timpul de execuție al secvenței de rafinare este proporțional cu dimensiunea totală a mulțimilor date algoritmului la fiecare etapă de rafinare.
Una dintre primele aplicații de rafinare a partițiilor a fost găsită în algoritmul lui Hopcroft pentru minimizarea DFA [6] . În această problemă, un automat finit determinist este dat ca intrare și trebuie să găsească un automat echivalent cu cât mai puține stări posibil. Algoritmul lui Hopcroft acceptă împărțirea stărilor automatelor de intrare în subseturi cu proprietatea că oricare două stări din subseturi diferite trebuie mapate la stări diferite ale automatelor de ieșire. Inițial, există două subseturi, dintre care unul conține toate stările de acceptare ale automatului, iar celălalt conține restul. La fiecare pas, se selectează un submult Si și unul dintre simbolurile de intrare x ale automatului, iar subseturile de stări sunt rafinate la stări pentru care tranziția etichetată x va duce la Si și stări pentru care x va duce la alta. loc. Când mulțimea aleasă S i este împărțită prin rafinare, doar una dintre cele două mulțimi rezultate (cea mai mică dintre cele două) trebuie luată în considerare din nou; astfel, fiecare stare participă la seturile X în timpul pașilor de rafinare O ( s log n ) , iar estimarea generală a timpului algoritmului este O ( ns log n ) , unde n este numărul de stări inițiale și s este dimensiunea alfabetului. [6]
Rafinarea partiției a fost aplicată de Sethi [7] într-o implementare eficientă a algoritmului Coffman-Graham pentru planificarea paralelă. Sethi a arătat că poate fi folosit pentru a construi un tip topologic ordonat lexicografic al unui graf aciclic direcționat dat în timp liniar; această ordonare topologică lexicografică este unul dintre pașii cheie în algoritmul Coffman-Graham. În această aplicație, elementele mulțimilor disjunctive sunt vârfurile graficului de intrare, iar mulțimile X utilizate pentru a rafina împărțirea sunt mulțimile vecine ale vârfurilor. Deoarece numărul total de vecini ai tuturor vârfurilor este pur și simplu numărul de muchii din grafic, algoritmul ia timp care este liniar în numărul de muchii.
Rafinarea partiției este, de asemenea, un pas cheie în căutarea lexicografică pe lățimea întâi, un algoritm de căutare în graf cu aplicații pentru recunoașterea grafurilor cordale și alte câteva clase importante de grafuri. În aceste cazuri, elementele mulțimilor disjunctive sunt vârfuri, iar mulțimea X este mulțimi de puncte de vecinătate , deci algoritmul ia timp liniar. [8] [9]