Dynamic ပရိုဂရမ်းမင်း, အခြေခံစည်းမျဉ်းစည်းကမ်းများ

ဖျော်ဖြေအခါအကောင်းဆုံးဖြေရှင်းနည်းကို select ဖို့ programming ကိုတာဝန်များကိုတစ်ခါတစ်ရံပုဂ္ဂိုလ်ရေးကွန်ပျူတာ၏မှတ်ဉာဏ်ကိုသက်ရောက်ကြောင်းဒေတာပေါင်းစပ်ပမာဏ sort ရန်လိုအပ်သည်။ ထိုကဲ့သို့သောနည်းလမ်းများ, ဥပမာ, "သွေးခွဲအုပ်ချုပ်ရေး" ၏ programming ကိုနည်းလမ်းပါဝင်သည်။ ဤကိစ္စတွင်အတွက် algorithm ကိုသီးခြားသေးငယ် subtasks သို့ခွဲခြာပြဿနာပေးပါသည်။ ဤနည်းလမ်းကိုသာသေးငယ်တဲ့ subtasks အပြန်အလှန်လွတ်လပ်သောနေရာရှိသူများကိစ္စများတွင်သက်ဆိုင်သည်။ အလှနျမှီခို Sub-တာဝန်များကိုလျှင်မလိုအပ်သောအလုပ်ဖျော်ဖြေရှောင်ရှားရန်, ပြောင်းလဲနေသော programming ကိုနည်းလမ်း 50s အတွက်အမေရိကန် R.Bellmanom အဆိုပြုထားအသုံးပြုသည်။

အဆိုပါနည်းလမ်း

dynamic programming ကိုသူမ၏ဎသီးခြားအဆင့်ဆင့်မျှဝေသည်အကောင်းဆုံးဖြေရှင်းနည်း n-ရှုထောင်ပြဿနာကိုဆုံးဖြတ်ရန်ရန်ဖြစ်ပါသည်။ သူတို့တစ်ဦးစီတစ်ဦး variable ကိုရိုသေလေးစားမှုနဲ့ခွဲလုပ်ငန်းတာဝန်ဖြစ်ပါတယ်။

ဒီချဉ်းကပ်မှု၏အဓိကအားသာချက် developer များတ-ရှုထောင် optimization ပြဿနာတွင်ပါဝင်ပတ်သက်သည်ဟုထည့်သွင်းစဉ်းစားရနိုင်မယ့်အစားတစ်ဦး n-ရှုထောင်ပြဿနာ subtasks, ငါတို့မူလတန်းရည်ရွယ်ချက်မှာ "Bottom-Up" ကိုသွားဖြစ်ပါတယ်။

, အခွဲများတာဝန်များကို ခွဲခြား. မရဘဲချိတ်ဆက်ထားရာသူတို့အားကိစ္စများတွင်ပြောင်းလဲနေသော programming ကိုလျှောက်ထားရန်ဆိုလိုသည်မှာအကြံပြုလိုတယ်ဒါဟာဖြစ်ပါသည် ဘုံ module တွေမျှဝေပါ။ အဆိုပါ algorithm ကိုတစ်ချိန်က subtasks ၏တစ်ဦးချင်းစီ၏ဆုံးဖြတ်ချက်သည်နှင့်တုံ့ပြန်မှုချွေတာတဲ့အထူး table ထဲမှာဖျော်ဖြေနေသည်။ ဤသည်ကိုသူတို့အတူတူခွဲလုပ်ငန်းတာဝန်နှင့်အတူနောက်တဖန်တွေ့သောအခါအဖြေကိုတွက်ချက်ဖို့မဖြစ်နိုင်ရင်စေသည်။

dynamic programming ကိုတာဝန် ပြဿနာကိုဖြေရှင်းနိုင်ပါတယ် optimization ၏။ ဒီနည်းလမ်းရဲ့စာရေးဆရာ R. Bellman Optimizer နိယာမအားဖြင့်ဖော်စပ်ခဲ့ပါတယ်: အသားအပေါငျးခြေလှမ်းရဲ့အဆုံးမှာစနစ်အားလက်ခံတွေ့ဆုံသောပြည်နယ်, ဆက်စပ်. အတွက်အကောင်းဆုံးရွေးချယ်ဖို့အောက်ပါတို့သည်ခြေလှမ်းများနှင့်ဤခြေလှမ်းအတွက်သတ်မှတ်ဖြေရှင်းချက်၏တစ်ဦးချင်းစီ၏ကနဦးပြည်နယ်ဖြစ်ပါတယ်ဘာပဲ။

အဆိုပါနည်းလမ်းကိုမျိုးကွဲများ၏နည်းလမ်းများ, ဒါမှမဟုတ်တဲ့ request အားဖြင့်ဖြေရှင်းသည့်အလုပ်များကိုစွမ်းဆောင်ရည်ပိုမိုကောင်းမွန်စေတယ်။

အဆောက်အဦးလုပ်ငန်းတာဝန် algorithm ကို

