Recursive Backtracker Maze မီးစက်

recursive backtracker algorithm ဟာ အမှန်တကယ်တော့ depth-first search တစ်ခုဖြစ်ပါတယ်။ maze generation အတွက်အသုံးပြုတဲ့အခါ လမ်းကြောင်းကို ကျပန်းရွေးချယ်ဖို့ အနည်းငယ်ပြုပြင်မွမ်းမံထားပါတယ်၊ အမှန်တကယ်ရှာဖွေမှုရည်ရွယ်ချက်အတွက်အသုံးပြုမယ်ဆိုရင် level တစ်ခုချင်းစီကို linear order အတိုင်းရှာဖွေလေ့ရှိပါတယ်။ ဒါဟာ ရှည်လျားပြီး ကွေ့ကောက်တဲ့ corridors တွေနဲ့ အလွန်ရှည်လျားပြီး လိမ်ကောက်တဲ့ solution ပါတဲ့ mazes တွေကို ဖန်တီးပေးပါတယ်။

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

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

recursive backtracker algorithm သည် ပြီးပြည့်စုံသော mazes များ (ကွင်းများမပါသော mazes များနှင့် အမှတ်နှစ်ခုကြားတွင် တစ်ခုတည်းသောလမ်းကြောင်း) ဖန်တီးရန်အတွက် depth-first search နည်းလမ်းတစ်ခုဖြစ်သည်။ ၎င်းသည် ရိုးရှင်းပြီး ထိရောက်မှုရှိပြီး ရှည်လျားပြီး ကွေ့ကောက်သော corridors များပါရှိသော အမြင်အာရုံဆွဲဆောင်မှုရှိသော mazes များကို ဖန်တီးပေးသည်။

၎င်း၏အမည်ရှိသော်လည်း၊ ၎င်းကို recursion ကိုအသုံးပြု၍ အကောင်အထည်ဖော်ရန်မလိုအပ်ပါ။ ၎င်းကို LIFO queue (ဆိုလိုသည်မှာ stack) ကို အသုံးပြု၍ iterative approach တွင် မကြာခဏအကောင်အထည်ဖော်လေ့ရှိသည်။ အလွန်ကြီးမားသော maze များအတွက်၊ recursion ကိုအသုံးပြုခြင်းသည် programming language နှင့် ရရှိနိုင်သော memory ပေါ် မူတည်၍ call stack overflow ဖြစ်ပေါ်စေနိုင်ခြေပိုများသည်။ LIFO queue ကို ရရှိနိုင်သော memory မလုံလောက်ပါက disk သို့မဟုတ် database တွင် queue ကိုသိမ်းဆည်းထားသည့်တိုင် data အမြောက်အမြားကို ကိုင်တွယ်ရန် ပိုမိုလွယ်ကူစွာ လိုက်လျောညီထွေဖြစ်အောင် ပြုလုပ်နိုင်သည်။

ဘယ်လိုအလုပ်လုပ်လဲ

အယ်လဂိုရီသမ်သည် stack-based depth-first search ချဉ်းကပ်မှုကို အသုံးပြု၍ လုပ်ဆောင်သည်။ အဆင့်ဆင့် ခွဲခြမ်းစိတ်ဖြာချက်မှာ အောက်ပါအတိုင်းဖြစ်သည်။

1. စတင်သည့်ဆဲလ်တစ်ခုကို ရွေးချယ်ပြီး ဝင်ရောက်ကြည့်ရှုပြီးအဖြစ် မှတ်သားပါ။
2. မလာရောက်ရသေးသော ဆဲလ်များရှိနေချိန်တွင်- မလာရောက်ရသေးသော အိမ်နီးချင်းဆဲလ်များကို ကြည့်ပါ။ မလာရောက်ရသေးသော အိမ်နီးချင်း အနည်းဆုံးတစ်ခုရှိနေပါက- မလာရောက်ရသေးသော အိမ်နီးချင်းများထဲမှ တစ်ခုကို ကျပန်းရွေးချယ်ပါ။ လက်ရှိဆဲလ်နှင့် ရွေးချယ်ထားသော အိမ်နီးချင်းကြားရှိ နံရံကို ဖယ်ရှားပါ။ ရွေးချယ်ထားသော အိမ်နီးချင်းသို့ ရွှေ့ပြီး သွားရောက်ကြည့်ရှုပြီးအဖြစ် မှတ်သားပါ။ လက်ရှိဆဲလ်ကို stack ပေါ်သို့ တွန်းပါ။ မလာရောက်ရသေးသော အိမ်နီးချင်းများ မရှိပါက- stack မှ နောက်ဆုံးဆဲလ်ကို ခေါက်ခြင်းဖြင့် နောက်ပြန်လှည့်ပါ။
3. stack ဗလာဖြစ်သွားတဲ့အထိ ဒီလုပ်ငန်းစဉ်ကို ဆက်လုပ်သွားပါ။

ဒီ algorithm ရဲ့ စိတ်ဝင်စားစရာကောင်းတဲ့အချက်ကတော့ maze generator အနေနဲ့ရော maze solver အနေနဲ့ပါ အလုပ်လုပ်တာပါပဲ။ generate လုပ်ပြီးသား maze ပေါ်မှာ run ပြီး ဆုံးဖြတ်ထားတဲ့ end point ကိုရောက်ရင် ရပ်လိုက်မယ်ဆိုရင် stack ထဲမှာ maze ရဲ့ အဖြေပါ ပါလာပါလိမ့်မယ်။

ဒီဆိုက်မှာ ဒီ algorithm ရဲ့ version နှစ်ခုရှိပါတယ်။ ဒီစာမျက်နှာမှာ maze တွေထုတ်ပေးဖို့အတွက် LIFO queue based နဲ့ maze တွေကိုဖြေရှင်းဖို့အတွက် recursion based ပါ။ တခြား algorithm တွေကနေထုတ်လုပ်ထားတဲ့ maze တွေလည်းပါဝင်ပါတယ် (အဲဒါက solution တွေပါတဲ့ map တွေကို ဖန်တီးထားတဲ့နည်းလမ်းပါ)။ ဗားရှင်းနှစ်ခုရှိတာ အားကစားအတွက်ပဲ၊ ဘာလို့လဲဆိုတော့ ကျွန်တော်က စိတ်ဝင်စားစရာကောင်းတဲ့ nerd တစ်ယောက်ဖြစ်လို့ပါ။ ဘယ်ဟာမဆို နှစ်ခုလုံးအတွက် အလုပ်ဖြစ်နိုင်ပါတယ်။ ;-)

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

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

• ဝီလ်ဆန်၏ အယ်လ်ဂိုရီသံ မြေဇ် ထုတ်လုပ်သူ
• အဲလ်လား၏ အယ်လ်ဂိုရီသံ မြေဇ် ထုတ်လုပ်သူ
• Kruskal ၏ Algorithm Maze မီးစက်