Steiners minsta trädproblem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 juni 2022; verifiering kräver 1 redigering .

Steiners minsta trädproblem
Döpt efter	Jacob Steiner
Beräkningskomplexitet	NP-komplett problem [1]
Mediafiler på Wikimedia Commons

Steiners minimala trädproblem är att hitta det kortaste nätverket som förbinder en given ändlig uppsättning punkter i planet. Problemet fick sitt namn för att hedra Jacob Steiner (1796-1863).

Det alternativa villkoret för problemet är att hitta en minimal subgraf som förbinder ett ändligt antal givna hörn (terminaler) och därmed bildar ett nätverk av kortaste vägar mellan dessa hörn. Problemet är alltså en generalisering av minimum spanning tree- problemet .

Historik

Historien om detta problem går tillbaka till tiden för Pierre de Fermat (1601-1665), som efter att ha förklarat sin metod för att undersöka minima och maxima 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 som inte uppskattade denna metod, låt honom lösa [följande problem]: för givna tre poäng, hitta en sådan fjärde att om tre segment dras från den till dessa punkter, så kommer summan av dessa tre segment att ge minsta värde.

Detta problem löstes delvis av E. Torricelli [3] [4] (1608-1647) och B. Cavalieri [5] (1598-1647), elever till B. Castelli (1577-1644), sedan var konstruktionen de fann var modifierad av T. Simpson [6] (1710-1761) och slutligen förfinad av F. Heinen [7] och J. Bertrand (1822-1900). Som ett resultat erhölls en geometrisk konstruktion av punkten S , nu kallad Fermat-punkten (ibland Torricelli-punkten ), som för tre givna punkter A , B och C ger den minsta möjliga summan av längderna av segmenten AS , BS , CS .

År 1934 formulerade V. Yarnik och O. Kessler [8] en generalisering av Fermatproblemet, och ersatte tre punkter med ett godtyckligt ändligt tal. Deras uppgift är nämligen att beskriva sammanhängande plana grafer av minsta längd som passerar genom en given ändlig uppsättning punkter i planet.

1941 , den populära boken Vad är matematik? » [9] R. Courant och G. Robbins, där författarna skrev följande:

Ett mycket enkelt och samtidigt lärorikt problem studerades i början av förra seklet av den berömde Berlingeometern Jakob Steiner. Det krävs att tre byar , , kopplas samman med ett vägsystem på ett sådant sätt att deras totala längd är minimal. Det skulle vara naturligt att generalisera detta problem till fallet med givna punkter enligt följande: det krävs att hitta en sådan punkt i planet att summan av avstånden (där anger avståndet ) blir ett minimum. … Detta generaliserade problem, som också studerats av Steiner, leder inte till intressanta resultat. I det här fallet har vi att göra med en ytlig generalisering, liknande som det finns många i den matematiska litteraturen. För att få en riktigt anmärkningsvärd generalisering av Steiners problem, måste man överge sökandet efter en enda punkt . Istället satte vi oss i uppgift att bygga ett "gatnät" eller "ett vägnät mellan givna byar" som har en minsta totallängd. [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$

Denna bok fick välförtjänt popularitet, som ett resultat av vilket både Fermatproblemet och Jarnick-Kesslerproblemet nu kallas Steinerproblemet.

Lösningsalgoritm

En effektiv (komplexitet uttrycks av en funktion som avgränsas ovanifrån av något polynom i problemparametern, i detta fall antalet grafens hörn) algoritm som ger en exakt lösning på Steinerproblemet existerar inte under förutsättning att klasserna P och NP är inte lika , eftersom problemet är NP-komplett . Det är lätt att bevisa detta genom att reducera till problemet med vertextäckning .

Trots begränsningarna kan problemet lösas ungefär, vilket är vad Coe, Markowski och Bergman-algoritmen gör. Tanken med detta tillvägagångssätt är att den nedre gränsen för kostnaden för att ansluta två hörn (terminaler) är den kortaste vägen mellan dem, och uppsättningen av minimikostnadsvägar som förbinder alla terminaler ger en ungefärlig lösning på två, som kommer att visas Nedan. Så algoritmen kommer att se ut så här:

Givet en graf , en uppsättning terminaler och en kostnadsfunktion . $G=(V,E)$ $T\subset V$ $c\colon E\to \mathbb {Q}$
Hitta en klick som . $G_{D}=(T,F)$ $c\colon F\to \mathbb {Q}$ $c_{D}(\{a,b\})=\operatörsnamn {avstånd} _{G}(a,b)$
Hitta det minsta spännträdet i grafen . $S_{D}=(T,F')$ $G_{D}$
För varje kant , definiera som banan för längden i grafen . $e\in F'$ $W_{e}=(V_{e},F_{e})$ $c_{D}(e)$ $G$
Beräkna subgrafen . $H=(\bigcup _{e\in F'}V_{e},\bigcup _{e\in F'}F_{e})$
Hitta det minsta återstående trädet i subgrafen . $S_{H}$ $H$
Ta bort från blad som inte finns i . $S_{H}$ $T$
Skriv ut resultatet.

Beviset för approximationsfaktorn reduceras till att uppskatta resultatet av algoritmen och den exakta lösningen: . Om vi fördubblar alla kanterna på den optimala lösningen får vi en cykel som innehåller alla hörn av . definierar ett spännande träd på grafen , som endast består av terminala hörn. Alltså . Kruskals effektiva algoritm kan användas som en algoritm för att hitta minsta spännträd . [tio] $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^{*})$

Denna approximationsuppskattning är dock inte gränsen, och det är möjligt att förbättra algoritmen genom att nå uppskattningen . $11/6$

Grundläggande definitioner

Vi presenterar flera moderna formuleringar av Steinerproblemet. Som ett omgivande utrymme, istället för det euklidiska planet, överväg ett godtyckligt metriskt utrymme .

Minimala Steiner-träd

Låta vara ett metriskt utrymme och vara en graf på X , det vill säga . För varje sådan graf definieras längden på dess kanter som avstånden mellan deras hörn, såväl som längden på själva grafen som summan av längderna av alla dess kanter. $(X,\rho)$ $G=(V,E)$ $V\delmängd X$ $e=\{u,v\}\i E$ $\rho (u,v)$ $\rho (G)$ $G$

If är en ändlig delmängd av , och är en ansluten graf på , för vilken , då kallas en graf som ansluter . I det här fallet är grafen som förbinder med minsta möjliga längd ett träd , vilket kallas det minimala Steinerträdet på . Det är studiet av sådana träd som en av versionerna av Steinerproblemet ägnas åt. $M$ $X$ $G=(V,E)$ $X$ $M\delmängd V$ $G$ $M$ $G$ $M$ $\rho (G)$ $M$

Observera att minimala Steinerträd inte alltid existerar. Men det minsta infimum av kvantiteterna över alla sammankopplade grafer som ansluter , finns alltid, kallas längden på det minsta Steinerträdet på och betecknas med . $\rho (G)$ $M$ $M$ $\operatörsnamn {smt}(M)$

Exempel

Om är det euklidiska standardplanet, det vill säga avståndet genereras av normen , då får vi det klassiska Steinerproblemet formulerat av Yarnik och Kessler (se ovan). $(X,\rho)$ $\rho$ $\|(x,y)\|={\sqrt {x^{2}+y^{2}}}$

Om är Manhattan-planet , det vill säga avståndet genereras av normen , då får det det rektangulära Steiner-problemet , en av vars tillämpningar är designen av mikrokretslayouter [11] . Modernare layouter modelleras av ett mått som genereras av λ-normen (enhetscirkeln är en vanlig 2λ-gon; i dessa termer är Manhattan-normen en 2-norm). $(X,\rho)$ $\rho$ $\|(x,y)\|=|x|+|y|$

Om sfären tas som sfären (som ungefär modellerar jordens yta), och för längden av den kortaste av de två bågarna i en storcirkel som är skuren från sfären av ett plan som passerar genom , och sfärens centrum, då erhålls ett slags transportproblem : det krävs för att ansluta en given uppsättning punkter (städer, företag, abonnenter, etc.) det kortaste kommunikationsnätet (vägar, rörledningar, telefonlinjer, etc.), vilket minimerar byggkostnaderna (det antas att kostnaderna är proportionella mot nätets längd). $X$ $\rho (a,b)$ $X$ $a$ $b$

Om uppsättningen av alla ord över något alfabet tas som värdet och Levenshtein-avståndet tas som värdet , erhålls en variant av Steinerproblemet, som används allmänt inom bioinformatik, i synnerhet för att bygga ett evolutionärt träd . $X$ $\rho (a,b)$

Om uppsättningen av hörn i en ansluten graf tas som värdet och avståndsfunktionen som genereras av någon viktfunktion tas som värdet, då erhålls Steinerproblemet i grafer . Ett specialfall av detta problem (när den givna mängden sammanfaller med mängden av alla hörn, ) är problemet med att konstruera ett minsta spännträd . $X$ $V$ $G=(V,E)$ $\rho$ $\omega \colon E\to \mathbb {R}$ $M=X$

Minimala parametriska nätverk

Låta vara någon delmängd av uppsättningen av hörn i grafen som innehåller alla hörn av grad 1 och 2. Ett par kallas en graf med gräns . Om är en sammankopplad graf, och är en mappning till ett metriskt utrymme , då kallas varje mappning vars begränsning sammanfaller med ett nätverk av typ med gräns i det metriska utrymmet . Begränsningen av ett nätverk till hörn och kanter av en graf kallas respektive hörn och kanter av detta nätverk . Längden på nätverkets kant är värdet , och nätverkets längd är summan av längderna av alla dess kanter. $\partiell G$ $V$ $G=(V,E)$ $(G,\partiell G)$ $\partiell G$ $G$ $\varphi \colon \partial G\till X$ $(X,\rho)$ $\Gamma \kolon G\till X$ $\partiell G$ $\varphi$ $(G,\partiell G)$ $\varphi$ $(X,\rho)$ $\Gamma$ $G$ $\Gamma \colon \{u,v\}\till X$ $\Gamma$ $\rho {\bigl (}\Gamma (u),\Gamma (v){\bigr )}$ $\rho (\gamma )$ $\Gamma$

Beteckna med uppsättningen av alla nätverk av typ med gräns . Nätverket från , som har minsta möjliga längd, kallas det minimala parametriska nätverket av typ med gräns . $[G,\varphi ]$ $(G,\partiell G)$ $\varphi$ $[G,\varphi ]$ $(G,\partiell G)$ $\varphi$

Observera att, som i fallet med minimala Steiner-träd, existerar inte alltid ett minimalt parametriskt nätverk. Men det minsta infimum av värden över alla nätverk från , finns alltid, kallas längden på det minsta parametriska nätverket och betecknas med . $\rho (G)$ $[G,\varphi ]$ $\operatörsnamn {mpn}[G,\varphi ]$

Om är en ändlig delmängd av , och mappar till alla , det vill säga, då säger vi att nätverket ansluter . Det är lätt att se det över allt , för vilket . Således reduceras Steiners allmänna problem till studiet av minimala parametriska nätverk och valet av de kortaste bland dem. $M$ $X$ $\varphi$ $\partiell G$ $M$ $\operatörsnamn {im}(\varphi )=M$ $\Gamma \i [G,\varphi ]$ $M$ $\operatörsnamn {smt}(M)=\inf \operatörsnamn {mpn}[G,\varphi ]$ $[G,\varphi ]$ $\operatörsnamn {im}(\varphi )=M$

Endimensionella minimala fyllningar i betydelsen Gromov

Denna naturliga generalisering av Steinerproblemet föreslogs av A. O. Ivanov och A. A. Tuzhilin [12] . Låta vara en godtycklig ändlig mängd och vara någon sammanhängande graf. Vi kommer att säga att ansluter om . Låt nu vara ett ändligt pseudometriskt utrymme (där, till skillnad från ett metriskt utrymme, avstånden mellan olika punkter kan vara lika med noll), vara en sammankopplad graf som förbinder , och vara någon avbildning till icke-negativa reella tal, vanligtvis kallad en viktfunktion och generera en viktad graf . Funktionen definierar den pseudometriska , nämligen avståndet mellan grafens hörn är det minsta av vikterna för de banor som förbinder dessa hörn. Om för några punkter och från , kallas den viktade grafen fyllningen av utrymmet , och grafen kallas typen av denna fyllning . Antalet som är lika med över alla fyllningar i utrymmet kallas vikten av minimifyllningen , och fyllningen , för vilken , kallas minimifyllningen . Huvuduppgiften är att lära sig att beräkna och beskriva minimifyllningarna. $M$ $G=(V,E)$ $G$ $M$ $M\delmängd 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}$ $sid$ $q$ $M$ $\rho (p,q)\leq d_{\omega }(p,q)$ ${\mathcal G}$ ${\mathcal {M}}$ $G$ $\operatörsnamn {mf}({\mathcal M})$ $\inf \omega ({\mathcal G})$ ${\mathcal G}$ ${\mathcal {M}}$ ${\mathcal G}$ $\omega ({\mathcal G})=\operatörsnamn {mf}({\mathcal M})$ $\operatörsnamn {mf}({\mathcal M})$