dynamic programming ကို algorithm ကို task ကိုနိုင်အောင်က၎င်း၏ဖြေရှင်းချက်မှနှစ်ခုသို့မဟုတ်နှစ်ခုထက်ပိုသော subtasks သို့ခွဲထွက်ကြောင်းထိုကဲ့သို့သောအလုပ်များကိုဆောက်လုပ်ရေးကပါဝင်ပတ်သက်အားလုံး subtasks ဖို့အကောင်းဆုံးဖြေရှင်းနည်း၏ရေးစပ်သည်ကပါဝင်သည်။ ထို့ပြင်ကထပ်မဖြစ်အောင်စပ်လျဉ်းရေးသားဖို့လိုအပ်သောဖြစ်တယ်, တစ်ဖွဲ့လုံးကတာဝန်များအတွက်အကောင်းဆုံး parameter သည်တန်ဖိုးများကိုတွက်ချက်။

တခါတရံမှာ, အ 3rd ခြေလှမ်းအပေါ်တစ်ခုချင်းစီကိုတာဝန်များ၏တိုးတက်မှုအပေါ်အချို့သောအပိုဆောင်းနောက်ခံသတင်းအချက်အလက်အလွတ်ကျက်ရန်ဖြစ်ပါသည်။ ဒါကပြန်လာလေဖြတ်ဟုခေါ်သည်။

လျှောက်လွှာနည်းလမ်း

နှစ်ခုဝိသေသအင်္ဂါရပ်တွေရှိပါတယ်သည့်အခါ dynamic programming ကိုလျှောက်ထားသည်:

• subtasks များအတွက်အကောင်းဆုံး;
• subproblems ထပ်၏ပြဿနာအတွက်ရှိနေခြင်း။

ပြောင်းလဲနေသောပရိုဂရမ်းမင်းအားဖြင့် optimization ပြဿနာဖြေရှင်းရေး, သင်ပထမဦးဆုံးအဖြေများ၏ဖွဲ့စည်းပုံကိုဖော်ပြရန်ဖို့လိုအပ်ပါတယ်။ task ကိုဖြေရှင်းနည်းက၎င်း၏ subtasks ရဲ့အကောင်းဆုံးဆုံးဖြတ်ချက်များကို၏ရေးစပ်လျှင်အကောင်းဆုံးဖြစ်ပါတယ်။ ဤကိစ္စတွင်ခုနှစ်, ဒါကြောင့်ပြောင်းလဲနေသော programming ကိုသုံးစွဲဖို့အကြံပြုလိုတယ်။

ဒီနည်းလမ်းကိုအတွက်မရှိမဖြစ်လိုအပ်သောပြဿနာဒုတိယပိုင်ဆိုင်မှု, - Sub-အလုပ်များကိုသေးငယ်တဲ့နံပါတ်။ တူထပ်ခွဲပြဿနာများ, ကနဦးသတင်းအချက်အလက်များ၏အရွယ်အစားပေါ်မူတည်သည့်အရေအတွက်ကိုအသုံးပြုပြီးပြဿနာ request ကိုဖြေရှင်းနည်း။ အဖြေအထူး table ထဲမှာသိုလှောင်ထားသည်ပရိုဂရမ်ကိုဒီဒေတာကို အသုံးပြု. အချိန်ကယ်တင်တော်မူ၏။

အထူးသဖြင့်ထိရောက်သော task ကိုမရှိမဖြစ်လိုအပ်တဲ့အဆင့်ဆုံးဖြတ်ချက်များစေရန်လိုအပ်သည့်အခါပြောင်းလဲနေသောပရိုဂရမ်းမင်း၏အသုံးပြုမှုသည်။ ဥပမာအားဖြင့်, အစားထိုးခြင်းနှင့်ပစ္စည်းကိရိယာများပြုပြင်ခြင်းများ၏ပြဿနာတစ်ခုရိုးရှင်းတဲ့ဥပမာစဉ်းစားပါ။ ရဲ့နှစ်ခုကွဲပြားခြားနားသောပုံစံများအတွက်တာယာစေတစ်ချိန်တည်းမှာတာယာများ၏ထုတ်လုပ်မှုများအတွက်သတ္တုများပုံသွန်းစက်စက်ရုံအပေါ်ဆိုပါစို့။ အဆိုပါပုံစံများကိုတစ်ဦးပျက်ကွက်သောဖြစ်ရပ်အတွက်ကြောင့်စက် disassemble ရန်လိုအပ်ပေသည်။ ဒါဟာအမှု၌စက် disassemble ရန်နှင့်ဤပုံစံကိုလာမယ့်စင်မြင့်အတွက် unworkable ဖြစ်လိမ့်မည်နိုင်ရန်အတွက်တစ်ခါတစ်ရံထက်ပိုအမြတ်အစွန်းအစားထိုးကြောင်းနားလည်နိုင်ပြီးဒုတိယပုံစံဖြစ်ပါတယ်။ သူတို့ကျရှုံးစတင်ရှေ့မှာနှစ်ဦးစလုံးအလုပ်လုပ်ပုံသဏ္ဍာန်အစားထိုးရန်ပိုမိုလွယ်ကူမယ့်အထူးသဖြင့်ကတည်းက။ အဆိုပါခေါင်းပုံဖြတ်၏ဆက်လက်ပုံစံများ၏အကျိုးကျေးဇူးများကို, စက်ကျချိန်၏ဆုံးရှုံးမှု, စွန့်ပစ်တာယာ၏ကုန်ကျစရိတ်နှင့်ပိုပြီး: dynamic programming ကိုနည်းလမ်းအကောင့်သို့အပေါငျးတို့သအချက်များယူပြီးဤပုံစံများ၏အစားထိုး၏အမှု၌ကိုအကောင်းဆုံးနည်းဗျူဟာဆုံးဖြတ်သည်။