Euklideszi minimum feszülő fa

Az euklideszi minimális feszítőfa ( Euklideszi minimum feszítőfa , EMST  ) a síkban (vagy általánosabban -ban ) lévő n pontból álló halmaz minimális feszítőfája , ahol bármely pontpár közötti él súlya az euklideszi távolság két pont. Egyszerűen fogalmazva, az EMST egy pontkészletet vonalszakaszokkal kapcsol össze, így az összes szakasz teljes hossza minimális, és bármely pont elérhető egy másik pontból ezen szakaszok mentén.

Az EMST síkon egy adott ponthalmazra Θ ( n log n ) időben O( n ) tér felhasználásával egy algebrai döntési fa modell kiszámításakor . A gyorsabb valószínűségi algoritmusok összetettséggel ismertek erősebb számítási modellekben, amelyek pontosabban modellezik a valódi számítógépek képességeit [1] .

Magasabb dimenziókban ( ) az optimális algoritmus megtalálása továbbra is nyitott probléma marad.

Alsó korlát

Az EMST probléma időbonyolultságának aszimptotikus alsó Ω ( n log n ) korlátja korlátozott számítási modellekben állítható fel, mivel az algebrai döntési fa és az algebrai döntési fa modellek, amelyekben az algoritmus csak a bemeneti pontokhoz fér hozzá. bizonyos korlátozott primitívek, amelyek egyszerű algebrai számításokat végeznek a koordinátákon. Ezekben a modellekben a legközelebbi pontpár problémája időbe telik , de a legközelebbi pár szükségszerűen egy EMST él lesz, így az EMST is ennyi időt vesz igénybe [2] . Ha azonban a bemeneti pontok egész koordinátákkal rendelkeznek, és elérhetőek a bitenkénti műveletek és a koordináták feletti táblázatindexelés , akkor gyorsabb algoritmusok is lehetségesek [1] .

Algoritmusok az EMST egy síkon történő kiszámításához

A legegyszerűbb algoritmus az EMST megtalálására 2D térben, n pont adott, egy teljes n csúcsú gráf felépítése, amelynek n ( n -1 )/2 éle van, és kiszámítja az egyes élek súlyát úgy, hogy megtalálja az egyes párok közötti távolságot. pontokat, majd végezzen el egy szabványos minimális feszítőfa-algoritmust (például a Prim-algoritmus vagy a Kruskal -algoritmus egy változatát ) a gráfon. Mivel ennek a gráfnak Θ ( n 2 ) éle van n különböző ponthoz, a gráf felépítéséhez Ω ( n 2 ) idő szükséges. A probléma megoldásához az összes él tárolására szolgáló méretű hely is szükséges.

Az EMST síkban történő megtalálásának fejlettebb megközelítéséhez vegye figyelembe, hogy ez bármely n pontból álló Delaunay-háromszöglet részgráfja , amely jelentősen csökkenti az élek számát:

  1. O( n log n ) idő alatt Delaunay-háromszögelést készítünk O( n ) memória felhasználásával. Mivel a Delaunay-háromszögelés egy síkgráf , és az élek száma legfeljebb háromszorosa a csúcsok számának, bármely síkgráfban ez a konstrukció csak O( n ) élt generál.
  2. Minden élt megjelölünk a hosszával.
  3. Lefuttatjuk az algoritmust a minimális feszítőfa megtalálására ezen a gráfon. Mivel O( n ) él van, ez az algoritmus O( n log n ) időt vesz igénybe, ha a szabványos minimális feszítőfa-algoritmusok, például a Boruvka - algoritmus, a Prim -algoritmus vagy a Kruskal -algoritmus bármelyikét használják .

Végső soron az algoritmushoz O( n log n ) időre és O( n ) térre van szükség .

Ha a bemeneti koordináták egész számok, és indexek tömbjeként használhatók, gyorsabb algoritmusok is lehetségesek - Delaunay-háromszögelés egy valószínűségi algoritmus segítségével időben matematikai elvárásokkal építhető [1] . Továbbá, mivel a Delaunay-háromszögelés egy síkgráf , minimális feszítőfája lineáris időben megtalálható a Boruvka-féle algoritmus egy olyan változatával, amely az algoritmus minden lépése után a legolcsóbb éleket eltávolítja az egyes komponenspárok között [3] [4] . Így ennek az algoritmusnak a teljes várható futási ideje [1] .

Magasabb méretek

