Förfining av partitionen
I utformningen av algoritmer är partitionsförfining en teknik för att representera en partition av en uppsättning som en datastruktur som gör att partitionen kan förfinas genom att dela upp dess uppsättningar i ett större antal mindre uppsättningar. I den meningen är det dubbelt med union-find-datastrukturen , som också upprätthåller en partition i disjunkta uppsättningar men där operationerna slår samman par av uppsättningar. I vissa tillämpningar av partitionsförfining, såsom lexikografisk bredd-först-sökning , upprätthåller datastrukturen också en ordning på uppsättningarna i partitionen.
Förfining av partitioner utgör en nyckelkomponent i flera effektiva algoritmer för grafer och ändliga automater , inklusive DFA-minimering , Coffman –Graham-algoritmen för parallell schemaläggning och lexikografisk bredd-första sökning av grafer.
Datastruktur
En partitionsförfiningsalgoritm upprätthåller en familj av disjunkta uppsättningar Si . I början av algoritmen innehåller denna familj en enda uppsättning av alla element i datastrukturen. Vid varje steg i algoritmen presenteras en mängd X för algoritmen , och Si ∩ X varje mängd Si \ X Si i familjen som innehåller medlemmar av X delas upp i två uppsättningar, skärningspunkten och skillnaden .
En sådan algoritm kan implementeras effektivt genom att upprätthålla datastrukturer som representerar följande information:
- Den ordnade sekvensen av uppsättningarna S i i familjen, i en form som en dubbellänkad lista som gör att nya uppsättningar kan infogas i mitten av sekvensen
- Associerad med varje uppsättning Si en , en samling av dess element av Si , i form såsom en dubbellänkad lista eller matrisdatastruktur som möjliggör snabb radering av individuella element från samlingen. Alternativt kan denna komponent av datastrukturen representeras genom att lagra alla element i alla uppsättningar i en enda array, sorterade efter identiteten för den uppsättning de tillhör, och genom att representera samlingen av element i vilken uppsättning som helst Si genom dess start- och slutpositioner i denna array.
- Associerad med varje element, uppsättningen den tillhör.
För att utföra en förfiningsoperation går algoritmen genom elementen i den givna uppsättningen X. För Si ∩ X varje sådant element x hittar den mängden Si som innehåller x och kontrollerar om en andra mängd för redan har startat. Om inte, skapar den den andra uppsättningen och lägger till Si till en lista L över de uppsättningar som delas av operationen. Sedan Si , oavsett om en ny uppsättning Si ∩ X bildades, tar algoritmen bort x från och adderar den till . I representationen där alla element är lagrade i en enda array, kan flytta Si x Si från en uppsättning till en annan utföras genom att byta x med det sista elementet av och sedan minska slutindexet för och startindexet för det nya uppsättning. Slutligen, efter att alla element i X har bearbetats på detta sätt, slingrar algoritmen genom L och separerar varje aktuell uppsättning Si från den andra uppsättningen som har delats från den, och rapporterar båda dessa uppsättningar som nybildade av förfiningen drift.
Tiden för att utföra en enda förfiningsoperation på detta sätt är O (| X |) , oberoende av antalet element i familjen av uppsättningar och även oberoende av det totala antalet uppsättningar i datastrukturen. Sålunda är tiden för en sekvens av förfinningar proportionell mot den totala storleken på uppsättningarna som ges till algoritmen i varje förfiningssteg.
Ansökningar
En tidig tillämpning av partitionsförfining var i en algoritm av Hopcroft (1971) för DFA-minimering . I detta problem får man som indata en deterministisk finit automat , och måste hitta en ekvivalent automat med så få tillstånd som möjligt. Hopcrofts algoritm upprätthåller en uppdelning av tillstånden för inmatningsautomaten i delmängder, med egenskapen att två tillstånd i olika delmängder måste mappas till olika tillstånd av utmatningsautomaten. Inledningsvis finns det två delmängder, en som innehåller alla accepterande tillstånd för automaten och en som innehåller de återstående tillstånden. Vid varje steg väljs en av delmängderna Si leda och en av automatens ingångssymboler x , och delmängderna av tillstånd förfinas till tillstånd för vilka en övergång märkt x skulle till Si - , och tillstånd för vilka en x övergången skulle leda någon annanstans. När en uppsättning Si som redan har valts delas av en förfining, behöver bara en av de två resulterande uppsättningarna (den minsta av de två) väljas igen; på detta sätt deltar varje tillstånd i uppsättningarna X för O ( s log n ) förfiningsstegen och den övergripande algoritmen tar tid O ( ns log n ) , där n är antalet initiala tillstånd och s är storleken på alfabetet.
Partitionsförfining tillämpades av Sethi (1976) i en effektiv implementering av Coffman-Graham-algoritmen för parallell schemaläggning. Sethi visade att den kunde 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 denna applikation är elementen i de disjunkta uppsättningarna hörn i inmatningsgrafen och uppsättningarna X som används för att förfina partitionen är uppsättningar av grannar till hörn. Eftersom det totala antalet grannar till alla hörn bara är antalet kanter i grafen, tar algoritmen tid linjärt i antalet kanter, dess indatastorlek.
Förfining av partitioner utgör också ett nyckelsteg i lexikografisk bredd-först-sökning, en grafsökningsalgoritm med tillämpningar för igenkänning av ackordsgrafer och flera andra viktiga klasser av grafer. Återigen, de disjunkta uppsättningselementen är hörn och uppsättningen X representerar uppsättningar av grannar , så algoritmen tar linjär tid.