Kruskal ၏ Algorithm Maze မီးစက်

Kruskal's algorithm သည် maze ဖန်တီးရန်အတွက် လိုက်လျောညီထွေဖြစ်အောင် ပြုလုပ်နိုင်သော minimum spanning tree algorithm တစ်ခုဖြစ်သည်။ ၎င်းသည် ပြီးပြည့်စုံသော maze များဖန်တီးရာတွင် အထူးထိရောက်မှုရှိသည်။ Kruskal's algorithm ၏ အခြားရွေးချယ်စရာတစ်ခုမှာ Prim's algorithm ဖြစ်ပြီး ၎င်းသည် minimum spanning tree algorithm လည်းဖြစ်သည်၊ သို့သော် ၎င်းတို့သည် တူညီသော maze များကိုထုတ်ပေးပြီး Kruskal's ၏ လည်ပတ်မှုမှာ ပိုမိုမြန်ဆန်သောကြောင့် Prim's ကို အကောင်အထည်ဖော်ရန် ကျွန်ုပ်စိတ်မ၀င်စားပါ။

ပြီးပြည့်စုံသော ဝင်္ကပါသည် ဝင်္ကပါရှိ မည်သည့်မှတ်တိုင်မှ အခြားနေရာသို့ လမ်းကြောင်းတစ်ခု အတိအကျ ရှိသည့် ဝင်္ကပါတစ်ခုဖြစ်သည်။ ဆိုလိုတာက သင် လှည့်ပတ်ပြီး နောက်ကြောင်းပြန်ဖို့ တွန်းအားပေးတဲ့ အသေအဆုံးတွေကို မကြာခဏ ကြုံတွေ့ရပါလိမ့်မယ်။

ဤနေရာတွင် ထုတ်လုပ်လိုက်သော ဝင်္ကပါမြေပုံများတွင် မည်သည့်အစမှအဆုံး အနေအထားများ မပါရှိဘဲ မူရင်းဗားရှင်းပါ၀င်သည်၊ ထို့ကြောင့် ၎င်းတို့ကို သင်ကိုယ်တိုင် ဆုံးဖြတ်နိုင်သည်- ဝင်္ကပါရှိ မည်သည့်အမှတ်မှ အခြားအမှတ်အထိ အဖြေတစ်ခု ရှိလိမ့်မည်။ သင်သည် လှုံ့ဆော်မှုကို လိုချင်ပါက၊ အကြံပြုထားသော အစနှင့် အပြီးသတ် အနေအထားကို ဖွင့်နိုင်သည် - နှစ်ခုကြားမှ ဖြေရှင်းချက်ကိုပင် ကြည့်နိုင်သည်။

Kruskal ရဲ့ Algorithm အကြောင်း

Kruskal ရဲ့ algorithm ကို အမေရိကန် သင်္ချာပညာရှင်၊ စာရင်းအင်းပညာရှင် နဲ့ ကွန်ပျူတာသိပ္ပံပညာရှင် Joseph Bernard Kruskal, Jr. က တီထွင်ခဲ့တာပါ။ သူဟာ ၁၉၅၆ ခုနှစ်မှာ သူ့ရဲ့ "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem" စာတမ်းမှာ algorithm ကို ပထမဆုံးဖော်ပြခဲ့ပါတယ်။

ဤအယ်လဂိုရီသမ်ကို ဂရပ်၏ အနည်းဆုံး spanning tree (MST) ကိုရှာဖွေရန် ဒီဇိုင်းထုတ်ထားပြီး၊ አዲስ ደረጃများကို အနည်းဆုံးဖြစ်နိုင်သော စုစုပေါင်းအနားအလေးချိန်နှင့် ချိတ်ဆက်ထားကြောင်း သေချာစေပါသည်။

Kruskal ရဲ့ Algorithm က Maze Generation အတွက် ဘယ်လိုအလုပ်လုပ်လဲ

အဆင့် ၁: စတင်ပါ