A probléma általánosítható a ℝ d d - dimenziós tér n pontjára . Magasabb dimenziókban a Delaunay-háromszögelés által meghatározott kapcsolat (amely a konvex hajótestet d - dimenziós egyszerűsítésekre osztja ) tartalmaz egy minimális feszítőfát. A háromszögelés azonban tartalmazhat egy teljes gráfot [5] . Emiatt egy euklideszi minimális feszítőfa megtalálása egy teljes gráf feszítőfájaként vagy Delaunay-háromszögelések feszítőfájaként időbe telik . A háromdimenziós térben időben megtalálhatja a minimális feszítőfát , és bármely magasabb dimenziójú térben a teljes gráf és Delaunay háromszögelési algoritmusok négyzetes időhatáránál gyorsabban oldhatja meg a feladatot [5] . Egyenletesen elosztott véletlen pontok esetén a minimális feszülőfák a rendezéssel azonos sebességgel számíthatók ki [6] . Az párok jól elkülönített dekompozíciójával kaphatunk egy -időbeli közelítést [7] .

A Delaunay-háromszögelés részfái

Az EMST minden éle a relatív szomszédsági gráf éle [8] [9] [10] , amelyek viszont a Gabriel gráf élei, amelyek élei a [11] [12] pontok Delaunay-háromszögletében , ami lehet az ellentétes állítás ekvivalensével bizonyított : a Delaunay-háromszögelésben nem szereplő élek nem szerepelnek egyetlen EMST-ben sem. A bizonyíték a minimális feszülőfák és a Delaunay-háromszögelés két tulajdonságán alapul:

  1. ( minimális feszítőfa ciklusok tulajdonsága ): Egy gráf bármely C ciklusa esetén, ha a C gráf egy e élének súlya nagyobb, mint egy másik C él súlya, akkor az az él nem tartozhat egy minimális feszítőfához .
  2. (Delaunay-háromszögelések tulajdonsága): Ha van egy ciklus két bemeneti ponttal a határán, és nem tartalmaz más bemeneti pontot, akkor a két pont közötti szakasz bármely Delaunay-háromszögelés éle.

Tekintsünk egy e élt két p és q bemeneti pont között , amely nem Delaunay-háromszögelési él. A 2. tulajdonság azt jelenti, hogy egy e átmérőjű C ciklusnak tartalmaznia kell egy másik r pontot is. De ekkor r közelebb van p -hez és q -hoz is, mint egymáshoz, és ezért a p -től q -ig tartó él a leghosszabb a pontciklusban , és az 1 e tulajdonság alapján nem tartozik egyik EMST-hez sem.

Várható méret

Az EMST várható méretét nagy ponthalmazok esetén J. Michael Steel határozta meg [13] . Ha a pontok kiválasztására szolgáló valószínűségi függvény sűrűségfüggvénye, akkor nagy és az EMST mérete megközelítőleg egyenlő

ahol csak a dimenziójától függő konstans . A konstansok pontos értéke nem ismert, de tapasztalati tapasztalatból meg tudjuk becsülni.

Alkalmazások

Az euklideszi minimális fesztávolságú fák kézenfekvő alkalmazása, hogy megtaláljuk a legolcsóbb vezeték- vagy csőhálózatot egy adott helyek összekapcsolásához, feltételezve, hogy az ár csak a csatlakozó termék egységnyi hosszától függ. Mivel azonban ez abszolút alsó korlátot ad a szükséges termék mennyiségére, a legtöbb ilyen hálózat inkább a k élhez kapcsolódó gráfot részesíti előnyben a fa helyett, így egyetlen kapcsolat elvesztése sem szakítja szét a hálózatot.

Az EMST másik alkalmazása egy konstans tényező közelítő algoritmus az euklideszi utazó értékesítő probléma közelítő megoldására , az utazó eladó probléma változata egy olyan síkban lévő pontok halmazán, amelyek élei megegyeznek a hosszukkal. A feladatnak ez a reális változata megközelítőleg 2-es tényezővel megoldható úgy, hogy kiszámítjuk az EMST-t, követve annak határát, amely a teljes fát lehatárolja, majd eltávolítjuk az összes többször előforduló csúcsot (csak egyet hagyunk meg).

Síkbeli megvalósítás

Az euklideszi minimális feszítőfák megvalósítási problémája a következő: Adott egy fa , keresse meg az egyes csúcsok D ( u ) pozícióját úgy, hogy T egy minimális feszítőfa , vagy határozza meg, hogy nincsenek ilyen pozíciók. A megvalósítás létezésének ellenőrzése a síkban NP -teljes probléma [14] .

Jegyzetek

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

Irodalom