Topologinen lajittelu - Topological sorting

Vuonna tietojenkäsittelytiede , eli topologinen lajittelu tai topologinen tilaaminen on suunnattu verkko on lineaarinen tilaaminen sen kärkipisteet siten, että jokaista suunnatun reunan uv solmusta u solmuun v , u tulee ennen v tilauksessa. Esimerkiksi kaavion kärkipisteet voivat edustaa suoritettavia tehtäviä ja reunat voivat esittää rajoituksia, jotka yksi tehtävä on suoritettava ennen toista; Tässä sovelluksessa topologinen järjestys on vain kelvollinen järjestys tehtäville. Täsmälleen topologinen lajittelu on kaavion läpikulku, jossa jokainen solmu v vieraillaan vasta sen jälkeen, kun kaikki sen riippuvuudet on käyty . Topologinen järjestys on mahdollinen silloin ja vain, jos kuvaajalla ei ole suunnattuja syklejä , toisin sanoen jos se on suunnattu asyklinen kuvaaja (DAG). Jokaisella DAG: lla on vähintään yksi topologinen järjestys, ja algoritmit tunnetaan minkä tahansa DAG: n topologisen järjestyksen muodostamiseksi lineaarisessa ajassa . Topologisella lajittelulla on monia sovelluksia erityisesti luokitusongelmissa, kuten palautekaarijoukossa . Topologinen lajittelu on mahdollista, vaikka DAG on irrottanut komponentit .

Esimerkkejä

Topologisen lajittelun kaanoninen sovellus on työtehtävien tai tehtävien ajoituksen määrittäminen niiden riippuvuuksien perusteella . Töitä edustavat kärkipisteet, ja x: n ja y: n välillä on reuna, jos työ x on suoritettava ennen työn y aloittamista (esimerkiksi pyykinpesun aikana pesukoneen on lopetettava ennen kuin laitamme vaatteet kuivausrumpuun) . Sitten topologinen lajittelu antaa järjestyksen töiden suorittamiseksi. Läheisesti liittyvää topologisten lajittelualgoritmien sovellusta tutkittiin ensimmäisen kerran 1960 -luvun alussa PERT -tekniikan yhteydessä projektinhallinnan ajoitukseen . Tässä sovelluksessa kaavion kärkipisteet edustavat projektin virstanpylväitä ja reunat edustavat tehtäviä, jotka on suoritettava virstanpylvään välillä. Topologinen lajittelu muodostaa perustan lineaarisille aika-algoritmeille projektin kriittisen polun löytämiseksi , virstanpylväiden ja tehtävien sarjan, joka ohjaa projektin kokonaisaikataulun pituutta.

Tietotekniikassa, sovellukset tämäntyyppisen syntyy opetus aikataulujen , tilaaminen kaavan solun arviointiin, kun Lasketaan uudelleen kaava arvot taulukkolaskenta , logiikkasynteesistä , määräytymisjärjestyksestä käännettäessä tehtäviä esiintymään Makefilet , tietojen serialization , ja ratkaista symboli riippuvuussuhteet linkkereitä . Sitä käytetään myös päättämään, missä järjestyksessä taulukot ladataan vierailla avaimilla tietokantoihin.

Vasemmalla olevassa kaaviossa on monia päteviä topologisia tyyppejä, mukaan lukien: 5, 7, 3, 11, 8, 2, 9, 10 (visuaalinen ylhäältä alas, vasemmalta oikealle) 3, 5, 7, 8, 11, 2, 9, 10 (pienin käytettävissä oleva kärkipiste ensin) 5, 7, 3, 8, 11, 10, 9, 2 (vähiten reunat ensin) 7, 5, 11, 3, 10, 8, 9, 2 (suurin numeroitu käytettävissä oleva kärki ensin) 5, 7, 11, 2, 3, 8, 9, 10 (yritetään ylhäältä alas, vasemmalta oikealle) 3, 7, 8, 5, 11, 10, 2, 9 (mielivaltainen)

