Kruskal ရဲ့ algorithm ကို - တစ်ဦးအကောင်းဆုံးမူဘောင်များဆောက်လုပ်ခြင်း

ဘာလင်ကနေ 19 ရာစုအစောပိုင်း geometer Jakob Steiner ခုနှစ်တွင်သူတို့၏အရှည်အတိုဆုံးခဲ့သောကြောင့်သုံးကျေးရွာများနှင့်ချိတ်ဆက်ရန်မည်သို့တာဝန်ထားကြ၏။ နောက်ပိုင်းတွင်သူသည်ထိုပြဿနာကိုအကျဉ်းချုံး: ကလေယာဉ်ထဲမှာတစ်ဦးပွိုင့်ကိုရှာဖွေရန်လိုအပ်သည်ဎဖို့ကနေအကွာအဝေးသည်အခြားအချက်များနိမ့်ဆုံးရှိကြ၏။ 20 ရာစုမှာတော့ဒီခေါင်းစဉ်အပေါ်လုပ်ကိုင်ဖို့ရောက်နေပါတယ်။ ဒါဟာအနည်းငယ်မှတ်ယူနှင့်သူတို့စပ်ကြားအကွာအဝေးအတိုဆုံးခဲ့ကြောင်းထိုကဲ့သို့သောလမ်းအတွက်သူတို့ကိုချိတ်ဆက်ဖို့ဆုံးဖြတ်ခဲ့ပါတယ်။ ဒါကအားလုံးလေ့လာခဲ့သည့်ပြဿနာကိုအထူးကိစ္စဖြစ်ပါတယ်။

"လောဘ" algorithm ကို

Kruskal ရဲ့ algorithm ကို (လည်း gradient ကိုခေါ်) က "လောဘ" algorithm ကိုရည်ညွှန်းသည်။ သူတို့အား၏အနှစ်သာရ - တစ်ဦးချင်းစီခြေလှမ်းအပေါ်အမြင့်မားဆုံးအနိုင်ရခဲ့။ အစဉ်အမြဲ "လောဘ" algorithms ပြဿနာဖို့အကောင်းဆုံးဖြေရှင်းချက်မပေး။ တိကျသောတာဝန်များကိုသူတို့ရဲ့လျှောက်လွှာအတွက်သူတို့ကအကောင်းဆုံးဖြေရှင်းနည်းပေးသောဖေါ်ပြခြင်းသီအိုရီရှိပါသည်။ ဤသည် matroids ၏သီအိုရီဖြစ်ပါတယ်။ Kruskal ရဲ့ algorithm ကိုထိုကဲ့သို့သောပြဿနာများကိုရည်ညွှန်းသည်။

နိမ့်ဆုံးအသေကောင်ကိုအလေးချိန်ရှာဖွေခြင်း

Viewed algorithm ကိုတစ်ဦးအကောင်းဆုံးဘောင်ရေတွက် constructs ။ အောက်မှာဖော်ပြထားတဲ့အတိုင်းပြုလုပ်၏ပြဿနာဖြစ်ပါတယ်။ ဒန်အပြိုင်အနားနှင့်ကွင်းမပါဘဲဂရပ် undirected နှင့်အနားများ၏အစုကိုအသီးအသီးအစွန်းအီးဖို့အရေအတွက်ကသတ်မှတ်ပေးထားတဲ့အရာ, w အလေးချိန် function ကိုပေးထား - အလေးချိန်နံရိုး - (င) w ။ နံရိုး၏ဗဟုတစ်ခုချင်းစီအစိတ်အပိုင်းအစု၏အလေးချိန်သည်၎င်း၏အနားများ၏အလေးများ၏ပေါင်းလဒ်သည်။ သေးငယ်တဲ့ခန္ဓာကိုယ်အလေးချိန်၏အရိုးစုကိုရှာဖွေရန်လိုအပ်သည်။

ဖေါ်ပြချက်

