Въведение в динамичното програмиране

Сред проблемите, решени с помощта на математическото програмиране, можем да отделим отделен клас от задачи, които изискват оптимизация на многоетапни (многоетапни) процеси. Тези задачи се отличават с възможността да се раздели решението на няколко взаимосвързани стъпки. За решаването на такива проблеми се използва динамично програмиране или, както се нарича, многоетапно програмиране. Неговите методи са оптимизирани за намиране на оптимално решение на многоетапни задачи, които могат да бъдат разделени на няколко етапа, стъпки и др.

Произход на термина

Използването на думата „динамичен“ в заглавието първоначално предполага, че разделянето на подзадачи ще се извърши главно във времето. Когато се използват динамични методи за решаване на производствени, бизнес и други задачи, които включват времевия фактор, разделянето на отделни етапи не е трудно. Но е възможно да се използва техниката на динамичното програмиране в задачи, при които отделните етапи не са свързани във времето. Винаги в многоетапна задача, можете да изберете параметър или свойство, според което можете да разделяте на отделни стъпки.

Алгоритъм (метод) за решаване на многоетапни проблеми

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

Метод по-горе и метод по-долу

Независимо от факта, че при изчисляване на отделен етап от решаването на даден проблем се използват параметрите на процеса за текущия момент, резултатът от оптимизацията на предишния етап влияе върху изчисленията на следващите етапи, за да се постигне най-добрият резултат като цяло. Динамичното програмиране нарича такъв принцип на решението на метода на оптималността, който определя, че оптималната стратегия за решаване на проблем, независимо от първоначалните решения и условия, трябва да представлява оптимална стратегия за първоначалното състояние на следващите етапи. Както виждаме, процесът на решаване на проблем е непрекъснато оптимизиране на резултата на всеки отделен етап от първия до последния. Този метод се нарича метод на горното програмиране. Фигурата схематично показва алгоритъма на решението отгоре надолу. Но има един клас от многостепенни проблеми, в които максималният ефект вече е известен на последния етап, например, вече сме пристигнали от точка А до точка Б и сега искаме да знаем дали сме вървели правилно на всеки предишен етап или ако можем да направим нещо по-оптимално. Възниква рекурсивна последователност от етапи, т.е. отиваме като “от обратното”. Този метод на решение се нарича "метод за програмиране на дъното".

Практическо приложение

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

Търсете най-добрия път

Чрез динамична оптимизация е възможно да се реши широк клас задачи за намиране или оптимизиране на най-краткия път и други проблеми, при които „класическият” метод за изброяване на възможните решения води до увеличаване на времето за изчисление, а понякога и като цяло неприемливо. Класическият проблем на динамичното програмиране е проблем на раницата: даден е определен брой обекти с определена маса и цена и е необходимо да се избере набор от обекти с максимална стойност и маса, която не надвишава обема на раницата. Класическото изброяване на всички опции в търсене на оптималното решение ще отнеме значително време и с помощта на динамични методи проблемът ще бъде решен в разумен срок. Задачите за намиране на най-краткия път за транспортна логистика са основни, а методите на динамично решение са оптимално подходящи за тяхното решение. Най-простият пример за такава задача е изграждането на най-краткия маршрут от автомобилен GPS навигатор.

производство

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

Научна област

Методите за динамично програмиране са широко използвани в различни научни изследвания. Например, те успешно се използват в алгоритмите за разпознаване на реч и изображение, при обработката на масиви от големи данни в социологията и икономическа дейност.