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

За да изберете оптималното решение за задачи по програмиране, понякога е необходимо да преминете през голям брой комбинации от данни, които зареждат паметта на персоналния компютър. Такива методи включват, например, методът на "разделяне и завладяване". В този случай алгоритъмът предвижда отделяне на задачата в отделни малки подзадачи. Този метод се използва само в случаите, когато малките подзадачи са независими един от друг. За да се избегне ненужната работа в случай, че подзадълженията са взаимозависими, се използва динамичният метод на програмиране, предложен от американския Р. Белман през 50-те години на ХХ век.

Същността на метода

Динамичното програмиране се състои в определяне на оптималното решение на n-dimensional проблем, разделяйки го на n отделни стъпки. Всеки от тях е подзадача по отношение на една променлива.

Основното предимство на този подход може да се счита, че разработчиците се занимават с едномерни оптимизационни задачи на поддиапазоните вместо с n-dimensional проблем и решението на основната задача се събира "отдолу нагоре".

Препоръчително е да се приложи динамично програмиране в случаите, когато подзадълженията са взаимосвързани, т.е. имат общи модули. Алгоритъмът предоставя еднократно решение за всяка от подлезите и отговорите се запазват в специална таблица. Това прави възможно да не се изчислява отново отговор, когато се натъкне на подобна подзадачка.

Задачата на динамичното програмиране решава проблема оптимизация. Авторът на този метод R. Bellman формулира принципа на оптималността: независимо от първоначалното състояние на всяка стъпка и решението, определено в тази стъпка, всички изброени по-долу са избрани да бъдат оптимални по отношение на състоянието, което системата взема в края на стъпката.

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

Изграждане на алгоритъма на проблема

Динамичното програмиране предполага изграждането на такъв алгоритъм на проблемите, при който задачата е разделена на две или повече подзадачи, така че нейното решение се формира от оптималното решение на всички включени в него подзадачи. Освен това е необходимо да се напише рекурентна връзка и да се изчисли оптималната стойност на параметъра за проблема като цяло.

Понякога, в третата стъпка, трябва да помните допълнително допълнителна информация за хода на всяка подзадачка. Това се нарича обратното.

Прилагане на метода

Динамичното програмиране се използва, когато има две характерни черти:

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

Решаването на проблема с оптимизацията чрез метода на динамичното програмиране, първо е необходимо да се опише структурата на решението. Проблемът е оптимален, ако решението на проблема се състои от оптималните решения на неговите подзадачи. В този случай е препоръчително да използвате динамично програмиране.

Втората характеристика на проблема, която е от съществено значение за този метод, е малък брой подзадачи. Рекурсивното решение на проблема използва същите припокриващи се подзадачи, броят на които зависи от размера на оригиналната информация. Отговорът се съхранява в специална таблица, като програмата спестява време, като използва тези данни.

Особено ефективно е да се използва динамично програмиране, когато по същество задачите трябва да бъдат изпълнявани на етапи. Например, помислете за един прост пример за задачата за подмяна и ремонт на оборудване. Да предположим, че в леярната на завод за производство на гуми, гумите се произвеждат едновременно в две различни форми. В случай че една от формите не успее, трябва да разглобите устройството. Ясно е, че понякога е по-изгодно да се замени втората форма, за да не се разглоби машината в случай, и тази форма ще бъде неефективна на следващия етап. Освен това е по-лесно да се заменят двете работни форми, преди да започнат да се провалят. Методът на динамично програмиране определя най-добрата стратегия по въпроса за замяната на такива форми, като се вземат предвид всички фактори: ползата от продължаването на работата на формулярите, загубата от машини с празен ход, цената на отхвърлените гуми и др.