Динамикалық бағдарламалау, негізгі принциптері

орындау кезінде оңтайлы шешімін таңдау үшін бағдарламалау міндеттері кейде жеке компьютердің жадында жүктер деректер комбинациялар үлкен көлемін сұрыптау үшін қажет. Мұндай әдістер, мысалы, «Бөліп билей» бағдарламалау әдісін қамтиды. Бұл жағдайда алгоритм жеке кішірек шығыңыз бөлу мәселесін ұсынады. Бұл әдіс тек шағын Қосалқы өзара тәуелсіз жағдайларда қолданылады. өзара қосалқы міндеттерді, егер қажетсіз жұмыстарды орындау болдырмау үшін, динамикалық бағдарламалау әдісі 50-ші жылдарда американдық R.Bellmanom ұсынды пайдаланады.

әдіс

Динамикалық бағдарламалау оған N жекелеген кезеңдерін ортақ, оңтайлы шешім N-өлшемді мәселені анықтау болып табылады. Олардың әрқайсысы бір айнымалы қатысты қосалқы міндет болып табылады.

Бұл тәсілдің басты артықшылығы әзірлеушілер бір өлшемді оңтайландыру мәселесіне қатысы деп санауға болады орнына N өлшемді мәселенің подзадач, және біздің басты мақсатымыз «төменнен-жоғары» жоспарлап отыр.

, Қосалқы тапсырмалар өзара жағдайларда динамикалық бағдарламалау қолдануға, яғни ұсынылады ортақ модульдерді ортақ. алгоритм бір рет подзадач әрбір шешімін қамтамасыз етеді, және жауап үнемдеу арнайы кестеде адресінен жүзеге асырылады. Бұл олар сол кіші-тапсырманы қайтадан кездесті кезде жауап есептеу емес мүмкіндік береді.

Динамикалық бағдарламалау міндеті мәселені шешеді оңтайландыру. Осы әдістің авторы Р. Беллмана оңтайлылық принципі бойынша тұжырымдалған болатын: барлық қадамда соңында жүйесін алады мемлекет, қатысты оңтайлы таңдау үшін келесі, қадамдар және осы қадамда анықталған шешу әрбір бастапқы мемлекет болып табылады кез келген.

әдісі нұсқаларын құралдарын, немесе Рекурсия бойынша шешілетін міндеттердің өнімділігін жақсартады.

Құрылыс міндеті алгоритмі

Динамикалық бағдарламалау алгоритм міндеті, сондықтан оны шешу үшін екі немесе одан да көп подзадач бөлінеді осындай міндеттерді салуды көздейді барлық подзадач үшін оңтайлы шешім тұрады, ол қамтиды. Әрі қарай, ол қайталану қатысы жазу керек, сондай-ақ жалпы тапсырма үшін оңтайлы параметр мәндерін есептеу.

Кейде, 3-ші қадамда әрбір тапсырманың орындалу барысы туралы кейбір қосымша анықтамалық ақпарат жаттап болып табылады. Бұл қайтару инсульт деп аталады.

қолдану әдісі

екі тән ерекшеліктері бар болған кезде динамикалық бағдарламалау қолданылады:

• подзадач үшін оңтайлы;
• подзадач қабаттасатын мәселесіне болуы.

динамикалық программалау арқылы оңтайландыру мәселесін шешу үшін, алдымен шешу құрылымын сипаттау үшін қажет. міндет шешім оның подзадач үздік шешімдерінің тұрады, егер оңтайлы болуы керек. Бұл жағдайда, ол динамикалық бағдарламалау пайдалану ұсынылады.

Осы әдістің маңызды мәселенің екінші меншік, - қосалқы тапсырмалар саны аз. сол шарасыз қосалқы мәселелерді, бастапқы ақпарат көлеміне байланысты оның нөмірін пайдалана отырып, мәселенің рекурсивті шешімі. Жауап арнайы кестеде сақталады, бағдарлама осы деректерді пайдалана отырып, уақытты үнемдейді.

Әсіресе тиімді міндет шын мәнінде кезеңдерінде шешімдерді қабылдау үшін қажет динамикалық бағдарламалау пайдалану болып табылады. Мысалы, ауыстыру және жабдықтарды жөндеу мәселесін қарапайым мысалды қарастырайық. екі түрлі нысандарда шина жасау бір мезгілде шиналар өндіру үшін құю машинасы зауытында делік. нысандарының бірі келмей қалған жағдайда, ол машинаны бөлшектеуге қажет. Бұл жағдайда машинаны бөлшектеуге және осы нысаны келесі кезеңде жарамсыз болады мақсатында кейде тиімдірек орнына сол түсінікті және екінші нысаны болып табылады. олар сәтсіздікке бастамас бұрын, ол екі жұмыс пішінін ауыстыру оңай Әсіресе бері. қанаудың жалғасып нысандарын артықшылықтары, машина тұрып жоғалту, керексіз шиналар құны және одан: Динамикалық бағдарламалау әдісі назарға барлық факторларды ескере отырып, осы нысандарын ауыстыру мәселеде ең үздік стратегиясын анықтайды.