Algoritmit

Tavallisilla topologisen lajittelun algoritmeilla on lineaarinen ajoaika solmujen lukumäärässä ja reunojen lukumäärä, asymptoottisesti, ${\ displaystyle O (\ vasen | {V} \ oikea |+\ vasen | {E} \ oikea |).}$

Kahnin algoritmi

Yksi näistä algoritmeista, jonka Kahn (1962) kuvasi ensimmäisen kerran , toimii valitsemalla kärkipisteet samassa järjestyksessä kuin mahdollinen topologinen lajittelu. Etsi ensin luettelo "aloitussolmuista", joilla ei ole tulevia reunoja, ja lisää ne joukkoon S; vähintään yhden tällaisen solmun on oltava ei-tyhjässä asyklisessä kaaviossa. Sitten:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge

while S is not empty do
    remove a node n from S
    add n to L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

if graph has edges then
    return error   (graph has at least one cycle)
else 
    return L   (a topologically sorted order)

Jos kuvaaja on DAG , ratkaisu sisältyy luetteloon L (ratkaisu ei välttämättä ole ainutlaatuinen). Muussa tapauksessa kaaviossa on oltava vähintään yksi sykli, joten topologinen lajittelu on mahdotonta.

Rakenne S voi heijastaa syntyneen lajittelun ei-ainutlaatuisuutta, ja se voi olla yksinkertaisesti joukko tai jono tai pino. Riippuen järjestyksestä, jolla solmut n poistetaan joukosta S, luodaan erilainen ratkaisu. Muunnelma Kahnin algoritmista, joka rikkoo siteet sanastografisesti, muodostaa keskeisen osan Coffman -Graham -algoritmia rinnakkaista ajoitusta ja kerrostettua kuvaajapiirrosta varten .

Syvyyshaku

Vaihtoehtoinen algoritmi topologista lajittelua varten perustuu syvyyshakuun . Algoritmi kulkee kaavion jokaisen solmun läpi mielivaltaisessa järjestyksessä ja aloittaa syvyyshaun, joka päättyy, kun se osuu mihinkään solmuun, jossa on jo vierailtu topologisen lajittelun alusta lähtien tai solmulla ei ole lähteviä reunoja (esim. lehtisolmu):

L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then
        return
    if n has a temporary mark then
        stop   (not a DAG)

    mark n with a temporary mark

    for each node m with an edge from n to m do
        visit(m)

    remove temporary mark from n
    mark n with a permanent mark
    add n to head of L

Kukin solmu n saa prepended lähtöön lista L vasta, kun otetaan huomioon kaikki muut solmut, jotka ovat riippuvaisia n (kaikki jälkeläiset n kaaviossa). Erityisesti, kun algoritmi lisää solmun n , takaamme, että kaikki solmut, jotka riippuvat n: stä, ovat jo lähtöluettelossa L: ne lisättiin L: ään joko rekursiivisella vierailukutsulla (), joka päättyi ennen vierailukutsua n , tai vierailukutsulla (), joka alkoi jo ennen kutsua vierailla n . Koska jokaisella reunalla ja solmulla vieraillaan kerran, algoritmi toimii lineaarisessa ajassa. Tämä syvyyshakuun perustuva algoritmi on Cormenin et ai. (2001) ; näyttää siltä, ​​että Tarjan on kuvannut sen ensimmäisen kerran painettuna vuonna 1976.

Rinnakkaisalgoritmit

On rinnakkainen random-access kone , topologinen tilaus voidaan konstruoida O (log ² n ) aika käyttämällä polynomia prosessorien lukumäärä, mikä ongelma tulee kompleksisuusluokka NC ² . Yksi tapa tehdä tämä on neliöidä toistuvasti annetun kuvaajan vierekkäismatriisi , logaritmisesti monta kertaa, käyttämällä min-plus-matriisin kertolaskua maksimoimalla minimoinnin sijasta. Tuloksena oleva matriisi kuvaa kaavion pisimmät polkuetäisyydet. Kun kärkipisteet lajitellaan niiden pisimpien saapuvien reittien pituuksien mukaan, saadaan aikaan topologinen järjestys.