• ပဟေဠိထဲက ဆဲလ်တစ်ခုစီကို သီးခြားအစုံ (ထူးခြားတဲ့ အစိတ်အပိုင်း) အဖြစ် သဘောထားပါ။
• ကပ်လျက်ဆဲလ်များကြားရှိ နံရံအားလုံးကို အလားအလာရှိသော အနားများအဖြစ် စာရင်းပြုစုပါ။

အဆင့် ၂: နံရံများကို စီပါ

• နံရံများကို ရောမွှေပါ သို့မဟုတ် ကျပန်းစီစဉ်ပါ။ ၎င်းကို Kruskal ၏ algorithm အစစ်အမှန်အဖြစ် အကောင်အထည်ဖော်ပါက နံရံများကို ကျပန်းအစီအစဉ်အတိုင်း စီပါ (maze generation သည် အလေးချိန်များ မလိုအပ်သောကြောင့်)။

အဆင့် ၃: လုပ်ငန်းစဉ်နံရံများ

• ရောနှောနေသော နံရံများမှတစ်ဆင့် ထပ်ခါတလဲလဲ လုပ်ဆောင်ပါ။
• နံရံဖြင့် ပိုင်းခြားထားသော ဆဲလ်နှစ်ခုသည် မတူညီသော အစုံများနှင့် သက်ဆိုင်ပါက (ဆိုလိုသည်မှာ ၎င်းတို့သည် ဝင်္ကပါထဲတွင် မချိတ်ဆက်ရသေးပါက)၊ နံရံကို ဖယ်ရှားပြီး အစုံများကို ပေါင်းစည်းပါ။
• သူတို့ဟာ တူညီတဲ့ set မှာ ရှိနေပြီးသားဆိုရင် နံရံကို ကျော်သွားပါ (စက်ဝန်းတွေကို ရှောင်ရှားဖို့)။

အဆင့် ၄: ပြီးစီးသည်အထိ ဆက်လက်လုပ်ဆောင်ပါ

• ဆဲလ်အားလုံး ချိတ်ဆက်သွားသည်အထိ ဤလုပ်ငန်းစဉ်ကို ပြန်လုပ်ပါ၊ ထို့နောက် တစ်ခုတည်းသော spanning tree တစ်ခု ဖြစ်ပေါ်စေသည်။
• အဆုံးတွင်၊ ဆဲလ်တိုင်းသည် ကွင်းဆက်များ သို့မဟုတ် သီးခြားအပိုင်းများမပါဘဲ အခြားဆဲလ်များနှင့် ချိတ်ဆက်ထားသည်။

Kruskal ရဲ့ algorithm က merging set တွေပေါ်မှာ မူတည်နေတာကြောင့် Union-Find algorithm ကို အသုံးပြုပြီး optimize လုပ်နိုင်ပါတယ်။ ဒါက maze generation အတွင်းမှာ ချိတ်ဆက်ထားတဲ့ cell တွေကို ခြေရာခံဖို့ ထိရောက်တဲ့နည်းလမ်းတစ်ခု ပေးစွမ်းပါတယ်။ Union-Find algorithm ရဲ့ ကျွန်တော့်ရဲ့ PHP implementation ကို ဒီမှာ ကြည့်နိုင်ပါတယ်- Link

နောက်ထပ်စာဖတ်ခြင်း။

ဤပို့စ်ကို သင်နှစ်သက်ပါက၊ ဤအကြံပြုချက်များကို သင်လည်း နှစ်သက်နိုင်ပါသည်-

• အဲလ်လား၏ အယ်လ်ဂိုရီသံ မြေဇ် ထုတ်လုပ်သူ
• ဟန်တ် နှင့် ကွယ်လွန် သွားမယ် မြေဇ် ထုတ်လုပ်သူ
• ဝီလ်ဆန်၏ အယ်လ်ဂိုရီသံ မြေဇ် ထုတ်လုပ်သူ