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

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

Методът

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

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

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

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

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

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

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

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

начин на нанасяне

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

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

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

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

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