Kruskal ගේ ඇල්ගොරිතමය - ප්රශස්ත රාමුව ඉදිකිරීම

19 වන සියවසේ මුල් geometer Jakob Steiner බර්ලිනයේ දී ඔවුන්ගේ දිග කෙටිම බව එසේ ගම්මාන තුනක් සම්බන්ධ කරන්නේ කෙසේද යන්න කර්තව්යය කළේය. පසුව, ඔහු ප්රශ්නය මෙසේ සාරාංශ කලේ ය: එය තලය තුළ ලක්ෂ්යයක් සොයා ගැනීමට අවශ්ය වේ, එය n ඇති දුර තවත් කරුණු අඩුම විය. 20 වන සියවසේ දී, එය දිගටම මෙම මාතෘකාව මත වැඩ කිරීම. එය කරුණු කිහිපයක් ගත සහ ඒවා අතර ඇති දුර ප්රමාණය කෙටිම බව එවැනි ක්රමයක් ඔවුන් සම්බන්ධ කිරීමට තීරණය කරන ලදී. මේ සියල්ල අධ්යයනය කරනු ලබන මේ ප්රශ්නයේ තවත් විශේෂ අවස්ථාවක් වේ.

"ගිජු" ඇල්ගොරිතමය

Kruskal ගේ ඇල්ගොරිතමය ඇති "කෑදර" ඇල්ගොරිතම (ද ඵලය අනුක්රමික හැඳින්වේ) සඳහන් කරයි. එම සාරය - එක් එක් පියවර මත වැඩිම ජය. සෑම විටම, "කෑදර" ගණිත ක්රමයක් ප්රශ්නය සඳහා හොඳ ම විසඳුම, ලබා නැත. විශේෂිත කාර්යයන් සඳහා අයදුම්පත් ඉදිරිපත් කරන ඔවුන් ප්රශස්ත විසඳුම ද ලබා දෙන බව පෙන්වන සිද්ධාන්තයක් වී ඇත. මෙම matroids න්යාය වේ. Kruskal ගේ ඇල්ගොරිතමය එවැනි ප්රශ්න කිරීමයි.

අවම වශයෙන් යම් තැනෙක්හි බර සොයා

බලපු ඇල්ගොරිතමය ප්රශස්ත රාමුව ගණන් වඩී. එය ප්රශ්නය පහත සඳහන් පරිදි වේ. දාන් සමාන්තර දාර සහ වළළු තොරව ප්රස්තාරය undirected, සහ දාර කුලකයකි සංඛ්යාව එක් එක් අද්දර ඊ පැවරී ඇති, w බර කාර්යය ලබා දෙන - බර ඉල - w (ඉ). ඉළ ඇට වල බහුත්ව එක් එක් උප කුලකයක් බර එහි දාරවල බර එකතුව වෙයි. කුඩා බර ඇටසැකිල්ලක් සොයා ගැනීමට අවශ්ය විය.

විස්තර

Kruskal ගේ ඇල්ගොරිතමය ක්රියා. පළමුව, මූලික ප්රස්තාරය සියලු දාර ද බර ආරෝහණ සඳහා සංවිධානය කරනු ලැබේ. මුලදී, රාමු ඕනෑම ඉළ ඇට අඩංගු නමුත් සියලු vertices ඇතුළත් වන්නේ නැත. දිග්ගැස්සෙමින් වනාන්තර වන සැකැස්මක් තිබීම, මේ වන විටත් ඉදි කොටසක් ඇල්ගොරිතමය ඊළඟ පියවර පසුව, එක් මුල්ලකට එකතු කර තිබේ. එය අත්තනෝමතික ලෙස තෝරා නැත. රාමු අයත් ෙනොවන, ප්රස්තාරය සියලු දාර, රතු සහ කොළ ද හැඳින්විය හැක. එක් එක් රතු දාර ඉහළ ඉදිකිරීම් වනාන්තර සම්බන්ධතා යටතේ එම සංරචකය, හා හරිත මුදුන් වේ - වඩා වෙනස්. ඒ නිසා, ඔබ රතු අද්දර එකතු නම්, එක් චක්රයක් වන අතර, සහ කොළ පැහැති නම් - මෙම පියවර පසුව ලැබෙන ලෙස ලී සම්බන්ධ සංරචක වඩා අඩු වනු ඇත. මේ අනුව, එහි ප්රතිඵලයක් ඉදිකිරීම් කිසිදු රතු අද්දර එක් කළ නොහැක, නමුත් ඕනෑම හරිත අද්දර වනාන්තරය ලබා ගැනීමට එකතු කළ හැක. හා අවම බර හරිත අද්දර පවසයි. ප්රතිඵලය අවම බර රාමුව යි.

