Algorithm Kruskal - y fframwaith gorau posibl adeiladu

Yn y geometer dechrau'r 19eg ganrif a osodwyd Jakob Steiner o Berlin dasg o sut i gysylltu tri phentref fel bod eu hyd yn y byrraf. Yn ddiweddarach, roedd yn crynhoi y broblem: mae'n ofynnol iddo ddod o hyd i bwynt mewn awyren, y pellter oddi wrthi i n pwyntiau eraill oedd yr isaf. Yn yr 20fed ganrif, mae'n parhau i weithio ar y pwnc hwn. Penderfynwyd cymryd ychydig o bwyntiau ac yn eu cysylltu yn y fath fodd fel bod y pellter rhyngddynt oedd y byrraf. Mae hyn i gyd yn achos arbennig o'r broblem sy'n cael ei astudio.

"Barus" algorithm

algorithm Kruskal yn cyfeirio at y "barus" algorithm (a elwir hefyd raddiant). Hanfod hynny - y fuddugoliaeth uchaf ar bob cam. Nid bob amser, "barus" algorithmau darparu'r ateb gorau i'r broblem. Mae damcaniaeth, gan ddangos bod wrth eu cymhwyso i dasgau penodol eu bod yn rhoi'r ateb gorau. Mae hyn yn y theori matroids. algorithm Kruskal yn cyfeirio at broblemau o'r fath.

Dod o hyd i bwysau carcas lleiafswm

algorithm poblogaidd yn llunio cyfrif ffrâm optimaidd. Y broblem ohono fel a ganlyn. undirected Dan graff heb ymylon paralel a dolenni, ac mae'r set o ymylon yn cael y swyddogaeth pwysau w, a oedd yn aseinio'r rhif i bob ymyl e - asen pwysau - w (d). Mae pwysau'r pob is-set o'r lluosogrwydd o asennau yw cyfanswm y pwysau ei ymylon. Ofynnol i ddod o hyd i'r sgerbwd o bwysau bach.

disgrifiad

algorithm Kruskal yn gweithio. Yn gyntaf, yr holl ymylon y graff cyntaf yn cael eu trefnu yn nhrefn y pwysau esgynnol. I ddechrau, nid y ffrâm yn cynnwys unrhyw asennau ond mae'n cynnwys yr holl fertigau. Ar ôl y cam nesaf y algorithm i ran adeiladwyd eisoes o'r carcas, sydd yn ymestyn dros goedwig, un ymyl yn cael ei ychwanegu. Nid yw'n cael ei ddewis yn fympwyol. Mae'r holl ymylon y graff, nad ydynt yn perthyn i'r ffrâm, yn gallu cael eu galw coch a gwyrdd. Ben pob ymylon coch yn yr un gydran dan cysylltedd coedwig adeiladu, ac mae'r topiau gwyrdd - yn wahanol. Felly, os ydych yn ychwanegu at yr ymyl goch, mae cylch, ac os bydd y gwyrdd - fel a dderbynnir ar ôl y cam hwn, bydd y cydrannau pren cysylltiedig fod yn llai nag un. Felly, ni all y gwaith adeiladu sy'n deillio ychwanegwch unrhyw ymyl coch, ond gall unrhyw ymyl gwyrdd yn cael eu hychwanegu i gael y goedwig. Ac yn ychwanegu ymyl werdd gyda lleiafswm pwysau. Y canlyniad yw fframwaith o leiaf pwysau.

gweithredu

Ddynodi'r goedwig bresennol F. Mae'n rhannu'r set o fertigau ym maes cysylltedd (eu ffurflenni undeb F, ac maent yn disjoint). Yn y ddau ymylon y fertigau coch maent yn gorwedd mewn un darn. Mae rhan (x) - swyddogaeth sydd ar gyfer pob fertig x yn dychwelyd cyfran o'r enw, mae'n perthyn x. Unite (x, y) - gweithdrefn sy'n adeiladu rhaniad newydd, sy'n cynnwys cyfuno rhannau o x ac y a'r holl rannau eraill. Gadewch n - nifer yr ymylon. Mae'r holl cysyniadau hyn yn cael eu cynnwys yn y algorithm Kruskal yn. Gweithredu:

1. Trefnu holl ymylon y graff o 1 i pwysau esgynnol n-th. (Ai, bi - i gyda rhif ymyl apig).

