Problema minimă a arborelui lui Steiner

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 28 iunie 2022; verificarea necesită 1 editare .

Problema minimă a arborelui lui Steiner
Numit după	Jacob Steiner
Complexitatea computațională	Problemă NP-completă [1]
Fișiere media la Wikimedia Commons

Problema arborelui minim Steiner este de a găsi cea mai scurtă rețea care conectează un anumit set finit de puncte în plan. Problema și-a primit numele în onoarea lui Jacob Steiner (1796-1863).

Condiția alternativă a problemei este de a găsi un subgraf minim care conectează un număr finit de vârfuri date (terminale) și formând astfel o rețea de cele mai scurte căi între aceste vârfuri. Problema este astfel o generalizare a problemei arborelui de întindere minim .

Istorie

Istoria acestei probleme datează de pe vremea lui Pierre de Fermat (1601-1665), care, după ce și-a expus metoda de investigare a minimelor și maximelor, a scris [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.

Cel care nu a apreciat această metodă, să rezolve [următoarea problemă]: pentru trei puncte date, găsiți un astfel de al patrulea, încât dacă din ea sunt trase trei segmente la aceste puncte, atunci suma acestor trei segmente va da cea mai mică valoare.

Această problemă a fost parțial rezolvată de E. Torricelli [3] [4] (1608-1647) și B. Cavalieri [5] (1598-1647), elevi ai lui B. Castelli (1577-1644), apoi construcția pe care au găsit-o a fost modificat de T. Simpson [6] (1710-1761) și rafinat în final de F. Heinen [7] și J. Bertrand (1822-1900). Ca urmare, s- a obținut o construcție geometrică a punctului S , numit acum punctul Fermat (uneori punctul Torricelli ), care pentru trei puncte date A , B și C dă suma minimă posibilă a lungimilor segmentelor AS , BS . , CS .

În 1934, V. Yarnik și O. Kessler au formulat [8] o generalizare a problemei Fermat, înlocuind trei puncte cu un număr finit arbitrar. Și anume, sarcina lor este de a descrie grafice plane conectate de cea mai mică lungime care trec printr-un anumit set finit de puncte din plan.

În 1941, populara carte Ce este matematica? » [9] R. Courant și G. Robbins, în care autorii au scris următoarele:

O problemă foarte simplă și în același timp instructivă a fost studiată la începutul secolului trecut de celebrul geometru berlinez Jakob Steiner. Este necesară conectarea a trei sate , , cu un sistem rutier astfel încât lungimea lor totală să fie minimă. Ar fi firesc să generalizăm această problemă la cazul punctelor date astfel: este necesar să se găsească un astfel de punct în plan încât suma distanțelor (unde indică distanța ) să devină minimă. … Această problemă generalizată, studiată și de Steiner, nu conduce la rezultate interesante. În acest caz, avem de-a face cu o generalizare superficială, asemănătoare căreia există multe în literatura matematică. Pentru a obține o generalizare cu adevărat demnă de remarcat a problemei lui Steiner, trebuie să renunțăm la căutarea unui singur punct . În schimb, ne-am propus să construim o „rețea de străzi” sau „o rețea de drumuri între anumite sate” care să aibă o lungime totală minimă. [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$

Această carte a câștigat o popularitate binemeritată, în urma căreia atât problema Fermat, cât și problema Jarnick-Kessler sunt acum numite problema Steiner.

Algoritm de soluție

Un algoritm eficient (complexitatea este exprimată printr-o funcție mărginită de sus de un polinom în parametrul problemei, în acest caz numărul de vârfuri ale grafului) care oferă o soluție exactă problemei Steiner nu există cu condiția ca clasele P și NP nu sunt egale , deoarece problema este NP-completă . Este ușor de demonstrat acest lucru prin reducerea la problema acoperirii vârfurilor .

În ciuda limitărilor, problema poate fi rezolvată aproximativ, ceea ce face algoritmul Coe, Markowski și Bergman. Ideea acestei abordări este că limita inferioară a costului conectării a două vârfuri (terminale) este cea mai scurtă cale dintre ele, iar setul de căi de cost minim care conectează toate terminalele oferă o soluție aproximativă de 2, așa cum se va arăta. de mai jos. Deci algoritmul va arăta astfel:

Având în vedere un grafic , un set de terminale și o funcție de cost . $G=(V,E)$ $T\subset V$ $c\colon E\to \mathbb {Q}$
Găsiți o clică astfel încât . $G_{D}=(T,F)$ $c\colon F\la \mathbb {Q}$ $c_{D}(\{a,b\})=\operatorname {dist} _{G}(a,b)$
Găsiți arborele de acoperire minim al graficului . $S_{D}=(T,F')$ $G_{D}$
Pentru fiecare muchie , definiți calea lungimii în grafic . $e\in F'$ $W_{e}=(V_{e},F_{e})$ $c_{D}(e)$ $G$
Calculați subgraful . $H=(\bigcup _{e\in F'}V_{e},\bigcup _{e\in F'}F_{e})$
Găsiți arborele minim rămas din subgraf . $S_{H}$ $H$
Scoateți din frunzele care nu sunt conținute în . $S_{H}$ $T$
Emite rezultatul.

Dovada factorului de aproximare se reduce la estimarea rezultatului algoritmului și a soluției exacte: . Dacă dublăm toate muchiile soluției optime, obținem un ciclu care conține toate vârfurile lui . definește un arbore care se întinde pe grafic , constând numai din vârfuri terminale. Astfel . Algoritmul eficient al lui Kruskal poate fi folosit ca algoritm pentru găsirea arborilor de întindere minimă . [zece] $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^{*})$

Cu toate acestea, această estimare de aproximare nu este limita și este posibil să se îmbunătățească algoritmul prin atingerea estimării . $11/6$

Definiții de bază

Prezentăm câteva formulări moderne ale problemei Steiner. Ca spațiu ambiental, în loc de planul euclidian, luați în considerare un spațiu metric arbitrar .

Arbori Steiner minimi

Fie un spațiu metric și un grafic pe X , adică . Pentru fiecare astfel de grafic, lungimile muchiilor sale sunt definite ca distanțele dintre vârfurile lor, precum și lungimea graficului în sine ca suma lungimilor tuturor muchiilor sale. $(X,\rho)$ $G=(V,E)$ $V\subset X$ $e=\{u,v\}\în E$ $\rho (u,v)$ $\rho (G)$ $G$

Dacă este o submulțime finită a , și este un graf conectat pe , pentru care , atunci se numește un graf care conectează . În acest caz, graficul care se conectează cu lungimea minimă posibilă este un arbore , care se numește arborele Steiner minim pe . Una dintre versiunile problemei Steiner îi este dedicată studiului unor astfel de arbori. $M$ $X$ $G=(V,E)$ $X$ $M\subset V$ $G$ $M$ $G$ $M$ $\rho (G)$ $M$

Rețineți că arborii Steiner minimi nu există întotdeauna. Cu toate acestea, cea mai mică infimă dintre cantitățile din toate graficele conectate care se conectează , există întotdeauna, se numește lungimea arborelui Steiner minim pe și este notat cu . $\rho (G)$ $M$ $M$ $\operatorname {smt}(M)$

Exemple

Dacă este planul euclidian standard, adică distanța este generată de norma , atunci obținem problema clasică Steiner formulată de Yarnik și Kessler (vezi mai sus). $(X,\rho)$ $\rho$ $\|(x,y)\|={\sqrt {x^{2}+y^{2}}}$

Dacă este planul Manhattan , adică distanța este generată de normă , atunci se obține problema Steiner dreptunghiulară , una dintre aplicațiile căreia este proiectarea schemelor de microcircuite [11] . Dispozițiile mai moderne sunt modelate de o metrică generată de norma λ (cercul unitar este un gon obișnuit 2λ; în acești termeni, norma Manhattan este o normă 2). $(X,\rho)$ $\rho$ $\|(x,y)\|=|x|+|y|$

Dacă sfera este luată ca sferă (modelând aproximativ suprafața Pământului) și pentru lungimea celui mai scurt dintre cele două arce de cerc mare tăiat din sferă de un plan care trece prin , și centrul sferei, atunci se obține un fel de problemă de transport : se cere conectarea unui set dat de puncte (orașe, întreprinderi, abonați etc.) cea mai scurtă rețea de comunicații (drumuri, conducte, linii telefonice etc.), minimizând costurile de construcție (este se presupune că costurile sunt proporționale cu lungimea rețelei). $X$ $\rho (a,b)$ $X$ $A$ $b$

Dacă se ia ca valoare setul tuturor cuvintelor dintr-un anumit alfabet, iar distanța Levenshtein este luată ca valoare , atunci se obține o variantă a problemei Steiner, care este utilizată pe scară largă în bioinformatică, în special, pentru a construi un arbore evolutiv. . $X$ $\rho (a,b)$

Dacă se ia ca valoare setul de vârfuri ale unui graf conectat și se ia ca valoare funcția distanță generată de o funcție de greutate , atunci se obține problema Steiner în grafice . Un caz special al acestei probleme (când mulțimea dată coincide cu mulțimea tuturor vârfurilor, ) este problema construirii unui arbore de întindere minim . $X$ $V$ $G=(V,E)$ $\rho$ $\omega \colon E\to \mathbb {R}$ $M=X$

Rețele parametrice minime

Fie o submulțime a mulțimii de vârfuri ale graficului care conține toate vârfurile de gradul 1 și 2. O pereche se numește grafic cu graniță . Dacă este un graf conectat și este o mapare într-un spațiu metric , atunci fiecare mapare a cărei constrângere coincide cu se numește o rețea de tip cu graniță în spațiul metric . Restricționarea unei rețele la vârfurile și muchiile unui graf se numesc, respectiv , vârfurile și muchiile acestei rețele . Lungimea marginii rețelei este valoarea , iar lungimea rețelei este suma lungimilor tuturor marginilor sale. $\partial G$ $V$ $G=(V,E)$ $(G,\G parțial)$ $\partial G$ $G$ $\varphi \colon \partial G\to X$ $(X,\rho)$ $\Gamma \colon G\la X$ $\partial G$ $\varphi$ $(G,\G parțial)$ $\varphi$ $(X,\rho)$ $\Gamma$ $G$ $\Gamma \colon \{u,v\}\la X$ $\Gamma$ $\rho {\bigl (}\Gamma (u),\Gamma (v){\bigr )}$ $\rho (\gamma )$ $\Gamma$

Se notează prin mulțimea tuturor rețelelor de tip cu graniță . Rețeaua de la , care are cea mai mică lungime posibilă, se numește rețea parametrică minimă de tip cu limită . $[G,\varphi ]$ $(G,\G parțial)$ $\varphi$ $[G,\varphi ]$ $(G,\G parțial)$ $\varphi$

Rețineți că, ca și în cazul arborilor Steiner minimi, o rețea parametrică minimă nu există întotdeauna. Cu toate acestea, cea mai mică infimă de valori din toate rețelele de la , există întotdeauna, se numește lungimea rețelei parametrice minime și se notează cu . $\rho (G)$ $[G,\varphi ]$ $\operatorname {mpn}[G,\varphi ]$

Dacă este o submulțime finită de , și mapează la toate , adică , atunci spunem că rețeaua se conectează . Este ușor să vezi că peste toate , pentru care . Astfel, problema generală a lui Steiner se reduce la studiul rețelelor parametrice minime și la alegerea celor mai scurte dintre ele. $M$ $X$ $\varphi$ $\partial 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$

Umpluturi minime unidimensionale în sensul lui Gromov

Această generalizare firească a problemei Steiner a fost propusă de A. O. Ivanov și A. A. Tuzhilin [12] . Fie o mulțime finită arbitrară și un graf conex. Vom spune că se conectează dacă . Să fie acum un spațiu pseudometric finit (unde, spre deosebire de un spațiu metric, distanțele dintre diferite puncte pot fi egale cu zero), să fie un grafic conectat care conectează și să fie o mapare în numere reale nenegative, de obicei numită funcție de greutate și generarea unui grafic ponderat . Funcția definește pseudometricul , și anume, distanța dintre vârfurile graficului este cea mai mică dintre greutățile căilor care leagă aceste vârfuri. Dacă pentru orice puncte și de la , atunci graficul ponderat se numește umplerea spațiului , iar graficul se numește tipul acestei umpleri . Numărul egal cu peste toate umpluturile spațiului se numește greutatea umpluturii minime , iar umplutura , pentru care , se numește umplutură minimă . Sarcina principală este să înveți cum să calculezi și să descrii umpluturile minime. $M$ $G=(V,E)$ $G$ $M$ $M\subset V$ ${{\mathcal M}}=(M,\rho )$ $G=(V,E)$ $M$ $\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$ $\operatorname {mf}({\mathcal M})$ $\inf \omega ({\mathcal G})$ ${\mathcal G}$ ${\mathcal {M}}$ ${\mathcal G}$ $\omega ({\mathcal G})=\operatorname {mf}({\mathcal M})$ $\operatorname {mf}({\mathcal M})$

Note

↑ Karp R. M. Reducibility among Combinatorial Problems - 1972. - doi: 10.1007 / 978-1-4684-2001-2_9
↑ Fermat P. de (1643), Ed. H. Tannery, ed., „Oeuvres” , voi. 1, Paris 1891, Supliment: Paris 1922, p. 153 , < https://archive.org/details/oeuvresdefermat901ferm >
↑ G. Loria, G. Vassura (1919), Opere de Evangelista Torriceli , vol. 1, p. 79-97
↑ J. Krarup, S. Vajda. Despre soluția geometrică a lui Torricelli la o problemă a lui Fermat // IMA J. Math. Aplic. autobuz. Industrie. : jurnal. - 1997. - Vol. 8 , nr. 3 . - P. 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 bodu , Ĉas, Pêstování Mat. (Essen) T. 63: 223-235 , < https://eudml.org/doc/25703#content > Arhivat 4 martie 2016 la Wayback Machine
↑ 1 2 R. Courant, H. Robbins (1941), What Is Mathematics? presa Universitatii Oxford
↑ Belousov A.I., Tkachev S.B. Matematică discretă. - M. : MGTU, 2006. - S. 306-311. — ISBN 5-7038-2886-4 .
↑ Kureichik V. M. Algoritmi genetici și aplicarea lor. Taganrog RTU, 2002. 244 p.
↑ A.O. Ivanov, A.A. Tujilin. Umplere minimă Gromov unidimensională (nedefinită) .

Literatură

A. O. Ivanov, A. A. Tuzhilin. Teoria rețelelor extreme. - Moscova-Ijevsk: Institutul de Cercetări Informatice, 2003. - ISBN 5-93972-292-X .
A. O. Ivanov, A. A. Tuzhilin. Problema Steiner în plan, sau rețele minime plane, Matem. Sâmbătă - 1991. - T. 182 , Nr. 12 . - S. 1813-1844 .
Protasov V. Yu. Maxime și minime în geometrie . — M .: MTsNMO. — 56 p. - (Biblioteca „Educația matematică”, numărul 31).
Weisstein, Eric W. Steiner Tree (engleză) pe site-ul Wolfram MathWorld .

Probleme NP-complete
Problema de maximizare a stivuirii (ambalării)	Ambalare in containere ambalare bidimensională ambalare liniară ambalare după greutate ambalare după valoare Problema rucsacului
teoria grafurilor teoria multimelor	Problemă de acoperire a vârfurilor Faceți clic pe problemă Problema unei multimi (multimi) independente Setați problema acoperirii Problema lui Steiner Problema vânzătorului ambulant Problemă generalizată a vânzătorului ambulant
Probleme algoritmice	Problemă de satisfacție pentru formulele booleene (în formă normală conjunctivă)
Jocuri de logică și puzzle-uri	Etichete generalizate (joc în N 2 -1) cea mai scurta solutie problema Probleme ale căror soluții sunt aplicate în Tetris Problemă generalizată de Sudoku Problemă de umplere a pătratului latin Sarcina lui Kakuro
Clasele de dificultate Cercetare operațională Optimizare Optimizare combinatorie Matematică aplicată Teoria algoritmilor Programare dinamică 21 Problemă Karp NP-completă