အဆုံးအဖြတ်ပေးသော တွက်ချက်မှုပုံစံများ၏ အချိန်ရှုပ်ထွေးမှုသည် အဆုံးအဖြတ်မရှိသော မော်ဒယ်များနှင့် မည်သို့ကွာခြားသနည်း။

/ / Published in ပြည်တွင်းသတင်း ဆိုက်ဘာလုံခြုံရေး, EITC/IS/CCTF တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီ အခြေခံအချက်များ, ရှုပ်ထွေး, ကွဲပြားခြားနားသောကွန်ပျူတာမော်ဒယ်များနှင့်အတူအချိန်ရှုပ်ထွေး, စာမေးပွဲသုံးသပ်ချက်

တွက်ချက်မှု၏ အဆုံးအဖြတ်နှင့် အဆုံးအဖြတ်မရှိသော မော်ဒယ်များသည် တွက်ချက်မှုဆိုင်ရာ ပြဿနာများ၏ အချိန်ရှုပ်ထွေးမှုကို ခွဲခြမ်းစိတ်ဖြာရန် အသုံးပြုသည့် ကွဲပြားသော ချဉ်းကပ်နည်းနှစ်ခုဖြစ်သည်။ ကွန်ပြူတာဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီနယ်ပယ်တွင်၊ အမျိုးမျိုးသော တွက်ချက်မှုဆိုင်ရာ ပြဿနာများကို ဖြေရှင်းရန် ထိရောက်မှုနှင့် ဖြစ်နိုင်ခြေကို အကဲဖြတ်ရန် ဤမော်ဒယ်များကြား ကွာခြားချက်များကို နားလည်ရန် အရေးကြီးပါသည်။ ဤအဖြေသည် အချိန်ရှုပ်ထွေးမှု သတ်မှတ်ချက်များတွင် အဆုံးအဖြတ်နှင့် အဆုံးအဖြတ်မဟုတ်သော ပုံစံများကြားတွင် ကွဲပြားမှုများ၏ ကျယ်ကျယ်ပြန့်ပြန့် ရှင်းလင်းချက်ကို ပံ့ပိုးပေးရန် ရည်ရွယ်ပါသည်။

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

အခြားတစ်ဖက်တွင်၊ ပရိုဂရမ်တစ်ခုအား အကောင်အထည်ဖော်နေစဉ်အတွင်း အဆုံးအဖြတ်မရှိသော တွက်ချက်မှုပုံစံများသည် လမ်းကြောင်းများစွာ သို့မဟုတ် ရွေးချယ်မှုများကို ခွင့်ပြုသည်။ ဆိုလိုသည်မှာ ထည့်သွင်းပေးထားသည့် ပရိုဂရမ်သည် မတူညီသော ဖြစ်နိုင်ခြေများကို တစ်ပြိုင်နက် ရှာဖွေနိုင်သည်။ တွက်ချက်မှုဆိုင်ရာ ပြဿနာများ၏ ပင်ကိုယ်အခက်အခဲကို ခွဲခြမ်းစိတ်ဖြာရန် သီအိုရီဆိုင်ရာ ကွန်ပျူတာသိပ္ပံတွင် အဆုံးအဖြတ်မရှိသော မော်ဒယ်များကို မကြာခဏ အသုံးပြုကြသည်။ ဤမော်ဒယ်များတွင်၊ ပရိုဂရမ်မှပြုလုပ်သော ဖြစ်နိုင်သောရွေးချယ်မှုအားလုံးကို ထည့်သွင်းစဉ်းစားပြီး အဖြေတစ်ခုရရှိရန် လိုအပ်သော အဆင့်အရေအတွက်ဖြင့် အချိန်ရှုပ်ထွေးမှုကို တိုင်းတာသည်။

