Steinerův problém minimálního stromu

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. června 2022; ověření vyžaduje 1 úpravu .

Steinerův problém minimálního stromu
Pojmenoval podle	Jakub Steiner
Výpočetní složitost	NP-úplný problém [1]
Mediální soubory na Wikimedia Commons

Steinerův problém minimálního stromu je najít nejkratší síť spojující danou konečnou množinu bodů v rovině. Problém dostal své jméno na počest Jacoba Steinera (1796-1863).

Alternativní podmínkou problému je najít minimální podgraf spojující konečný počet daných vrcholů (terminálů) a tvořící tak síť nejkratších cest mezi těmito vrcholy. Problém je tedy zobecněním problému minimálního kostrového stromu .

Historie

Historie tohoto problému sahá až do doby Pierra de Fermata (1601-1665), který poté, co vysvětlil svou metodu zkoumání minim a maxim, napsal [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 minima quantitas.

Komu se tato metoda nelíbila, ať vyřeší [následující úlohu]: pro dané tři body najděte takový čtvrtý, že když se z něj k těmto bodům dokreslí tři úsečky, pak součet těchto tří úseček dá nejmenší hodnotu.

Tento problém částečně vyřešili E. Torricelli [3] [4] (1608-1647) a B. Cavalieri [5] (1598-1647), studenti B. Castelliho (1577-1644), pak konstrukce, kterou našli, byla upravil T. Simpson [6] (1710-1761) a nakonec zpřesnil F. Heinen [7] a J. Bertrand (1822-1900). Výsledkem byla geometrická konstrukce bodu S , nyní nazývaného Fermatův bod (někdy Torricelliho bod ), který pro tři dané body A , B a C udává minimální možný součet délek segmentů AS , BS . , CS .

V. Yarnik a O. Kessler v roce 1934 formulovali [8] zobecnění Fermatova problému, kde nahradili tři body libovolným konečným číslem. Jejich úkolem je totiž popsat souvislé rovinné grafy nejmenší délky procházející danou konečnou množinou bodů v rovině.

V roce 1941 vyšla populární kniha Co je matematika? » [9] R. Courant a G. Robbins, ve kterém autoři napsali následující:

Velmi jednoduchým a zároveň poučným problémem se na začátku minulého století zabýval slavný berlínský geometr Jakob Steiner. Je potřeba propojit tři obce , , silničním systémem tak, aby jejich celková délka byla minimální. Bylo by přirozené zobecnit tento problém na případ daných bodů následovně: je potřeba najít takový bod v rovině , aby součet vzdáleností (kde značí vzdálenost ) byl minimální. … Tento zobecněný problém, který také studoval Steiner, nevede k zajímavým výsledkům. V tomto případě máme co do činění s povrchním zobecněním, jakých je v matematické literatuře mnoho. Abychom získali skutečně pozoruhodné zobecnění Steinerova problému, musíme opustit hledání jediného bodu . Místo toho jsme si dali za úkol vybudovat „uliční síť“ nebo „síť silnic mezi danými vesnicemi“, která má minimální celkovou délku. [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$

Tato kniha si získala zaslouženou oblibu, v jejímž důsledku se Fermatův problém i Jarnick-Kesslerův problém nyní nazývají Steinerův problém.

Algoritmus řešení

Efektivní (složitost je vyjádřena funkcí ohraničenou shora nějakým polynomem v parametru problému, v tomto případě počtem vrcholů grafu) algoritmu, který dává přesné řešení Steinerovy úlohy, neexistuje za podmínky, že třídy P a NP se nerovnají , protože problém je NP-úplný . Je snadné to dokázat redukcí na problém pokrytí vrcholů .

Navzdory omezením lze problém vyřešit přibližně, což dělá Coeův, Markowski a Bergmanův algoritmus. Myšlenka tohoto přístupu spočívá v tom, že spodní hranice nákladů na spojení dvou vrcholů (terminálů) je nejkratší cesta mezi nimi a sada cest s minimálními náklady spojující všechny terminály poskytuje 2-přibližné řešení, jak bude ukázáno níže. Algoritmus tedy bude vypadat takto:

Daný graf , množina terminálů a nákladová funkce . $G=(V,E)$ $T\subset V$ $c\colon E\to \mathbb {Q}$
Najděte kliku takovou , že . $G_{D}=(T,F)$ $c\colon F\to \mathbb {Q}$ $c_{D}(\{a,b\})=\jméno operátora {dist} _{G}(a,b)$
Najděte minimální kostru grafu . $S_{D}=(T,F')$ $G_{D}$
Pro každou hranu definujte jako cestu délky v grafu . $e\in F'$ $W_{e}=(V_{e},F_{e})$ $c_{D}(e)$ $G$
Vypočítejte podgraf . $H=(\bigcup _{e\in F'}V_{e},\bigcup _{e\in F'}F_{e})$
Najděte minimální zbývající strom podgrafu . $S_{H}$ $H$
Odstraňte z listů, které nejsou obsaženy v . $S_{H}$ $T$
Vypište výsledek.

Důkaz aproximačního faktoru je redukován na odhad výsledku algoritmu a přesné řešení: . Pokud zdvojnásobíme všechny hrany optimálního řešení, dostaneme cyklus obsahující všechny vrcholy . definuje kostru v grafu sestávající pouze z koncových vrcholů. Tedy . Kruskalův účinný algoritmus může být použit jako algoritmus pro nalezení minimálního kostry . [deset] $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^{*})$

Tento aproximační odhad však není limitní a je možné algoritmus vylepšit dosažením odhadu . $11/6$

Základní definice

Uvádíme několik moderních formulací Steinerova problému. Jako okolní prostor uvažujme místo euklidovské roviny libovolný metrický prostor .

Minimální Steinerovy stromy

Dovolit být metrický prostor a být graf na X , to je, . Pro každý takový graf jsou délky jeho hran definovány jako vzdálenosti mezi jejich vrcholy a také délka samotného grafu jako součet délek všech jeho hran. $(X,\rho)$ $G=(V,E)$ $V\podmnožina X$ $e=\{u,v\}\v E$ $\rho (u,v)$ $\rho (G)$ $G$

Jestliže je konečná podmnožina , a je připojený graf na , pro který , pak se nazývá graf spojující . V tomto případě je graf spojující s minimální možnou délkou strom , který se nazývá minimální Steinerův strom na . Právě studiu takových stromů je věnována jedna z verzí Steinerova problému. $M$ $X$ $G=(V,E)$ $X$ $M\podmnožina V$ $G$ $M$ $G$ $M$ $\rho (G)$ $M$

Všimněte si, že minimální Steinerovy stromy vždy neexistují. Nejmenší infimum z množství přes všechny připojené grafy spojující , vždy existuje, se nazývá délka minimálního Steinerova stromu na a značí se . $\rho (G)$ $M$ $M$ $\operatorname {smt}(M)$

Příklady

Pokud je standardní euklidovská rovina, to znamená, že vzdálenost je generována normou , pak dostáváme klasický Steinerův problém formulovaný Yarnikem a Kesslerem (viz výše). $(X,\rho)$ $\rho$ $\|(x,y)\|={\sqrt {x^{2}+y^{2}}}$

Pokud je rovina Manhattan , to znamená, že vzdálenost je generována normou , pak dostáváme obdélníkový Steinerův problém , jehož jednou z aplikací je návrh uspořádání mikroobvodů [11] . Modernější rozložení jsou modelována metrikou generovanou λ-normou (jednotkový kruh je pravidelný 2λ-úhelník; v těchto termínech je manhattanská norma 2-normou). $(X,\rho)$ $\rho$ $\|(x,y)\|=|x|+|y|$

Je-li koule brána jako koule (přibližně modelující povrch Země) a pro délku nejkratšího ze dvou oblouků velké kružnice vyříznuté z koule rovinou procházející skrz , a středem koule, pak se získá určitý druh dopravního problému : je třeba propojit danou sadu bodů (města, podniky, předplatitelé atd.) nejkratší komunikační síť (silnice, potrubí, telefonní linky atd.), což minimalizuje náklady na výstavbu (to předpokládá se, že náklady jsou úměrné délce sítě). $X$ $\rho (a,b)$ $X$ $A$ $b$

Pokud se za hodnotu vezme množina všech slov v nějaké abecedě a za hodnotu se vezme Levenshteinova vzdálenost , získá se varianta Steinerova problému, která je široce používána v bioinformatice, zejména k sestavení evolučního stromu . . $X$ $\rho (a,b)$

Pokud se za hodnotu vezme množina vrcholů souvislého grafu a za hodnotu se vezme funkce vzdálenosti generovaná nějakou váhovou funkcí , pak se získá Steinerův problém v grafech . Speciálním případem tohoto problému (kdy se daná množina shoduje s množinou všech vrcholů, ) je problém sestrojení minimální kostry . $X$ $PROTI$ $G=(V,E)$ $\rho$ $\omega \colon E\to \mathbb {R}$ $M=X$

Minimální parametrické sítě

Dovolit být nějaká podmnožina množiny vrcholů grafu obsahující všechny vrcholy stupně 1 a 2. Dvojice se nazývá graf s hranicí . Jestliže je souvislý graf a je nějakým zobrazením do metrického prostoru , pak každé zobrazení, jehož omezení se shoduje s , se nazývá síť typu s hranicí v metrickém prostoru . Omezení sítě na vrcholy a hrany grafu se nazývají vrcholy a hrany této sítě . Délka hrany sítě je hodnota a délka sítě je součet délek všech jejích hran. $\částečné G$ $PROTI$ $G=(V,E)$ $(G,\částečné G)$ $\částečné G$ $G$ $\varphi \colon \partial G\to X$ $(X,\rho)$ $\Gamma \dvojtečka G\to X$ $\částečné G$ $\varphi$ $(G,\částečné G)$ $\varphi$ $(X,\rho)$ $\Gamma$ $G$ $\Gamma \colon \{u,v\}\to X$ $\Gamma$ $\rho {\bigl (}\Gamma (u),\Gamma (v){\bigr )}$ $\rho (\gamma)$ $\Gamma$

Označme množinou všech sítí typu s hranicí . Síť z , která má nejmenší možnou délku, se nazývá minimální parametrická síť typu s hranicí . $[G,\varphi]$ $(G,\částečné G)$ $\varphi$ $[G,\varphi]$ $(G,\částečné G)$ $\varphi$

Všimněte si, že stejně jako v případě minimálních Steinerových stromů, minimální parametrická síť vždy neexistuje. Nejmenší infimum hodnot ze všech sítí od , vždy existuje, se nazývá délka minimální parametrické sítě a označuje se . $\rho (G)$ $[G,\varphi]$ $\operatorname {mpn}[G,\varphi ]$

Jestliže je konečná podmnožina , a mapuje se na všechny , to znamená , pak říkáme , že se síť připojuje . Je snadné vidět, že přes všechny , pro které . Steinerův obecný problém je tedy redukován na studium minimálních parametrických sítí a výběr těch nejkratších z nich. $M$ $X$ $\varphi$ $\částečné G$ $M$ $\operatorname {im}(\varphi )=M$ $\Gamma \in [G,\varphi ]$ $M$ $\operatorname {smt}(M)=\inf \operatorname {mpn}[G,\varphi ]$ $[G,\varphi]$ $\operatorname {im}(\varphi )=M$

Jednorozměrné minimální výplně ve smyslu Gromova

Toto přirozené zobecnění Steinerova problému navrhli A. O. Ivanov a A. A. Tuzhilin [12] . Nechť je libovolná konečná množina a je nějaký souvislý graf. Řekneme, že spojuje , pokud . Nechť je nyní konečný pseudometrický prostor (kde se na rozdíl od metrického prostoru mohou vzdálenosti mezi různými body rovnat nule), buďme spojený graf spojující , a buďme nějaké zobrazení na nezáporná reálná čísla, obvykle nazývaná váhová funkce a generování váženého grafu . Funkce definuje pseudometric , jmenovitě vzdálenost mezi vrcholy grafu je nejmenší z vah cest spojujících tyto vrcholy. Pokud pro nějaké body a od , pak se vážený graf nazývá vyplnění prostoru a graf se nazývá typ tohoto vyplnění . Číslo rovné přes všechny výplně prostoru se nazývá hmotnost minimální výplně a výplň , pro kterou se nazývá minimální výplň . Hlavním úkolem je naučit se vypočítat a popsat minimální náplně. $M$ $G=(V,E)$ $G$ $M$ $M\podmnožina V$ ${{\mathcal M}}=(M,\rho )$ $G=(V,E)$ $M$ ${\displaystyle \omega \colon E\to {\mathbb {R} }_{+))$ ${\mathcal G}=(G,\omega )$ $\omega$ $PROTI$ $d_{\omega }$ ${\mathcal G}$ $p$ $q$ $M$ $\rho (p,q)\leq d_{\omega }(p,q)$ ${\mathcal G}$ ${\mathcal {M}}$ $G$ $\operatorname {mf}({\mathcal M})$ $\inf \omega ({\mathcal G})$ ${\mathcal G}$ ${\mathcal {M}}$ ${\mathcal G}$ $\omega ({\mathcal G})=\jméno operátora {mf}({\mathcal M})$ $\operatorname {mf}({\mathcal M})$

Poznámky

↑ Karp R. M. Redukovatelnost mezi kombinatorickými problémy - 1972. - doi: 10.1007 / 978-1-4684-2001-2_9
↑ Fermat P. de (1643), Ed. H. Tannery, ed., "Oeuvres" , sv. 1, Paris 1891, Supplement: Paris 1922, str. 153 , < https://archive.org/details/oeuvresdefermat901ferm >
↑ G. Loria, G. Vassura (1919), Opere de Evangelista Torriceli , sv. 1, str. 79-97
↑ J. Krarup, S. Vajda. O Torricelliho geometrickém řešení Fermatova problému // IMA J. Math. Appl. autobus. Průmysl. : deník. - 1997. - Sv. 8 , č. 3 . - str. 215-224 . - doi : 10.1093/imaman/8.3.215 .
↑ B. Cavalieri (1647), Excercitationes Geometricae
↑ T. Simpson (1750), "The Doctrine and Application of Fluxions"
↑ 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 bodů , Ĉas, Pêstování Mat. (Essen) T. 63: 223-235 , < https://eudml.org/doc/25703#content > Archivováno 4. března 2016 na Wayback Machine
↑ 1 2 R. Courant, H. Robbins (1941), Co je matematika? Oxford University Press
↑ Belousov A.I., Tkachev S.B. Diskrétní matematika. - M. : MGTU, 2006. - S. 306-311. — ISBN 5-7038-2886-4 .
↑ Kureichik V. M. Genetické algoritmy a jejich aplikace. Taganrog RTU, 2002. 244 s.
↑ A. O. Ivanov, A. A. Tuzhilin. Jednorozměrné Gromovovo minimální plnění (neurčité) .

Literatura

A. O. Ivanov, A. A. Tužilin. Teorie extremních sítí. - Moskva-Iževsk: Institut pro počítačový výzkum, 2003. - ISBN 5-93972-292-X .
A. O. Ivanov, A. A. Tužilin. Steinerův problém v rovině, nebo planární minimální sítě, Mateme. So - 1991. - T. 182 , č. 12 . - S. 1813-1844 .
Protasov V. Yu Maxima a minima v geometrii . — M. : MTsNMO. — 56 str. - (Knihovna "Matematická výchova", číslo 31).
Weisstein, Eric W. Steiner Tree (anglicky) na webových stránkách Wolfram MathWorld .

NP-úplné problémy
Maximalizační problém stohování (balení)	Balení v kontejnerech dvourozměrné balení lineární balení balení podle hmotnosti balení podle hodnoty Problém s batohem
teorie grafů teorie množin	Problém s krytím vertexu Klikněte na problém Problém nezávislé množiny (množiny) Nastavit problém s krytím Steinerův problém Problém cestujícího prodejce Obecný problém cestujícího prodejce
Algoritmické problémy	Problém splnitelnosti pro booleovské vzorce (v konjunktivní normální formě)
Logické hry a hádanky	Generalizované značky (hra v N 2 -1) problém s nejkratším řešením Problémy, jejichž řešení jsou aplikována v Tetrisu Generalizovaný problém sudoku Problém vyplňování latinského čtverce Kakurův úkol
Třídy obtížnosti Operační výzkum Optimalizace Kombinatorická optimalizace Aplikovaná matematika Teorie algoritmů Dynamické programování 21 NP-úplný Karp problém