Dynamic Programming အခြေခံ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Infosys MAQ
Dynamic Programming သဘောတရား

Dynamic Programming အခြေခံများတွင် DP ၏အခြေခံနှင့်၎င်း၏လောဘ၊ Divide and Conquer and Recursion တို့၏ကွဲပြားခြားနားမှုများကိုကျွန်ုပ်တို့တင်ပြပါမည်။

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

၎င်းသည်ပရိုဂရမ်များ၏အကောင်းဆုံးကိုအသုံးပြုသည်။ ၎င်းသည်ယခင်တွက်ချက်ထားသည့်ရလဒ်များကိုအသုံးပြုသောကြောင့်၎င်း၏အဆအချိန်ရှုပ်ထွေးမှုကိုအသုံးပြုခြင်းသည် polynomial ကိုလျှော့ချနိုင်သည်။ ဥပမာ - Ugly နံပါတ်များကိုပြန်လည်တွက်ချက်ရသောအချိန်၏ရှုပ်ထွေးမှုသည်အဆနှင့် DP ဖြေရှင်းချက်သည် linear ဖြစ်သည်။

DP ၏အချို့သောအခြေခံပြproblemsနာများ

  • အရုပ်ဆိုးနံပါတ်များပြproblemနာ
  • အကြွေစေ့ပြောင်းလဲမှု
  • ဖီဘိုနာချီဂဏန်းများ
  • ခေါင်းလောင်းနံပါတ်များပြproblemနာ
  • ဟနွိုင်းမျှော်စင်
  • ခေါင်းလောင်းနံပါတ်များ
  • Knapsack ပြproblemနာ

Dynamic Programming (DP) vs.

DP တွင်အဆင့်တစ်ခုစီသည်အကောင်းဆုံးအဖြေရရှိရန်လက်ရှိနှင့်ယခင်ဖြေရှင်းချက်များကိုစဉ်းစားသောဖြေရှင်းချက်ကိုဆန်းစစ်သည်။ သို့သော်လောဘကြီးသော algorithm တွင်ကျွန်ုပ်တို့သည်လက်ရှိအခြေအနေကိုသာစဉ်းစားရန်အကောင်းဆုံးရွေးချယ်မှုကိုရွေးချယ်သည်။

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

Dynamic Programming (DP) vs Divide & Conquer Method

Divide and Conquer တွင်ပြaနာတစ်ခုအား subproblems အဖြစ်ခွဲပြီး subproblem တစ်ခုချင်းစီကိုသီးခြားဖြေရှင်းသည်။ သို့သော် DP တွင်ပြproblemsနာများကိုသီးခြားလွတ်လပ်စွာဖြေရှင်းခြင်းထက်ကျွန်ုပ်တို့သည်အသစ်သောတွက်ချက်မှုများအတွက်ယခင်ရရှိထားသောရလဒ်များကိုအသုံးပြုသည်။ တစ်နည်းပြောရရင် Divide and Conquer + Memoization = အပေါ်မှအောက်ပြောင်းလဲပြောင်းလဲခြင်းကိုပြောနိုင်ပါတယ်။

(Memoization သည်ယခင်တွက်ချက်ထားသည့်ရလဒ်များကိုယေဘုယျအားဖြင့် hash-map တွင်သိမ်းဆည်းခြင်းနည်းလမ်းကိုရည်ညွှန်းသည်။ တူညီသောပြproblemsနာများ၏တွက်ချက်မှုကိုထပ်ခါတလဲလဲပြုလုပ်သည်။ )

Dynamic Programming (Recursion နည်းလမ်း vs DP)

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

Recursion သည်ပြcalculationနာများအားပြန်လည်တွက်ချက်ခြင်းအတွက်အကြိမ်များစွာဖြစ်ပေါ်စေသည်။ ထို့ကြောင့်ထိုကဲ့သို့သောကိစ္စရပ်များတွင်ပြန်လည်ပြုပြင်ခြင်း၏အချိန်ရှုပ်ထွေးမှုသည်အမြဲတမ်း DP ဖြေရှင်းချက်ထက်သာလွန်သည်။

ဤဆောင်းပါး၌၊ Dynamic Programming အခြေခံ။ နောက်ဆောင်းပါးများတွင် DP နှင့်ပတ်သက်သောအခြေခံပြproblemsနာအချို့ကိုကျွန်ုပ်တို့ဆွေးနွေးပါမည်။

အညွှန်း အင်တာဗျူးမေးခွန်းများ။