Kruskal ta algorithm - gina wani mafi kyau duka tsarin

A farkon karni na 19th geometer Jakob Steiner daga Berlin saita aiki na yadda za a haɗa uku kauyuka haka cewa su tsawon kasance mafi guntu. Daga baya, ya takaita matsalar: shi ake bukata don samun maki a wani jirgin saman, da nisa daga shi zuwa n sauran maki sun magangara mafi ƙasƙanci. A cikin karni na 20th, shi ya ci gaba da aiki a kan wannan topic. An yanke shawarar daukar 'yan maki kuma ka haɗa su a cikin irin wannan hanyar da nisa tsakanin su kasance mafi guntu. Wannan duk wata musamman idan akwai matsalar da ake karatu.

"Hadamar" algorithm

Kruskal ta algorithm nufin da "m" algorithm (wanda kuma ake kira dan tudu). Jigon da waɗanda - da mafi nasara a kan kowane mataki. Ba ko da yaushe, "m" Algorithms samar da mafi kyau warware matsalar. Akwai ka'idar, da ya nuna cewa a cikin aikace-aikace zuwa takamaiman ayyuka da suka bayar da ganiya bayani. Wannan ne ka'idar matroids. Kruskal ta algorithm yana nufin irin wannan matsaloli.

Gano wani m gawa nauyi

An sano algorithm gina wani mafi kyau duka frame count. Matsalar shi ne kamar haka. Dan undirected jadawali ba tare da layi daya gefuna da madaukai, da kuma sa na gefuna da aka bai wa nauyi aiki w, wanda sanya da yawan zuwa kowane gefe e - nauyi haƙarƙari - w (e). The nauyi na kowane tsarin cikin tsari na jam'i na hakarkarinsa ne Naira Miliyan Xari da kaya masu nauyi daga sãsanninta. Da ake bukata domin samun kwarangwal na karamin nauyi.

description

Kruskal ta algorithm aiki. Na farko, duk gefuna da farko jadawali ana shirya a hawa domin na kaya masu nauyi. Da farko, da firam ba ya dauke da wani hakarkarinsa amma ya hada da dukan vertices. Bayan na gaba mataki na algorithm da riga gina ɓangare na gawa, wanda shi ne mai taqin gandun daji, daya gefen da aka kara. An ba zaba siddan. All gefuna da jadawali, ba na zuwa da firam, za a iya kira ja da kore. A saman kowane ja gefuna ne a cikin wannan bangaren a karkashin gini gandun daji connectivity, da kuma kore fi - daban-daban. Saboda haka, idan ka ƙara zuwa ja gefe, akwai wani zagayowar, kuma idan kore - kamar yadda samu bayan wannan mataki da itace da alaka aka gyara zasu zama kasa da daya. Saboda haka, sakamakon yi ba zai iya ƙara babu ja gefe, amma wani kore baki za a iya kara samun gandun daji. Kuma in ji wani kore baki tare da m nauyi. A sakamakon haka ne tsarin na m nauyi.

aiwatar

Nuna a fakaice na yanzu gandun daji F. Yana da rababben sa na vertices a fagen connectivity (su jam'iyya siffofin F, kuma su ne disjoint). A duka biyu gefuna da ja vertices da suka karya a yanki daya. Part (x) - da aiki da cewa ga kowane kokuwa x kõma da wani yanki daga sunan, shi ne ke da x. Gama (x, y) - wata hanya da ya gina wani sabon bangare, kunsha na hada sassa na x da kuma y kuma duk sauran sassa. Bari n - yawan gefuna. Duk wadannan matsalolin suna kunshe a Kruskal ta algorithm. aiwatar:

1. Shirya duk gefuna da jadawali daga 1st ga n-th hawa kaya masu nauyi. (Ai, guda biyu - i da koli baki lambar).

2. ga i = 1 zuwa n yi.

3. x: = Part (ai).

4. y: = Part (guda biyu).

5. Idan x ya aikata ba daidai y sa'an nan gama (x, y), to hada da gefen F i lambar.

correctness

Bari T - firam na asali jadawali gina ta amfani da Kruskal algorithm da S - ta sabani firam. Dole mu tabbatar da cewa w (T) ba fi w (S).

Bari M - jam'i na fins S, P - a jam'i na fins T. Idan S ba daidai yake da T, sa'an nan akwai wani firam haƙarƙari et T, ba na zuwa S. S. et adjoin da sake zagayowar, shi ne ake kira C. C cire daga duk wani gefen es, na S. Mun samu wani sabon frame, saboda gefuna da vertices ne guda. Its nauyi ne ba mafi girma daga w (S), tun w (et) ba w (es) a cikin ikon Kruskal algorithm. Wannan aiki (canza T S hakarkarinsa a kan hakarkarinsa) za a maimaita muddin sami T. The nauyi na kowace m samu frame ba mafi girma fiye da na baya nauyi, wanda ya nuna cewa w (T) ba fi w (S).

A robustness na Kruskal ta algorithm haka daga Theorem na Rado-Edmonds a kan matroids.

Aikace-aikace Misalai Kruskal algorithm

Dan jadawali da nodes a, b, c, d, e da karankarman ƙirji (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). The nauyi na gefuna aka nuna a tebur da kuma a cikin adadi. Da farko, yi gandun daji F ƙunshi dukkan vertices na jadawali da kuma ba ya dauke da wani hakarkarinsa. Shikenan lissafin Kruskal farko ƙara haƙarƙari (a, e), tun da nauyi da mafi ƙasƙanci, da vertices wani da e ne a cikin daban-daban aka gyara katako connectivity F (haƙarƙari (a, e) ne kore), sa'an nan haƙarƙari (c, d), saboda cewa a kalla wannan gefe nauyin jadawali gefuna, ba na zuwa F, kuma shi ne kore, sai ga wannan dalilai ƙara baki (a, b). Amma gefen (b, e) da aka wuce, ko da yake ya kuma m nauyin sauran gefuna, domin shi ne ja: da vertices b da kuma e kasance a cikin wannan bangaren na gandun daji connectivity F, cewa shi ne, idan muka ƙara zuwa F gefen (b, e), an kafa sake zagayowar. Sa'an nan kuma kara kore baki (b, c), an shige ja gefe (c, e), sa'an nan d, e. Saboda haka, gefuna suna kara sequentially (a, e), (c, d), (a, b), (b, c). Daga nihera mafi kyau duka firam da kuma kunshi asali jadawali. Saboda haka a wannan harka shi aiki wani algorithm Kruskal. An misali aka nuna.

A adadi ya nuna wani jadawali, wanda kunshi biyu alaka aka gyara. The m Lines nuna mafi kyau duka frame hakarkarinsa (kore) gina ta amfani da Kruskal algorithm.

A saman hoton ya nuna asalin jadawali, da kuma kasa - a kwarangwal na kadan nauyi, gina shi ta hanyar amfani da algorithm.

A jerin kara hakarkarinsa (1.6); (0,3), (2,6) ko (2,6), (0,3) - shi ne ba da muhimmanci; (3,4). (0,1), (1,6) ko (1,6), (0,1), kuma damu (5,6).

Kruskal ta algorithm sami m aikace-aikace, misali, don inganta GASKET sadarwa, hanyoyi, a sababbin gidaje kadarori kwaminonin a kowace kasa, kazalika da a wasu lokuta.