Euklidiskt minimumspännande träd

Euklidiskt minimum spanande träd ( Euclidean minimum spaning tree , EMST  ) är det minsta spännträdet för en uppsättning av n punkter i planet (eller mer allmänt, i ), där vikten av en kant mellan ett par punkter är det euklidiska avståndet mellan två poäng. Enkelt uttryckt länkar EMST en uppsättning punkter med linjesegment så att den totala längden på alla segment är minimal och vilken punkt som helst kan nås från en annan punkt längs dessa segment.

På EMST-planet för en given uppsättning punkter kan hittas i tiden Θ ( n log n ) med O( n )-rymden vid beräkning av en algebraisk beslutsträdmodell . Snabbare probabilistiska algoritmer är kända med komplexitet i starkare beräkningsmodeller som mer exakt modellerar kapaciteten hos riktiga datorer [1] .

I högre dimensioner ( ) är det fortfarande ett öppet problem att hitta den optimala algoritmen.

Nedre gräns

En asymptotisk nedre gräns Ω ( n log n ) för tidskomplexiteten för EMST-problemet kan fastställas i begränsade beräkningsmodeller, eftersom algebraiska beslutsträd och algebraiska beslutsträdmodeller, där algoritmen har tillgång till inmatningspunkter endast genom vissa begränsade primitiver, som utför enkla algebraiska beräkningar på koordinater. I dessa modeller tar problemet med ett par närmaste punkter tid , men det närmaste paret kommer nödvändigtvis att vara en EMST-kant, så EMST tar också den tid [2] . Men om inmatningspunkterna har heltalskoordinater och bitvisa operationer och tabellindexering över koordinaterna är tillgängliga, är snabbare algoritmer möjliga [1] .

Algoritmer för att beräkna EMST på ett plan

Den enklaste algoritmen för att hitta en EMST i 2D-rymden, givet n poäng, är att bygga en komplett n -vertexgraf som har n ( n -1 )/2 kanter, beräkna vikten av varje kant genom att hitta avståndet mellan varje par av poäng, och gör sedan en standard minimi-spännande trädalgoritm (som en version av Prims algoritm eller Kruskals algoritm ) på den grafen. Eftersom denna graf har Θ ( n 2 ) kanter för n olika punkter, kräver det att bygga grafen tid Ω ( n 2 ). Lösningen på problemet kräver också ett storleksutrymme för att lagra alla kanter.

För ett mer avancerat tillvägagångssätt för att hitta EMST i planet, notera att det är en subgraf av alla Delaunay-triangulering av n punkter, vilket avsevärt minskar antalet kanter:

  1. Vi bygger en Delaunay-triangulering i O( n log n ) tid med O( n ) minne. Eftersom Delaunay-trianguleringen är en plan graf och antalet kanter är högst tre gånger antalet hörn, genererar denna konstruktion endast O( n ) kanter i alla plana grafer.
  2. Vi märker varje kant med dess längd.
  3. Vi kör algoritmen för att hitta det minsta spännträdet på denna graf. Eftersom det finns O( n )-kanter, kommer denna algoritm att ta O( n log n )-tid om någon av de standardmässiga minimumspännande trädalgoritmerna som Boruvkas algoritm, Prims algoritm eller Kruskals algoritm används .

I slutändan kräver algoritmen O( n log n ) tid och O( n ) utrymme .

Om inmatningskoordinaterna är heltal och kan användas som en rad index , är snabbare algoritmer möjliga - Delaunay-triangulering kan byggas med en probabilistisk algoritm i tid med matematiska förväntningar [1] . Dessutom, eftersom Delaunay-triangulering är en plan graf , kan dess minsta spännträd hittas i linjär tid med en variant av Boruvkas algoritm som tar bort alla utom de billigaste kanterna mellan varje par av komponenter efter varje steg i algoritmen [3] [4] . Således är den totala förväntade körtiden för denna algoritm [1] .

Högre dimensioner

