Recursive Backtracker Maze မီးစက်

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

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

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

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

၎င်း၏အမည်ရှိသော်လည်း၊ ၎င်းကို recursion သုံးပြီးအကောင်အထည်ဖော်ရန်မလိုအပ်ပါ။ ၎င်းကို LIFO တန်းစီ (ဆိုလိုသည်မှာ stack တစ်ခု) ကို အသုံးပြု၍ ထပ်ခါတလဲလဲ ချဉ်းကပ်မှုတွင် မကြာခဏ အကောင်အထည်ဖော်လေ့ရှိသည်။ အလွန်ကြီးမားသော ဝင်္ကပါများအတွက်၊ ပရိုဂရမ်းမင်းဘာသာစကားနှင့် ရရှိနိုင်သောမှတ်ဉာဏ်ပေါ်မူတည်၍ ခေါ်ဆိုမှုအစုအဝေးတွင် ပိုများပါသည်။ ရနိုင်သောမှတ်ဉာဏ်မလုံလောက်ပါက LIFO တန်းစီသည် ဒေတာအများအပြားကို ကိုင်တွယ်ရာတွင် ပိုမိုလွယ်ကူစွာ လိုက်လျောညီထွေဖြစ်စေနိုင်သည်၊ တန်းစီခြင်းကို ဒစ်ပေါ်တွင် သို့မဟုတ် ဒေတာဘေ့စ်တွင် ထားရှိပေးနိုင်သည်။

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

algorithm သည် stack-based depth-first search approach ကို အသုံးပြု၍ လုပ်ဆောင်သည်။ ဤသည်မှာ အဆင့်ဆင့်ခွဲခြမ်းစိတ်ဖြာခြင်းဖြစ်သည်-

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

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

ဤ site ပေါ်တွင် ကစားရန် ဤ algorithm ၏ ဗားရှင်းနှစ်မျိုး ရှိသည်- ဤစာမျက်နှာပေါ်ရှိ ဝင်္ကပါများကို ဖန်တီးရန်အတွက် အခြေခံ LIFO တန်းစီတစ်ခု နှင့် ဝင်္ကပါများကို ဖြေရှင်းရန်အတွက် ထပ်ခါတလဲလဲ အခြေခံထားသော၊ အခြား algorithms များမှ ထုတ်လုပ်သော ဝင်္ကပါများ (ထိုနည်းဖြင့် ဖြေရှင်းချက်ပါသော မြေပုံများကို ပြုလုပ်ပုံ)။ မတူညီသောဗားရှင်းနှစ်ခုရှိခြင်းသည် အားကစားအတွက်သာဖြစ်ပြီး စိတ်ဝင်စားဖွယ်ကောင်းသည်ကို တွေ့ရသောကြောင့် နှစ်ခုစလုံးအတွက် အသုံးပြုနိုင်သည် ;-)