ක්රියාත්මක කිරීම

වත්මන් වන එෆ් දැක්වීමට එය සම්බන්ධතා ක්ෂේත්රයේ vertices කුලකයකි බෙදී (ඔවුන්ගේ වෘත්තීය සමිති ආකෘති එෆ්, ඔවුන් disjoint වේ). රතු vertices දාර දෙකේදීම ඔවුන් එක එක කෑල්ලක් තැන්පත් කර ඇත. කොටසක් (x) - එක් එක් ශීර්ෂයක් සඳහා x නම කොටසක් නැවත, එය x අයත් කාර්යය. ජනමාධ්ය කලාවක් (x, y) - x හා y සහ අනෙකුත් සියලුම කොටස් කොටස් ඒකාබද්ධ සමන්විත, නව කොටසක්, ඇල්ම, බව පරිපාටිය. ඉඩ n - දාර සංඛ්යාව. මේ සියලු සංකල්ප Kruskal ගේ ඇල්ගොරිතමය ඇතුළත් වේ. ක්රියාත්මක කිරීම:

1. ප්රස්තාරය සියලු දාර 1 දා සිට n-වැනි ආරෝහණ බර, කිරීමට සැලසුම් කරන්න. (ආයි, ද්වි - i මුඳුන් අද්දර අංකය සමග).

2. i = 1 කරන්න n සඳහා.

3. x: = කොටස (ai).

4. y: = කොටස (ද්වි).

5. x අද්දර එෆ් සමග ඇතුළත් කිරීමට, සමාන y නම් එක්සත් කළ නොහැකි (x, y) කරන්නේ නම් මම ගණන්.

නිවැරදි භාවය

ටී කරමු - එහි අත්තනෝමතික රාමුව - මුල් වගුවේ රාමුව Kruskal ඇල්ගොරිතමය හා S ඉදිකර. අපි w (T) w (S) ට වැඩි නොවන බව ඔප්පු කිරීමට ඇත.

වරල් එස් බහුත්වයක්, P, - - වරල් ටී බහුත්වයක් එස් ටී සමාන නොවේ නම්, එවිට රාමුව ඉල et ටී පවතී, එස් එස් et අයත් ෙනොවන, චක්රය adjoin, එය සී සී අයත්, ඕනෑම නවීන es ඉවත් හැඳින්වේ එම් ඉඩ එස් අපි, නව රාමුව ලබා දාර සහ vertices එම නිසා. එහි බර නොවන w (S) ට වැඩි, w (et) සිට තවදුරටත් බලය Kruskal ඇල්ගොරිතමය දී (ලිපින) w වේ. මෙම මෙහෙයුම (ඉළ ඇට මත ආදේශකයක් ටී එස් ඉළ ඇට) එක් එක් අනුයාත ලැබී රාමුව බර පෙර w (T) w (S) ට වැඩි නොවන බව එයින් ගම්ය වන බර, වඩා උතුමි නොවේ ටී ලබා තාක් කල් නැවත නැවතත් කරනු ඇත.

Kruskal ගේ ඇල්ගොරිතමය සවිමත්භාවය matroids මත Rado-එඩ්මන්ඩ්ස් වන ප්රමේයය සිට පහත සඳහන්.