Problemet kan generaliseras till n punkter i det d -dimensionella rummet ℝ d . I högre dimensioner innehåller anslutningen som definieras av Delaunay-trianguleringen (som delar upp det konvexa skrovet i d -dimensionella förenklingar ) ett minsta spännträd. Triangulering kan dock innehålla en fullständig graf [5] . Av denna anledning kommer det att ta tid att hitta ett euklidiskt minimumspännande träd som ett spännträd i en komplett graf eller som ett spännträd för Delaunay-triangulering . I tredimensionellt rymd kan du hitta det minsta spännträdet i tid , och i alla rum med högre dimension kan du lösa problemet snabbare än den kvadratiska tidsgränsen för hela grafen och Delaunays trianguleringsalgoritmer [5] . För likformigt fördelade slumpmässiga punkter kan minsta spännande träd beräknas med samma hastighet som sortering [6] . Med hjälp av en väl separerad sönderdelning av par kan man få en -approximation i tid [7] .

Underträd av Delaunay-triangulering

Alla kanter på EMST är kanter på den relativa grannskapsgrafen [8] [9] [10] , som i sin tur är kanter på Gabriel-grafen , som är kanter i Delaunay-trianguleringen av punkter [11] [12] , som kan vara bevisat genom en motsvarighet till det kontrapositiva påståendet: någon kant som inte ingår i Delaunay-trianguleringen ingår inte i någon EMST. Beviset är baserat på två egenskaper hos minimalt spännande träd och Delaunay-triangulering:

  1. ( egenskapen för minsta spännträdscykler): För varje cykel C i en graf, om vikten av en kant e av graf C är större än vikten av en annan kant C, kan den kanten inte tillhöra ett minsta spännträd .
  2. (egenskapen för Delaunay-trianguleringarna): Om det finns en cykel med två ingångspunkter på sin gräns som inte innehåller några andra ingångspunkter, är segmentet mellan dessa två punkter en kant av någon Delaunay-triangulering.

Betrakta en kant e mellan två ingångspunkter p och q som inte är en Delaunay-trianguleringsflank. Egenskap 2 innebär att en cykel C med e som diameter måste innehålla någon annan punkt r inuti. Men då är r närmare både p och q än de är varandra, och därför är kanten från p till q den längsta i punktcykeln och tillhör, med egenskap 1 e , inte till någon EMST.

Förväntad storlek

Den förväntade storleken på EMST för stora punktuppsättningar bestämdes av J. Michael Steel [13] . Om är densitetsfunktionen för sannolikhetsfunktionen för valet av punkter, så är för stor och storleken på EMST ungefär lika med

där är en konstant beroende endast på dimensionen av . Det exakta värdet på konstanterna är inte känt, men vi kan uppskatta det från empirisk erfarenhet.

Applikationer

En uppenbar tillämpning av euklidiska minimumspännande träd är att hitta det billigaste nätverket av ledningar eller rör för att ansluta en uppsättning platser, förutsatt att priset endast beror på enhetslängden på den anslutande produkten. Men eftersom detta ger en absolut lägre gräns för mängden produkt som krävs, föredrar de flesta sådana nätverk en k -kant- ansluten graf istället för ett träd, så att förlusten av en enskild anslutning inte kommer att bryta isär nätverket.

En annan tillämpning av EMST är en konstantfaktorapproximationsalgoritm för den ungefärliga lösningen av det euklidiska resandeförsäljarproblemet , en version av resandeförsäljarproblemet på en uppsättning punkter i ett plan med kanter vars priser är lika med deras längder. Denna realistiska version av problemet kan lösas ungefär med en faktor 2 genom att beräkna EMST, följa dess gräns, som avgränsar hela trädet, och sedan ta bort alla hörn som förekommer flera gånger (lämnar bara en).

Planär implementering

Implementeringsproblemet för euklidiska minimumspännande träd är ställt enligt följande: Givet ett träd , hitta positionen D ( u ) för varje vertex så att T är ett minimumspännande träd , eller bestäm att inga sådana positioner existerar. Att kontrollera förekomsten av en realisering i planet är ett NP-komplett problem [14] .

Anteckningar

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

Litteratur