Anteckningar

↑ Karp R. M. Reducibility among Combinatorial Problems - 1972. - doi: 10.1007 / 978-1-4684-2001-2_9
↑ Fermat P. de (1643), Ed. H. Tannery, red., "Oeuvres" , vol. 1, Paris 1891, Tillägg: Paris 1922, sid. 153 , < https://archive.org/details/oeuvresdefermat901ferm >
↑ G. Loria, G. Vassura (1919), Opere de Evangelista Torriceli , vol. 1, sid. 79-97
↑ J. Krarup, S. Vajda. Om Torricellis geometriska lösning på ett problem med Fermat // IMA J. Math. Appl. buss. Industri. : journal. - 1997. - Vol. 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 > Arkiverad 4 mars 2016 på Wayback Machine
↑ 1 2 R. Courant, H. Robbins (1941), Vad är matematik? Oxford University Press
↑ Belousov A.I., Tkachev S.B. Discrete Mathematics. - M. : MGTU, 2006. - S. 306-311. — ISBN 5-7038-2886-4 .
↑ Kurichik V. M. Genetiska algoritmer och deras tillämpning. Taganrog RTU, 2002. 244 sid.
↑ A.O. Ivanov, A.A. Tuzhilin. Endimensionell Gromov minimal fyllning (obestämd) .

