အဲလ်လား၏ အယ်လ်ဂိုရီသံ မြေဇ် ထုတ်လုပ်သူ
ထုတ်ဝေသည်- ၂၀၂၅၊ ဖေဖော်ဝါရီ ၁၆ UTC ၂၀:၃၉:၄၆
ပြီးပြည့်စုံသော ဝင်္ကပါတစ်ခုကို ဖန်တီးရန် Eller ၏ အယ်လဂိုရီသမ်ကို အသုံးပြု၍ ဝင်္ကဘာမီးစက်။ ဤ algorithm သည် လက်ရှိအတန်း (ဝင်္ကပါတစ်ခုလုံးမဟုတ်ပါ) ကို မှတ်ဉာဏ်တွင်သာ ထားရှိရန် လိုအပ်သောကြောင့် စိတ်ဝင်စားစရာကောင်းသောကြောင့် အလွန်အကန့်အသတ်ရှိသော စနစ်များတွင်ပင် အလွန်ကြီးမားသော ဝင်္ကပါများကို ဖန်တီးရန် အသုံးပြုနိုင်သည်။Eller's Algorithm Maze Generator
Eller ၏ အယ်လဂိုရီသမ်သည် အတန်းအလိုက် ချဉ်းကပ်နည်းကို အသုံးပြု၍ ပြီးပြည့်စုံသော ဝင်္ကပါများ (ကွင်းမရှိသော ဝင်္ကပါများနှင့် အမှတ်နှစ်ခုကြားရှိ လမ်းကြောင်းတစ်ခု) ကို ထိရောက်စွာ ထုတ်လုပ်ပေးသည့် ဝင်္ကပါမျိုးဆက် အယ်လဂိုရီသမ်တစ်ခု ဖြစ်သည်။ ၎င်းသည် Kruskal ၏ အယ်လဂိုရီသမ်နှင့် ဆင်တူသော ဝင်္ကပါများကို ထုတ်လုပ်ပေးသည်၊ သို့သော် ဝင်္ကပါတစ်ခုလုံးကို မှတ်ဉာဏ်တွင် သိမ်းဆည်းရန်မလိုအပ်ဘဲ တစ်ကြိမ်လျှင် အတန်းတစ်ခုသာ ဖန်တီးခြင်းဖြင့် ၎င်းသည် ထိုသို့လုပ်ဆောင်သည်။ ၎င်းသည် အလွန်အကန့်အသတ်ရှိသော စနစ်များပေါ်တွင် အလွန်ကြီးမားသော ဝင်္ကပါများကို ဖန်တီးရန်နှင့် လုပ်ထုံးလုပ်နည်းဆိုင်ရာ အကြောင်းအရာများကို ဖန်တီးရန်အတွက် အသုံးဝင်စေသည်။
ပြီးပြည့်စုံသော ဝင်္ကပါသည် ဝင်္ကပါရှိ မည်သည့်မှတ်တိုင်မှ အခြားနေရာသို့ လမ်းကြောင်းတစ်ခု အတိအကျ ရှိသည့် ဝင်္ကပါတစ်ခုဖြစ်သည်။ ဆိုလိုတာက သင် လှည့်ပတ်ပြီး နောက်ကြောင်းပြန်ဖို့ တွန်းအားပေးတဲ့ အသေအဆုံးတွေကို မကြာခဏ ကြုံတွေ့ရပါလိမ့်မယ်။
ဤနေရာတွင် ထုတ်လုပ်လိုက်သော ဝင်္ကပါမြေပုံများတွင် မည်သည့်အစမှအဆုံး အနေအထားများ မပါရှိဘဲ မူရင်းဗားရှင်းပါ၀င်သည်၊ ထို့ကြောင့် ၎င်းတို့ကို သင်ကိုယ်တိုင် ဆုံးဖြတ်နိုင်သည်- ဝင်္ကပါရှိ မည်သည့်အမှတ်မှ အခြားအမှတ်အထိ အဖြေတစ်ခု ရှိလိမ့်မည်။ သင်သည် လှုံ့ဆော်မှုကို လိုချင်ပါက၊ အကြံပြုထားသော အစနှင့် အပြီးသတ် အနေအထားကို ဖွင့်နိုင်သည် - နှစ်ခုကြားမှ ဖြေရှင်းချက်ကိုပင် ကြည့်နိုင်သည်။
Eller's Algorithm အကြောင်း
David Eller မှ Eller's Algorithm ကို မိတ်ဆက်ခဲ့သည်။
အယ်လဂိုရီသမ်သည် ဝင်္ကပါမျိုးဆက်ဆီသို့ ၎င်း၏ ထိရောက်သော အတန်းအလိုက် ချဉ်းကပ်မှုအတွက် မှတ်သားဖွယ်ဖြစ်ပြီး ၎င်းသည် အချိန်နှင့်တပြေးညီ အဆုံးမရှိ ဝင်္ကပါများ သို့မဟုတ် ဝင်္ကပါများကို ထုတ်ပေးရန်အတွက် စံပြဖြစ်သည်။ ၎င်းကို လုပ်ထုံးလုပ်နည်းဆိုင်ရာ အကြောင်းအရာမျိုးဆက်နှင့် ဝင်္ကပါမျိုးဆက်စာပေများတွင် ကိုးကားလေ့ရှိသော်လည်း ၎င်း၏မူရင်းထုတ်ဝေမှုအကြောင်း အသေးစိတ်ကို ကျွန်ုပ်ရှာမတွေ့ပါ။
Maze Generation အတွက် Eller's Algorithm အလုပ်လုပ်ပုံ
Eller ၏ အယ်လဂိုရီသမ်သည် တစ်ကြိမ်လျှင် အတန်းတစ်တန်းကို လုပ်ဆောင်ပြီး ချိတ်ဆက်ထားသောဆဲလ်များကို ထိန်းသိမ်းခြင်းနှင့် ပြုပြင်မွမ်းမံခြင်း။ ၎င်းသည် loops များကိုရှောင်ရှားနေစဉ်ချိတ်ဆက်မှုကိုသေချာစေပြီး၎င်းသည် ဝင်္ကပါအောက်သို့ထိရောက်စွာတိုးချဲ့သည်။
၎င်းကို အနန္တဝင်္ကပါများ ဖန်တီးရန် သီအိုရီအရ အသုံးပြုနိုင်ပြီး၊ သို့သော် ထုတ်လုပ်လိုက်သော ဝင်္ကပါသည် အမှန်တကယ် ဖြေရှင်းနိုင်စေရန် သေချာစေရန်၊ ဝင်္ကပါကို အပြီးသတ်ရန် တစ်ချိန်ချိန်တွင် "နောက်ဆုံးအတန်း" သို့ ပြောင်းရန် လိုအပ်ပါသည်။
အဆင့် 1- ပထမတန်းကို စတင်ပါ။
- အတန်းရှိဆဲလ်တစ်ခုစီကို သီးသန့်သတ်မှတ် ID တစ်ခုသတ်မှတ်ပါ။
အဆင့် 2- ကပ်လျက်ဆဲလ်အချို့ကို အလျားလိုက်ချိတ်ဆက်ပါ။
- တူညီသောအစုံ ID သို့ သတ်မှတ်ခြင်းဖြင့် ကပ်လျက်ဆဲလ်များကို ကျပန်းပေါင်းစည်းပါ။ အလျားလိုက် လမ်းကြောင်းများ ရှိနေကြောင်း သေချာစေပါသည်။
အဆင့် 3- နောက်အတန်းသို့ ဒေါင်လိုက်ချိတ်ဆက်မှုများကို ဖန်တီးပါ။
- အတန်းတွင်ပေါ်လာသည့်အစုံတစ်ခုစီအတွက်၊ အနည်းဆုံးဆဲလ်တစ်ခုသည် အောက်ဘက်သို့ချိတ်ဆက်ရမည် (ချိတ်ဆက်မှုကိုသေချာစေရန်)။
- နောက်အတန်းသို့ချိတ်ဆက်ရန် set တစ်ခုစီမှ တစ်ခု သို့မဟုတ် တစ်ခုထက်ပိုသောဆဲလ်များကို ကျပန်းရွေးချယ်ပါ။
အဆင့် 4- နောက်အတန်းသို့ ရွှေ့ပါ။
- တူညီသော set ID ကို အောက်ဖော်ပြပါ ဆက်စပ်ဆဲလ်များသို့ သတ်မှတ်ပေးခြင်းဖြင့် ဒေါင်လိုက်ချိတ်ဆက်မှုများကို ရှေ့တိုးလုပ်ဆောင်ပါ။
- သတ်မှတ်မထားသော ဆဲလ်များအတွက် သတ်မှတ် ID အသစ်များကို သတ်မှတ်ပါ။
အဆင့် 5- နောက်ဆုံးအတန်းမပြီးမချင်း အဆင့် 2-4 ကို ထပ်လုပ်ပါ။
- အတန်းလိုက် အတန်းလိုက် ဆက်လက်လုပ်ဆောင်ပါ။
အဆင့် 6- နောက်ဆုံးအတန်းကို လုပ်ဆောင်ပါ။
- ကျန်ရှိသော သီးခြားအတွဲများကို ပေါင်းစည်းခြင်းဖြင့် နောက်ဆုံးအတန်းရှိ ဆဲလ်အားလုံးသည် တူညီသောသတ်မှတ်မှုတွင်ဖြစ်ကြောင်း သေချာပါစေ။