2. i fi = 1 i n ei wneud.

3. x: = Rhan (ai).

4. y: = Rhan (bi).

5. Os nad yw x yn y gyfartal, yna Unite (x, y), i gynnwys gyda'r rhif ymyl F i.

cywirdeb

Gadewch T - ffrâm y graff gwreiddiol a adeiladwyd gan ddefnyddio'r algorithm Kruskal a S - ei ffrâm mympwyol. Mae'n rhaid i ni brofi bod w (T) yn peidio fwy na w (S).

Gadewch M - lluosogrwydd esgyll S, P - lluosogrwydd o esgyll Nid T. Os S yn hafal i T, yna mae et rib ffrâm T, nad ydynt yn perthyn i S. S. et ffinio y cylch, fe'i gelwir C. C dynnu o unrhyw es ymyl, perthyn S. Rydym yn cael ffrâm newydd, oherwydd yr ymylon a fertigau yr un fath. Ei bwysau ddim yn fwy na w (S), gan fod w (et) mwyach w (au) mewn grym Kruskal algorithm. Bydd y llawdriniaeth (dirprwy T S asennau ar asennau) yn cael ei ailadrodd ar yr amod derbyn T. Mae pwysau'r pob ffrâm a dderbynnir wedi hynny ddim yn fwy na'r pwysau blaenorol, sy'n awgrymu bod w (T) yn peidio fwy na w (S).

Cadernid algorithm Kruskal yn dilyn o'r theorem o Rado-Edmonds ar matroids.

Enghreifftiau Cais Kruskal algorithm

Dan graff gyda nodau a, b, c, d, e ac asennau (a, b), (a, e), (b, c), (b, d), (c, d), (c, d) , (d, e). Mae pwysau o ymylon yn cael eu dangos yn y tabl ac yn y ffigur. I ddechrau, coedwig adeiladu F yn cynnwys yr holl fertigau y graff ac nid yw'n cynnwys unrhyw asennau. Algorithm Kruskal ychwanegu gyntaf asen (a, e), gan fod y pwysau oedd â'r isaf, a'r fertigau yn ac e mewn gwahanol gydrannau cysylltedd pren F (asen (a, e) yn wyrdd), yna bydd y asen (c, d), gan fod bod o leiaf y pwysau ymyl ymylon graff, nad ydynt yn perthyn i F, ac mae'n wyrdd, ac yna am yr un rhesymau yn cronni ymyl (a, b). Ond yr ymyl (b, d) yn cael ei basio, er ei fod a'r pwysau isafswm o ymylon sy'n weddill, oherwydd ei fod yn goch: y fertigau b ac e yn perthyn i'r un gydran o gysylltedd coedwig F, hynny yw, os ydym yn ychwanegu at F ymyl (b, d), yn cael ei ffurfio beicio. Yna ychwanegodd ymyl gwyrdd (b, c) ymyl goch, yn cael ei basio (c, d), ac yna d, e. ddilyniannol Felly, ymylon yn cael eu hychwanegu (a, e), (c, ch), (a, b), (b, c). O nihera ffrâm gorau posibl ac mae'n cynnwys y graff gwreiddiol. Felly, yn yr achos hwn mae'n gweithredu algorithm Kruskal. Mae enghraifft i'w gweld.

Mae'r ffigur yn dangos graff, sy'n cynnwys dwy elfen gysylltiedig. Mae'r llinellau beiddgar yn dangos y asennau ffrâm optimaidd (gwyrdd) a adeiladwyd gan ddefnyddio algorithm Kruskal.

Mae'r llun uchaf yn dangos y graff gwreiddiol, a gwaelod - sgerbwd o ychydig iawn o bwysau, a adeiladwyd ar ei gyfer drwy ddefnyddio'r algorithm.

Mae'r dilyniant o asennau ychwanegwyd (1.6); (0,3), (2,6) neu (2,6), (0,3) - nid yn bwysig; (3,4); (0,1), (1,6) neu (1,6), (0,1), hefyd yn gofalu (5,6).

algorithm Kruskal yn canfod defnydd ymarferol, er enghraifft, i wneud y gorau y cyfathrebu gasged, ffyrdd mewn ardaloedd stadau tai newydd ym mhob gwlad, yn ogystal ag mewn achosion eraill.