අයදුම් උදාහරණ Kruskal ඇල්ගොරිතමය

ශීර්ෂයන් සමඟ දාන් ප්රස්තාරය A, B, C, D, E සහ ඉළ ඇට (A, B), (අ, ඉ), (ආ, ඇ), (ආ, ඉ), (ඇ, ඈ), (ඇ, ඉ) , (ඈ, ඉ). දාරවල බර මේසය හා එම සංඛ්යාව පෙන්වා ඇත. මුලින්, ඉදිකිරීම් වනාන්තර එෆ් ප්රස්තාරය සියලු vertices අඩංගු ඕනෑම ඉළ ඇට අඩංගු නොවේ. ඇල්ගොරිතමය Kruskal පළමු ඉල (අ, ඉ), බර අඩුම විය, සහ vertices ඒ හා ඊ වෙනස් සංරචක දැව සම්බන්ධතා F (ඉල (අ, ඉ) හරිත මිල) වන අතර, ඉන්පසු ඉල (c, d) සිට, නිසා එකතු කරන්න ප්රස්තාරය දාර බව අවම වශයෙන් මෙම නවීන බර, F, අයත්, සහ එය කොළ, එම හේතු අද්දර (අ, ආ) අනාගතයේදී අත්විඳින්නට නම් නොවේ. නමුත් අද්දර (ආ, ඉ) එය රතු පැහැය ගන්නා නිසා වුවත් ඔහු සහ ඉතිරි දාර අවම බර, සම්මත: ආ හා ඊ ද vertices, එනම්, වනාන්තර සම්බන්ධතා එෆ් එකම අංගයක් අයත් අපි එෆ් එකතු නම් අද්දර (ආ, ඉ), පිහිටුවා ඇත චක්රය. එවිට කොළ අද්දර එකතු (ආ, ඇ), රතු අද්දර (ඇ, ඉ), පසුව ඈ, ඊ සම්මත කර ඇත. මේ අනුව, දාර අනුපිලිවෙලට (අ, ඉ), (ඇ, ඈ), (අ, ආ), (ආ, ඇ) එකතු කර ඇත. nihera ප්රශස්ත රාමුව හා මුල් ප්රස්තාරය කින් සමන්විත වේ. ඒ නිසා මේ අවස්ථාවේ දී එය ඇල්ගොරිතමය ක්රියාත්මක Kruskal. උදාහරණයක් පෙන්වා ඇත.

එම සංඛ්යාව සම්බන්ධ සංරචක දෙකකින් සමන්විත ප්රස්ථාරයක්, පෙන්නුම් කරයි. නිර්භීත රේඛා ප්රශස්ත රාමුව ඉළ ඇට (කොළ) එම Kruskal ඇල්ගොරිතමය ඉදිකර බවයි.

මෙම ඇල්ගොරිතමය භාවිතා ඔහු වෙනුවෙන් ඉදි අවම බර ඇටසැකිල්ලක්, - ඉහළ ඡායාරූපයේ මුල් ප්රස්තාරය, සහ පහළ පෙන්වයි.

එකතු ඉළ ඇට (1.6) අනුක්රමය, (0,3), (2,6) හෝ (2,6), (0,3) - වැදගත් නැත; (3,4); (0,1), (1,6) හෝ (1,6), (0,1), ද (5.6) සැලකිල්ලක්.

Kruskal ගේ ඇල්ගොරිතමය එම හිමිකරුවන්ට අසමසම ප්රතිලාභ රැසක්ම හිමිකර දෙන්නක්වන සන්නිවේදනය, එක් එක් රට තුළ නව නිවාස වතු ප්රදේශවල මාර්ග, මෙන්ම වෙනත් අවස්ථාවලදී උපරිම ඵල ලබා ගැනීම සඳහා, උදාහරණයක් ලෙස, ප්රායෝගික භාවිතය ගනු ලැබේ.