Steiners minimum træ problem

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 28. juni 2022; verifikation kræver 1 redigering .

Steiners minimum træ problem
Opkaldt efter	Jacob Steiner
Beregningsmæssig kompleksitet	NP-komplet problem [1]
Mediefiler på Wikimedia Commons

Steiner-minimumstræproblemet er at finde det korteste netværk, der forbinder et givet endeligt sæt punkter i planet. Problemet fik sit navn til ære for Jacob Steiner (1796-1863).

Den alternative betingelse for problemet er at finde en minimal subgraf, der forbinder et endeligt antal givne toppunkter (terminaler) og dermed danner et netværk af korteste veje mellem disse toppunkter. Problemet er altså en generalisering af minimum spanning tree problemet .

Historie

Historien om dette problem går tilbage til Pierre de Fermats tid (1601-1665), som efter at have forklaret sin metode til at undersøge minima og maksima skrev [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.

Den, der ikke satte pris på denne metode, lad ham løse [følgende problem]: for givet tre point, find sådan et fjerde, at hvis der trækkes tre segmenter fra det til disse punkter, så vil summen af disse tre segmenter give mindste værdi.

Dette problem blev delvist løst af E. Torricelli [3] [4] (1608-1647) og B. Cavalieri [5] (1598-1647), elever af B. Castelli (1577-1644), så var den konstruktion, de fandt, var modificeret af T. Simpson [6] (1710-1761) og endelig forfinet af F. Heinen [7] og J. Bertrand (1822-1900). Som et resultat blev der opnået en geometrisk konstruktion af punktet S , nu kaldet Fermat-punktet (nogle gange Torricelli-punktet ), som for tre givne punkter A , B og C giver den mindst mulige sum af længderne af segmenterne AS , BS , CS .

I 1934 formulerede V. Yarnik og O. Kessler [8] en generalisering af Fermat-problemet, idet de erstattede tre punkter med et vilkårligt endeligt tal. Deres opgave er nemlig at beskrive forbundne plane grafer af den mindste længde, der passerer gennem et givet endeligt sæt punkter i planet.

I 1941 udkom den populære bog Hvad er matematik? » [9] R. Courant og G. Robbins, hvori forfatterne skrev følgende:

En meget enkel og samtidig lærerig problemstilling blev studeret i begyndelsen af forrige århundrede af den berømte Berlingeometer Jakob Steiner. Det er påkrævet at forbinde tre landsbyer , , med et vejsystem på en sådan måde, at deres samlede længde er minimal. Det ville være naturligt at generalisere dette problem til tilfældet med givne punkter som følger: det er nødvendigt at finde et sådant punkt i planet , at summen af afstandene (hvor angiver afstanden ) bliver et minimum. … Dette generaliserede problem, også undersøgt af Steiner, fører ikke til interessante resultater. I dette tilfælde har vi at gøre med en overfladisk generalisering, som der er mange af i den matematiske litteratur. For at få en virkelig bemærkelsesværdig generalisering af Steiners problem, må man opgive søgen efter et enkelt punkt . I stedet satte vi os til opgave at anlægge et "gadenet" eller "et netværk af veje mellem givne landsbyer", der har en minimum totallængde. [9] $EN$ $B$ $C$
$n$ $A_{1},A_{2},\ldots ,A_{n}$ $P$ $a_{1}+a_{2}+\ldots +a_{n}$ $a_{i}$ $PA_{i}$ $P$

Denne bog vandt velfortjent popularitet, som et resultat af, at både Fermat-problemet og Jarnick-Kessler-problemet nu kaldes Steiner-problemet.

Løsningsalgoritme

En effektiv (kompleksitet er udtrykt af en funktion afgrænset ovenfra af et eller andet polynomium i problemparameteren, i dette tilfælde antallet af grafens hjørnepunkter) algoritme, der giver en nøjagtig løsning på Steiner-problemet, eksisterer ikke under den betingelse, at klasserne P og NP er ikke ens , da problemet er NP-komplet . Det er let at bevise dette ved at reducere til problemet med topdækslet .

Trods begrænsningerne kan problemet løses tilnærmelsesvis, hvilket er hvad Coe, Markowski og Bergman algoritmen gør. Ideen med denne tilgang er, at den nedre grænse for omkostningerne ved at forbinde to toppunkter (terminaler) er den korteste vej mellem dem, og sættet af minimumsomkostningsveje, der forbinder alle terminaler, giver en 2-tilnærmet løsning, som det vil blive vist under. Så algoritmen vil se sådan ud:

Givet en graf , et sæt terminaler og en omkostningsfunktion . $G=(V,E)$ $T\subset V$ $c\colon E\to \mathbb {Q}$
Find en klike sådan , at . $G_{D}=(T,F)$ $c\colon F\to \mathbb {Q}$ $c_{D}(\{a,b\})=\operatørnavn {dist} _{G}(a,b)$
Find det mindste spændingstræ på grafen . $S_{D}=(T,F')$ $G_{D}$
For hver kant skal du definere som kurven for længden i grafen . $e\in F'$ $W_{e}=(V_{e},F_{e})$ $c_{D}(e)$ $G$
Beregn undergrafen . $H=(\bigcup _{e\in F'}V_{e},\bigcup _{e\in F'}F_{e})$
Find det mindste resterende træ i undergrafen . $S_{H}$ $H$
Fjern fra blade, der ikke er indeholdt i . $S_{H}$ $T$
Udskriv resultatet.

Beviset for tilnærmelsesfaktoren reduceres til at estimere resultatet af algoritmen og den nøjagtige løsning: . Hvis vi fordobler alle kanterne af den optimale løsning, får vi en cyklus, der indeholder alle hjørnerne af . definerer et spændingstræ på grafen , der kun består af terminale hjørner. Således . Kruskals effektive algoritme kan bruges som en algoritme til at finde minimumsspændende træer . [ti] $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^{*})$

Dette tilnærmelsesestimat er dog ikke grænsen, og det er muligt at forbedre algoritmen ved at nå estimatet . $11/6$

Grundlæggende definitioner

Vi præsenterer flere moderne formuleringer af Steiner-problemet. Som et omgivende rum skal du i stedet for det euklidiske plan overveje et vilkårligt metrisk rum .

Minimal Steiner træer

Lad være et metrisk rum og være en graf på X , det vil sige . For hver sådan graf er længden af dens kanter defineret som afstanden mellem deres hjørner, såvel som længden af selve grafen som summen af længderne af alle dens kanter. $(X,\rho)$ $G=(V,E)$ $V\undersæt X$ $e=\{u,v\}\i E$ $\rho (u,v)$ $\rho (G)$ $G$

Hvis er en endelig delmængde af , og er en forbundet graf på , for hvilket , så kaldes en graf forbinder . I dette tilfælde er grafen, der forbinder med den mindst mulige længde , et træ , som kaldes det minimale Steiner-træ på . Det er studiet af sådanne træer, som en af versionerne af Steiner-problemet er viet til. $M$ $x$ $G=(V,E)$ $x$ $M\undersæt V$ $G$ $M$ $G$ $M$ $\rho (G)$ $M$

Bemærk, at minimale Steiner-træer ikke altid eksisterer. Men det mindste infimum af mængderne over alle forbundne grafer, der forbinder , eksisterer altid, kaldes længden af det mindste Steiner-træ på og er betegnet med . $\rho (G)$ $M$ $M$ $\operatørnavn {smt}(M)$

Eksempler

Hvis er det euklidiske standardplan, det vil sige afstanden genereres af normen , så får vi det klassiske Steiner-problem formuleret af Yarnik og Kessler (se ovenfor). $(X,\rho)$ $\rho$ $\|(x,y)\|={\sqrt {x^{2}+y^{2}}}$

Hvis er Manhattan-planet , det vil sige afstanden er genereret af normen , så får det det rektangulære Steiner-problem , hvor en af anvendelserne er designet af mikrokredsløbslayouts [11] . Mere moderne layout er modelleret af en metrik genereret af λ-normen (enhedscirklen er en regulær 2λ-gon; i disse termer er Manhattan-normen en 2-norm). $(X,\rho)$ $\rho$ $\|(x,y)\|=|x|+|y|$

Hvis kuglen tages som kuglen (som tilnærmelsesvis modellerer Jordens overflade), og for længden af den korteste af de to buer i en storcirkel skåret fra kuglen af et plan, der går gennem og midten af kuglen, så opnås en slags transportproblem : det er nødvendigt at forbinde et givet sæt punkter (byer, virksomheder, abonnenter osv.) det korteste kommunikationsnetværk (veje, rørledninger, telefonlinjer osv.), hvilket minimerer byggeomkostningerne (det forudsættes, at omkostningerne er proportionale med længden af nettet). $x$ $\rho (a,b)$ $x$ $-en$ $b$

Hvis mængden af alle ord over et eller andet alfabet tages som værdien, og Levenshtein-afstanden tages som værdien , opnås en variant af Steiner-problemet, som er meget udbredt i bioinformatik, især til at bygge et evolutionært træ . . $x$ $\rho (a,b)$

Hvis sættet af hjørner af en forbundet graf tages som værdien, og afstandsfunktionen genereret af en vægtfunktion tages som værdien, så opnås Steiner-problemet i grafer . Et særligt tilfælde af dette problem (når det givne sæt falder sammen med mængden af alle toppunkter, ) er problemet med at konstruere et minimumspændende træ . $x$ $V$ $G=(V,E)$ $\rho$ $\omega \colon E\to \mathbb {R}$ $M=X$

Minimale parametriske netværk

Lade være en delmængde af sættet af hjørner af grafen, der indeholder alle hjørner af grad 1 og 2. Et par kaldes en graf med grænse . Hvis er en forbundet graf, og er en afbildning til et metrisk rum , så kaldes hver afbildning, hvis begrænsning falder sammen med , et netværk af typen med grænse i det metriske rum . Begrænsningen af et netværk til toppunkter og kanter af en graf kaldes henholdsvis toppunkter og kanter af dette netværk . Længden af netværkets kant er værdien , og længden af netværket er summen af længderne af alle dets kanter. $\delvis G$ $V$ $G=(V,E)$ $(G,\delvis G)$ $\delvis G$ $G$ $\varphi \colon \partial G\til X$ $(X,\rho)$ $\Gamma \kolon G\til X$ $\delvis G$ $\varphi$ $(G,\delvis G)$ $\varphi$ $(X,\rho)$ $\Gamma$ $G$ $\Gamma \colon \{u,v\}\til X$ $\Gamma$ $\rho {\bigl (}\Gamma (u),\Gamma (v){\bigr )}$ $\rho (\gamma )$ $\Gamma$

Betegn ved sættet af alle netværk af typen med grænse . Netværket fra , som har den mindst mulige længde, kaldes det minimale parametriske netværk af typen med grænse . $[G,\varphi ]$ $(G,\delvis G)$ $\varphi$ $[G,\varphi ]$ $(G,\delvis G)$ $\varphi$

Bemærk, at der, som i tilfældet med minimale Steiner-træer, ikke altid eksisterer et minimalt parametrisk netværk. Men det mindste infimum af værdier over alle netværk fra , eksisterer altid, kaldes længden af det minimale parametriske netværk og er betegnet med . $\rho (G)$ $[G,\varphi ]$ $\operatørnavn {mpn}[G,\varphi ]$

Hvis er en endelig delmængde af , og maps til alle , det vil sige , så siger vi , at netværket forbinder . Det er let at se, at over alt , for hvilket . Således er Steiners generelle problem reduceret til studiet af minimale parametriske netværk og valget af de korteste blandt dem. $M$ $x$ $\varphi$ $\delvis G$ $M$ $\operatørnavn {im}(\varphi )=M$ $\Gamma \i [G,\varphi ]$ $M$ $\operatørnavn {smt}(M)=\inf \operatørnavn {mpn}[G,\varphi ]$ $[G,\varphi ]$ $\operatørnavn {im}(\varphi )=M$

Endimensionelle minimale fyldninger i betydningen Gromov

Denne naturlige generalisering af Steiner-problemet blev foreslået af A. O. Ivanov og A. A. Tuzhilin [12] . Lad være en vilkårlig endelig mængde og være en sammenhængende graf. Vi vil sige, at forbinder hvis . Lad nu være et endeligt pseudometrisk rum (hvor, i modsætning til et metrisk rum, afstandene mellem forskellige punkter kan være lig med nul), være en forbundet graf, der forbinder , og være en vis afbildning til ikke-negative reelle tal, normalt kaldet en vægtfunktion og generere en vægtet graf . Funktionen definerer den pseudometriske , nemlig afstanden mellem grafens toppunkter er den mindste af vægtene af stierne, der forbinder disse toppunkter. Hvis der er tale om nogle punkter og fra , så kaldes den vægtede graf fyldningen af rummet , og grafen kaldes typen af denne fyldning . Tallet lig med over alle fyldninger af rummet kaldes vægten af minimumsfyldningen , og fyldningen , for hvilken , kaldes minimumsfyldningen . Hovedopgaven er at lære at beregne og beskrive minimumsfyldningerne. $M$ $G=(V,E)$ $G$ $M$ $M\undersæt 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}$ $s$ $q$ $M$ $\rho (p,q)\leq d_{\omega }(p,q)$ ${\mathcal G}$ ${\mathcal {M}}$ $G$ $\operatørnavn {mf}({\mathcal M})$ $\inf \omega ({\mathcal G})$ ${\mathcal G}$ ${\mathcal {M}}$ ${\mathcal G}$ $\omega ({\mathcal G})=\operatørnavn {mf}({\mathcal M})$ $\operatørnavn {mf}({\mathcal M})$

