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

За да изберете оптимално решение при извршување на задачите на програмирање се понекогаш е потребно да се најде решение за големи количини на податоци кои комбинации вчитува меморија на персонален компјутер. Таквите методи вклучуваат, на пример, метод на програмирање на "раздели па владеј". Во овој случај алгоритам обезбедува проблем поделба во посебни помали подзадачи. Овој метод се применува само во оние случаи каде што малите подзадачи се меѓусебно независни. За да се избегне извршување на непотребни работи ако независни под-задачи, користи динамичен програмирање метод предложениот американски R.Bellmanom во 50-тите.

начинот

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

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

Препорачливо е да се примени и динамичкото програмирање во оние случаи во кои се меѓусебно поврзани со под-задачи, т.е. делат заеднички модули. Алгоритмот обезбедува одлука на секоја од под-задачи одеднаш, и одговори штедење се изведуваат во посебна табела. Ова го прави можно да се пресмета одговор кога тие повторно се сретна со истиот под-задача.

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

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

алгоритам задача зграда

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

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

примена на метод

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

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

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

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

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