Динамичко програмирање, основни принципи

Да бисте изабрали оптимално решење када обављање послова програмска се понекад да се сортирају велике количине комбинација података који учитава сећање на персоналном рачунару. Такви поступци обухватају, на пример, поступак програмирање "завади па владај". У овом случају алгоритам омогућава раздвајање проблем у одвојене мање подзадатке. Ова метода се примењује само у оним случајевима у којима су мали подзадатке међусобно независна. Да би се избегло обављање непотребан посао ако зависних под-задатака, користи динамички метод програмирање предложени амерички Р.Беллманом у 50.

metod

Динамичко програмирање је да се утврди оптимално решење за н-димензионални проблем, дељење своје н одвојене фазе. Сваки од њих је под-задатак у односу на једне променљиве.

Основна предност оваквог приступа може се сматрати да су програмери који су укључени у једнодимензионог оптимизације проблема подзадатке уместо н-димензионални проблем, а наш примарни циљ је да "одоздо према горе".

Препоручљиво је да се пријаве динамичко програмирање у оним случајевима у којима су међусобно повезани су под задаци, односно деле заједничке модула. Алгоритам даје одлуку сваког од подзадатке једном, и одговори штедње врши се у посебном табели. То омогућава да се израчуна одговор када су се поново срели са истом под-задатак.

Динамички задатак програмирање решава проблем оптимизације. Аутор ове методе је формулисао Р Беллмана принципу оптималност: год је почетно стање сваког од корака и решења дефинисано у овом кораку, све следеце да изабере оптималну у односу на државу, која прима систем на крају корака.

Метод побољшава перформансе задатака решених путем варијанте, или рекурзије.

Зграда алгоритам задатак

Динамички алгоритам програмирање укључује изградњу таквих задатака које је задатак да се подели на два или више подзадатке његовом решавању се састоји од оптималног решења за све подзадатке, обухвата. Даље, неопходно је да се напише понављања однос, и израчунавање оптималне вредности параметара за задатак у целини.

Понекад, на 3. корак је да запамтите неке додатне основне информације о напретку сваког задатка. Ово се зове повратак удар.

metod апликација

Динамичко програмирање се примењује када постоје две карактеристичне црте:

• оптималан за подзадатке;
• присуство у проблем преклапања субпроблемс.

Решавање проблема оптимизације по динамичког програмирања, прво треба да опише структуру решења. Задатак мора да буде оптимално ако решење се састоји од најбољих одлука њених подзадатке. У овом случају, препоручљиво је да се користи динамичко програмирање.

Друга имовина проблема, од суштинске важности у овом поступку, - мали број под-задатака. Рекурзиван решење проблема користећи исте преклапају под-проблеме, број који зависи од величине првобитној информацији. Одговор се чува у посебној табели, програм штеди време помоћу ове податке.

Посебно ефикасна је употреба динамичког програмирања, када је у суштини потребна задатак да доносе одлуке у фазама. На пример, размотримо једноставан пример проблема замене и поправке опреме. Рецимо на фабрику за ливење машине за производњу гума у исто време чине гуму у два различита облика. У случају да је један од облика не успе, потребно је растављање машине. Разумљиво је да понекад профитабилније да замени и други облик како би се демонтира машине у случају и овај облик ће бити неизводиво, у наредној фази. Посебно јер је лакше да замени оба радном стању пре него што почну да пропадне. Динамичка метода програмирања одређује најбољу стратегију у питању замене ових облика, узимајући у обзир све факторе: предности континуиране облика експлоатације, губитка машине застоја, трошкова одбачених гума и више.