Дынамічнае праграмаванне, асноўныя прынцыпы

Для выбару аптымальнага рашэння пры выкананні задач праграмавання часам патрабуецца перабіраць вялікая колькасць камбінацый дадзеных, што нагружае памяць персанальнага кампутара. Да такіх метадаў ставіцца, напрыклад, метад праграмавання «падзяляй і ўладар». У дадзеным выпадку алгарытмам прадугледжана падзел задачы на асобныя дробныя подзадачи. Такі метад прымяняецца толькі ў тых выпадках, калі дробныя подзадачи незалежныя паміж сабой. Для таго каб пазбегнуць выканання лішняй працы ў тым выпадку, калі подзадачи ўзаемазалежныя, выкарыстоўваецца метад дынамічнага праграмавання, прапанаваны амерыканцам Р.Беллманом ў 50-х гадах.

сутнасць метаду

Дынамічнае праграмаванне заключаецца ў вызначэнні аптымальнага рашэння n-мернай задачы, падзяляючы яе n асобных этапаў. Кожны з іх з'яўляецца подзадачей ў адносінах да адной зменнай.

Асноўным перавагай такога падыходу можна лічыць тое, што распрацоўшчыкі займаюцца аднамерны аптымізацыйных задачамі подзадач замест n-мернай задачы, а вырашэнне галоўнай задачы збіраецца «знізу ўверх».

Мэтазгодна ўжываць дынамічнае праграмаванне ў тых выпадках, калі подзадачи ўзаемазвязаны, г.зн. маюць агульныя модулі. Алгарытмам прадугледжана рашэнне кожнай з подзадач адзін раз, і захаванне адказаў выконваецца ў спецыяльнай табліцы. Гэта дае магчымасць не вылічаць адказ зноўку пры сустрэчы з аналагічнай подзадачей.

Задача дынамічнага праграмавання вырашае пытанне аптымізацыі. Аўтарам гэтага метаду Р. Беллманом быў сфармуляваны прынцып аптымальнасці: якім бы ні з'яўлялася зыходны стан на кожным з крокаў і рашэнне, вызначанае на гэтым кроку, усё наступныя выбіраюцца аптымальнымі ў адносінах да таго стану, якое прымае сістэма ў канцы кроку.

Метад удасканаліць выкананне задач, якія вырашаюцца з дапамогай перабору варыянтаў ці рэкурсіі.

Пабудова алгарытму задачы

Дынамічнае праграмаванне прадугледжвае пабудову такога алгарытму задач, пры якім задача так разбіваецца на дзве або больш подзадач, каб яе рашэнне складвалася з аптымальнага вырашэння ўсіх подзадач, якія ўваходзяць у яе. Далей узнікае неабходнасць у напісанні рэкурэнтнага суадносін і вылічэнні аптымальнага значэння параметру для задачы ў цэлым.

Часам на 3-м кроку трэба дадаткова запамінаць некаторую дапаможную інфармацыю аб ходзе выканання кожнай подзадачи. Гэта называецца адваротным ходам.

прымяненне метаду

Дынамічнае праграмаванне прымяняецца пры наяўнасці двух характэрных прыкмет:

• аптымальнасць для подзадач;
• наяўнасць ў задачы перакрываюцца подзадач.

Вырашаючы аптымізацыйных задачу метадам дынамічнага праграмавання, спачатку неабходна апісаць структуру рашэнні. Задача валодае аптымальным, калі рашэнне задачы складваецца з аптымальных рашэнняў яе подзадач. У гэтым выпадку мэтазгодна выкарыстоўваць дынамічнае праграмаванне.

Другая ўласцівасць задачы, істотнае пры дадзеным метадзе, - невялікі лік подзадач. Рэкурсіўнае рашэнне задачы выкарыстоўвае адны і тыя ж перакрываюцца подзадачи, колькасць якіх залежыць ад памеру зыходнай інфармацыі. Адказ захоўваецца ў адмысловай табліцы, праграма эканоміць час, карыстаючыся гэтымі дадзенымі.

Асабліва эфектыўна прымяненне дынамічнага праграмавання тады, калі па сутнасці задачы трэба прымаць рашэнні паэтапна. Напрыклад, разгледзім просты прыклад задачы замены і рамонту абсталявання. Дапусцім, на ліцейні машыне завода па вырабе шын робяць адначасова шыны ў двух розных формах. У тым выпадку, калі адна з формаў выходзіць з ладу, даводзіцца машыну разбіраць. Зразумела, што часам больш выгадна замяніць і другую форму для таго, каб не разбіраць машыну на выпадак, калі і гэтая форма апынецца непрацаздольнай на наступным этапе. Тым больш, бывае прасцей замяніць абедзве працуюць формы да таго, як яны пачнуць выходзіць з ладу. Метад дынамічнага праграмавання вызначае найлепшую стратэгію ў пытанні пра замену такіх формаў, улічваючы ўсе фактары: выгаду ад працягу эксплуатацыі формаў, страты ад прастою машыны, кошт забракаваных шын і іншае.