Noter

↑ Karp R. M. Reducibility among Combinatorial Problemer - 1972. - doi: 10.1007 / 978-1-4684-2001-2_9
↑ Fermat P. de (1643), udg. H. Tannery, red., "Oeuvres" , bind. 1, Paris 1891, Tillæg: Paris 1922, s. 153 , < https://archive.org/details/oeuvresdefermat901ferm >
↑ G. Loria, G. Vassura (1919), Opere de Evangelista Torriceli , bd. 1, s. 79-97
↑ J. Krarup, S. Vajda. Om Torricellis geometriske løsning på et problem med Fermat // IMA J. Math. Appl. bus. Industri. : journal. - 1997. - Bd. 8 , nr. 3 . - S. 215-224 . - doi : 10.1093/imaman/8.3.215 .
↑ B. Cavalieri (1647), Excercitationes Geometricae
↑ T. Simpson (1750), "The Doctrin 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 bodu , Ĉas, Pêstování Mat. (Essen) T. 63: 223-235 , < https://eudml.org/doc/25703#content > Arkiveret 4. marts 2016 på Wayback Machine
↑ 1 2 R. Courant, H. Robbins (1941), What Is Mathematics? Oxford University Press
↑ Belousov A.I., Tkachev S.B. Diskret matematik. - M. : MGTU, 2006. - S. 306-311. — ISBN 5-7038-2886-4 .
↑ Kurichik V. M. Genetiske algoritmer og deres anvendelse. Taganrog RTU, 2002. 244 s.
↑ A.O. Ivanov, A.A. Tuzhilin. Endimensionel Gromov minimal fyldning (ubestemt) .