အဆုံးအဖြတ်ပေးခြင်းနှင့် အဆုံးအဖြတ်မဟုတ်သော မော်ဒယ်များအကြား အဓိက ခြားနားချက်မှာ ၎င်းတို့၏ အချိန်ရှုပ်ထွေးမှု ခွဲခြမ်းစိတ်ဖြာမှု၏ သဘောသဘာဝတွင် တည်ရှိသည်။ အဆုံးအဖြတ်မော်ဒယ်များသည် အဆိုးဆုံးအခြေအနေတွင် အာရုံစိုက်ထားပြီး၊ ထည့်သွင်းမှုအရွယ်အစားအတွက် ပြဿနာတစ်ခုဖြေရှင်းရန် လိုအပ်သည့်အချိန်အပေါ် ပိုင်းခြားသတ်မှတ်ထားသည်။ ၎င်းသည် အဆိုးရွားဆုံးအခြေအနေထက် အချိန်ပိုကြာမည်မဟုတ်ကြောင်း အာမခံထားသောကြောင့် algorithm များ၏ ထိရောက်မှုကို ပိုမိုလက်တွေ့အကဲဖြတ်နိုင်စေပါသည်။ ဥပမာအားဖြင့်၊ algorithm တစ်ခုတွင် O(n^2) ၏ အချိန်ရှုပ်ထွေးမှုရှိပါက၊ ဆိုလိုသည်မှာ၊ algorithm သည် n^2 ၏ ကိန်းသေအဆင့်များထက် ပိုမကြာကြောင်းသေချာစေရန်အတွက် execution time သည် input size ဖြင့် လေးထောင့်ပုံသဏ္ဍာန်တိုးလာသည်ဟု ဆိုလိုသည်။

အခြားတစ်ဖက်တွင်၊ အဆုံးအဖြတ်မရှိသော မော်ဒယ်များသည် ပရိုဂရမ်သည် အဆင့်တစ်ဆင့်ချင်းစီတွင် အကောင်းဆုံးရွေးချယ်မှုများ ပြုလုပ်ပေးသည့် အကောင်းဆုံးကိစ္စရပ်ကို ထည့်သွင်းစဉ်းစားသည်။ အဆုံးအဖြတ်မဟုတ်သော မော်ဒယ်များတွင် အချိန်ရှုပ်ထွေးမှု ခွဲခြမ်းစိတ်ဖြာခြင်းသည် ပြဿနာတစ်ခုအား ဖြေရှင်းရန် လိုအပ်သည့်အချိန်ကို လျှော့ချပေးသည်၊ အဘယ်ကြောင့်ဆိုသော် ၎င်းသည် အဖြေတစ်ခုသို့ရောက်ရှိရန် လိုအပ်သော အနိမ့်ဆုံးအဆင့်အရေအတွက်ကို ကိုယ်စားပြုသောကြောင့်၊ သို့သော်၊ လက်တွေ့ကျသော အကောင်အထည်ဖော်မှုများနှင့် တိုက်ရိုက်မသက်ဆိုင်သောကြောင့် အဆုံးအဖြတ်မရှိသော မော်ဒယ်များသည် သဘာဝတွင် သီအိုရီပိုဆန်ပါသည်။ ပြဿနာတစ်ခု၏ အဆုံးအဖြတ်မရှိသော အချိန်ရှုပ်ထွေးမှုကို အများအားဖြင့် အမျိုးအစား NP (Non-deterministic Polynomial time) ဖြင့် အဓိပ္ပါယ်ဖွင့်ဆိုထားသည့် ဆုံးဖြတ်ချက်ပြဿနာများအစုအဝေးကို ကိုယ်စားပြုသော အချိန်မဟုတ်သော Turing machine က ဖြေရှင်းနိုင်သော ဆုံးဖြတ်ချက်ပြဿနာအစုံဖြစ်သည်။