Kruskal ရဲ့ algorithm ကိုအကျင့်ကိုကျင့်။ ပထမဦးစွာကနဦးဂရပ်၏အားလုံးအစွန်းအလေး၏တက်လျက်ရှိနေသည်ကိုနိုင်ရန်အတွက်စီစဉ်ပေးထားပါသည်။ အစပိုင်းမှာ frame ကိုမဆိုနံရိုးဆံ့ပေမယ့်အားလုံး vertices ပါဝင်သည်ပါဘူး။ တစ်ဦး spanning သစ်တောသောအသေကောင်ကို၏ပြီးသားဆောက်လုပ်ထားတစ်စိတ်တစ်ပိုင်းဖို့ algorithm ကိုရဲ့နောက်ခြေလှမ်းပြီးနောက်, တဦးတည်းအစွန်းကဆက်ပြောသည်ဖြစ်ပါတယ်။ ဒါဟာမတရားဖမ်းဆီးရွေးကောက်တော်မူသည်မဟုတ်။ frame ကိုပိုင်မရပ်အားလုံးသည်အနား, အနီရောင်နဲ့အစိမ်းရောင်ကိုခေါ်နိုင်ပါသည်။ အသီးအသီးအနီအနားထိပ်ဆောက်လုပ်ရေးသစ်တောဆက်သွယ်မှုအောက်မှာအတူတူအစိတ်အပိုင်း, စိမ်းထိပ်၌ရှိကြ၏ - ကွဲပြားခြားနားသော။ သငျသညျအနီရောင်အစွန်းမှ add လျှင်ထိုအကြောင်းကြောင့်, အဲဒီမှာတစ်သံသရာဖြစ်ပြီး, အစိမ်းရောင်ပါလျှင် - ဤခြေလှမ်းပြီးနောက်လက်ခံရရှိအဖြစ်သစ်သားချိတ်ဆက်အစိတ်အပိုင်းများကိုတစ်ခုထက်လျော့နည်းဖြစ်လိမ့်မည်။ ထို့ကြောင့်ရရှိလာတဲ့ဆောက်လုပ်ရေးမျှအနီရောင်အစွန်း add လို့မရဘူး, ဒါပေမယ့်မဆိုအစိမ်းရောင်အစွန်းသစ်တောရဖို့ကဆက်ပြောသည်နိုင်ပါသည်။ ထိုအနိမ့်ဆုံးအလေးချိန်နှင့်အတူအစိမ်းရောင်အစွန်းကထပ်ပြောသည်။ အဆိုပါရလဒ်နိမ့်ဆုံးအလေးချိန်တစ်မူဘောင်ဖြစ်ပါတယ်။

အကောင်အထည်ဖော်မှု

လက်ရှိသစ်တောအက်ဖ်ဖျောညှနျးဒါဟာဆက်သွယ်မှု၏လယ်ပြင်တွင် vertices ၏ set ကိုအပိုင်းသုံးပိုင်း (မိမိတို့၏ပြည်ထောင်စုပုံစံများက F, သူတို့သည် disjoint ရှိပါတယ်) ။ အနီရောင် vertices နှစ်ခုစလုံးအနားမှာသူတို့တဦးတည်းအပိုင်းအစထဲမှာအိပ်ရကြ၏။ အပိုင်း (က x) - တစ်ဦးချင်းစီ vertex များအတွက် x ကိုနာတစ်ဦးသောအဘို့ကိုပြန်လည်ရောက်ရှိပါက x ကိုပိုငျဆိုငျသော function ကို။ Unit (x, y) - x နှင့် y နှင့်အပေါငျးတို့သညျအခွားအစိတ်အပိုင်းများအစိတ်အပိုင်းများကိုပေါင်းစပ်ပါဝင်သည်ဟုအသစ်တစ်ခု partition ကိုတည်ဆောက်မယ့်လုပ်ထုံးလုပ်နည်း။ စို့ဎ - အနားအရေအတွက်။ ဤသူအပေါင်းတို့သည်သဘောတရားများကို Kruskal ရဲ့ algorithm ကိုတွင်ထည့်သွင်းထားပါသည်။ အကောင်အထည်ဖော်ရေး:

1. n-ကြိမ်မြောက်တက်လျက်ရှိနေသည်ကိုအလေးဖို့ 1st ကနေဂရပ်အပေါငျးတို့သအနားစီစဉ်ပါ။ (အာဣမြို့, bi - ဈအထွတ်အစွန်းနံပါတ်) ။

2. ကိုယ့် = 1 ပြုပါဎရန်အဘို့အ။

3. x က: = အပိုင်း (ai) ။

4. y ကို: = အပိုင်း (bi) ။

5. x ကအစွန်းက F နှင့်အတူထည့်သွင်းရန်, မတန်းတူ y ကပြီးတော့ Unit (x, y) မပါလျှင်ကိုယ့်ကိုရေတွက်။

မှန်ကန်မှု

T ကပါစို့ - ၎င်း၏မတရားဘောင် - မူလဂရပ်၏ frame ကို Kruskal algorithm ကိုနဲ့ S ကို အသုံးပြု. တည်ဆောက်ခဲ့သည်။ ကျနော်တို့ (T) ကို w (S) မ w ထက် သာ. ကြီးမြတ်သည်မဟုတ်ကြောင်းကိုသက်သေပြဖို့ရှိသည်။

အယပ် S ကို၏ဗဟု, P ကို - - အယပ်တီ၏ဗဟု S က T ကညီမျှမဟုတ်ပါဘူးလျှင်တစ်ဦးသည် frame နံရိုး et T ကရှိ, အက်စ်အက်စ် et ပိုင်မဟုတ်သံသရာယျြ, က C. ကို C ပိုင်မဆိုအစွန်း es ကနေဖယ်ရှားပစ်ဟုခေါ်သည် M ကကြစို့ အနားနှင့် vertices အတူတူပင်ဖြစ်ပါသည်ဘာဖြစ်လို့လဲဆိုတော့အက်စ်ကျွန်တော်တို့သည်သစ်တစ်ခု frame ကိုရရှိရန်။ ၎င်း၏အလေးချိန်အာဏာ Kruskal algorithm ကိုအတွက် (es) w မရှိတော့ w (et) ကတည်းက, (S) ကို w ထက် သာ. ကြီးမြတ်သည်မဟုတ်။ ဤသည်စစ်ဆင်ရေး (နံရိုးအပေါ်အစားထိုး T က S နဲ့နံရိုး) အဖြစ်ကြာမြင့်စွာတစ်ဦးချင်းစီနောက်ဆက်တွဲလက်ခံရရှိဘောင်၏အလေးချိန် (T) ကို w (S) မ w ထက် သာ. ကြီးမြတ်သည်မဟုတ်ကြောင်းကိုအဓိပ္ပာယ်သက်ရောက်သောယခင်အလေးချိန်ထက် သာ. ကြီးမြတ်သည်မဟုတ်တီခံယူအဖြစ်အကြိမ်ကြိမ်ပါလိမ့်မည်။

Kruskal ရဲ့ algorithm ကို၏အားကောင်း matroids အပေါ် Rado-Edmond ၏ theorem ကနေအောက်ပါအတိုင်း။

လျှောက်လွှာဥပမာ Kruskal algorithm ကို