Algoritmi rinnakkaista topologista lajittelua varten hajautetuissa muistikoneissa rinnastaa Kahnin algoritmin DAG: lle . Korkealla tasolla Kahnin algoritmi poistaa toistuvasti indegree 0: n kärkipisteet ja lisää ne topologiseen lajitteluun siinä järjestyksessä, jossa ne poistettiin. Koska myös poistettujen pisteiden lähtevät reunat poistetaan, tulee uusi joukko pisteitä, joiden aste on 0, jossa menettely toistetaan, kunnes kärkipisteitä ei ole jäljellä. Tämä algoritmi suorittaa iteraatioita, joissa D on pisin polku G: ssä . Jokainen iterointi voidaan rinnastaa, mikä on seuraavan algoritmin idea. ${\ displaystyle G = (V, E)}$${\ displaystyle D+1}$

Seuraavassa oletetaan, että kuvaajaosio on tallennettu p prosessointielementteihin (PE), jotka on merkitty . Jokainen PE i alustaa joukon paikallisia pisteitä, joilla on aste 0, jossa ylempi indeksi edustaa nykyistä iteraatiota. Koska kaikilla paikallisjoukkojen kärkipisteillä on aste 0, eli ne eivät ole vierekkäisiä, ne voidaan antaa mielivaltaisessa järjestyksessä kelvollista topologista lajittelua varten. Yleisen indeksin määrittämiseksi kullekin kärkipisteelle lasketaan etuliitteen summa . Joten jokaisessa vaiheessa topologiseen lajitteluun lisätään kärkipisteitä. ${\ displaystyle 0, \ dots, p-1}$${\ displaystyle Q_ {i}^{1}}$${\ displaystyle Q_ {0}^{1}, \ pisteitä, Q_ {p-1}^{1}}$${\ displaystyle Q_ {0}^{1}, \ pisteitä, Q_ {p-1}^{1}}$${\ texttyle \ sum _ {i = 0}^{p-1} | Q_ {i} |}$

Rinnakkaisen topologisen lajittelualgoritmin suorittaminen DAG: llä, jossa on kaksi käsittelyelementtiä.

Ensimmäisessä vaiheessa PE j määrittää indeksit paikallisille kärkipisteille . Nämä kärkipisteet poistetaan yhdessä niitä vastaavien lähtevien reunojen kanssa. Kullekin lähtevälle reunalle, jolla on päätepiste v toisessa PE: ssä , viesti lähetetään PE l: ään . Kun kaikki kärkipisteet on poistettu, lähetetyt viestit lähetetään vastaavalle PE: lle. Jokainen vastaanotettu viesti päivittää paikallisen kärjen v asteen . Jos aste laskee nollaan, v lisätään kohtaan . Sitten alkaa seuraava iterointi. ${\ texttyle \ sum _ {i = 0}^{j-1} | Q_ {i}^{1} |, \ pisteitä, \ vasen (\ sum _ {i = 0}^{j} | Q_ {i }^{1} | \ oikea) -1}$${\ displaystyle Q_ {j}^{1}}$${\ displaystyle Q_ {j}^{1}}$${\ displaystyle (u, v)}$${\ displaystyle l, j \ neq l}$${\ displaystyle (u, v)}$${\ displaystyle Q_ {j}^{1}}$${\ displaystyle (u, v)}$${\ displaystyle Q_ {j}^{2}}$

