I algoritmdesign är partitionsförfining en metod för att representera en partition av en uppsättning som en datastruktur som gör att dess uppsättningar kan delas upp i fler mindre uppsättningar. I denna mening är förfining av partitionering dubbelt med disjoint set-systemet , som också stöder partitionering i disjoint set, men där operationer kombinerar par av set. I vissa tillämpningar för förfining av partitioner, som lexikografisk bredd-först-sökning , bibehåller datastrukturen också ordningen för uppsättningarna inom partitionen.
Partitionsförfining är en nyckelkomponent i flera effektiva algoritmer för grafer och finita automater , inklusive DFA-minimering , Coffman–Graham-algoritmen för parallell schemaläggning och lexikografisk bredd-först-sökning . [1] [2] [3]
Algoritmen för partitionsförfining stöder familjen av disjunkta uppsättningar Si . I början av algoritmen innehåller denna familj den enda uppsättningen av alla element i datastrukturen. Vid varje steg erhåller algoritmen en mängd X , och varje mängd Si i familjen som innehåller element av X delas upp i två uppsättningar : skärningspunkten Si ∩ X och skillnaden S i \ X
Denna algoritm kan implementeras effektivt med hjälp av datastrukturer som representerar följande information: [4] [5]
För att utföra förfiningsoperationen itererar algoritmen över elementen i den givna uppsättningen X. För varje sådant element x hittar den en mängd Si som innehåller x och kontrollerar om skärningen Si ∩ X har gjorts . Om inte, skapar den en andra uppsättning och lägger till Si till listan med L uppsättningar separerade av operationen. Sedan, oavsett om en ny mängd har bildats, tar algoritmen bort x från Si och adderar den till Si ∩ X byter med det sista elementet Si och minskar sedan slutindexet Si och startindexet för den nya mängden . Slutligen, efter att alla element i X har bearbetats på detta sätt, går algoritmen genom L , och delar varje strömmängd Si i två, och betraktar båda dessa uppsättningar som bildade som ett resultat av förfiningsoperationen.
Tidsuppskattningen för att utföra en enda förfiningsoperation på detta sätt är O (| X |) , oavsett antalet element i uppsättningsfamiljen, och även oberoende av det totala antalet uppsättningar i datastrukturen. Därför är exekveringstiden för förfiningssekvensen proportionell mot den totala storleken på uppsättningarna som ges till algoritmen vid varje förfiningssteg.
En av de första tillämpningarna av partitionsförfining hittades i Hopcrofts algoritm för att minimera DFA [6] . I det här problemet ges en deterministisk finit automat som indata , och den måste hitta en ekvivalent automat med så få tillstånd som möjligt. Hopcrofts algoritm stöder uppdelningen av inmatningsautomattillstånd i delmängder med egenskapen att två valfria tillstånd i olika delmängder måste mappas till olika utgångsautomattillstånd. Inledningsvis finns det två delmängder, varav den ena innehåller alla accepterande tillstånd för automaten och den andra innehåller resten. Vid varje steg väljs en delmängd Si och en av automatens ingångssymboler x , och tillståndsundermängderna förfinas till tillstånd för vilka övergången märkt x kommer att leda till Si , och tillstånd för vilka x kommer att leda till en annan plats. När den valda uppsättningen Si delas genom förfining, behöver endast en av de två resulterande uppsättningarna (den minsta av de två) beaktas igen; sålunda deltar varje tillstånd i uppsättningar X under O ( slogn ) -förfiningsstegen , och den övergripande algoritmtidsuppskattningen är O ( nslogn ) , där n är antalet initiala tillstånd och s är alfabetets storlek . [6]
Partitionsförfining tillämpades av Sethi [7] i en effektiv implementering av Coffman-Graham-algoritmen för parallell schemaläggning. Sethi visade att den kan användas för att konstruera en lexikografiskt ordnad topologisk sort av en given riktad acyklisk graf i linjär tid; denna lexikografiska topologiska ordning är ett av nyckelstegen i Coffman-Graham-algoritmen. I den här applikationen är elementen i de disjunkta uppsättningarna hörn av ingångsgrafen, och uppsättningarna X som används för att förfina uppdelningen är grannmängderna till hörnen. Eftersom det totala antalet grannar till alla hörn helt enkelt är antalet kanter i grafen, tar algoritmen tid som är linjär i antalet kanter.
Förfining av partitioner är också ett nyckelsteg i lexikografisk bredd-först-sökning, en grafsökningsalgoritm med applikationer för att känna igen ackordsgrafer och några andra viktiga klasser av grafer. I dessa fall är elementen i de disjunkta uppsättningarna hörn, och mängden X är grannskapspunkter , så algoritmen tar linjär tid. [8] [9]