node များနှင့်အတူဒန်ဂရပ် a, b, c ကို, ဃ, ငနဲ့နံရိုး (က, ခ), (တစ်ဦး, င), (ခ, ဂ), (ခ, င), (ဂ, ဃ), (ဂ, င) , (ဃ, င) ။ အနား၏အလေးစားပွဲနှင့်ကိန်းဂဏန်းမှာပြနေကြသည်။ အစပိုင်းမှာ, ဆောက်လုပ်ရေးသစ်တော F ကိုဂရပ်ဖ်အပေါငျးတို့သ vertices ပါရှိသည်နှင့်မည်သည့်နံရိုးဆံ့မခံပါဘူး။ အလေးချိန်နိမ့်ဆုံးခဲ့ရသည်, ထို vertices တစ်ဦးနှင့် e ကွဲပြားခြားနားသောအစိတ်အပိုင်းများအတွက်ကျွန်းသစ်ဆက်သွယ်မှုက F (နံရိုး (က, င) အစိမ်းရောင်သည်) ဖြစ်ကြောင်း, ထို့နောက်နံရိုး (ဂ, ဃ) ကတည်းက algorithm Kruskal ပထမဦးဆုံးဖြစ်သောကြောင့်, နံရိုး (က, င) add ဂရပ်အနား၏ကအနည်းဆုံးဒီအစွန်းအလေးချိန်, တူညီတဲ့အကြောင်းပြချက်အစွန်း (က, ခ) လောကအတွက်ထို့နောက်အဘို့, F ကိုပိုင်နှင့်စိမ်းလန်းဘူး။ ကအနီရောင်ကြောင့်ဒါပေမဲ့အစွန်း (ခ, င), ပင်သော်လည်းသူနှင့်ကျန်ရှိနေသေးသောအနား၏အနိမ့်ဆုံးအလေးချိန်, လွန်နေသည်: ခနှင့် e ဒေါင်လိုက်ကျနော်တို့က F မှ add လျှင်အစွန်း (ခ, င), ဖွဲ့စည်းသည်, ထိုဖြစ်ပါသည်, သစ်တောဆက်သွယ်မှုက F ၏တူညီသောအစိတ်အပိုင်းပိုင် သံသရာ။ ထို့နောက်အစိမ်းရောင်အစွန်းကဆက်ပြောသည် (ခ, ဂ) အနီရောင်အစွန်း (ဂ, င), ပြီးတော့ဃ, ငလွန်နေသည်။ ထို့ကြောင့်အနားဆင့်ကဲ (က, င), (ဂ, ဃ), (a, b), (ခ, ဂ) ကဆက်ပြောသည်နေကြသည်။ nihera အကောင်းဆုံးဘောင် မှစ. နှင့်မူရင်းဂရပ်ပါဝင်ပါသည်။ ဒါကြောင့်ဤကိစ္စတွင်ထဲမှာတစ်ခု algorithm ကိုလည်ပတ် Kruskal ။ ဥပမာတစ်ခုပြသနေသည်။

အဆိုပါကိန်းဂဏန်းနှစ်ခုချိတ်ဆက်အစိတ်အပိုင်းများပါဝင်သည်သောဂရပ်, ပြသထားတယ်။ အဆိုပါရဲရင့်လိုင်းများအကောင်းဆုံးဘောင်နံရိုး (အစိမ်းရောင်) ကို Kruskal algorithm ကိုသုံးပြီးဆောက်လုပ်ထားဖော်ပြသည်။

အဆိုပါ algorithm ကိုအသုံးပြုခြင်းအားဖြင့်သူ့ကိုအဘို့တည်အနည်းငယ်မျှသာအလေးချိန်တစ်အရိုးစု - ထိပ်ရုပ်ပုံမူရင်းဂရပ်များနှင့်အောက်ခြေပြသထားတယ်။

ယင်းကဆက်ပြောသည်နံရိုး (1.6) ၏ sequence ကို; (0,3), (2,6) သို့မဟုတ် (2,6), (0,3) - အရေးမရှိ၏ (3,4); (0,1), (1,6) သို့မဟုတ် (1,6), (0,1), အစ (5,6) ဂရုမစိုက်။

Kruskal ရဲ့ algorithm ကိုပု gasket ဆက်သွယ်ရေးစီတိုင်းပြည်သစ်အိမ်ရာ estates ဒေသအတွက်လမ်းများအဖြစ်ကအခြားကိစ္စများတွင်ပိုကောင်းအောင်ဥပမာ, လက်တွေ့ကျတဲ့ application ကိုတွေ့။