Динамично оптимиране

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

Динамичното оптимиране се използва в математиката, икономиката, информатиката и биоинформатиката. Същността му се състои в решаването на задача чрез разделянето ѝ на набор от по-прости подзадачи, всяка от които се решава само веднъж, а решенията им се запазват в подходяща структура от данни. Когато решението на някоя подзадача потрябва пак, то се взима наготово. Така се пести време, но за сметка на изразходването на повече памет. Техниката за запомняне на решенията на подзадачите (вместо повторното им решаване) се нарича „мемоизация“.

Оптимизационните задачи могат да се решават не само чрез динамично оптимиране, а и по други начини, например с помощта на т. нар. „алчни алгоритми“ на английски: greedy algorithm. Те построяват търсеното най-добро решение стъпка по стъпка, като на всеки етап избират онзи вариант, който е най-добър за момента. Затова се изпълняват бързо и се програмират лесно, но не винаги са коректни. Динамичното оптимиране е коректно, но по-бавно и изразходва повече памет, тъй като пази не едно възможно решение, а няколко – толкова, колкото е нужно. От друга страна, динамичното оптимиране е много по-бързо от пълното изчерпване, защото разглежда не всички възможни случаи, а само най-малкия необходим брой.

Например в задачата за намиране на минималния брой монети за изплащане на дадена парична сума динамичното оптимиране ще открие най-доброто решение, като първо потърси оптимално решение за всички по-малки суми, а след това ще използва тези решения, за да построи оптималното решение за търсената сума. За сравнение, алчният алгоритъм на всяка стъпка използва монета с възможно най-голяма стойност (която е по-малка от оставащата сума). Той е коректен за система от монети със стойности 1, 2, 5, 10, 20, 50, но не е коректен, ако стойностите на монетите са 1, 4, 5, 15, 20: например за сумата 23 алчният алгоритъм предлага решението 20 + 1 + 1 + 1, което не е оптимално (използва четири монети); най-доброто решение е 15 + 4 + 4 (с три монети).

**Намиране на най-краткия път в граф**: правите отсечки изобразяват един ъгъл; вълнистите отсечки изобразяват най-краткия път между двата върха; удебелената линия е глобалния най-кратък път, от началото да края.

Общ преглед

Динамичното програмиране е едновременно математически метод за оптимизация и метод за компютърно програмиране. И в двете ситуации дадена сложна задача се опростява чрез разделяне на по-прости подзадачи. По това динамичното програмиране прилича на известния метод „разделяй и владей“. Разликата между тях е, че при динамичното програмиране две или повече различни задачи могат да имат обща подзадача, а при метода „разделяй и владей“ това не е възможно. Затова последният е обикновено много по-прост от динамичното програмиране.

Динамичното програмиране се основава на връзката, която съществува между задачата и нейните подзадачи. Тази връзка се изразява формално чрез уравнение на Белман на английски: Bellman equation.^[1]

В математиката

При математическата оптимизация динамичното оптимиране опростява решението на дадена задача чрез разделянето ѝ на поредица от стъпки. Нека определим последователност от стойности на функция V с аргумент у V₁, V₂, ..., V_n, представляващи състоянието в моменти от време i от 1 до n. Нека V_n(у) е стойността на функцията за състояние у в последния момент n. Стойностите V_i в по-ранните моменти от време n – 1, n – 2, ..., 2, 1 могат да се намерят с помощта на рекурсивни връзка, наречена уравнение на Белман. За всяко състояние у и моменти i = 2, ..., n, стойността на предходно състояние V_i-1 се изчислява от V_i, чрез максимизиране на нова проста функция (обикновено сумата), когато V_i е известна. След n-1 на брой операции накрая се получава V₁ на първоначалното състояние на системата и това е стойността на оптималното решение. Оптималните стойности на променливите могат да бъдат възстановени, една по една, като се проследят вече извършените изчисления.

В биоинформатиката

Динамичното оптимиране се използва широко в биоинформатиката за задачи, като подравняване на редици, сгъване на протеин, прогнозиране на РНК структура и свързване на протеин с ДНК. Първите такива алгоритми са разработени през 1970 г. независимо от Чарлз ДеЛиси в САЩ и Георгий Гурский и Александър Заседателев в СССР. Тези алгоритми са станали много популярни в биоинформатиката и изчислителната биология, особено в проучванията за разполагането на нуклеозоми и свързването на транскрипционен фактор.

В програмирането

За да може да се прилага динамично оптимиране, една задача трябва да има два основни атрибута: оптимална подструктура и припокриващи се подзадачи. Ако една задача може да бъде решена чрез комбиниране на оптимални решения за неприпокриващи се подзадачи, алгоритъмът се нарича „разделяй и владей“. Ето защо сортирането чрез сливане и бързото сортиране не се считат за задачи за динамично оптимиране.

Оптимална подструктура означава, че решението може да се получи от комбинацията на оптималните решения на подзадачите. Такива оптимални подструктури обикновено се описват чрез рекурсия. Такава оптимална подструктура например при граф G = (V, E) e най-краткият път p от връх u до връх v: р е наистина най-краткият път и ако се вземе някой междинен връх w, който е част от p, то р може да се раздели на части p₁ (от u до w) и p₂ (от w до v) така, че p₁ и p₂ също са най-кратки пътища между съответните върхове. Следователно, може лесно да се формулира рекурсивен алгоритъм за намиране на най-кратките пътища, което се прави например с алгоритъм на Белман-Форд или алгоритъм на Флойд-Уаршал.

Графика на подзадачите за редицата на Фибоначи. Фактът, че структурата не е дървовидна, показва припокриващи се подзадачи.

Припокриващи се подзадачи означава, че пространството на подзадачите трябва да бъде малко, тоест, всеки рекурсивен алгоритъм трябва да решава същите подзадачи отново и отново, а не да създава нови. Например да разгледаме рекурсивен метод за генериране на редицата на Фибоначи: F_i = F_i-1 + F_i-2, с база F₁ = F₂ = 1. Тогава F₄₃ = F₄₂ + F₄₁ и F₄₂ = F₄₁ + F₄₀. F₄₁ се решава в рекурсивните поддървета на F₄₃ и F₄₂. ако приемем наивно рекурсивно решение като това, ние решаваме отново и отново една и съща подзадача, макар че общият брой всъщност не е голям (само 43).

Динамичното оптимиране отчита този недостатък и решава всяка подзадача само веднъж. Това може да се постигне по два начина:

От горе надолу: Ако решението на задачата може да се получи чрез решение на подзадачи и ако подзадачите се припокриват, тогава техните решения може да се запазят в таблица. Всеки път, когато е нужно решение на подзадача, се поверява в таблицата дали тази подзадача е вече решена. Ако да, тогава се използва записаното в таблицата решение. В противен случай подзадачата се решава и решението се добавя в таблицата.
От долу нагоре: След като сме се открили решение на задача рекурсивно, можем да пренаредим задачата отдолу-нагоре: решаваме първо подзадачите и използваме решенията им, за да решим все по-големи задачи. Този метод също обикновено се реализира с матрица. Например, ако сме намерили стойностите на F₄₁ и F₄₀ в примера за редицата на Фибоначи, можем директно да изчислим F₄₂.

Източници

↑ Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2001), Introduction to Algorithms (2nd ed.), MIT Press & McGraw–Hill, ISBN 0-262-03293-7. pp. 327 – 8.

Тази страница частично или изцяло представлява превод на страницата Dynamic programming в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.

[1] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2001), Introduction to Algorithms (2nd ed.), MIT Press & McGraw–Hill, ISBN 0-262-03293-7. pp. 327 – 8.

[1]