အဆုံးအဖြတ်နှင့် အဆုံးအဖြတ်မရှိသော အချိန်ရှုပ်ထွေးမှုကြား ခြားနားချက်ကို ဥပမာပြရန်၊ ခွဲခြားမထားသောစာရင်းတစ်ခုတွင် သီးခြားဒြပ်စင်တစ်ခုကို ရှာဖွေခြင်းပြဿနာကို သုံးသပ်ကြည့်ကြပါစို့။ အဆုံးအဖြတ်ပုံစံတစ်ခုတွင်၊ ဤပြဿနာ၏ အဆိုးဆုံးအချိန်အတွင်း ရှုပ်ထွေးမှုသည် O(n) ဖြစ်ပြီး၊ n သည် စာရင်း၏အရွယ်အစားကို ကိုယ်စားပြုသည်။ ဆိုလိုသည်မှာ၊ အဆိုးဆုံးအခြေအနေတွင်၊ အယ်လဂိုရီသမ်သည် လိုချင်သောဒြပ်စင်ကိုမရှာဖွေမီ စာရင်း၏ n အစိတ်အပိုင်းအားလုံးကို စစ်ဆေးရန် လိုအပ်ပေမည်။ အဆုံးအဖြတ်မရှိသော မော်ဒယ်တစ်ခုတွင်၊ ဤပြဿနာ၏ အကောင်းဆုံးအချိန် ရှုပ်ထွေးမှုသည် O(1) ဖြစ်ပြီး၊ ပရိုဂရမ်သည် အကောင်းဆုံးရွေးချယ်မှုကို ပြုလုပ်နိုင်ပြီး လိုချင်သောဒြပ်စင်ကို ချက်ချင်းရှာဖွေနိုင်သောကြောင့် ဖြစ်သည်။ သို့သော်၊ ဤသတ်မှတ်မဟုတ်သော အချိန်ရှုပ်ထွေးမှုသည် ပြဿနာကို လက်တွေ့သဘောအရ အဆက်မပြတ်အချိန်အတွင်း ဖြေရှင်းနိုင်သည်ဟု မဆိုလိုကြောင်း သတိပြုရန် အရေးကြီးပါသည်။

အဆုံးအဖြတ်ပေးသော တွက်ချက်မှုပုံစံများ၏ အချိန်ရှုပ်ထွေးမှုသည် ပြဿနာတစ်ခုဖြေရှင်းရန် လိုအပ်သည့်အချိန်အပေါ် အဆိုးဆုံးအခြေအနေအပေါ် အခြေခံထားသည်။ အခြားတစ်ဖက်တွင်မူ အဆုံးအဖြတ်မရှိသော မော်ဒယ်များသည် အကောင်းဆုံးကိစ္စရပ်ကို ထည့်သွင်းစဉ်းစားပြီး အချိန်ရှုပ်ထွေးမှုအပေါ် နိမ့်ကျသော ဘောင်ကို ပေးဆောင်သည်။ အဆုံးအဖြတ်ပေးသော မော်ဒယ်များသည် လက်တွေ့ကမ္ဘာ အယ်လဂိုရီသမ်များနှင့် တိုက်ရိုက်သက်ဆိုင်သော်လည်း၊ အဆုံးအဖြတ်မဟုတ်သော မော်ဒယ်များကို သီအိုရီပိုင်းခြားစိတ်ဖြာမှုနှင့် ရှုပ်ထွေးမှုအတန်းများအတွက် အဓိကအားဖြင့် အသုံးပြုပါသည်။ ဤမော်ဒယ်များအကြား ခြားနားချက်များကို နားလည်ခြင်းသည် ထိရောက်သော တွက်ချက်မှုဆိုင်ရာ ဖြေရှင်းချက်များကို ခွဲခြမ်းစိတ်ဖြာခြင်းနှင့် ဒီဇိုင်းရေးဆွဲခြင်းအတွက် မရှိမဖြစ်လိုအပ်ပါသည်။

အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ ရှုပ်ထွေး:

Complexity တွင် နောက်ထပ်မေးခွန်းများနှင့် အဖြေများကို ကြည့်ပါ။

နောက်ထပ်မေးခွန်းများနှင့် အဖြေများ-

အောက်တွင် tag လုပ်ခဲ့သည် , , , , ,