Algorithm Kruskal-së - ndërtimi i një kornize optimale

Në fillim të shekullit të 19 gjeometër Jakob Steiner nga Berlini vendosur detyrën e se si të lidhë tri fshatra në mënyrë që gjatësia e tyre ishte më e shkurtër. Më vonë, ai përmbledhur problemin: është e nevojshme për të gjetur një pikë në një avion, distanca prej tij n pikat e tjera ishin më të ulët. Në shekullin e 20, ajo vazhdon të punojë në këtë temë. Ai ishte vendosur për të marrë një pikë pak dhe të lidhur ato në një mënyrë të tillë që distanca në mes tyre ishte më e shkurtër. E gjithë kjo është një rast i veçantë i problemit që po studiohet.

"Babëzitur" algorithm

algorithm Kruskal i referohet algorithm "babëzitur" (i quajtur edhe gradient). Thelbi i atyre - të fitojë më i lartë në çdo hap. Jo gjithmonë "babëzitur" algoritme të ofrojë zgjidhjen më të mirë për problemin. Nuk është një teori, që tregon se në zbatimin e tyre në detyra të veçanta që japin zgjidhje optimale. Kjo është teoria e matroids. algorithm Kruskal i referohet problemeve të tilla.

Gjetja e një peshë minimale kufomën

algorithm shihet ndërton një akuzë optimale kornizë. Problemi i saj është si më poshtë. Dan undirected graf pa tehe paralele dhe unazore, dhe grupi i skajeve jepet funksionin peshe W, që cakton numrin secilit buzë e - brinjë peshë - w (e). Pesha e çdo mesin e morise se brinjët është shuma e peshave të skajet e saj. Nevojshme për të gjetur skeletin e një peshë të vogël.

përshkrim

algorithm Kruskal punon. Së pari, të gjitha skajet e grafikut fillestar janë të rregulluar në rend të peshave ngjitje. Fillimisht, korniza nuk përmban asnjë brinjë, por përfshin të gjitha vertices. Pas hapin e ardhshëm të algorithm në pjesën e ndërtuar tashmë e trupave të pajetë, e cila është një pyll që përfshin, një avantazh është shtuar. Ajo nuk është zgjedhur në mënyrë arbitrare. Të gjitha skajet e grafikut, nuk i përkasin kuadër, mund të quhet e kuqe dhe jeshile. Krye të çdo edges kuqe janë në të njëjtën komponentin bazë të lidhjes pyjeve të ndërtimit, dhe në krye të gjelbër - të ndryshme. Prandaj, në qoftë se ju të shtoni në buzë të kuqe, ka një cikël, dhe nëse e gjelbër - si e pranuara pas këtij hapi të drurit lidhur komponentët do të jetë më pak se një. Kështu, duke rezultuar ndërtimi nuk mund të shtoni ndonjë buzë të kuqe, por çdo buzë të gjelbër mund të shtohet për të marrë pyll. Dhe shton një avantazh të gjelbër me peshë minimale. Rezultati është një kornizë e peshës minimale.

zbatim

Treguar pyllin e tanishme F. Ajo ndan sërë vertices në fushën e lidhjes (format e tyre të sindikatave F, dhe ata janë të veçoj). Në të dy skajet e vertices kuqe ato qëndrojnë në një copë. Pjesë (x) - funksioni që për çdo kulm x kthen një pjesë të emrit, ajo i takon x. Unite (x, y) - një procedurë që ndërton një ndarje të re, e përbërë nga kombinuar pjesë të X dhe Y dhe të gjitha pjesët e tjera. Le n - numri i edges. Të gjitha këto koncepte janë të përfshira në algorithm Kruskal-së. zbatimi:

1. Organizoni të gjitha skajet e grafikut nga 1 deri n-th pesha ngjitje. (Ai, bi - i me numër kulmi buzë).

2. për i = 1 deri n bëjë.

3. x: = Pjesa (AI).

4. y: = Pjesa (bi).

5. Nëse x nuk ka y barabartë pastaj Unite (x, y), për të përfshirë me numrin buzë F i.

korrektësi

Le T - frame i grafik fillestar ndërtuar duke përdorur algoritmin Kruskal dhe S - kornizë saj arbitrare. Ne duhet të provojë se w (T) nuk është më i madh se w (S).

Le M - shumësi e fins S, P - një shumicë e fins T. Nëse S nuk është e barabartë me T, atëherë ka një et kornizë brinjë T, nuk i përkasin S. S. et prek cikli, ajo është quajtur C. C hequr nga çdo buzë es, i përkasin S. Ne të marrë një kornizë të re, për shkak se edges dhe vertices është i njëjtë. pesha e saj nuk është më i madh se w (S), pasi W (et) nuk w (es) në një fuqi Kruskal algoritmi. Ky operacion (zëvendësues T S brinjë në brinjë) do të përsëritet deri sa të marrin T. peshën e çdo kuadër të mëvonshëm marra nuk është më i madh se pesha e mëparshme, që nënkupton se w (T) nuk është më i madh se w (S).

Fuqinë e algorithm Kruskal ndjek nga teorema e Rado-Edmonds në matroids.

Shembujt e aplikimit Kruskal algorithm

grafik Dan me nyje a, b, c, d, e dhe brinjët (a, b), (A, E), (b, c), (b, e), (c, d), (c, d) (d, e). Peshat e edges janë paraqitur në tabelën dhe në figurë. Fillimisht, pyll ndërtimi F përmban të gjitha vertices e grafik dhe nuk përmban asnjë brinjë. Algoritmi Kruskal pari shtoni brinjë (a, e), pasi pesha kishte më të ulët, dhe vertices A dhe E janë në komponente të ndryshme të lidhjes drurit F (brinjë (a, e) është i gjelbër), pastaj me brinjën (c, d), për shkak se se të paktën kjo peshë buzë të skajeve grafik, nuk i përkasin F, dhe kjo është e gjelbër, atëherë për të njëjtat arsye të rritet buzë (a, b). Por buzë (b, d) është e kaluar, edhe pse ai dhe pesha minimale e skajeve mbetura, sepse ajo është e kuqe: vertices b dhe d përkasin të njëjtës komponent i lidhjes pyjeve F, që është, në qoftë se ne shtoni në F buzë (b, e), është formuar cikli. Pastaj shtoi buzë të gjelbër (b, c), është kaluar buzë të kuqe (C, E), dhe pastaj d, e. Kështu, skajet janë shtuar në mënyrë të njëpasnjëshme (a, d), (c, d), (a, b), (b, c). Nga nihera kornizë optimale dhe përbëhet nga grafiku origjinale. Pra, në këtë rast vepron një algoritëm Kruskal. Një shembull është treguar.

Shifra tregon një grafik, i cili përbëhet nga dy komponente të lidhur. Linjat e guximshme tregojnë brinjë optimale kornizë (green) të ndërtuara duke përdorur algoritmin Kruskal.

Foto e lartë tregon grafik origjinale, dhe në fund - një skelet të peshës minimale, e ndërtuar për të duke përdorur algoritmin.

Sekuenca e brinjëve të shtuara (1.6); (0,3), (2,6) ose (2,6), (0,3) - nuk është i rëndësishëm; (3,4); (0,1), (1,6) ose (1,6), (0,1), gjithashtu kujdes (5,6).

algorithm Kruskal gjen aplikim praktik, për shembull, për të optimizuar komunikimit copë litari, rrugët në Nju lokalitetet pronave të banimit në çdo vend, si dhe në raste të tjera.