Մասնակից:Teni Tadevosyan
Euclidean minimum spanning tree-ն կամ EMST-ը minimum spanning treeէ հարթության վրա մի շարք n կետերից (կամ ընդհանրապես ℝd),որտեղ գագաթի կշիռը յուրաքանչյուր զույգ միավորների միջև հեռավորությունն է այդ երկեւ կետերի միջև.Այդ տեսանկյունից պարզ է որ EMST-ը կետերը իրար է միացնում գծերի միջոցով և ցանկացած կետ կարող է հասնել մեկ ուրիշին հետևելով այդ գծերին.
Հարթության վրա EMST-ը կարող է հանդես գալ Θ(n log n)այն ժամանակ երբ O(n)-ը տարածություն է algebraic decision tree հաշվարկի մոդել-ում. բարդությունների ավելի արագ randomized algorithms-ները O(n log log n)հայտնի են որպես հաշվարկի ավելի հզոր մոդելներ,որոնք ավելի ճշգրիտ մոդելներ են իրենց համակարգչային իրական կարողություններով.[1]
Բարձրագույն հարթություններում գտնելով օպտիմալ ալգորիթմներ մնում է (d ≥ 3) open problem.
Պարտավորվածության իջեցում
[խմբագրել | խմբագրել կոդը]Ասիմտոտ իջեցված սահմանը Ω(n log n)-ի համար time complexity -ի է .որը կարող է լուծել EMST-ի պրոբլեմները սահմանափակված մոդելների հաշվարկում,ինչպիսիք են algebraic decision tree -ն և algebraic computation tree մոդելները, որտեղ ալգորիթմը ունի ներդրված միավորներ միայն որոշակի սահմանափակված պրիմիտիվներով ,որոնք կատարում են պարզ հանրահաշվական հաշվարկներ իրենց կոորդինատներում:այս մոդելում , closest pair of points problem պահանջվում է Ω(n log n)ժամանակ, բայց ամենամոտ զույգը անհրաժեշտ է EMST-ի եզրին, ուստի EMST-ը նույնպես պահանջում է շատ ժամանակ .[2] Ինչևէ ,եթե ներմուծված միավորները ունեն ամբողջական թիվ համակարգում և bitwise operation-ը և [Random access|table indexing]] գորշողությունները թույլատրվում է օգտագործել այդ համակարգում այնուհետև ավելի արագ են ալգորիթմները դառնում հնարավոր .[1]
Ալգորիթմներ,որոնք հաշվում են EMST-ը երկու հարթություններում
[խմբագրել | խմբագրել կոդը]Ամենապարզ ալգորիթմը գտնել EMST-ը երկու հարթություններում ,տալով n միավորը,իրականում կառուցել complete graph n-ի վրա,որը n(n-1)/2 գագաթն է,հաշվել յուրաքանչյուր գագաթի կշիռը գտնելով հեռավորությունը ցանկացած զույգ միավորների միջև և հետո նոր ստեղծել standard minimum spanning tree-ի ալգորիթմ (ինչպիսին է Prim's algorithm-ի վերսիան կամ Kruskal's algorithm).Քանի որ այդ գրաֆիկն ունի Θ(n2)տեսքը, գագաթ n կետով, կառուցելը առդեն պահանջում է Ω(n2) ժամանակ. Այս որոշումը հաճախ պահանջում է Ω(n2) տարածություն պահելու բոլոր գագաթները.
Լավագույն մոտեցումը EMST-ը հարթության վրա գտնելու, դա նշելն է թե ինչպես յուրաքանչյուր գրաֆիկ Delaunay triangulation n կետից, ավելի է փոքրացնում գագաթների շարքը:
- Հաշվել Delaunay triangulation-ը O(n log n) ժամանակ և O(n)տարածությունում.Որովհետև Delaunay triangulation-ը դաplanar graph է,և այնտեղ չկա ավելի քան երեք անգամ ավելի շատ գագաթներ քան ուրիշ գրաֆիկներում,դա առաջացնում է միայն O(n) գագաթներ.
- Պիտակավորել յուրաքնչյուր գագաթը իր երկարությամբ
- Ստեղծել գրաֆիկ minimum spanning tree ալգորիթմով և այդ գրաֆիկի վրա գտնել minimum spanning tree-ն. Քանի որ այնտեղ O(n)-ը գագաթներն են,անհրաժեշտ է O(n log n) standard minimum spanning tree ալգորիթմներ ինչպիսին են Borůvka's algorithm-ը, Prim's algorithm-ը, կամ Kruskal's algorithm-ը.
Վեռջնական առդյունքը հանդիսանում է ալգորիթմը O(n log n) ժամանակով և O(n) տարածությամբ.
Եթե շահույթը կորդինացված ամբողջ թիվ է և կարող է օգտագործվել array indices-ում,ավելի արագ ալգորիթմները դառնում են հնարավոր: Delaunay triangulation-ը կարող է կառուցվել randomized algorithm-ով O(n log log n) ակնկալված ժամանակ.[1] Բացի այդ,քանի որ Delaunay triangulation-ը planar graph է,դրա minimum spanning tree-ն կարելի է գտնել linear time-ում Borůvka's ալգորիթմի տարբերակով,որը հեռացնում է բոլորը բայց ամենաէժան եզրը տարրերի ցանկացած զույգի միջև ալգորիթմի ամեն մի փուլից հետո.[3] Հետևաբար ընդհանուր ակնկալվող ժամանակը ալգորիթմի համար դա O(n log log n).[1]
Բարձրագույն մեծություններ
[խմբագրել | խմբագրել կոդը]Խնդիրը հաճախ կարող է լինել ընդհանրացված n կետից մինչև d-ծավալային տարածք ℝd.Բարձրագույն մեծություններում փոխկապակցվածությունը որոշվում է Delaunay triangulation-ով (որը, նմանապես, բաժանմունք է convex hull d-տարածական simplices) ,որը պառունակում է minimum spanning tree-ն ; ինչևէ, triangulation -ը պետք է պարունակի ամբողջ գրաֆիկը.[4] Հետևաբար, գտնելով որ Euclidean minimum spanning tree-ն ամբողջական գրաֆիկի spanning tree է կամ Delaunay triangulation-ի spanning tree երկուսն ել տանւմ են O(dn2)ժամանակի.Երեք մեծությունների համար հնարավոր է գտնել minimum spanning tree-ն ժամանակին O((n log n)4/3),և ցանկացած մեծություն ավելի քան երեքը հնարավոր է վճռելու ժամանակին,այսինքն ավելի արագ քան quadratic ժամանակ ամբողջական գրաֆիկում և Delaunay triangulation ալգորիթմներում.[4][5]
Subtree of Delaunay triangulation
[խմբագրել | խմբագրել կոդը]EMST-ի բոլոր եզրերը եզրեր են relative neighborhood graph-ի,[6][7][8] որոնք իրենց հերթին ունեն եզրեր Gabriel graph-ից, ունեն եզրեր Delaunay triangulation-ի կետերից ,[9][10] Որոնք կարելի է ապացուցել համարժեքության միջոցով contrapositive հայտարարությամբ.Ապացույցը հիմնված է minimum spanning tree-ի և Delaunay triangulation-ի երկու հատկությունների հիման վրա:
- (the cycle property of minimum spanning trees): գրաֆիկի ցանկացած C շրջանի վրա,եթե C եզրի e կշիռը ավելի մեծ է քան C եզրի այլ կշիռները,ապա այդ կշիռները MST-ին չեն կարող պատկանել.
- ( Delaunay triangulation-ի սեփականություն): Եթե կա շրջան իր սահմաններին ներգծված երկու կետերով,որը չի պարունակում այլ կետեր գիծը այդ երկու կետերի միջև եզրն է ամեն մի Delaunay triangulation-ի.
Դիտարկենք e եզրի միջև ընկած p և q կետերը ,որոնք Delaunay triangulation-ի եզրերը չեն. Property 2-ն ենթադրում է ,որ Cշրջանը e-ի հետ նրանց տրամագիծը պետք է պարունակի մեկ այլ r կետ ներսում . Բացի այդ r-ը ավելի մոտ է p-ն և q-ին քան նրանք միմյանց և այսպիսով եզրերը դեպի p-ից q ամենաերկար եզրն է կետերի շրջանակներում p → q → r → p, և property 1 -ի e -ն ցանկացած EMST-ի չէ.
Սպասվելիք չափը
[խմբագրել | խմբագրել կոդը]EMST-ի սպասվելիք չափը մեծ թվով միավորների համար սահմանվել է J. Michael Steele-ի կողմից . Եթե -ը հավանականության ֆունկցիայի տեսակարար կշիռն է միավորներ հավաքելիս, այնուհետև մեծ -ի և -ի EMST չափի համար մոտավորապես
- է, որտեղ
-ը դա հարթության վրաի հաստատուն կախվածություն է -ից. Կոնստանտի իրական արժեքը անհայտ է բայց կարող է գնահատված լինել փորձնական ապացույցներից.
Ծրագրեր
[խմբագրել | խմբագրել կոդը]Euclidean minimum spanning tree-ի ակնհայտ հայտը դա ամենաէժան լարերի կամ խողովակների ցանց գտնելն է ,որը պետք է միացնել մի շարք վայրերում. Ինչևէ, ամենանման ցանցերը նախընտրում են k-ծառին միացված գրաֆը, այսպիսով ցանկացած անհատական հղման ձախողումը չի պառակտում ցանցը մասերի.
Մեկ ուրիշ EMST-ի ծրագիրը դա constant-factor approximation algorithm-ն է մոտավորապեսEuclidean traveling salesman problem-ի լուծման համար, traveling salesman problem- վերսիան մի շարք հարթության կետերի և երկարության ծայրերի հետ .
Հարթ լուծումներ
[խմբագրել | խմբագրել կոդը]խնդրի լուծումը Euclidean minimum spanning tree-ի համար սկսվում է հետևյալով : Տալով tree T = (V, E)-ը, գտնել D(u) կետը ցանկացած u ∈ V' 'այսպիսով T -ն D(u) minimum spanning tree -ի համար : u ∈ V, կամ որոշել որ նման տեղեր գոյություն ունեն. Իրականության մեջ փորձարկումը the plane դա NP-hard.[11]
Հիպերհղումներ
[խմբագրել | խմբագրել կոդը]- ↑ 1,0 1,1 1,2 1,3 Buchin, Kevin; Mulzer, Wolfgang (2009), «Delaunay triangulations in O(sort(n)) time and more», [[Symposium on Foundations of Computer Science|Proc. 50th IEEE Symposium on Foundations of Computer Science]] (PDF), էջեր 139–148, doi:10.1109/FOCS.2009.53
{{citation}}
: URL–wikilink conflict (օգնություն). - ↑ Yao, A. C.-C. (1989), «Lower bounds for algebraic computation trees with integer inputs», Proc. 30th Annual Symposium on Foundations of Computer Science (FOCS 1989), էջեր 308–313, doi:10.1109/SFCS.1989.63495.
- ↑ Eppstein, David (1999), «Spanning trees and spanners», in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry, Elsevier, էջեր 425–461; Mareš, Martin (2004), «Two linear time algorithms for MST on minor closed graph classes» (PDF), Archivum mathematicum, 40 (3): 315–320.
- ↑ 4,0 4,1 Agarwal, P. K.; Edelsbrunner, H.; Schwarzkopf, O.; Welzl, E. (1991), «Euclidean minimum spanning trees and bichromatic closest pairs», Discrete and Computational Geometry, Springer, 6 (1): 407–422, doi:10.1007/BF02574698.
- ↑ Chatterjee, S.; Connor, M.; Kumar, P. (2010,), «Geometric minimum spanning trees with GeoFilterKruskal», in Festa, Paola (ed.), Symposium on Experimental Algorithms, Lecture Notes in Computer Science, vol. 6049, Springer-Verlag, էջեր 486–500, doi:10.1007/978-3-642-13193-6_41
{{citation}}
: CS1 սպաս․ հավելյալ կետադրություն (link). - ↑ Jerzy W. Jaromczyk and Godfried T. Toussaint, "Relative neighborhood graphs and their relatives," Proceedings of the IEEE, Vol. 80, No. 9, September 1992, pp. 1502-1517.
- ↑ Godfried T. Toussaint, "Comment on algorithms for computing relative neighborhood graph," Electronics Letters, Vol. 16, No. 22, October l981, pp. 860-861.
- ↑ Godfried T. Toussaint, "The relative neighborhood graph of a finite planar set," Pattern Recognition, Vol. 12, 1980, pp. 261-268.
- ↑ Robert Pless. Lecture 17: Voronoi Diagrams and Delauney Triangulations. Spring 2003, Computational Geometry Class Page. Associate Professor of Computer Science and Engineering at Washington University. http://www.cs.wustl.edu/~pless/506/l17.html
- ↑ Robert Sedgewick and Kevin Wayne. Minimum Spanning Tree lecture notes. Computer Science 226: Algorithms & Data Structures, Spring 2007. Princeton University. http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/19MST.pdf
- ↑ Eades, Peter; Whitesides, Sue (1994), «The realization problem for Euclidean minimum spanning trees is NP-hard», Proc. 10th ACM Symposium on Computational Geometry, էջեր 49–56, doi:10.1145/177424.177507.
- Smith College: The Open Problems Project: Problem 5: Euclidean Minimum Spanning Tree
- Max-Planck-Institut fuer Informatik: Exercise solutions, by Kavitha Telikepalli (Postscript)
- STANN (Michael Connor, Piyush Kumar and Samidh Chatterjee): A C++ library that can compute Euclidean Minimum Spanning Trees in low dimensions