Litteratur

A. O. Ivanov, A. A. Tuzhilin. Teori om extrema nätverk. - Moskva-Izhevsk: Institutet för datorforskning, 2003. - ISBN 5-93972-292-X .
A. O. Ivanov, A. A. Tuzhilin. Steinerproblemet på planet, eller plana minimala nätverk, Matem. lör - 1991. - T. 182 , nr 12 . - S. 1813-1844 .
Protasov V. Yu Maxima och minima i geometri . — M. : MTsNMO. — 56 sid. - (Bibliotek "Mathematical Education", nummer 31).
Weisstein, Eric W. Steiner Tree (engelska) på Wolfram MathWorld- webbplatsen .

NP-kompletta problem
Maximeringsproblem med stapling (packning)	Förpackning i behållare tvådimensionell packning linjär packning packning efter vikt förpackning efter värde Ryggsäcksproblemet
grafteori mängdteori	Vertex Cover Problem Klicka problem Problemet med en oberoende uppsättning (uppsättning) Ställtäckningsproblem Steiners problem Problemet med resande säljare Generaliserat resandeförsäljarproblem
Algoritmiska problem	Tillfredsställelseproblem för booleska formler (i konjunktiv normal form)
Logiska spel och pussel	Generaliserade taggar (spel i N 2 -1) kortaste lösningen problem Problem vars lösningar tillämpas i Tetris Generaliserat Sudoku problem Latinsk kvadrat fyllningsproblem Kakuros uppgift
Svårighetsklasser Operationsforskning Optimering Kombinatorisk optimering Tillämpad matematik Teori om algoritmer Dynamisk programmering 21 NP-komplett Karp-problem