Euklidinen minimivirittävä puu

Euklidinen pienin virittävä puu ( Euklidinen minimi virittävä puu , EMST  ) on n pisteen joukon pienin virittävä puu tasossa (tai yleisemmin in ), jossa minkä tahansa pisteparin välisen reunan paino on euklidinen etäisyys kaksi pistettä. Yksinkertaisesti sanottuna EMST linkittää joukon pisteitä viivanosien kanssa niin, että kaikkien segmenttien kokonaispituus on minimaalinen ja mikä tahansa piste voidaan saavuttaa toisesta pisteestä näitä segmenttejä pitkin.

EMST-tasolla tietylle pistejoukolle voidaan löytää ajassa Θ ( n log n ) käyttämällä O( n )-avaruutta laskettaessa algebrallista päätöspuumallia . Nopeammat todennäköisyysalgoritmit tunnetaan monimutkaisemmin vahvemmissa laskentamalleissa, jotka mallintavat tarkemmin todellisten tietokoneiden ominaisuuksia [1] .

Korkeammissa ulottuvuuksissa ( ) optimaalisen algoritmin löytäminen on edelleen avoin ongelma.

Alaraja

EMST-ongelman aikamonimutkaisuuden asymptoottinen alaraja Ω ( n log n ) voidaan määrittää rajoitetuissa laskentamalleissa, koska algebrallinen päätöspuu ja algebrallinen päätöspuumallit, joissa algoritmilla on pääsy sisääntulopisteisiin vain tietyt rajoitetut primitiivit, jotka suorittavat yksinkertaisia ​​algebrallisia laskutoimituksia koordinaateille. Näissä malleissa lähimpien pisteiden parin ongelma vie aikaa , mutta lähin pari on välttämättä EMST-reuna, joten EMST vie myös sen verran aikaa [2] . Kuitenkin, jos syötepisteillä on kokonaislukukoordinaatit ja bittikohtaiset toiminnot ja taulukon indeksointi koordinaattien yli ovat käytettävissä, nopeammat algoritmit ovat mahdollisia [1] .

Algoritmit EMST:n laskemiseen tasossa

Yksinkertaisin algoritmi EMST:n löytämiseksi 2D-avaruudesta n pisteen perusteella on rakentaa täydellinen n -vertex-graafi, jossa on n ( n -1 )/2 reunaa. Laske jokaisen reunan paino etsimällä kunkin parin välinen etäisyys. pisteet ja tee sitten standardi vähimmäisvirittävän puualgoritmi (kuten Primin algoritmin versio tai Kruskalin algoritmi ) kyseiselle kuvaajalle. Koska tällä graafilla on Θ ( n 2 ) reunaa n eri pisteelle, graafin rakentaminen vaatii aikaa Ω ( n 2 ). Ongelman ratkaisu vaatii myös kokoisen tilan kaikkien reunojen säilyttämiseen.

Jos haluat edistyneemmän lähestymistavan EMST:n löytämiseen tasosta, huomaa, että se on minkä tahansa n pisteen Delaunayn kolmioiden aligraafi , joka vähentää merkittävästi reunojen määrää:

  1. Rakennamme Delaunayn kolmiota O( n log n ) -ajassa käyttämällä O( n ) muistia. Koska Delaunayn kolmiomittaus on tasograafi ja reunojen määrä on korkeintaan kolminkertainen pisteiden lukumäärään verrattuna, missä tahansa tasograafissa tämä konstruktio tuottaa vain O( n ) reunaa.
  2. Merkitsemme jokaisen reunan pituudellaan.
  3. Suoritamme algoritmin tämän kaavion vähimmäisvirittävän puun löytämiseksi. Koska reunoja on O( n ), tämä algoritmi vie O( n log n ) aikaa, jos käytetään mitä tahansa standardinmukaisia ​​vähimmäisvirittävän puun algoritmeja, kuten Boruvkan algoritmia , Primin algoritmia tai Kruskalin algoritmia .

Lopulta algoritmi vaatii O( n log n ) aikaa ja O( n ) avaruutta .

Jos syötekoordinaatit ovat kokonaislukuja ja niitä voidaan käyttää indeksien joukkona , nopeammat algoritmit ovat mahdollisia - Delaunayn kolmiomittaus voidaan rakentaa käyttämällä todennäköisyysalgoritmia ajassa matemaattisella odotuksella [1] . Lisäksi, koska Delaunay-kolmio on tasograafi , sen pienin virittävä puu voidaan löytää lineaarisessa ajassa käyttämällä Boruvkan algoritmin muunnelmaa, joka poistaa kaikki paitsi halvimmat reunat kunkin komponenttiparin välillä algoritmin jokaisen vaiheen jälkeen [3] [4] . Näin ollen tämän algoritmin odotettu kokonaiskesto on [1] .

Suuremmat mitat