Litteratur

A. O. Ivanov, A. A. Tuzhilin. Teori om ekstreme netværk. - Moskva-Izhevsk: Institut for Computerforskning, 2003. - ISBN 5-93972-292-X .
A. O. Ivanov, A. A. Tuzhilin. Steiner-problemet på flyet, eller plane minimale netværk, Matem. Lørdag - 1991. - T. 182 , nr. 12 . - S. 1813-1844 .
Protasov V. Yu Maxima og minima i geometri . — M. : MTsNMO. — 56 s. - (Bibliotek "Matematisk uddannelse", hæfte 31).
Weisstein, Eric W. Steiner Tree (engelsk) på Wolfram MathWorld- webstedet .

NP-komplette problemer
Maksimeringsproblem ved stabling (pakning)	Emballering i containere todimensionel pakning lineær pakning pakning efter vægt emballage efter værdi Rygsækproblemet
grafteori mængdeteori	Vertex Cover Problem Klik problem Problemet med et uafhængigt sæt (sæt) Sæt dækningsproblem Steiners problem Problemet med den rejsende sælger Generaliseret rejsende sælger problem
Algoritmiske problemer	Tilfredshedsproblem for booleske formler (i konjunktiv normal form)
Logiske spil og puslespil	Generaliserede tags (spil i N 2 -1) korteste løsningsproblem Problemer, hvis løsninger anvendes i Tetris Generaliseret Sudoku problem Latinsk kvadratisk påfyldningsproblem Kakuros opgave
Sværhedsklasser Operationsforskning Optimering Kombinatorisk optimering Anvendt matematik Teori om algoritmer Dynamisk programmering 21 NP-komplet Karp problem