Vaiheessa k , PE j määrittää indeksit , missä on käsiteltyjen pisteiden kokonaismäärä vaiheen jälkeen . Tämä menettely toistetaan, kunnes käsiteltäviä pisteitä ei ole jäljellä . Alla on yleiskatsaus yhteen ohjelmaan, useiden tietojen pseudokoodikatsaus tästä algoritmista. ${\ texttyle a_ {k-1}+\ summa _ {i = 0}^{j-1} | Q_ {i}^{k} |, \ pisteet, a_ {k-1}+\ vasen (\ summa _ {i = 0}^{j} | Q_ {i}^{k} | \ oikea) -1}$${\ displaystyle a_ {k-1}}$${\ displaystyle k-1}$${\ texttyle \ sum _ {i = 0}^{p-1} | Q_ {i}^{D+1} | = 0}$

Huomaa, että paikallisten siirtojen etuliitteen summa voidaan laskea tehokkaasti rinnakkain. ${\ texttyle a_ {k-1}+\ summa _ {i = 0}^{j-1} | Q_ {i}^{k} |, \ pisteet, a_ {k-1}+\ vasen (\ summa _ {i = 0}^{j} | Q_ {i}^{k} | \ oikea) -1}$

p processing elements with IDs from 0 to p-1
Input: G = (V, E) DAG, distributed to PEs, PE index j = 0, ..., p - 1
Output: topological sorting of G

function traverseDAGDistributed
    δ incoming degree of local vertices V
    Q = {v ∈ V | δ[v] = 0}                     // All vertices with indegree 0
    nrOfVerticesProcessed = 0

    do                 
        global build prefix sum over size of Q     // get offsets and total amount of vertices in this step
        offset = nrOfVerticesProcessed + sum(Qi, i = 0 to j - 1)          // j is the processor index
        foreach u in Q                                       
            localOrder[u] = index++;
            foreach (u,v) in E do post message (u, v) to PE owning vertex v
        nrOfVerticesProcessed += sum(|Qi|, i = 0 to p - 1)
        deliver all messages to neighbors of vertices in Q  
        receive messages for local vertices V
        remove all vertices in Q
        foreach message (u, v) received:
            if --δ[v] = 0
                add v to Q
    while global size of Q > 0

    return localOrder

Viestintäkustannukset riippuvat suuresti annetusta graafiosiosta. Mitä tulee ajonaikaan, tämä algoritmi toimii CRCW-PRAM- mallissa, joka mahdollistaa haun ja vähennyksen vakioaikana , jossa D on jälleen pisin polku G: ssä ja Δ maksimiaste. ${\ texttyle {\ mathcal {O}} \ vasen ({\ frac {m+n} {p}}+D (\ Delta+\ log n) \ right)}$

Sovellus lyhyimmän polun löytämiseen

Topologinen tilaus voidaan käyttää myös nopeasti laskea lyhimmän polun kautta painotettu suunnattu asyklinen kaavio. Olkoon V tällaisen kuvaajan kärkipisteiden luettelo topologisessa järjestyksessä. Sitten seuraava algoritmi laskee lyhyimmän polun jostakin lähteen kärjestä s kaikkiin muihin pisteisiin:

Vastaavasti:

N kärjen ja m reunan kuvaajalla tämä algoritmi vie Θ ( n + m ) eli lineaarisen ajan.

Ainutlaatuisuus

Jos topologinen lajittelu on se ominaisuus, että kaikki parit peräkkäisten pisteiden lajitellut järjestyksessä on liitetty reunoista, niin nämä reunat muodostavat suunnattu Hamiltonin polku on DAG . Jos Hamiltonin polku on olemassa, topologinen lajittelujärjestys on ainutlaatuinen; mikään muu järjestys ei kunnioita polun reunoja. Päinvastoin, jos topologinen lajittelu ei muodosta Hamiltonin polkua, DAG: llä on kaksi tai useampia kelvollisia topologisia järjestyksiä, sillä tässä tapauksessa on aina mahdollista muodostaa toinen kelvollinen järjestys vaihtamalla kaksi peräkkäistä kärkeä, joita ei yhdistä reuna toisilleen. Siksi on mahdollista testata lineaarisesti, onko olemassa ainutlaatuinen järjestys ja onko olemassa Hamiltonin polku, vaikka Hamiltonin polun ongelman NP-kovuus on yleisempiä suunnattuja kaavioita (eli syklisiä suunnattuja kaavioita).