Ongelma voidaan yleistää d - ulotteisen avaruuden ℝ d n pisteeseen . Korkeammissa ulottuvuuksissa Delaunayn kolmiomittauksella määritelty yhteys (joka jakaa kuperan rungon d -ulotteisiksi yksinkertaisiksi ) sisältää minimivirittävän puun. Triangulaatio voi kuitenkin sisältää täydellisen graafin [5] . Tästä syystä euklidisen minimivirittävän puun löytäminen täydellisen graafin virittävänä puuna tai Delaunayn kolmioiden virittävänä puuna vie aikaa . Kolmiulotteisessa avaruudessa voit löytää minimivirittävän puun ajassa ja missä tahansa korkeamman ulottuvuuden avaruudessa voit ratkaista ongelman nopeammin kuin neliöllinen aikaraja koko graafille ja Delaunayn kolmiomittausalgoritmille [5] . Tasaisesti jakautuneille satunnaispisteille voidaan laskea vähimmäisvirittävät puut samalla nopeudella kuin lajittelu [6] . Käyttämällä -parien hyvin erotettua hajotusta voidaan saada aika- likiarvo [7] .

Delaunayn triangulaation alipuut

Kaikki EMST:n reunat ovat suhteellisen naapuruusgraafin [8] [9] [10] reunoja, jotka puolestaan ​​ovat Gabriel-graafin reunoja, jotka ovat Delaunayn pisteiden [11] [12] triangulaatiossa olevia reunoja , jotka voivat olla todistettu vastaavalla kontrapositiiviselle väitteelle: mikään reuna, joka ei sisälly Delaunayn kolmioon, ei sisälly mihinkään EMST:hen. Todistus perustuu kahteen vähimmäisvirittävän puiden ominaisuuteen ja Delaunayn kolmioon:

  1. ( vähimmäisvirittävän puun syklien ominaisuus ): Jos graafin missä tahansa syklissä C graafin C reunan e paino on suurempi kuin toisen reunan C paino, kyseinen reuna ei voi kuulua minimivirittävän puuhun .
  2. (Delaunayn kolmioiden ominaisuus): Jos syklin rajalla on kaksi tulopistettä, joka ei sisällä muita tulopisteitä, näiden kahden pisteen välinen segmentti on minkä tahansa Delaunayn kolmioiden reuna.

Tarkastellaan kahden syötepisteen p ja q välistä reunaa e , joka ei ole Delaunayn kolmioreuna. Ominaisuus 2 tarkoittaa, että syklin C , jonka halkaisija on e , täytyy sisältää jokin toinen piste r sisällä. Mutta silloin r on lähempänä sekä p :tä että q :ta kuin ne ovat toisiaan, ja siksi reuna p :stä q :hen on pisin syklin pisin eikä ominaisuuden 1 e mukaan kuulu mihinkään EMST:hen.

Odotettu koko

EMST:n odotetun koon suurille pistejoukoille määritti J. Michael Steel [13] . Jos on todennäköisyysfunktion tiheysfunktio pisteiden valinnassa, niin suurille ja EMST:n koko on suunnilleen yhtä suuri kuin

missä on vakio, joka riippuu vain dimensiosta . Vakioiden tarkkaa arvoa ei tiedetä, mutta voimme arvioida sen empiirisen kokemuksen perusteella.

Sovellukset

Ilmeinen euklidisten vähimmäisvirittävien puiden sovellus on löytää halvin johto- tai putkiverkosto paikkojen yhdistämiseksi, olettaen, että hinta riippuu vain yhdistävän tuotteen yksikköpituudesta. Koska tämä kuitenkin antaa absoluuttisen alarajan vaadittavalle tuotteen määrälle, useimmat tällaiset verkot suosivat k -reunaan yhdistettyä kuvaajaa puun sijaan, jotta yhden yhteyden katkeaminen ei hajottaisi verkkoa.

Toinen EMST:n sovellus on vakiokertoimen approksimaatioalgoritmi euklidisen matkustavan myyjä-ongelman likimääräiseen ratkaisuun , versio liikkuvan myyjän tehtävästä joukossa tasossa olevia pisteitä, joiden reunat ovat yhtä pitkiä. Tämä ongelman realistinen versio voidaan ratkaista noin kertoimella 2 laskemalla EMST, seuraamalla sen rajaa, joka rajaa koko puun, ja poistamalla sitten kaikki useita kertoja esiintyvät kärjet (jätä vain yksi).

Tasomainen toteutus

Toteutusongelma euklidisille minimivirittäville puille esitetään seuraavasti: Kun on annettu puu , etsi kunkin kärjen sijainti D ( u ) siten, että T on minimivirittävä puu , tai määritä, ettei tällaisia ​​paikkoja ole olemassa. Realisoinnin olemassaolon tarkistaminen tasossa on NP-täydellinen tehtävä [14] .

Muistiinpanot

  1. ↑ 1 2 3 4 Buchin ja Mulzer, 2009 , s. 139-148.
  2. ↑ Yao, 1989 , s. 308–313.
  3. ↑ Eppstein, 1999 , s. 425–461.
  4. ↑ Mares, 2004 , s. 315–320.
  5. ↑ 1 2 Agarwal, Edelsbrunner, Schwarzkopf, Welzl, 1991 , s. 407–422.
  6. ↑ Chatterjee, Connor, Kumar, 2010 , s. 486-500.
  7. ↑ Smid, 2005 .
  8. ↑ Jaromczyk, Toussaint, 1992 , s. 1502-1517
  9. ↑ Toussaint, 1981 , s. 860–861.
  10. ↑ Toussaint, 1980 , s. 261-268.
  11. ↑ Pless, 2003 .
  12. ↑ Sedgewick, Wayne, 2007 .
  13. ↑ Steele, 1988 , s. 1767-1787
  14. ↑ Eades, Whitesides, 1994 , s. 49–56.

Kirjallisuus