Kruskal ၏ Algorithm Maze မီးစက်
ထုတ်ဝေသည်- ၂၀၂၅၊ ဖေဖော်ဝါရီ ၁၆ UTC ၁၈:၁၀:၀၅
ပြီးပြည့်စုံသော ဝင်္ကဘာတစ်ခုကို ဖန်တီးရန် Kruskal ၏ အယ်လဂိုရီသမ်ကို အသုံးပြု၍ ဝင်္ကဘာမီးစက်။ ဤ algorithm သည် အလယ်အလတ် အရှည်ရှိသော စင်္ကြံများ နှင့် အသေစွန်းများ နှင့် ဝင်္ကပါများကို ဖန်တီးလေ့ ရှိပြီး ဖြောင့်မှန်သော ဖြေရှင်းချက် ဖြစ်သည်။Kruskal's Algorithm Maze Generator
Kruskal ၏ အယ်လဂိုရီသမ်သည် ဝင်္ကပါမျိုးဆက်အတွက် လိုက်လျောညီထွေဖြစ်စေနိုင်သော အနည်းဆုံး spanning tree algorithm တစ်ခုဖြစ်သည်။ ပြီးပြည့်စုံသော ဝင်္ကပါများကို ဖန်တီးရန်အတွက် အထူးထိရောက်သည်။ Kruskal ၏ အယ်လဂိုရီသမ်အတွက် အခြားရွေးချယ်စရာတစ်ခုမှာ Prim ၏ အယ်လဂိုရီသမ်ဖြစ်ပြီး အနိမ့်ဆုံး spanning tree algorithm လည်းဖြစ်သည်၊ သို့သော် ၎င်းတို့သည် ထပ်တူထပ်မျှသော ဝင်္ကပါများကို ဖန်တီးပေးပြီး Kruskal ၏ လည်ပတ်မှု ပိုမိုမြန်ဆန်သောကြောင့်၊ Prim's ကို အကောင်အထည်ဖော်ရန် ကျွန်ုပ်စိတ်မ၀င်စားပါ။
ပြီးပြည့်စုံသော ဝင်္ကပါသည် ဝင်္ကပါရှိ မည်သည့်မှတ်တိုင်မှ အခြားနေရာသို့ လမ်းကြောင်းတစ်ခု အတိအကျ ရှိသည့် ဝင်္ကပါတစ်ခုဖြစ်သည်။ ဆိုလိုတာက သင် လှည့်ပတ်ပြီး နောက်ကြောင်းပြန်ဖို့ တွန်းအားပေးတဲ့ အသေအဆုံးတွေကို မကြာခဏ ကြုံတွေ့ရပါလိမ့်မယ်။
ဤနေရာတွင် ထုတ်လုပ်လိုက်သော ဝင်္ကပါမြေပုံများတွင် မည်သည့်အစမှအဆုံး အနေအထားများ မပါရှိဘဲ မူရင်းဗားရှင်းပါ၀င်သည်၊ ထို့ကြောင့် ၎င်းတို့ကို သင်ကိုယ်တိုင် ဆုံးဖြတ်နိုင်သည်- ဝင်္ကပါရှိ မည်သည့်အမှတ်မှ အခြားအမှတ်အထိ အဖြေတစ်ခု ရှိလိမ့်မည်။ သင်သည် လှုံ့ဆော်မှုကို လိုချင်ပါက၊ အကြံပြုထားသော အစနှင့် အပြီးသတ် အနေအထားကို ဖွင့်နိုင်သည် - နှစ်ခုကြားမှ ဖြေရှင်းချက်ကိုပင် ကြည့်နိုင်သည်။
Kruskal ၏ Algorithm အကြောင်း
Kruskal ၏ အယ်လဂိုရီသမ်ကို အမေရိကန်သင်္ချာပညာရှင်၊ စာရင်းအင်းပညာရှင်နှင့် ကွန်ပျူတာပညာရှင် Joseph Bernard Kruskal ဂျူနီယာက ဖန်တီးခဲ့သည်။ 1956 ခုနှစ်တွင် သူသည် သူ၏ algorithm ကို "ဂရပ်ဖ်၏ အတိုဆုံးသော အပိုင်းခွဲသစ်တစ်ခုနှင့် ခရီးသွား အရောင်းသမား ပြဿနာ" တွင် ပထမဆုံး ဖော်ပြခဲ့သည်။
algorithm သည် ဂရပ်တစ်ခု၏ အနိမ့်ဆုံး spanning tree (MST) ကို ရှာရန် ဒီဇိုင်းထုတ်ထားပြီး၊ ထောင့်များအားလုံးကို ဖြစ်နိုင်ချေရှိသော စုစုပေါင်းအစွန်းအလေးချိန်နှင့် ချိတ်ဆက်ထားကြောင်း သေချာစေရန် ဒီဇိုင်းထုတ်ထားသည်။
Kruskal ၏ Algorithm သည် Maze Generation အတွက် မည်သို့အလုပ်လုပ်သည်
အဆင့် 1: စတင်လိုက်ပါ။
- ဝင်္ကပါရှိ ဆဲလ်တစ်ခုစီကို သီးခြားအစုတစ်ခု (ထူးခြားသောအစိတ်အပိုင်းတစ်ခု) အဖြစ် ဆက်ဆံပါ။
- ကပ်လျက်ဆဲလ်များကြားရှိ နံရံအားလုံးကို ဖြစ်နိုင်ချေရှိသော အစွန်းများအဖြစ် စာရင်းပြုစုပါ။
အဆင့် 2- နံရံများကိုစီပါ။
- နံရံများကို မွှေနှောက်ခြင်း သို့မဟုတ် ကျပန်းအမိန့်ပေးခြင်း။ ၎င်းကို စစ်မှန်သော Kruskal ၏ အယ်လဂိုရီသမ်တစ်ခုအဖြစ် အကောင်အထည်ဖော်ပါက၊ နံရံများကို ကျပန်းအစီအစဥ် စီပါ (ဝင်္ကပါမျိုးဆက်ဖြစ်သောကြောင့် အလေးများမလိုအပ်ပါ)။
အဆင့် 3- နံရံများကို လုပ်ဆောင်ပါ။
- ပြိုကျနေသော နံရံများကို ဖြတ်၍ ထပ်လောင်းပါ။
- နံရံဖြင့် ပိုင်းခြားထားသော ဆဲလ်နှစ်ခုသည် မတူညီသောအစုံများ (ဆိုလိုသည်မှာ ၎င်းတို့သည် ဝင်္ကပါတွင် မချိတ်ဆက်ရသေးပါက) နံရံကိုဖယ်ရှားပြီး အစုံများကို ပေါင်းစည်းပါ။
- ၎င်းတို့သည် တူညီသောအတွဲတွင် ရှိနေပါက၊ နံရံကို ကျော်သွားပါ (သံသရာကိုရှောင်ရန်)။
အဆင့် 4- ပြီးစီးသည်အထိ ဆက်လက်လုပ်ဆောင်ပါ။
- ဆဲလ်များအားလုံးကို ချိတ်ဆက်ပြီး အရှည်လိုက် သစ်ပင်တစ်ပင်အဖြစ် ဖြစ်ပေါ်လာသည်အထိ ဤလုပ်ငန်းစဉ်ကို ပြန်လုပ်ပါ။
- အဆုံးတွင်၊ ဆဲလ်တိုင်းသည် အကွက်များ သို့မဟုတ် သီးခြားအပိုင်းများမပါဘဲ အခြားဆဲလ်များနှင့် ချိတ်ဆက်ထားသည်။
Kruskal ၏ အယ်လဂိုရီသမ်သည် ပေါင်းစည်းထားသောအစုံများပေါ်တွင် မှီခိုနေသောကြောင့်၊ ဝင်္ကဘာမျိုးဆက်အတွင်း ချိတ်ဆက်ထားသောဆဲလ်များကို ထိရောက်စွာခြေရာခံရန် ထိရောက်သောနည်းလမ်းကို ပံ့ပိုးပေးသည့် Union-Find algorithm ကိုအသုံးပြုခြင်းဖြင့် ၎င်းကို အကောင်းဆုံးဖြစ်အောင်ပြုလုပ်နိုင်သည်။ Union-Find algorithm ကို ကျွန်ုပ်၏ PHP အကောင်အထည်ဖော်မှုကို ဤနေရာတွင် ကြည့်နိုင်သည်- PHP တွင် Disjoint Set (Union-Find Algorithm)