Suhde osittaisiin tilauksiin

Topologinen orderings myös läheisesti käsite Lineaarinen on osittaisjärjestys matematiikan. Osittain järjestetty joukko on vain joukko objekteja yhdessä "≤" - eriarvoisuussuhteen määritelmän kanssa, mikä täyttää heijastuskyvyn ( x  ≤  x ), antisymmetrian (jos x  ≤  y ja y  ≤  x sitten x  =  y ) ja transitiivisuuden aksioomat. (jos x  ≤  y ja y  ≤  z , niin x  ≤  z ). Täydellinen järjestys on osittainen järjestys, jossa, jokaista kahden objektin x ja y joukossa, joko x  ≤  y tai y  ≤  x . Kokonaistilaukset ovat tietotekniikassa tuttuja vertailuoperaattoreina, joita tarvitaan vertailulajittelualgoritmien suorittamiseen . Äärellisten joukkojen osalta kokonaisjärjestykset voidaan tunnistaa lineaarisista objektisarjoista, joissa "≤" -suhde on totta aina, kun ensimmäinen objekti edeltää järjestyksen toista objektia; vertailulajittelualgoritmia voidaan käyttää kokonaisjärjestyksen muuntamiseen sarjaksi tällä tavalla. Ositilauksen lineaarinen jatke on kokonaisjärjestys, joka on sen kanssa yhteensopiva siinä mielessä, että jos x  ≤  y osittaisessa järjestyksessä, niin x  ≤  y myös kokonaisjärjestyksessä.

Voidaan määritellä osittaisen tilaamiseksi tahansa DAG antamalla joukko kohteita olla pisteiden DAG, ja määritellään x  ≤  y olevan totta, minkä tahansa kaksi pistettä x ja y , kun on olemassa suunnattu polku välillä x ja y ; eli kun y on tavoitettavissa alkaen x . Näillä määritelmillä DAG: n topologinen järjestys on sama asia kuin tämän osittaisen järjestyksen lineaarinen jatke. Päinvastoin, mikä tahansa osittainen järjestys voidaan määritellä tavoitettavuussuhteeksi DAG: ssa. Yksi tapa tehdä tämä on määrittää DAG, jolla on kärki jokaiselle osittain järjestetyn joukon objektille ja reuna xy jokaiselle objektiparille, joiden x  ≤  y . Vaihtoehtoinen tapa tehdä tämä on käyttää osittaisen järjestyksen transitiivista pienennystä ; yleensä tämä tuottaa DAG: ita, joissa on vähemmän reunoja, mutta tavoitettavuussuhde näissä DAG: issä on edelleen sama osittainen järjestys. Käyttämällä näitä rakenteita voidaan käyttää topologisia järjestysalgoritmeja osittaisten tilausten lineaaristen laajennusten löytämiseksi.

Katso myös

• tsort , Unix -ohjelma topologiseen lajitteluun
• Takaisinkytkentäkaari , reunat, joiden poistaminen sallii jäljellä olevan osakaavion lajittelun topologisesti
• Tarjanin vahvasti kytkettyjen komponenttien algoritmi , algoritmi, joka antaa topologisesti järjestetyn luettelon vahvasti kytketyistä komponenteista kaaviossa
• Esitopologinen järjestys

Viitteet

Lue lisää

• DE Knuth , The Art of Computer Programming , Volume 1, jakso 2.2.3, jossa on algoritmi osittaisen järjestyksen topologiseen lajitteluun ja lyhyt historia.

Ulkoiset linkit

• NIST Algoritmien ja tietorakenteiden sanakirja: topologinen lajittelu
• Weisstein, Eric W. , "Topologinen lajittelu" , MathWorld