Steiner minimális fa problémája

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. június 28-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Steiner minimális fa problémája
Valaki után elnevezve	Jacob Steiner
Számítási komplexitás	NP-teljes probléma [1]
Médiafájlok a Wikimedia Commons oldalon

A Steiner-minimálfa feladat az, hogy megtaláljuk a sík adott véges ponthalmazát összekötő legrövidebb hálózatot. A probléma nevét Jacob Steiner (1796-1863) tiszteletére kapta.

A feladat alternatív feltétele, hogy találjunk egy minimális részgráfot, amely véges számú adott csúcsot (terminált) köt össze, és így a legrövidebb utak hálózatát alkotja ezen csúcsok között. A probléma tehát a minimális feszítőfa probléma általánosítása .

Történelem

A probléma története Pierre de Fermat (1601-1665) idejére nyúlik vissza, aki, miután kifejtette a minimumok és maximumok vizsgálati módszerét, ezt írta [2] :

Qui hanc methodum non probaverit, ei proponitur: Datis tribus punctis, quartum reperire, a quo si ducantur tres rectae ad data puncta, summa trium harum rectarum sit minimum quantitas.

Aki nem értékelte ezt a módszert, oldja meg [a következő feladatot]: adott három ponthoz keressen egy olyan negyediket, hogy ha ebből három szakaszt húzunk ezekre a pontokra, akkor ennek a három szakasznak az összege adja a legkisebb érték.

Ezt a problémát részben E. Torricelli [3] [4] (1608-1647) és B. Cavalieri [5] (1598-1647), B. Castelli (1577-1644) tanítványai oldották meg, majd az általuk talált konstrukció módosította T. Simpson [6] (1710-1761), végül finomította F. Heinen [7] és J. Bertrand (1822-1900). Ennek eredményeként megkaptuk az S pont geometriai konstrukcióját , amelyet ma Fermat-pontnak (néha Torricelli-pontnak ) neveznek, és amely három adott A , B és C pontra megadja az AS , BS szakaszok hosszának minimális lehetséges összegét. , CS .

1934 -ben V. Yarnik és O. Kessler megfogalmazta [8] a Fermat-probléma általánosítását, három pontot egy tetszőleges véges számmal helyettesítve. Nevezetesen az a feladatuk, hogy a sík adott véges ponthalmazán átmenő, összefüggő, legkisebb hosszúságú síkgráfokat írjanak le.

1941 - ben megjelent a Mi a matematika? » [9] R. Courant és G. Robbins, amelyben a szerzők a következőket írták:

Egy nagyon egyszerű és egyben tanulságos problémát vizsgált a múlt század elején a híres berlini geométer, Jakob Steiner. Három falut , , úthálózattal kell összekötni úgy, hogy azok teljes hossza minimális legyen. Természetes lenne ezt a problémát adott pontokra általánosítani a következőképpen: olyan pontot kell találni a síkban , hogy a távolságok összege (ahol a távolságot jelöli ) minimum legyen. … Ez az általánosított probléma, amelyet Steiner is tanulmányozott, nem vezet érdekes eredményekhez. Ebben az esetben egy felületes általánosításról van szó, amelyhez hasonló a matematikai szakirodalomban is. Ahhoz, hogy Steiner problémájáról igazán figyelemre méltó általánosítást kapjunk, fel kell hagynunk egyetlen pont keresésével . Ehelyett egy "utcahálózat" vagy "adott falvak közötti úthálózat" kiépítését tűztük ki feladatul, amelynek minimális összhossza van. [9] $A$ $B$ $C$
$n$ $A_{1},A_{2},\ldots ,A_{n}$ $P$ $a_{1}+a_{2}+\ldots +a_{n}$ $a_{i}$ $PA_{i}$ $P$

Ez a könyv megérdemelt népszerűségre tett szert, aminek következtében a Fermat-problémát és a Jarnick-Kessler-problémát is Steiner-problémának hívják.

Megoldási algoritmus

A Steiner-probléma pontos megoldását adó hatékony (a komplexitást a feladatparaméterben valamilyen polinom által felülről határolt függvény fejezi ki, jelen esetben a gráf csúcsok száma) algoritmus nem létezik, ha a P osztályok és NP nem egyenlőek , mivel a probléma NP-teljes . Ezt könnyű bizonyítani a csúcsfedő problémára redukálva .

A korlátok ellenére a probléma megközelítőleg megoldható, amit a Coe, Markowski és Bergman algoritmus tesz. Ennek a megközelítésnek az az ötlete, hogy két csúcs (terminál) összekapcsolásának költségének alsó korlátja a legrövidebb út közöttük, és az összes terminált összekötő minimális költségű utak halmaza 2 hozzávetőleges megoldást ad, amint látható. lent. Tehát az algoritmus így fog kinézni:

Adott egy gráf , egy sor terminál és egy költségfüggvény . $G=(V,E)$ $T\subset V$ $c\colon E\to \mathbb {Q}$
Keress egy ilyen klikket . $G_{D}=(T,F)$ $c\colon F\to \mathbb {Q}$ $c_{D}(\{a,b\})=\operátornév {dist} _{G}(a,b)$
Keresse meg a gráf minimális feszítőfáját . $S_{D}=(T,F')$ $G_{D}$
Minden élhez adja meg a hossz elérési útját a gráfban . $e\in F'$ $W_{e}=(V_{e},F_{e})$ $c_{D}(e)$ $G$
Számítsa ki a részgráfot . $H=(\bigcup _{e\in F'}V_{e},\bigcup _{e\in F'}F_{e})$
Keresse meg a részgráf minimális fennmaradó fáját . $S_{H}$ $H$
Távolítsa el a levelekről, amelyeket nem tartalmaz . $S_{H}$ $T$
Adja ki az eredményt.

A közelítési tényező bizonyítása az algoritmus eredményének és a pontos megoldás becslésére redukálódik: . Ha az optimális megoldás összes élét megduplázzuk, akkor olyan ciklust kapunk, amely tartalmazza az összes csúcsot . egy feszítőfát határoz meg a gráfon , amely csak terminális csúcsokból áll. Így . A Kruskal hatékony algoritmusa használható algoritmusként a minimális feszülőfák megtalálására . [tíz] $c(S_{D})\leqslant 2\cdot c(S^{*})$ $Z$ $T$ $Z$ $T_{Z}$ $G_{D}$ $c(S_{D})\leqslant c(T_{Z})\leqslant c(Z)=2\cdot c(S^{*})$

Ez a közelítő becslés azonban nem szab határt, és a becslés elérésével javítható az algoritmus . $11/6$

Alapdefiníciók

A Steiner-probléma számos modern megfogalmazását mutatjuk be. Környezeti térként az euklideszi sík helyett vegyünk egy tetszőleges metrikus teret .

Minimális Steiner fák

Legyen egy metrikus tér és egy gráf X - en , azaz . Minden ilyen gráf esetében az éleinek hossza a csúcsaik közötti távolság , valamint magának a gráfnak a hossza az összes éle hosszának összegeként. $(X,\rho)$ $G=(V,E)$ $V\X részhalmaz$ $e=\{u,v\}\in E$ $\rho (u,v)$ $\rho (G)$ $G$

Ha véges részhalmaza , és egy összefüggő gráf -on , amelyre , akkor -t összekötő gráfnak nevezzük . Ebben az esetben a minimális lehetséges hosszúsággal összekötő gráf egy fa , amelyet a minimális Steiner-fának nevezünk . Az ilyen fák tanulmányozásának szentelték a Steiner-probléma egyik változatát. $M$ $x$ $G=(V,E)$ $x$ $M\alhalmaz V$ $G$ $M$ $G$ $M$ $\rho (G)$ $M$

Vegye figyelembe, hogy minimális Steiner fák nem mindig léteznek. Azonban a -t összekötő összes gráfon a mennyiségek legkisebb infimuma mindig létezik, ezt a minimális Steiner-fa hosszának nevezzük, és -vel jelöljük . $\rho (G)$ $M$ $M$ $\operátornév {smt} (M)$

Példák

Ha a standard euklideszi sík, vagyis a távolságot a norma generálja , akkor megkapjuk a Yarnik és Kessler által megfogalmazott klasszikus Steiner-problémát (lásd fent). $(X,\rho)$ $\rho$ $\|(x,y)\|={\sqrt {x^{2}+y^{2}}}$

Ha a manhattani sík , azaz a távolságot a norma generálja , akkor megkapja a téglalap alakú Steiner-problémát , melynek egyik alkalmazása a mikroáramkörök elrendezéseinek tervezése [11] . A modernebb elrendezéseket a λ-norma által generált metrika modellezi (az egységkör egy szabályos 2λ-gon; ilyen értelemben a manhattani norma egy 2-norma). $(X,\rho)$ $\rho$ $\|(x,y)\|=|x|+|y|$

Ha a gömböt vesszük gömbnek (körülbelül a Föld felszínét modellezve), és a gömbből a gömbből átmenő sík által metszett nagykör két íve közül a legrövidebb hosszára és a gömb középpontjára, akkor egyfajta közlekedési probléma adódik : egy adott ponthalmazt (városok, vállalkozások, előfizetők stb.) össze kell kötni a legrövidebb kommunikációs hálózattal (utak, vezetékek, telefonvonalak stb.), minimalizálva az építési költségeket (ez feltételezzük, hogy a költségek arányosak a hálózat hosszával). $x$ $\rho (a,b)$ $x$ $a$ $b$

Ha egy ábécé feletti összes szó halmazát vesszük értéknek, és a Levenshtein távolságot vesszük értéknek , akkor megkapjuk a Steiner-probléma egy változatát, amelyet széles körben használnak a bioinformatikában, különösen egy evolúciós fa felépítésére. . $x$ $\rho (a,b)$

Ha egy összefüggő gráf csúcsainak halmazát vesszük értéknek , és valamilyen súlyfüggvény által generált távolságfüggvényt vesszük értéknek, akkor a gráfok Steiner-problémáját kapjuk . Ennek a feladatnak egy speciális esete (amikor az adott halmaz egybeesik az összes csúcs halmazával, ) egy minimális feszítőfa felépítésének problémája . $x$ $V$ $G=(V,E)$ $\rho$ $\omega \colon E\to \mathbb {R}$ $M=X$

Minimális paraméteres hálózatok

Legyen a gráf csúcshalmazának valamilyen részhalmaza, amely tartalmazza az összes 1. és 2. fokú csúcsot. Egy párat határos gráfnak nevezünk . Ha egy összefüggő gráf, és valamilyen metrikus térbe való leképezés, akkor minden olyan leképezést, amelynek a kényszere egybeesik, olyan típusú hálózatnak nevezzük , amelynek határa a metrikus térben van . A hálózatnak a gráf csúcsaira és éleire való korlátozását ennek a hálózatnak a csúcsainak és éleinek nevezzük . A hálózat élének hossza az érték , a hálózat hossza pedig az összes éle hosszának összege. $\részleges G$ $V$ $G=(V,E)$ $(G,\részleges G)$ $\részleges G$ $G$ $\varphi \colon \partial G\to X$ $(X,\rho)$ $\Gamma \kettőspont G\-X$ $\részleges G$ $\varphi$ $(G,\részleges G)$ $\varphi$ $(X,\rho)$ $\Gamma$ $G$ $\Gamma \colon \{u,v\}\-X$ $\Gamma$ $\rho {\bigl (}\Gamma (u),\Gamma (v){\bigr )}$ $\rho (\gamma)$ $\Gamma$

Jelölje az összes határral rendelkező hálózat halmazával . A hálózatból induló hálózatot , amely a lehető legkisebb hosszúságú, határvonalas típusú minimális parametrikus hálózatnak nevezzük . $[G,\varphi ]$ $(G,\részleges G)$ $\varphi$ $[G,\varphi ]$ $(G,\részleges G)$ $\varphi$

Vegye figyelembe, hogy a minimális Steiner-fákhoz hasonlóan nem mindig létezik minimális paraméteres hálózat. Azonban a legkevesebb érték az összes hálózaton -tól kezdve mindig létezik, ezt a minimális paraméteres hálózat hosszának nevezzük, és jelöli . $\rho (G)$ $[G,\varphi ]$ $\operátornév {mpn}[G,\varphi ]$

Ha véges részhalmaza , és mindenre leképez , akkor azt mondjuk, hogy a hálózat csatlakozik . Könnyen belátható, hogy mindenre , amihez . Így Steiner általános problémája a minimális parametrikus hálózatok tanulmányozására és a legrövidebbek kiválasztására redukálódik. $M$ $x$ $\varphi$ $\részleges G$ $M$ $\operátornév {im}(\varphi )=M$ $\Gamma \in [G,\varphi ]$ $M$ $\operátornév {smt}(M)=\inf \operátornév {mpn}[G,\varphi ]$ $[G,\varphi ]$ $\operátornév {im}(\varphi )=M$

Egydimenziós minimális tömések Gromov értelmében

A Steiner-probléma ezen természetes általánosítását A. O. Ivanov és A. A. Tuzhilin javasolta [12] . Legyen tetszőleges véges halmaz és valamilyen összefüggő gráf. Azt mondjuk, hogy összeköt , ha . Legyen most egy véges pszeudometrikus tér (ahol a metrikus térrel ellentétben a különböző pontok távolsága nullával egyenlő lehet), legyen egy összefüggő gráf, amely összeköti a -t , és legyen valamilyen leképezés nemnegatív valós számokra, amit általában súlyfüggvénynek neveznek. súlyozott gráf generálása . A függvény definiálja a pszeudometriát , vagyis a gráf csúcsai közötti távolság az ezeket a csúcsokat összekötő utak súlya közül a legkisebb. Ha bármely pontra és -ból , akkor a súlyozott gráfot a tér kitöltésének , a gráfot pedig ennek a kitöltés típusának nevezzük . A tér összes kitöltésével egyenlő számot a minimális töltés tömegének, a kitöltést pedig minimális kitöltöttségnek nevezzük . A fő feladat a minimális kitöltések kiszámításának és leírásának megtanulása . $M$ $G=(V,E)$ $G$ $M$ $M\alhalmaz V$ ${{\mathcal M}}=(M,\rho )$ $G=(V,E)$ $M$ ${\displaystyle \omega \colon E\to {\mathbb {R} }_{+))$ ${\mathcal G}=(G,\omega )$ $\omega$ $V$ $d_{\omega}$ ${\mathcal G}$ $p$ $q$ $M$ $\rho (p,q)\leq d_{\omega }(p,q)$ ${\mathcal G}$ ${\mathcal {M}}$ $G$ $\operátornév {mf}({\mathcal M})$ $\inf \omega ({\mathcal G})$ ${\mathcal G}$ ${\mathcal {M}}$ ${\mathcal G}$ $\omega ({\mathcal G})=\operátornév {mf}({\mathcal M})$ $\operátornév {mf}({\mathcal M})$

Jegyzetek

↑ Karp R. M. Redukálhatóság a kombinatorikus problémák között - 1972. - doi: 10.1007 / 978-1-4684-2001-2_9
↑ Fermat P. de (1643), Szerk. H. Tannery, szerk., "Oeuvres" , vol. 1, Párizs 1891, Melléklet: Párizs 1922, p. 153 , < https://archive.org/details/oeuvresdefermat901ferm >
↑ G. Loria, G. Vassura (1919), Opere de Evangelista Torriceli , vol. 1. o. 79-97
↑ J. Krarup, S. Vajda. Egy Fermat-probléma Torricelli geometriai megoldásáról // IMA J. Math. Appl. busz. Ipar. : folyóirat. - 1997. - 1. évf. 8 , sz. 3 . - P. 215-224 . - doi : 10.1093/imaman/8.3.215 .
↑ B. Cavalieri (1647), Excercitationes Geometricae
↑ T. Simpson (1750), "A fluxusok doktrínája és alkalmazása"
↑ F. Heinen (1834), Über Systeme von Kräften, Gymnasium zu Cleve (Essen)
↑ V. Jarník, O. Kössler (1934), O minimálních grafech obsahujících n daných bodu , Ĉas, Pêstování Mat. (Essen) T. 63: 223-235 , < https://eudml.org/doc/25703#content > Archiválva : 2016. március 4. a Wayback Machine -nél
↑ 1 2 R. Courant, H. Robbins (1941), Mi a matematika? Oxford University Press
↑ Belousov A.I., Tkachev S.B. Discrete Mathematics. - M. : MGTU, 2006. - S. 306-311. — ISBN 5-7038-2886-4 .
↑ Kureichik V. M. Genetikai algoritmusok és alkalmazásuk. Taganrog RTU, 2002. 244 p.
↑ A.O. Ivanov, A.A. Tuzhilin. Egydimenziós Gromov minimális kitöltés (határozatlan) .

Irodalom

A. O. Ivanov, A. A. Tuzhilin. Az extremális hálózatok elmélete. - Moszkva-Izhevsk: Számítógépes Kutatóintézet, 2003. - ISBN 5-93972-292-X .
A. O. Ivanov, A. A. Tuzhilin. A Steiner-probléma a síkon, vagy síkbeli minimális hálózatok, Matem. Szo. - 1991. - T. 182 , 12. sz . - S. 1813-1844 .
Protasov V. Yu. Maximák és minimumok a geometriában . — M. : MTsNMO. — 56 p. - ("Matematikai oktatás" könyvtár, 31. szám).
Weisstein, Eric W. Steiner Tree (angol) a Wolfram MathWorld webhelyén .

NP-teljes problémák
A halmozás (csomagolás) maximalizálási problémája	Csomagolás konténerekbe kétdimenziós csomagolás lineáris csomagolás súly szerinti csomagolás érték szerinti csomagolás A hátizsák probléma
gráfelmélet halmazelmélet	Csúcsborítási probléma Kattintson a probléma Egy független halmaz (halmaz) problémája Állítsa be a fedési problémát Steiner probléma Az utazó eladó probléma Általános utazó eladó probléma
Algoritmikus problémák	Kielégíthetőségi probléma Boole-képleteknél (konjunktív normál formában)
Logikai játékok és rejtvények	Általános címkék (játék N 2 -1-ben) legrövidebb megoldási probléma Problémák, amelyek megoldásait a Tetrisben alkalmazzák Általános Sudoku probléma Latin négyzet kitöltési probléma Kakuro feladata
Nehézségi osztályok Operációkutatás Optimalizálás Kombinatorikus optimalizálás Alkalmazott matematika Algoritmusok elmélete Dinamikus programozás 21 NP-teljes Karp probléma